Kaspersky CTF writeup - きゅうり。

遅くなりましたが、Kaspersky CTFのwriteupです。

Cryptoを2問だけ解いたので書きます。

（当初はあまり書く気がなかったものの、勉強会中解き終わって暇なので書きます）

謎の暗号化されたpngが渡される問題。問題文にヒントは特になし。

pngのマジックナンバーすら破壊されているため、なんとなくpngのマジックナンバー（0x89 50 4E 47）と暗号のxorをとってみると、どのバイトも0xffとなる。

したがって、暗号の全バイトと0xffでxorをとると画像が復号できる。

やたら読みにくいスクリプトが渡される。（実はこれが暗号文だった説）

が、ある程度cryptoを（特に公開鍵暗号）解いたことのある人ならば、egcdやmod_invあたりは関数の中身を見ると判別できると思う。

結論から述べると、スクリプトを読むとpaillier暗号であることがわかる。

関数 L(x) = (x-1)/n や、暗号化の処理などが特徴的なので知っているとわかる。

さて、ここで暗号化の処理を詳しく追ってみる。

$dcew \equiv g^b * r^n \pmod{n^2}$

$c \equiv g^m * r^n * dcew \pmod{n^2}$

$c \equiv L(c^{\lambda}) * L(g^{(p-1)(q-1)})^{-1} \pmod{n}$

最初のcの計算でpaillier暗号における暗号化を行った後、次に復号処理をしていることがわかる。ここで暗号化の際に余計にくっついているdcewを見てみると、bを暗号化している。

つまり、平文mとb=22の暗号文の積をとった後、それについて復号を行う。

ここで、paillier暗号は平文について加法準同型性を持つ。

すなわち、 $Enc(m)*Enc(b) \equiv Enc(m+b)$ となる。

今回の問題ではこれについて復号を行っているため、与えられた暗号文は $m+b = m + 22$ となっている。

したがって、暗号文の各文字から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しか返ってこなかったので諦めて投げました。