TokyoWesterns CTF 2018 Revolutional Secure Angou 復習 ctf crypto
Revolutional Secure Angou 復習
https://ctftime.org/writeup/10865 Writeup見て復習。
require 'openssl' e = 65537 while true p = OpenSSL::BN.generate_prime(1024, false) q = OpenSSL::BN.new(e).mod_inverse(p) next unless q.prime? key = OpenSSL::PKey::RSA.new key.set_key(p.to_i * q.to_i, e, nil) File.write('publickey.pem', key.to_pem) File.binwrite('flag.encrypted', key.public_encrypt(File.binread('flag'))) break end
僕はまったく分からなかったが、qの生成方法が普通と違うので不備があることに気付けるらしい。
通常のRSAの手順は以下のようになる。
- ランダムに2つの素数を生成、
と
と
に対して素な整数
, public exponentを選ぶ、たいてい0x10001, 65537になっている。
, private exponentを計算する。これは
で計算される。
を計算し、
を公開鍵、
を秘密鍵にする。
普通はqもランダムに生成するが、このスクリプトではq = OpenSSL::BN.new(e).mod_inverse(p)
となっている。
つまり、で生成されている。
この式を変形するととなり、
と表せる(kは任意の整数)。
ここで、両辺にをかける。
すると、となる。
なので、
は知ることができる。
つまり、という2次方程式になる。
これによりを求めることができる。
が分かれば
を計算できる、これで暗号化されたフラグを復号できる。