RaRCTF 2021 Writeup
今回は適当に出場してみましたがチーム数が1200弱ありすげーーーと気圧されてましたが
結果は 126位でほぼcryptoだけでこれたので満足です．
解けた問題
- 解けた問題
- sRSA (100 points)
- unrandompad (150 points)
- Shamir's Stingy Sharing (200 points)
- babycrypt (200 points)
- PsychECC (400 points)
sRSA (100 points)
$e,n,ct$が与えられ$ct = flag*e \ \ mod(n)$
よって$ct*e^{-1} = flag*e*e^{-1} \ \ mod(n)$とできるので$flag = ct*e^{-1} \ \ mod(n)$を求めれば答えが出る．rarctf{ST3GL0LS_ju5t_k1dd1ng_th1s_w4s_n0t_st3g_L0L!_83b7e829d9}
unrandompad (150 points)
ある素数を2つ取ってきてRSAの準備を行いpad関数でpaddingしているみたい...いや、encryptoで使ってねーのかよ!!という突っ込みが入りました．
閑話休題
なので、ただ単純に平文$m$を渡せば$c = m^{e}\ \ mod(n)$を返してくれます．
これを用いてHåstad's Broadcast Attackというものを行います．
$e=3$なので3個の$c,n$のペアがあれば行えるはずなのでnetcatを3回行い取ってきて中国人剰余定理で$flag$を復元していきます．
rarctf{https://cdn.discordapp.com/attachments/751845431063085160/866641917714235392/unknown.png_8538853c64}
Shamir's Stingy Sharing (200 points)
問題は大まかに2つのパートに分けられます．
*1.bxor
*2.polyを用いた多項式
解き方の手順としては2でpoly[0]の値を求めて1の乱数を再現しbxorで$flag$を求めます．
問題の2の部分を見る限り多項式の係数は与えれるものの不定元はこちらで与えられることができます．よって，$2^{129}$進数としてxに$2^{129}$を与え$mod($2^{129}$)$を行えばpoly[0]を取り出すことができます．
これで2の部分が終わです．
1の部分はnetcatの初めに与えられる文字列をbytesに変換しbxorの片方に入れます．もう一方は，2でわかってるpoly[0]を乱数のシードとして桁数のbitを指定して放り込みます．
ぶっちゃけ桁数を求めるのがなんとなくだるかったので試してダメなら1桁増やすみたいなことをしてました．よって$flag$は以下となる．
rarctf{n3v3r_trust_4n_1nt3g3r}
babycrypt (200 points)
pubkeyが$e,n$,privkeyが$p,q$となって，$c = m^{e} \ \ mod(n)$となる
これだけでは厳しいところがあるのでhintとして$hint = n\ mod (q - 1)$が与えられている．問題のプログラムの条件より$pq=(p+1)(q-1)+p-(q-1)$と一意に定まるため$hint = p-(q-1)$と読み替えることができる．
これは基本対称式と呼ばれるもので構成される式(詳しくはググってもらって...)より簡単に$p+q$を算出することができ秘密鍵の$d$を導出することができる
よって以下のflagを得ることができる．rarctf{g3n3r1c_m4th5_equ4t10n_th1ng_ch4ll3ng3_5a174f54e6}
PsychECC (400 points)
ある与えられた楕円曲線において有理点$(x_1,y_1)$を入力とし，あるスカラー倍算された有理点$(x_2,y_2)$を出力とするプログラム．さらに、有理点を入力して出力された有理点と同じならflagがもらえるみたいです．
ECの攻撃はanomalous曲線やsupersingular等があるみたいです(あまり詳しくない)が今回は有理点が楕円曲線上のに乗っているかチェックされていないのでinvalid curve attackが成立します．
どういう攻撃かというと別の楕円の有理点を与えてそれを計算させる⇒それの答え合わせを行うというまぁ単純なものです．
なので今回与える有理点は$(79238730022396037033643944491844772521873745954229361958773910554826830893621,62628993809527930529233211427211299031131458459128039437787214582616587965475)$として，出力の方の有理点は
$(69473202296790888221989641114439625856056410065759153429712028574142323887235,27224964365716519755044877081930694306533217160896231828903674165207513413426)$です．
ちなみに今回与えた有理点の位数は113なので，何回か(300回程度)netcatして攻撃することになります．攻撃が成功すると以下のflagが手にはいります．
rarctf{w0ah_str4ight_cl41r0v0y4nc3!!_8119733d69}
感想
本格的参加して3回目?のCTFでここまで解けてうれしかったですが，rotoRSAが多分惜しいところまで解けているはずなので解きたかったかなぁ...と
どちらによ今回のCTFはPsychECCが19番目に解けて満足です．
誤字脱字，訂正等ありましたらお知らせください...