2019-05-29

duckが送るBeginnersCTF2019 BitFlip（Crypto)の解説 Not初心者向け

どうもduckです。最近は仕事とctfしかしてません。ブログタイトル「CTFと共に生きる」とかにしません？
今回はCryptoのラスボスBitFlipです。いろんな方のwriteupを読ませていただきましたが、使われている数学について解説しているwriteupはないんじゃないか？
私がやるしかないな！（需要？なにそれおいしいの？）
まずはもらったコードから

f:id:falconctf:20190529191346p:plain — BitFlip

これを解析すると以下の操作が行われていることがわかります。

f:id:falconctf:20190529192334p:plain — Flip

まず最初に思いつく方法はブルートフォースです。
が、美しくないうえ、サーバーから全てのReturnの情報を得なければならないので割愛します。
（ついでに言えば途中で運営側からBitFlipのサーバーにアクセスしすぎだよ自重しろというお達しもありました。つまりはブルートフォース以外の方法があるはず）
気になる方はこちらの方のWriteupを見るとよいです。
SECCON Beginners CTF 2019 - Qiita

さてここから数学のお話。
今回私の記事の中では

$f_n = FLAGのNビット目を反転した値$ (ただし1番下位のbitを０bitとします)
$f= FLAG$
$C_n = (f_n)^3 mod N$ （サーバーから返ってくる値）

として話を進めます。
$f_n = f \pm 2 ^n$ となることにも注意しておきます。(Flipが0→1のときは＋、1→0のときは-)
また、書くのが面倒なのでこれ以降 $mod N$ と書くのをやめます。適宜置き換えてください。

まず、サーバーにアクセスして
$C_n \neq C_m$ となる $C_n ,C_m$ をゲットしましょう。よほど運が悪くなければ２回でゲットできます。
もちろんこの段階ではどのビットが反転されたのかわかりませんのでn,mは不明です。

ーーーーー
目標は、平文が線形関係であるときに用いることができるFranklin-Reiter Related Message Attackを行うことです。
$m_1 = a * m_2 + b$ と表せるとき、
$c_1 = m_1 ^ e mod n$
$c_2 = m_2 ^e mod n$
の暗号文 $c_1,c_2$ と公開鍵 $e,n$ がわかれば、平文 $m_1,m_2$ を求められることを使います。
まあ後でもう少しだけ解説します。
ーーーーー

1.Coppersmith’s Short Pad Attackする
$f_n - f_m = \pm2^n \mp 2^m$ でありこれを $s$ とおきます。
そうすると
$C_n = (f_m + s) ^ 3$ 　...①
$C_m = f_m ^ 3$ 　　...②
と表せます。
このsさえ求まればFranklin-Reiter Related Message Attackが使える形になります。

ここで
$P(x) = C_n - (x + s) ^ 3$
$Q(x) = C_m - x^ 3$ の多項式を考えます。( $f_m$ を未知数xに置き換えただけ)
$P(x)=0,Q(x)=0$ の解は $f_m$ を含むことは明らかです。（つまり共通解をもつ）

この性質から、sを求めるのに終結式を使います。（終結式の定義については割愛します。終結式の定義といくつかの性質 | 高校数学の美しい物語）
終結式は共通解をもつ二つの多項式に対しては０になるという性質を持ちます。
つまり $P(x),Q(x)$ から終結式を計算して、それが０になることからｓを求めます。

終結式の計算にはシルベスター行列の行列式を使います。(終結式の定義といくつかの性質 | 高校数学の美しい物語)
今回の場合は以下のようになります。
$\begin{vmatrix} 1 & 3s & 3s^2 & s^3-C_n & 0 & 0\\ 0 & 1 & 3s & 3s^2 & s^3 - C_n & 0 \\ 0 & 0 & 1 & 3s & 3s^2 & s ^3 - C_n\\ 1 & 0 & 0 & -C_m & 0 & 0 \\ 0 & 1 & 0 & 0 & -C_m & 0 \\ 0 & 0 & 1 & 0 & 0 & -C_m \end{vmatrix}$

