zer0pts CTF 2021 writeup - Attack All Around

こんにちは、Ken.Sです！

久しぶりにCTFのwriteupです。今年初めて書くので拙い文章なのはご了承ください…。

Crypto

war(sa)mup

Do you know RSA? I know.
author:theoldmoon0602
warsamup_05d9e1f890f75cc7aadf145af49fddbb.tar.gz

とりあえず中を覗いて見ると、平文mを色々パディングしておりそれをm'とすると、公開鍵に加えm'を暗号化したものとm'//2を暗号化したものを与えられています。

m'を2で割ったものは上位ビットが同じだからFranklin-Reiter Related Message Attackができるのでは？とチームメイトが発見。ここで私は起床しました。昨日は朝3時に論文発表していたんです。近日その模様が公開されるので乞うご期待！

そのチームメイトがこのサイトを使えばいけるのでは？となり早速読んでみる

そもそもこの攻撃をよく知らないのでここらでお勉強。

今回m1は平文をパディングしたもの、m2はm1//2となっています。

つまり、m1 = 2*m2 or m = 2*m2+1と上記サイトのa,bが分かります。Xornetさんのwriteupより考えると、

g2(x) = (x)^e - c2 = 0 mod n -> g2(x) = (x-m2)h2(x) mod n

g1(x) = (2*x)^e - c1 = 0 mod n もしくは

g1(x) = (2*x+1)^e - c1 = 0 mod n

-> g1(x) = (x-m2)h1(x) mod n

となります。h1(x),h2(x)はsageにぶん投げて求めてもらいます。

そして、先程載せたgithubのコードをsagemathにぶん投げます。

output.txtをコピペしてパラメータを定義し、このように実行します。

franklinreiter(c1,c2,e,n,2,1)

resultをそのまま表示させて、あとはpythonで2倍して1加えたものをlong_to_bytesすればflagが出てきました。

ほとんどコードを丸パクリしただけなので、写真でご勘弁…。

f:id:partender810:20210306133943p:plain

zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}

他にも、easy pseudo random や janken vs yoshiking などを解いたんですけど歯が立たず…。公式writeupはこちらです。

それでは！

See you next time!