zipファイルを解凍すると

ができる。encrypt.cppを覗いてみると、名前の通り暗号化するプログラムだった。どうやらencrypt.encはencrypt.cppを暗号化したもの、flag.encはflag.jpgを暗号化したものらしい。

ふむふむ、このflag.encを解読しろってことね。

暗号化のアルゴリズムを詳しく見ていくと、mt19937ar.cppで定義されている擬似乱数発生器を未知の"seed"っていうファイルで初期化した後、生成される擬似乱数を使ってencrypt.cppとflag.jpgに対して続けてXOR暗号をかけているらしい。

XOR暗号は2度かけると元に戻るという性質があり、encrypt.encとencrypt.cppは与えられているので、encrypt.cppの暗号化時に生成された乱数列は求めることができる。

ここで、求めた乱数列からseedを逆算できないかと思いググってみると、seedは逆算できないものの、後続の乱数列を予測できるらしい。

ふむふむ。メルセンヌツイスターって聞いたことはあったけど、こういう仕組みになってるのね。

このページを参考に、flag.encを解読。勉強になりました。

ksnctf 17問

すごく大きなxに対してy^101 = xを満たすyを求める問題。

この問題は下の桁から求めていくと解ける。

つまり、

xの下1桁はyの下1桁によってのみ決まる。

xの下2桁はyの下2桁によってのみ決まる。

xの下3桁はyの下3桁によってのみ決まる。

......

のでyを下の桁から決定していくことができる。

ksnctf 16問 RSA暗号

ksnctfの16問目を問いた。

パッと見、単純にやってもとても現実的に終わりそうにない問題。

多分RSA暗号の問題だろうと思いながら、一応自力で式をこねくり回しましたがやはりわからず。諦めて以下の文書を参考にした。

簡潔でわかりやすい解説。

これを見ながらコーディング。

ディオファントス方程式を解く関数、累乗の計算方法を少し工夫して完成。