~~こっから先は手計算では無理だ。~~
アホなので手計算でシルベスターの行列式計算しました。
$(s^3 + C_m - C_n) ^ 3 - 27 * s^3 * C_m (s^3 + C_m - C_n) + 27 * s^3 * C_m ^2 + 27 s^6 * C_m$
sの大きさに注意しつつプログラムに投げましょう。後でやります。（おい）Sagemathがpythonライクでおすすめだった気がします。
mathematicaとかフリーで使えたっけ？使えるならそっちでも。
sのサイズが大きすぎるため、このままプログラムに投げるには $C_n,C_m$ としていい値が来ないと計算無理です。
何回も問題サーバーにアクセスして解けるパターンを待ってもいいですが、今回はわかってる情報からsがある程度絞り込めるのでそれを利用します。
$s = \pm2^n \mp 2^m$ の形なのがわかっているので、これを使い $\frac{(max(n))*max(n-1)} {2}*4$ 回くらい終結式を計算すればよいことがわかります。
今回はmax(n)として250くらいを取りました。
このmax(n)は実験中にサーバーサクセスを繰り返してたときに推測した値です。
これでSagemathをつかわなくともsが求まります。
以下くそコード。

N = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
e = 3
#max(n)
nm = 250
C1 = 19668512534871703818804721058464184088540192186216654188589585883263154008964228350399514299852538811337835790238510703474647742023573370430287373841543674974547734434937124159068497046659147350241364684829208188803795307462087810637640642350674397153687260268727800582499681256385837706667398671154929189579
C2 = 44939803625275977251911534717835431979049524856461188120868461571121976859707514547338914366715426490130522458001402249990220314314873155256383447002643583335186960138112746521599509022925369612324695641201278318699732590955718931066187237603506202339345820308234883558809220466506231185260966657450242854347

#2べきを先にリストに格納
list2 = []
t = 1
ans = 0
i = 0
while i <= nm:
    list2.append(t)
    t = t * 2
    t = t % N
    i += 1

#sを表示する
def result(s,n,m,l):
    print(s,n,m,l)
    ans = s

#ブルートフォース
for n in range(nm):
    for m in range(nm)[n+1:nm]:
        #2^m + 2^n or 2^m - 2^n
        s = (list2[m] + list2[n]) % N
        if solve(s):
            result(s,n,m,0)
        elif solve(-s):
            result(s,n,m,1)
        #2^m - 2^n or 2^n - 2^m
        s = (list2[m] - list2[n]) % N
        if solve(s):
            result(s,n,m,2)
        elif solve(-s):
            result(s,n,m,3)

solve関数が消えていますが、うえで示した終結式に代入して、＝ $０$ ならTrue　, $\neq 0$ ならFalseを返すだけの関数です。
結果はこちら
383123885216472214589586756787577295904680382499389440 42 178 3

今回のケースでは
FLAGの42bit目が０→１反転したものと、178bit目が1→０反転したものであることがわかりました。
まあ $s=383123885216472214589586756787577295904680382499389440$ さえ知ってれば大体OKですが。

2．Franklin-Reiter Related Message Attackする
$C_n = (f_m + s) ^ 3$ 　...①
$C_m = f_m ^ 3$ 　　...②
のsが1で求まったとします。
$s=383123885216472214589586756787577295904680382499389440$ です。
この時 $f_m$ は $gcd(P(x),Q(x))$ で求まります。（雑）

もうちょっとだけ解説を加えます。
$gcd(P(x),Q(x))$ は多項式版ユークリッドの互除法をして、最大公約多項式を求めろということです。
整数のユークリッドの互除法とおんなじです。そしたら答えがわかります。（雑）

例を挙げます。
$p = x ^2 - 1$
$q = x ^ 3 - 1$
の最大公約単項式を求めてみましょう。
頑張ってユークリッドの互除法をすると以下のようになります。
$gcd(p,q)=x-1$
ということは
$p=(x-1)*(なんかの１次式)$
$q=(x-1)*(なんかの2次式)$
となっていることを意味します。
つまり共通因数がわかったってことだ！！
これ見たら $p,q$ の共通解はどう見ても１やんけ！ってなわけですね。

