duckが送るBeginners CTF 2019 Party(Crypto)の解説
どうもduckです。唯一自力で解いたPartyについて解説したい。
さて、問題をDLしたらparty.tar.gzというファイルだったので、
tar -zxvf party.tar.gzコマンドで解凍する。
tarはLinuxの標準的な圧縮形式で、windowsでいうzipみたいなファイルらしい(よくわからん)。
解凍するとencrypt.pyというファイルとencryptedというファイルが出てきた。
encryptedをcatするとなんか数字がめちゃくちゃ出てくる。
encrypt.pyを読めば意味がわかるはず。
さて、ここからは大きく二つのフェイズに分けて説明しようと思う。
1.pythonファイルの解析。これによりflagを得るためにやるべきことがわかる。
2.実際にflagをゲットしてみる。(3元1次連立方程式を解くことになるんだけれどね)
頑張っていこう。
1.pythonを読む
python party
1,2行目:モジュールのimportだ。Cでいうインクルードだ。
5~9行目:関数の定義だ。関数が呼ばれた時に見ればいい。
12,13行目:変数の定義。放っておこう。
14行目からコードをしっかり見ていくことになる。
が、先に15行目について一言触れておく。assert文と呼ばれるもので、普通デバッグのときに使われる。(はず)
assert(条件式)のように書き、条件式がFalseのときにのみ処理を停止させる。
今の例だとを満たせば動くが、それ以外はプログラムが落ちる。
(一応補足。pythonではa**bでをあらわす。)
気になる方は試すべし。この先の説明では無視する。
14行目:
secret = bytes_to_long(FLAG)
2行目でimportしたCrypto.Util.numberの関数bytes_to_longを使っている。
Crypto.Util.numberを詳しく調べたわけではないが、FLAGの文字列を数字列に直してsecretに代入しているのだろう。
ちなみに数字列を文字列に直すのにはlong_to_bytesを使えばいけた。単純。
つまりsecretという数字列が求まれば
FLAG = bytes_to_long(secret)
でFLAGが求まる。
17行目:
coeff = [secret] + [getRandomInteger(N) for i in range(M-1)]
[]はpythonではリストを表す。
リストの結合は+でかける。
[2,3] + [1,1,2,4] #[2,3,1,1,2,4]
例はこんな感じ。
次に
[getRandomInteger(N) for i in range(M-1)]
がわからない方。python内包表記で調べると幸せになれる。
超簡単な例↓
リスト内包表記の活用と悪用 - Qiita
結局こうなる。
coeff = [secret,getRandomInteger(N) ,getRandomInteger(N) ]
getRandomIntegerも2行目でimportしたCrypto.Util.numberの関数。
Nまでの乱整数を取ってくるのだろう。(調べてないけど)
長い変数はうざったいので短い名前にする。getRandomIntegerは毎回結果が異なることに注意。
coeff = [s,r1,r2 ]
18行目:
party = [getRandomInteger(N) for i in range(M)]
つまり
party = [getRandomInteger(N),getRandomInteger(N),getRandomInteger(N)]
というリスト。
だるいので短い名前にする。
party = [p1,p2,p3]
20行目:
val = map(lambda x: f(x, coeff), party)
無名関数(lambdaのこと)とかmapについて説明するのは面倒になので、わからない方は
Python2,3での比較!map関数を使う方法【初心者向け】 | TechAcademyマガジン
ここら辺を参照いただきたく。
結局valはこうなる。
val = [f(party[0],coeff),f(party[1],coeff),f(party[2],coeff)]
やっと関数fが出てきたので5行目に戻ろう
5行目:
def f(x, coeff): y = 0 for i in range(len(coeff)): y += coeff[i] * pow(x, i) return y
len(list)はlistの長さを返す関数で、
pow(a,b)はを表す関数である。
よってf(x,coeff)は今、len(coeff)=3だったことに注意すると
を表す。
coeff = [s,r1,r2 ] party = [p1,p2,p3]
としていたから、結局
であり
val = [s+ r1 * p1 + r2 * (p1 ** 2),s+ r1 * p2+ r2 * (p2 ** 2),s+ r1 * p3 + r2 * (p3**2)]
である。
長いので
val = [v1,v2,v3]
としておく。
21行目:
output = list(zip(party, val))
これがencryptedの中身である(続く22行目でoutputで出力されているから)。結局encryptedにはpartyとvalが格納されていることが分かった。
つまりp1,p2,p3,v1,v2,v3が与えられたということだ。
partyとvalからsecret(=sとおいていた)を復元しよう。
val = [s+ r1 * p1 + r2 * (p1 ** 2),s+ r1 * p2+ r2 * (p2 ** 2),s+ r1 * p3 + r2 * (p3**2)]
なのだから
となる。
v1,v2,v3,p1,p2,p3はencryptedに書いてある。残りはs(secret),r1,r2だけだ。
未知数3個。式3つ。中学生でも解ける連立方程式だ。
2.flagをゲットする
詰まったところだけ書く。
・numpy(数学ライブラリ、有名)をつかって解いてみる
v1,v2,v3,p1,p2,p3が大きすぎて解けない。おそらく中でCコードが動いてるからかと予想。
・自力で解く
連立方程式を解くと以下のようになる。
それをpythonに(四則演算のみ、もはや電卓として使う)解かせる。コードを書くのはsupereggに任せる。
python慣れも兼ねて頑張って。
python2だと問題なくとけるが、python3の場合は
Python3の割り算は切り捨てではない - Qiita
のため解けない。
計算途中で小数に変換されることによる誤差のせい。
/じゃなく//を使えば3でも解ける。r2をわざわざ通分した表示にしているのもそのためである。
出てきた答えを
FLAG = bytes_to_long(s)
とすればFLAGが求まる。