TokyoWesterns CTF 6th 2020 一問も解けなかった話
皆さん、こんにちは！ Ken.Sです！
今日の朝9時まで開催されてたTokyoWesterns CTF 6th 2020に参加しました！ 結果はタイトルの通り、一問も解けませんでした…。一問あと一歩のとこまで行けたので、その問題のwriteupを書いていこうと思います。
問題概要
問題名：twin-d
分野：crypto
得点：172pt (68 solves)
問題ファイル
- task.rb
- output
解法
まずは、問題ファイルから見ていきましょう。rubyプログラムは久しぶりですが、特段変わったことはしてません。流れはこんな感じです。
p,q <- 1024bitsの素数
phi_n = (p-1)*(q-1) とする
while:
d <- 1024bitsの素数
gcd(phi_n,d) == 1 and gcd(phi_n,d+2) == 1 ならbreak
e1 = d^-1 mod phi_n
e2 = (d+2)^-1 mod phi_n
//e1*d = 1 mod phi_n
//e2*(d+2) = 1 mod phi_n
msg <- flag.txt
enc = pow(msg,e1,n)
p*q,e1,e2,encを出力
phi_nについて秘密鍵dの逆数e1と、d+2の逆数e2が与えられており、出力された結果がoutputに入っています。
k,k'を正整数とすると、
e1*d = k*phi_n+1 ・・・①
e2*(d+2) = k'*phi_n+1 ・・・②
となります。
②をdの式にすると、
d+2 = (k'*phi_n+1)/e2
d = (k'*phi_n+1)/e2 - 2 ・・・③
となります。
③を①に代入すると、
e1*( (k'*phi_n+1)/e2 - 2 ) = k*phi_n+1
phi_nの式に変形します。まず、両辺にe2を掛け、
e1*(k'*phi_n+1-2*e2) = e2*k*phi_n+e2
e1*k'*phi_n + e1 - 2*e1*e2 = e2*k*phi_n+e2
e1*k'*phi_n - e2*k*phi_n = e2 + 2*e1*e2 - e1
phi_n*(e1*k' - e2*k) = e2 + 2*e1*e2 - e1
となり、
e2 + 2*e1*e2 - e1 = 0 mod phi_n ・・・⑤
ということが分かりました。
ここまでは導出できました！！
ここから、左辺を素因数分解してphi_nの候補を出してやろうと思いましたが、数がデカすぎて無理でした…。ここで、他の方法が思い浮かばず断念しました。
では、続きを。
式⑤を変形すると、
2*e1*e2 = e1-e2 mod phi_n
となります。
ここから、同じ平文を違う公開鍵で暗号化した暗号文を導出します。
enc = m^e1 mod n
enc^(2*e2) = m^(e1*2*e2) mod n = m^(e1-e2) mod n
新しい暗号文を手に入れることができました。
gcd(e1,e1-e2) = 1より、common modulus attackが可能です。やり方はこの記事を見てみてください。
new_enc = enc^(2*e2) mod n とすると
e1*s1+(e1-e2)*s2 = 1となるs1,s2を求めればOKです。
TWCTF{even_if_it_is_f4+e}
最後のcommon modulus attackへの導き方はこちらを参考にさせていただきました。
この方、sqrtも解かれててすごい…！自分も挑戦はしてみましたが、一切歯が立たず…。最近のCTFはかなり難しくなっている気がします。
それでは！
See you next time!