$P(x),Q(x)$ は共通解 $f_m$ を持つことがわかっているので、 $gcd(P(x),Q(x))$ は必ず１ではない多項式です。
ほとんどの場合で、それは1次多項式であり $gcd(P(x),Q(x)) = x -f_m$ となりますから $f_m$ がわかります。
（まれに $gcd(P(x),Q(x))$ が２次式以上になりますが、それを解いて $f_m$ を求めるのはかなりめんどくさいのでおとなしく $C_1,C_2$ の選択からやり直すのをおすすめします。）

実際にやってみた結果。（Sagemathを使いました。sympyだと整数環上でしかできなかったためあきらめた。）

PRx.<x> = PolynomialRing(Zmod(N))
g1 = x^e - c1
g2 = (x+s)^e - c2

while g2:
    g1, g2 = g2, g1 % g2
    print(g1.monic())

結果。
$x + 82212154592315489750110187598968636841905821953623851870053845076997511568524415687534405445330110037385522700226033733612223434284079949332614038131717774815337863135195292470488899872185912270098336585556230191588353421626879687269516794206695695261382777258681677254870347368455087826235419500816586773161$
つまり
$f_m = - 82212154592315489750110187598968636841905821953623851870053845076997511568524415687534405445330110037385522700226033733612223434284079949332614038131717774815337863135195292470488899872185912270098336585556230191588353421626879687269516794206695695261382777258681677254870347368455087826235419500816586773161$

bit反転させるのが筋ですが、もうめんどいのでこのまま復号します。

from Crypto.Util.number import bytes_to_long, getRandomInteger, getPrime,long_to_bytes

N = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
m = -82212154592315489750110187598968636841905821953623851870053845076997511568524415687534405445330110037385522700226033733612223434284079949332614038131717774815337863135195292470488899872185912270098336585556230191588353421626879687269516794206695695261382777258681677254870347368455087826235419500816586773161
m = m % N

print(long_to_bytes(m))

ctf4b{b1tfl1pp1ng_1s_r3lated_m3ss4ge} DUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMIYDUMMYDUMMYDUMMYDUMMY\n

反転さぼった影響で赤い部分の文字が変わってますね。（気になる人は178bit目を反転させましょう）まあもうFLAG出たしいいでしょう。
お疲れさまでした。

2019-05-28

supereggが送るBeginners CTF 2019[warmup]Ramen(Web)の解説

初心者向け superegg writeup Beginners CTF 2019 Web

どうもこんにちは、supereggです。今回がBeginnersCTF2019にWebの問題である「Ramen」の解説をしたいと思います。

まずは問題のサイトにアクセスします。
https://ramen.quals.beginners.seccon.jp/

f:id:falconctf:20190528202957p:plain

めちゃめちゃ美味しそうですね。私はラーメンが大好きなので嬉しいです。

まず以下の入力フォームとそのしたの表に注目します
f:id:falconctf:20190528203431p:plain

名前を検索できる入力フォームがあり、その下にラーメン屋の店員の名前と一言が書いてあります。

入力フォームがあるので、まずはSQLインジェクションが使えないかチェックみようと思います。

