Revolutional Secure Angou 復習

https://ctftime.org/writeup/10865 Writeup見て復習。

RSA問題、珍しくRubyで書かれている。

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つの素数を生成、 $p$ と $q$
$p-1$ と $q-1$ に対して素な整数 $e$ , public exponentを選ぶ、たいてい0x10001, 65537になっている。
$d$ , private exponentを計算する。これは $d = e^{-1}\ mod\ (p-1)(q-1)$ で計算される。
$n = pq$ を計算し、 $(n, e)$ を公開鍵、 $d$ を秘密鍵にする。

普通はqもランダムに生成するが、このスクリプトではq = OpenSSL::BN.new(e).mod_inverse(p)となっている。
つまり、 $q = e^{-1}\ mod\ p$ で生成されている。
この式を変形すると $qe = 1\ mod\ p$ となり、 $qe = pk + 1$ と表せる(kは任意の整数)。
ここで、両辺に $p$ をかける。
すると、 $pqe = kp^2 + p$ となる。
$n = pq$ なので、 $pqe$ は知ることができる。
つまり、 $kp^2 + p - ne = 0$ という2次方程式になる。
これにより $p$ を求めることができる。