Bsides CTF 2019 Crypto Writeup(+1) Crypto道場六[9/100]

どうも。duckです。
1問解けたのでWriteup書きます。

1.BabyRSA
二つのファイルが配られた。
暗号化処理が書いてあるpythonファイルとflagや公開鍵などが書いてあるファイル。
data.txt
Dropbox - data.txt - Simplify your life
encrypt.py
Dropbox - encrypt.py - Simplify your life

まずは数式に書き起こす。ただし長い変数名は嫌いなので短くおく。
$s=\mathit{salt},m=\mathit{magic\_value},e=\mathit{ee},d=\mathit{ed},E=\mathit{enc},N_1=n_1,N_2=n_2,N=pq,C_1=c_1,C_2=c_2,C_3=c_3$ とする。

$s=m \oplus \mathit{FLAG}　\\ N_1=p_1 q_1,N_2=p_2 q_2 \\ C_1 \equiv m^{e_1} \pmod {N_1},C_2 \equiv m^{e_2} \pmod {N_2} \\ ed \equiv 1 \pmod {\phi(N)} \\ C_3 \equiv (p_1p_2)^d \pmod N \\ E = s^e \pmod N$

また、data.txtから
$\mathit{given}:C_1,C_2,C_3,N_1,N_2,e_1,e_2,E,N,d$ 。

$\mathit{FLAG} = s \oplus m$
であるから（ワンタイムパッド） $s,m$ を求めればよい。

(1) $s$ を求める。
$s \equiv E^d \pmod N$ より容易。

s=11295349226607404013471021010341147978232157635167255049065532106494114988908324617162496015788158425092740147662943160785286369117660955898007291303207104

(2) $m$ を求める。
やったことを書く。

(a)Wiener's Attackにより $e$ が求まる。
$d$ と $N$ の大きさがほとんど一緒であるので、Wiener's Attackが使えそうと判断。
codeは
rsa-wiener-attack/Arithmetic.py at master · pablocelayes/rsa-wiener-attack · GitHubのものを使わせてもらった。

e=230194238437088036834072549225817051199

(b) $N_1,N_2$ を素因数分解する。
$C_3 \equiv (p_1 p_2)^d \pmod N , ed \equiv 1 \pmod {\phi(N)}$ であるから
$p_1 p_2 \equiv {C_3}^e \pmod N$

よって
$p_1={\gcd(N_1,p_1 p_2)},q_1=N_1 \div p_1 \\ p_2={\gcd(N_2,p_1 p_2)},q_2=N_2 \div p_2$

通常であればここで ${\phi(N_1)},{\phi(N_2)}$ から
$e_i d_i \equiv 1 \pmod {\phi(N_i)}$ から $d_i$ ( $i=1,2$ )が求まり終了する。

しかし
$\gcd(e_1,{\phi(N_1)})=562 \\ \gcd(e_2,{\phi(N_2)})=166$

であり、互いに素ではない。
よって拡張ユークリッドの互除法により求められるのは
${C_1}' \equiv m ^ {562} \pmod {N_1} \\ {C_2}' \equiv m ^ {166} \pmod {N_2}$

どまりである。
これを $m$ について解くのは計算量的に困難。

(c)2乗なら解ける。
${\rm mod}N_i$ ではなく ${\rm mod}q_i,{\rm mod}p_i$ でなら $m$ が解けるのでは？と思いつく。
それさえ解ければ中国剰余定理で $m$ が求まるはず。（後述）
案の定
$\gcd(\phi{(q_1)},562) = 2$ , $\gcd(\phi{(q_2)},166) = 2$
であったので
$562*d_1 \equiv 2 \pmod {\phi(q_1)}$ , $166 * d_2 \equiv 2 \pmod {\phi(q_2)}$ となる $d_1,d_2$ を用いて
${{C_i}'}^{d_i} \equiv m^2 \pmod {q_i}$ と書ける。

幸運なことに $q_i \bmod 4 = 3$ であったため、 $m= \pm {{C_i}'} ^ {\frac {q_i + 1}{4}} \pmod {q_i}$ とすぐに $m$ が求まった。
（これに関してはそのうち $x^2 \equiv \pmod p$ の解き方としてそのうちまとめたい。オイラーの規準、平方剰余などがでてくるやつだ）

(d)中国式剰余定理で $m$ を求める。
$\gcd{(q_1,q_2)}=1$ であったから、
$x\equiv m \pmod {q_1} \\ x \equiv m \pmod {q_2}$

を両方満たす $x$ は中国式剰余定理ですぐ求まる。
ただ、 $m$ はそれぞれ二つずつ値の候補があったから４通りの候補が出た。

m=[130204528787507505773710923666654908063951342300341290679481831089048475661769804679434320541299854192944581837117095632601550663649704580455239831296388244795699081558529808425017950463304134904449847423117536416689316941082295460328322896891187718311773570823357440044019285149368069722662004114150614222139, 11295349226607404013471021010341147978232157635167255049065532106494114988908324616956647488198714894202591671750797554105930964810174872213148351201383613, 155328494801539469659088679666851276753591192017192346542864403340513541152283708502912394372206759224607578141814677435838429120228926266030995634784793810029010046854516342686756175376802934265799821368172545904638220345216445314249676172852240226067187570748506096577796912199512986620072139171057340043068, 25123966014031963885377756000196368689639849716851055863382572251465065490513903823478073830906905031662996304697581803236878456579221685575755803488405576528660191903390547732759235254646777593507609112310058553481009898249138762245970232608540706470308202516820407331331732981109727072282348205257927204542]

あとは４通りの $m$ について $\mathit{FLAG} = s \oplus m$ を計算し、正しい $\mathit{FLAG}$ を求めるだけだ。