SQLインジェクションとは・・・アプリケーションのセキュリティ上の不備を意図的に利用し、アプリケーションが想定しないSQL文を実行させることにより、データベースシステムを不正に操作する攻撃方法のこと。また、その攻撃を可能とする脆弱性のことである。(あ（引用:wikipedia）>>https://ja.wikipedia.org/wiki/SQL%E3%82%A4%E3%83%B3%E3%82%B8%E3%82%A7%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3>>

SQLインジェクションが使えるかどうか判断する方法として典型的なものとして「'(シングルクォーテーション)を1つ入力するとエラーメッセージが表示されるというものがあります。

何故判断できるのかを簡単に説明すると入力フォームで入力されてきた値は普通すべて、特殊な意味を持たない文字列として扱うようにしなければなりません。そのため、「'」などのメタキャラクタ（特殊な意味を持つ文字）はエスケープして「'」を特殊な意味を持たない文字列として扱うようにしなければなりません。（PHPの場合は\'）もし「'」をエスケープしていなかった場合、入力フォームから入力されてきた値で予期しないSQL文が実行されることになるのです。

それでは実際に入力フォームに「'」を入れてみましょう。
f:id:falconctf:20190528205845p:plain

次にSEARCHボタンをクリック」すると・・・

f:id:falconctf:20190528210041p:plain

何やらエラー文が出てきました。index.phpの11行目のエラーだそうです。(本来ならリリースの段階では画面にエラー表示はさせないようになっているのが常識なのですがCTFではこのようにエラーが画面に表示するように設定している場合があるそうです。エラーメッセージが画面に表示しない設定の場合は、開発者ツールでHTTPステータスコードを確認すれば内部エラーが起きたかどうか判断できます。（エラーコードは500））

何故エラーになるのかというと、

SLECT * FROM users WHERE name=''';

となり、シングルクォーテーションが1つ余計になり、SQLのシンタックスエラーになり、それがPHP側で表示されます。

これでSQLインジェクションを使えばいいというのがほぼ確定になりました。

次にどのRDBMS(データベースソフトのこと）が使われているのか判別します。

代表的なRDBMSの中には「MySQL」、「PostgreSQL」、「SQLite」があります。

この3つの書式の違いでまずあるのがコメントアウトです。

MySQL 「#」

PostgreSQL 「--」

SQLite 「--」

となります。

この3つなら「#」コメントをつけることが出来たらMySQLだと決めつけることができます。

早速判断するために試してみましょう。
f:id:falconctf:20190528215429p:plain

なんとエラーが出ませんでした。MySQLが使われているということが分かりましたね。

エラーが出ない理由は以下のように最後の「'」が#でコメントアウトされているからです

''#'

これにより、好きなSQL文を実行できるようになります。なんと恐ろしい( ﾟДﾟ)

RDBMSではユーザが定義する領域の他に、そのデータ領域のメタ情報（テーブルやカラムの情報）を保持する領域が作られます。

MySQLの場合はINFORMATION_SCHEMAとして定義されていて、データベースの形態をとっていて、SQL文により中身の情報を取り出すことが可能です。

次の文字列を検索フォームに入力すると、データベース名とカラム名を表示させることができます。

'union select table_name, column_name from information_schema.columns#

入力してSEARCHボタンを押すと、データベースが結合されて、たくさん値が表示されますが、下の方までスクロールすると怪しげなデータベース名とカラム名が表示されています。
f:id:falconctf:20190528223708p:plain

これによってflagというテーブルのfragというカラムに求めるものがあると考えられます。これでなかったら逆にヤバイですよね。

上のコードの意味は、information_schemaの中のculumnsテーブルの中のtable_nameとcolumn_nameとう名前（これはinformation_schemaの中で定義されている）のカラムを画面に表示されているデータベースのにunionを使って結合させています。そして内部プログラムは以下のようになっています。

select * from users where name='' union select table_name, column_name from information_schema.columns#'

このように「'」をエスケープしていなければSQL文を実行できます。今回はunionを使っていますが、ANDやORを使って好き勝手にSQLをぶっ放すことが出来ます。例えば

select * from users where name=''OR 1=1#'

ですべて真にしたり・・・
次に

'union select flag,"hello" from flag#

を入力すると（"hello"の部分はデータベースを結合させるときにカラムの数合わせにてきとうに入れた値なのでなんでもいいです）

すると・・・

f:id:falconctf:20190528225506p:plain

イエーーーーーーーーーーーイ！！！！！！！！！！！

2019-05-28

duckが送るBeginners CTF 2019 Go RSA（Crypto)の解説

writeup 初心者向け duck Beginners CTF 2019 Crypto

どうもduckです。今日はGo RSAについて書くよ。
名前から見てわかる通り、公開鍵暗号の１種であるRSA暗号がわからないと解けない。
公開鍵暗号については↓を見るかググって。
公開鍵暗号方式とは？初心者でもわかる公開鍵暗号方…｜Udemy メディア

まずはざっくりRSAについて数式部分を書くよ。アタックするからには理解しておきたい。
平文を $m$ ,暗号文を $c$ ,公開鍵 $N,e$ ,秘密鍵 $d$ とする。
具体的なアルゴリズムの流れを見よう。
（１）受信側： $p,q$ (十分大きな素数)を選び $N=p*q$ とする。（任意）
（２）受信側： $\phi(N) = (p-1)*(q-1)$ を計算する。（ $\phi(N)$ はオイラーのトーシェント関数と呼ばれ、定義があるが今はこの形のみ知っていれば十分）
（３）受信側： $\phi(N)$ と互いに素な整数 $e$ をもってくる。（任意）
（４）受信側： $e * d \equiv 1 (mod \phi(N))$ となる $d$ を求める。（拡張ユークリッドの互除法を用いる）
（５）受信側：公開鍵 $N,e$ を公開。
（６）送信側： $c = m ^{e} (mod N)$ と暗号文を作成し、送り付ける。
（７）受信側： $m = c ^{d} (mod N)$ で復号でき平文をゲットできる。

通常RSAへのアタックは秘密鍵dを求め、暗号文を解読することが考えられる。
正しく運用されていれば安全であるが、以下のサイト（おすすめ）に挙げられるようなパラメータの設定ミスをすると解読されうる。
CTFではそう言った問題がでるのだろうか？（ちなみにCryptoのBitFlipではその中の脆弱性を突く問題が出た）

RSA暗号運用でやってはいけない n のこと #ssmjp from sonickun

www.slideshare.net

さて、では実際に問題を見よう。
Server: nc 133.242.17.175 1337と問題文に書かれている。
Linuxのnc(ネットキャット？)コマンドで接続しよう。

f:id:falconctf:20190528203001p:plain — GoRSA

まずEncypted　flag is~と書いてあるから、これを複合すればよいことがわかる。問題文でNを忘れたといっていたからNがわかれば解けそうと思っておく。
次に最後の行を見よう。The D was~と書いてある。おそらくこれが秘密鍵だろう。
真ん中部分はユーザー入力である。こちらが入れた数字に対し、謎の数字が返ってくるようだ。
Encyptedflag,D,ユーザー入力により返ってくる値は再接続のたびに変わるようだ。
つまり我々は、３回までのユーザー入力からヒントを得てNを計算すればよいのだろう。
頑張ろう。

ユーザー入力が何を返しているのかがよくわからないのでまずは実験してみる。
その結果、
(a)いつでも１に対しては１が返ってくる。
(b)同じ接続の中で同じ数字を入れると同じ値が返ってくる。
(c)1を除いた入力に対して、大体同じ桁数の値が返ってくる。
などの特徴があることが分かった。

(b)から乱数などは使われていなそうだし,(a)から何かのべき乗計算をしているのではないかと推測できる。
また(c)からmodを取っているのではという推測もたつ。

これらの推測と上で説明したRSAの式たちを見比べると
$m ^{e} (mod N)$ とかか？と勘繰る。
つまり
$（ユーザー入力）^{e} (mod N)$ が返ってきてそうである。

この仮定の下でNを求めに行こう。
我々が入手できるのは以下の３本の式をみたすinput,rの組である。
$r1 \equiv \mathit{input1} ^{e} (mod N)$
$r2 \equiv \mathit{input2} ^{e} (mod N)$
$r3 \equiv \mathit{input3} ^{e} (mod N)$
input1,2,3:ユーザー入力、r1,r2,r3:サーバーから返ってくる値

inputを操作してNを顕現させたい。
こういう任意で入力できる問題は大体小さい数字をinputとするとか、２のべきをinputとするとかだとうまくいくことが多い。
またmodで悩んだときは $=$ を使った形に直すとうまくいくことも多い。（特に数学よくわからないという人にお勧めする）
なんともひどい誘導だが以下のようにすればNが求まる。

inputとして2,3を与える。
$r1 \equiv 2 ^{e} (mod N)$
$r2 \equiv 3 ^{e} (mod N)$
これは適当な整数 $k,k'$ を用いて
$r1 = N * k + 2 ^ e$
$r2 = N * k' + 3 ^ e$
と書ける。 $2^e,3^e$ を移項すると
$r1 - 2 ^ e= N * k$
$r2 - 3 ^ e= N * k'$
となる。お分かりだろうか？これでNが求まるのだと。我々は勝利したのだと。
公約数を思い出してほしい。
$r1 - 2 ^ e$ と $r2 - 3 ^ e$ の約数に明らかにNがある！やったぜ。
追記：
書き忘れていましたが、RSAでは一般的に $e=65537$ が用いられることが一般的です。
それを使いましょう。

最大公約数はユークリッドの互除法というアルゴリズムで高速に求まる。
わからない人は学習指導要領が改定されて高校生でも知ってるからなんとか学んで。

一つだけ注意しておくと、場合によってはNの整数倍が出てきてしまうことだ。
具体的には $k$ と $k'$ が互いに素ではない場合である。

でてきたN で
$flag = (\mathit{encryptedflag}) ^{d} (mod N)$
をしてもうまくFLAGが出ないときは、違うペアで試してみるとよい。

まあ私もまだやってないんだけどな！！
おつかれさま！また明日！！！！！

追記：いままでずっとFLAG書くの忘れてた。この回のだけ残ってたので貼っておく。
ctf4b{f1nd_7he_p4ramet3rs}

コード

from Crypto.Util.number import long_to_bytes
import math

c=17085620552658351183335544500690226272875422158935145341165358891244918062440861767294934344129747923141668732715787177751203261627026230386846774546801758980449060209320668104704097944761232115359564279944744011306082649286738268431655969673959744882964166437946605686952999392726525064814877455046451725768410312677212123398538560508582810195854081569284454616942253143100785505524167586197713206797113052644900411469422688939261982981855377987421758621965591995651651907064794890066406751092949615529766196252331712555809200696136040227513088824530815886117265362591775970066168663851386432407675346081685681927303
r1=12308943287801278381602271020636811688003973209453971581897097872964067773128210282456593395262732270249597048332555708886509308319520920180598650511766799712167512259642431520797141790111692065487078128961600689554367757339155513577144978675218793446249701301839641500569661759646423276187542173318171335382960662774233945196912603079740368273195927210668950566249353140103271649493388077952820446391920593020564832067217333892843371485574515498385351718470670460084994536203053240439442202272531830723505883179658297522435407455008248311187789781960113589834827112974168260506676775743411648452439899496100115579052
r2=2266282824131486468448037400097649751436638343554890873042053537566051913016220134485956663087061113434331598112257987671237397919781153037511303664236178026024200716300256313054976795440759304679065940565652927875017851134819722783392228160931697899128129053901710489789174445944014043443083527638965765809070488225452982880922703011627801716957978130236512493237537609220292483693697781504935020101279551815050569381943159352285456791072657310654958418397051221153029472723065900747600963890428868830367126410421411370704517816919980344041449903545200031548407512798483005492350803089508282331827149736642020562720
d=1814452580735375349943862720618828918630139915423974587850653785462197560999774344107135368454555043491667375552314392616309506004814918478288708383302285286685970221339255810252747773103059121031264059575772453212207545840235008436247634620933941004726742219846507737410336486611203816257479343986488367114011777255284708000213494879044090517505540067938866432994071508106192379566964836729181005004378702445684759533988544066532056379172318125748705772688436663116204079306930926328994293354010739696046248305808409576809006078527713033315527061213274532299699148742370572758989921371532108833619290755313406817153

e=65537
N = math.gcd(r1-pow(2,e),r2-pow(3,e))
m = pow(c,d,N)
print(long_to_bytes(m))

2019-05-27

duckが送るBeginners CTF 2019 Party（Crypto)の解説

初心者向け writeup duck Beginners CTF 2019 Crypto

どうもduckです。唯一自力で解いたPartyについて解説したい。

さて、問題をDLしたらparty.tar.gzというファイルだったので、
tar -zxvf party.tar.gzコマンドで解凍する。
tarはLinuxの標準的な圧縮形式で、windowsでいうzipみたいなファイルらしい（よくわからん）。
解凍するとencrypt.pyというファイルとencryptedというファイルが出てきた。
encryptedをcatするとなんか数字がめちゃくちゃ出てくる。
encrypt.pyを読めば意味がわかるはず。

さて、ここからは大きく二つのフェイズに分けて説明しようと思う。
１．pythonファイルの解析。これによりflagを得るためにやるべきことがわかる。
２．実際にflagをゲットしてみる。（３元１次連立方程式を解くことになるんだけれどね）
頑張っていこう。

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行目：

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だけだ。
未知数３個。式３つ。中学生でも解ける連立方程式だ。

２．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
のため解けない。
計算途中で小数に変換されることによる誤差のせい。
/じゃなく//を使えば３でも解ける。r2をわざわざ通分した表示にしているのもそのためである。

出てきた答えを