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を読む

f:id:falconctf:20190527201912p:plain

python party
1,2行目:モジュールのimportだ。Cでいうインクルードだ。
5~9行目:関数の定義だ。関数が呼ばれた時に見ればいい。
12,13行目:変数の定義。放っておこう。

14行目からコードをしっかり見ていくことになる。
が、先に15行目について一言触れておく。assert文と呼ばれるもので、普通デバッグのときに使われる。(はず)
assert(条件式)のように書き、条件式がFalseのときにのみ処理を停止させる。
今の例だとsecret < 2^Nを満たせば動くが、それ以外はプログラムが落ちる。
(一応補足。pythonではa**bで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)はa^bを表す関数である。
よってf(x,coeff)は今、len(coeff)=3だったことに注意すると
f(x,coeff) = coeff[0] + coeff[1] * x + coeff[2] * x ^{2}を表す。

coeff = [s,r1,r2 ]
party = [p1,p2,p3]

としていたから、結局
f(x,coeff) = s+ r1 * x + r2 * x ^{2}
であり

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 = s+ r1 * p1 + r2 * p1 ^{2}
v2 = s+ r1 * p2 + r2 * p2 ^{2}
v3 = 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コードが動いてるからかと予想。

・自力で解く
連立方程式を解くと以下のようになる。
 r2 = \frac{(v1-v2)(p2-p3)-(v2-v3)(p1-p2)}{(p1-p3)(p1-p2)(p2-p3)}
r1 = \frac{v1-v2}{p1-p2} -r2*(p1+p2)
s = v1 - r1 * p1 - r2 * p1 ^2

それをpythonに(四則演算のみ、もはや電卓として使う)解かせる。コードを書くのはsupereggに任せる。
python慣れも兼ねて頑張って。
python2だと問題なくとけるが、python3の場合は
Python3の割り算は切り捨てではない - Qiita
のため解けない。
計算途中で小数に変換されることによる誤差のせい。
/じゃなく//を使えば3でも解ける。r2をわざわざ通分した表示にしているのもそのためである。

出てきた答えを

FLAG = bytes_to_long(s)

とすればFLAGが求まる。