Kaspersky CTF writeup
遅くなりましたが、Kaspersky CTFのwriteupです。
Cryptoを2問だけ解いたので書きます。
(当初はあまり書く気がなかったものの、勉強会中解き終わって暇なので書きます)
Security home cameras (crypto 300)
謎の暗号化されたpngが渡される問題。問題文にヒントは特になし。
pngのマジックナンバーすら破壊されているため、なんとなくpngのマジックナンバー(0x89 50 4E 47)と暗号のxorをとってみると、どのバイトも0xffとなる。
したがって、暗号の全バイトと0xffでxorをとると画像が復号できる。
Bad computation (crypto 800)
やたら読みにくいスクリプトが渡される。(実はこれが暗号文だった説)
が、ある程度cryptoを(特に公開鍵暗号)解いたことのある人ならば、egcdやmod_invあたりは関数の中身を見ると判別できると思う。
結論から述べると、スクリプトを読むとpaillier暗号であることがわかる。
関数 L(x) = (x-1)/n や、暗号化の処理などが特徴的なので知っているとわかる。
さて、ここで暗号化の処理を詳しく追ってみる。
最初のcの計算でpaillier暗号における暗号化を行った後、次に復号処理をしていることがわかる。ここで暗号化の際に余計にくっついているdcewを見てみると、bを暗号化している。
つまり、平文mとb=22の暗号文の積をとった後、それについて復号を行う。
ここで、paillier暗号は平文について加法準同型性を持つ。
すなわち、となる。
今回の問題ではこれについて復号を行っているため、与えられた暗号文はとなっている。
したがって、暗号文の各文字から22を引くとフラグが得られる。
ソルバ
print "KLCTF{"+"".join(map(lambda x:chr(ord(x)-22),"hnd/goJ/e4h1foWDhYOFiIZ+f3l1e4R5iI+Gin+FhA==".decode('base64')))+"}"
フラグ
KLCTF{paillier_homomorphic_encryption}
あとがき
decrypt the message (crypto 700)が解けていないので誰か教えてください。
padding oracleかなぁと思ったら500しか返ってこなかったので諦めて投げました。