Posted at

InterKosenCTF Crypto 100pts strengthened Write-up


問題

flagをencryptするpythonのツールと、その結果得られた暗号文c、key e,nが与えられるので、暗号をといてflagを求めよ。


解法

eがかなり小さいので、様々な計算が素早く終わる。

暗号化しているpythonのコードを見ると、平文がnを超えるまで2を乗算している部分がある。

この時掛けられた2の数をxとすると、以下の数式が成り立つ。

$$ pow(text*2^{x-1},3) < n < pow(text*2^{x},3) $$

もう少しわかりやすく式を変形すると、以下のようになっている。

$$ {text}^{3}*8^{x-1} < n < {text}^{3}*8^{x} = c $$

つまり、mod n上であることを考えて、mod n上での8の逆数をcに掛けてやれば、平文の3乗に8をいくつか掛けたものが求まり、かつn以下になってmodを考える必要がなくなる。

$$ {text}^{3}*8^{x-1} = c * 8^{-1} $$

mod n上での逆元はO(log n)くらいで求まるので、計算量的に全く問題ない。

詳しくはこのページを参照すると良いだろう。

逆元をcに掛け算して、mod nをとると、以下の数字が出てくる。

$$ 1316396754071787260749276308838639754285073899462945718347726712784130677263450459740777962722337713124066868015739491785773096382695726174088867236809252485418345525092050026317616386885271024

3781163703423686769163750230865961250699596275581926902394149024737646022233671688266078665414896024093246820574385057795618365850856631593634221982139021289399438650755322583380932414042718992

0637578487218479660407180381561409347804074220020193428037658958051267228620099879743342419350026940120942894197660975374800470053723759262250970175268110239089104777403535546423603389336722364

01198931530596070263467537969054744576 $$

さて、これはn以下であるので、通常通り3乗根を求めてあげれば良い。

私は、n以下での2分探索を実施した。

$$ text*2^{?} = 2361179120916491260487295733398579541036135715922639566341079409083115969988692336721397075809071199074365105926917330638471144444341126013084436417918456154879472961912134977605594983742830765

7593796427776 $$

となる。

あとは、?が分かれば平文がわかるが、nの大きさより?は2048以下であるはずなので全てのパターンに対して復号化を試して、flagになったものを採用すれば良い。

# NNN = text*2^?

for i in xrange(300):
print str(NNN)
print str(hex(NNN))[2:][:-1]
print str(hex(NNN))
try:
print str(hex(NNN))[2:][:-1].decode("hex")
except TypeError:
pass
NNN/=2

このような形で処理すると



KOSENCTF{THIS_ATTACK_DOESNT_WORK_WELL_PRACTICALLY}



という文字列が見つかる。


反省

もう少し、Cryptoツール類に詳しくなった方が良い気がしてきた。