2019-09-17

CTFで使う数学　後編

どうも。duckです。
後編始めるよ。

ちょっと全体的に難易度が上がるから、前編にもまして証明が雑になるよ。
よくわからんって人はとりあえずcoppersmithの定理だけみておけばいいです。
頻出なんで。
じゃあやっていこうかー。

６．coppersmithの定理　頻度「４」
これ難しいからスルーしてたんだけどCTFで出会った回数が4回目になったときに学ぶ決心をした。
定理を使う条件さえ覚えていれば後はSagemath(数学ライブラリ)が計算してくれるのであんまり気負わず。

条件　・ $N$ は素因子が未知の合成数
　　　・ $N$ の素因子 $b$ が $b \leq N ^ \beta (0 < \beta \leq 1)$
　　　・ $f(x)$ は次数 $\delta$ の1変数モニック多項式（最高次係数が１）
定理： $f(x) \equiv 0 \pmod b (|x| \leq cN^{\frac{\beta^2}{\delta}})$ を満たす解 $x$ は簡単に求まる。

定理の使い方例
① $b \leq N ^ \beta$ から $\beta$ を求める。
② $(|x| \leq cN^{\frac{\beta^2}{\delta}})$ から（c=1とでもしておくとよい）簡単に求まる $x$ の範囲を求める。
③この範囲に求めたい値が含まれれば上の定理を使う。

sagemathコード例

sage: N = 1279012345679004320987654321
sage: K = Zmod(N)
sage: PR.<x> = PolynomialRing(K)
sage: f = x^2 + 78523430
sage: f.small_roots()

small_roots()関数がcoppersmithの定理の計算を勝手にやってくれて、答えの集合の配列を返す。
数字は適当なので気にしないで。ちなみにsmall_roots()は引数も持たせられる。

f.small_roots(X=2^kbits, beta=1/3)

$X$ は解 $cN^{\frac{\beta^2}{\delta}}$ のこと。

この定理にまつわる自身の論文を快く提供してくださった同期Kに感謝します。
証明は1ミリもブログに書いてないけどな。すまんな。

７．平方剰余　頻度「１」
今のところで出会ったことがほとんどない。

定義： $x^2 \equiv a \pmod N$ となる $x$ が存在するとき $a$ は $N$ を法とする平方剰余であるという。

定理： $a$ が $N$ を法とする平方剰余かどうかは簡単にわかる。

端的に言うと $\mod N$ の世界で $\sqrt{a}$ が存在するかはすぐわかるということ。
証明は平方剰余の相互法則によるが、書かない。
sagemathでの使い方を述べるにとどめる。

#kronecker(a,N)
#1なら平方剰余
sage: kronecker(2,7)
1
#-1なら平方非剰余
sage: kronecker(3,7)
-1
#あるNでの平方剰余が全部知りたいとき
sage: quadratic_residues(7)
[0, 1, 2, 4]

８．中国剰余定理　頻度「３」
まあまあでる。直接ではなくても間接的によくお世話になる。

定理：連立合同式
$x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \quad \vdots\\ x \equiv a_n \pmod {m_n}$
の解 $x$ は $\gcd(m_i,m_j)=1$ ならば $0 \leq x < m_1 m_2 \cdots m_n$ の中に唯一存在する。

答えとなる $x$ を構成することで証明とする。（唯一性の証明は省略）

$m_{ij}^{-1}$ とかいたらそれは $m_i$ の $j$ における逆数という意味で使う。

Garner 法
$x_1 \equiv a_1 \pmod {m_1}$ となる $x_1$ をとってくる。
$x_2 = x_1 + m_1 t_1$ とおき、 $x_2 \equiv a_2 \pmod {m_2}$ となるように $t_1$ を決める。
つまり $x_1 + m_1 t_1 \equiv a_2 \pmod {m_2}$ より $t_1=(a_2-x_1){m_{12}}^{-1}$ とする。
このとき $x_2 \equiv a_1 \pmod {m_1}$ かつ $x_2 \equiv a_2 \pmod {m_2}$
$x_3 = x_2 + m_1 m_2 t_2$ とおき、・・・以下繰り返し。

イメージとしては連立合同式の上から順番に満たすように $x_i$ を拡張していく感じ。

コード：

def inverse(a,N):
    return extend_gcd(a,N)[0] % N

def chinese(a_list,m_list):
    n=len(a_list)
    x=a_list[0]
    m=m_list[0]
    i = 1
    while i < n:
        x=x+(a_list[i] - x) * inverse(m,m_list[i]) * m
        m*=m_list[i]
        i+=1
    return x % m

gcd,extend_gcdは自分で定義した関数。詳しくは前編参照。
CTFで使う数学前編 - CTFと共に生きる

重要な例としてRSA暗号の復号計算を高速化するのに使われているが、それは”暗号まとめ”記事にまとめようと思う。

９．オイラーの定理　頻度「1」
フェルマーの定理の拡張。
まずオイラーのトーシェント関数の定義（ファイ関数ともいう）。

定義：自然数 $N$ と互いに素で1以上 $N$ 以下となるものの自然数の個数を $\varphi (N)$ で表す。

本題。

定理： $a,N$ が互いに素ならば $a ^{\varphi(N)} \equiv 1 \pmod N$

証明概略： $N$ と互いに素な数の集合 $A=\{r_1,r_2,\cdots,r_{\varphi(N)}\}(1 \leq r_i \leq N)$ と $B=\{ar_1,ar_2,\cdots,ar_{\varphi(N)}\}$ の集合は $N$ を法として等しい。
なぜならば $ar_i$ は $N$ と互いに素であるから $ar_i \bmod N = r_j$ ( $A$ の集合の要素のどれかと一致)であり $ar_i \not \equiv ar_j \pmod N$ 。(*)
よって $a ^ {\varphi(N)} r_1 r_2 \cdots r_{\varphi(N)} \equiv r_1 r_2 \cdots r_{\varphi(N)} \pmod N$ 。

(*)フェルマーの小定理5.1を参照(CTFで使う数学前編 - CTFと共に生きる)

コメント：
素数 $p$ に対し $\varphi(p)=p-1$ よりこれはフェルマーの定理の拡張である。
またRSAへの応用として $\phi(pq)=(p-1)(q-1)$ となることにも注意。（復号で使う）
トーシェント関数にはほかにも面白い性質があるがここに書くには余白が(ry)

二次合同式についても触れるつもりでしたが、またの機会に。多分そのうちしれっと追記します。
次は”数学を使わないで解けるCrypto問題”、”暗号方式を学ぶ”みたいなタイトルの記事を書きたいです。

2019-09-16

CSAWCTF 2019 Crypto Writeup(+2) Crypto道場五[8/100]

Crypto duck Crypto道場 writeup

どうも。duckです。
csawCTFはCrypto問題多かったですね。
とりあえず解けた二つ(Crypto400　Fault BoxとCrypto300　SuperCurve)だけwriteup書きます。

1.Crypto300　SuperCurve

楕円曲線暗号です。
配られたファイルはこちら。ローカルで動くので解けなかった方はぜひ。
server.py
Dropbox - server.py - Simplify your life
supercurve.py
Dropbox - supercurve.py - Simplify your life

単純にsecretkeyを見つければFLAGを返してくれる。
パラメータが素人目に見ても残念なのであっさりブルートフォースできた。

for secret in range(curve.order):
# (13815, 1298)はサーバーからのpub
    if curve.mult(secret, base) == (13815, 1298):
        print(secret)

getしたsecretkeyをサーバーにぶん投げればおしまい。

flag{use_good_params}

あまりにあんまりなのでこれを機に楕円曲線暗号について勉強しようかな。きっとそれが運営の狙いに違いない。

2.Crypto400　Fault Box
上が3分で解けたのと引き換えにこっちは16時間かかりました。
知識が足りんかったね。
配られたファイルをローカルで動くように加工しておいたものはこちら。
server.py
Dropbox - server.py - Simplify your life

起動画面。

f:id:falconctf:20190916113821p:plain — menu

メニュー：
1.RSAで暗号化されたFLAGの表示
2.RSAで暗号化されたfake_flagの表示
3.RSAもどきで暗号化されたfake_flagの表示
4.任意の平文入力をRSAで暗号化してくれる

ただ、1,2,3のうちどれか2回、コマンドを打つと強制終了する。4は無制限。
方針：使うコマンドは1,3一回ずつと4を三回。
(a)2と3と $N$ がわかれば $p$ がわかることを示す。
(b) $N$ を求める。
(c)2をブルートフォースし $p$ を求める。
(d)復号する。

(a)
まず3のencrypto部分を抜き出す。ただし変数名を一部変えている。(p→mとした。self.pと紛らわしいため)

def TEST_CRT_encrypt(self, m, fun=0):
        ep = inverse(self.d, self.p-1)
        eq = inverse(self.d, self.q-1)
        qinv = inverse(self.q, self.p)
        c1 = pow(m, ep, self.p)
        c2 = pow(m, eq, self.q) ^ fun
        h = (qinv * (c1 - c2)) % self.p
        c = c2 + h*self.q
        return c

結局サーバーから返ってくるのは連立方程式

$C_1=m^{e_p} \bmod p = m^e \bmod p \\ C_2=m^{e_q} \bmod q \quad {\rm XOR} \quad fun$

の解 $C=C_2 + h * q$ になる。なぜこの $C$ が上記連立方程式の解になるのかは~~”CTFで使う数学後編”の記事に書くのでそちらを参照のこと。~~
→暗号方式まとめRSA編まで待って。

2を $C_f$ とおく。
$C_f= m^e \bmod p$
を満たすことは明らか。よって、
$C - C_f \equiv 0 \pmod p$ であり $C-C_f$ は $p$ の倍数である。
$N=pq$ ゆえ $\gcd (N,C-C_f)$ から $p$ が求まる。

(b) $N$ を求める。
4から三つのデータを取り、最大公約数を取ることで $N$ は求まる。
こちらからのinputとしては!,#,$を選んだ。
それぞれアスキーコードでは33,35,36に対応する。
数式：サーバーからのリターンを $R_{i}$ とする

$R_{33}={33}^{e} \bmod N \cdots ①\\ R_{35}={35}^{e} \bmod N \cdots ②\\ R_{36}={36}^{e} \bmod N \cdots ③$

（①－②）と（②－③）の最大公約数を取れば、それは $N$ の倍数となる。
小さい素数で割って、 $N$ を求めれば終了。

コード：

def gcd(a,b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

e=65537
a33=0x4FC26FA362C01A29D736A0BCEAB5BE9C1862C88ADDECD9E7B6F82E5714CC6C8089963C1239B4DB9B9D1A5D1D9D4A7338EDC23129CDF387108FC76BC9501FA29C77BEEFC86515F206AA0F2962959ED2DBDC6EBCB172C20DBE7E6D359570094DC552691FAC046BD4EEA07AC48A09B4D849861F063E66CCF61D54937CE4D09EF5C617C606B3D30AD6D798653E2CF7675AA0701888B6B10641DE349C22192E8F3A95A871C004A17F5191F1F3E07BE1699BB94166254A1746EB4DBF3B7FB120C6B9E906B41E6971C335CE55F5A56EB755F7ED373070F084EA01CA509D2EDF4A324A9CDA53EAB49AF839C6C1EDD3542D8D4B3876D95BA0E3D8396003100711316F64
a35=0x39AC520C665B84FEC4E9E74992A53E77EBECB3A7E356D2CACB7A4E3A4192BC4CF9C41FEB27E97A7F101B01FDB37FD3D64AFFD943F96B0329F8C99180EC8157E83BAC86E1E3E4761540FF82FB4884E1992D32211C50EF5621A22F092C7700F17DF6C59E122860E0973C23F197B3AA767D76B8EADA6B3A73CA87DEDED3C3C066FF4CDE0542626C49CB7AD34BF2F77EAC4F2F85690CFA046E8083E2A4A517C187D19BF10BE0D84646F0B2E8C51DCAE729CB410BA97F85F7175C7BEA7CBEED681B27CACFC15A64FF2D8AF0A9CB6FBE95EC2D61D3A3D70572FCC5333B836FF36CE2608FE45716F15B78A353606BBD2B4EFD2285A1BDB0C39C200A42F2DC1C8F6C38D
a36=0x1755F0E5CD015A5DCC76E285D9B25D8360567461AFCF63976B6F1ECFFCCF7114FCB8FB7E5CFD74C37CE2B21078E56AA764439F98B41CC913FB59077AFDF0723B6E5694B1A8D990F91A617B0C448227EAD04145FE41277A9C2183B58F92AEB582CA1BC7A276F09C4B3ACE0E2AA892F8C483647AA7D4D18BBF84AC06DDF3FD671A69AB9E4F7A9E2F194F621ACF2886EB032C31B54170FDD35A0032F512BB31CE820F07BCD9734B2B71B63BB44E5E063C1A326E5560EB60CD41973DD918E766D14F2C3E0EEE609214FF6CDB9369CDB66EBCB252E7DB491520A1CB83C1CAB48285654D8C8F8ADAF809D34CD1F4AEFDC9031ABB40A1850A27E439387354D438CE1C3

pow33=pow(33,e)
pow35=pow(35,e)
pow36=pow(36,e)

N=gcd(pow35 - a35 - pow33 + a33,pow36 - pow35 - a36 + a35)
prime_list=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]
for prime in prime_list:
    while N % prime == 0:
        N = N // prime
        print(prime)

print(hex(N))
print(len(str(hex(N)))*4)

$N$ のbit数が2048とわかっているので、乖離していた場合は取り直すべき。

コード：

N=0x4f4834ffa488e1c782f91942a71544b8aea3d28d86408d54a625315538e455d3ecfe69cf9b8bf3ddaa65ac65604270bd38af00f0f2f1efeb6f818ae87832dde30ed9468b3e85501f36fc6ea2140eae996152394dc7e697441192ecb258207b75af50d436856efe68b38198199b057487e339bb70eedd95ea0efa208e4a4982848c7c09668d021c80e5a932becb81c8101efe71a0a270124923272588b292cc32b032d01956c609d1470fab26855547081d9a7a4972eb0e3af918f5063147b30f4ec3791ec9c6e9be0bc8cda591725a17ceef60e648ed692456bec1a4b0367fe5c18020e9e09fa80084c1bc0931644a933bea3990ca9f830377af5e4c8f92777
e=0x10001
C=0x38CB3043F98E1F6D09A1A1D5D81322E785737C306B717365DC6FD9F8340366A191D6B9255E8363B8259894BD20886F43A26D14CC701659A170F76B039DF4E6F7D51BA8DFCA050CDB1DDD19B3ABDE9B7E7DE4EF44498BAAD25DEF46167583864AA4CDE729BA8924939C9FD960EEF68A6AFF0808B5D42B18B63E63CAFF6AACA179AA0E0E7D2D19A2CB99F568770CE70BE8D1FC14770C08079DC0E6001C3650CA9BC94F62CEF917A4534A4257DD29CAA893654358A52939B6CA73D803D6738A323FAFDC5CD15853415627825CE5983D807CFD35446468232CCB8A7DC8EDC4996A9600590F23C5A76F2B9339270B548E13240E5C9F43736F4491EDAA20424CCA538

li=["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"]

#fake_flagに対して総当たりする
BF=""
for i in li:
    BF+=i
    for j in li:
        BF+=j
        for k in li:
            BF+=k
            fake_flag="fake_flag{00000000000000000000000000000"+BF+"}"
            m=s2n(fake_flag)
            Cf=pow(m,e,N)
            if gcd(Cf-C,N) != 1:
                print("p:{%d}" % gcd(Cf-C,N))
                print("Cf:{%x}" % Cf)
            BF=BF[0:2]
        BF=BF[0]
    BF=""

これにて $p$ が求まった。

(d)復号する。
$p$ がわかったので $q$ , $d$ ももとまる。ゆえに復号可能。
コード：

def extend_gcd(a,b):
    k_list=[]
    while b != gcd(a,b):
        r = a % b
        k_list.append((a - r) // b)
        a = b
        b = r
    k_list.reverse()
    y = 1
    x = 0
    for k in k_list:
        temp_y = y
        y = x - k * temp_y
        x = temp_y
    return [x,y]

N=0x4f4834ffa488e1c782f91942a71544b8aea3d28d86408d54a625315538e455d3ecfe69cf9b8bf3ddaa65ac65604270bd38af00f0f2f1efeb6f818ae87832dde30ed9468b3e85501f36fc6ea2140eae996152394dc7e697441192ecb258207b75af50d436856efe68b38198199b057487e339bb70eedd95ea0efa208e4a4982848c7c09668d021c80e5a932becb81c8101efe71a0a270124923272588b292cc32b032d01956c609d1470fab26855547081d9a7a4972eb0e3af918f5063147b30f4ec3791ec9c6e9be0bc8cda591725a17ceef60e648ed692456bec1a4b0367fe5c18020e9e09fa80084c1bc0931644a933bea3990ca9f830377af5e4c8f92777
p=146121412489499472018936606208560315649851850426210311487767280785113784146895230548028829336346860550793966332799881971944233778584359574153755251587931570761602782385240314394277542506686618532791786610113830452217010923218599464860941149784418258798996522026079976590154467841339783864766395145168554744133
q=N//p
e=0x10001
phi=(p-1)*(q-1)
C=0x37480606FE2F01C9C09D173E841AB32158ADBD156077B6D0A27F2FBC5AB5EA071B19769DB8FAD69DB4857967BC97A9A5E66F2E965235656550B6780A13BAAB236CD6E7C56E09E3F8F34642885725A8B27FE810B085451FB726FE064DED15A65AAC1958D11E8AF4FAB98ADD0F31286B75FB01C9B2F85E15CB2FE22140747CFBA317C7E3AFC9E0A02CBD78C110AC503D8E94ED3E60C359B56EB1D9D29091EF1C81C21267517A5BAABEF7A688436E8726782CC28D5C40E1F42D879BEFD06A935AFA5C55A92EF0A62A92F459BF97A8B784ADF3A0FE1FBD44B4FFDC95A7E40765CCA8ADDE6CB0F9E62F4013D804ED835D65B78C09F90C9A00B8354FB22F9C21115CC

d=extend_gcd(e,phi)[0]
print(n2s(pow(C,d,N)))

flag{ooo000_f4ul7y_4nd_pr3d1c74bl3_000ooo}

共通カギ暗号、楕円曲線暗号、RSAパディングについて理解が甘いので調べてまとめます。
あとはコードが渡されないエスパー問題もよくわからんのでWriteup読みます。

いやあもうCryptoいけんじゃね？Webやろうかとか思ってた自分が恥ずかしい。世界は広い。

2019-09-12

CTFで使う数学　前編

Crypto Cryptoまとめ duck Crypto数学

どうも。duckです。
とあるCTF（後で書きます）の過去問解いてたんですが、あまりの数学のできなさに絶望したのでまとめます。
証明は適当につけたのであってるかわかりません。（オイ）
まあわかるっしょっていう条件は書いてなかったり厳密性を重視してなかったりするのでお気を付けくださいませ。
あと個人的にCTFで使う頻度（五段階評価）も書いておきます。まあまだ全然解いてないのであてにはならないですが。
じゃあこっから数学れっつごー。

１．合同式　頻度「５」
ないと死ぬ。Cryptoは整数論でできているのです。
いちいち説明する気にならないので
合同式の意味とよく使う６つの性質 | 高校数学の美しい物語ここらを見ていただければ。

そのうちまとめます。勉強会とか開いたら。（開くとは言っていない）

２．ユークリッドの互除法　頻度「３」

定理： $a,b \in \mathbb N$ の最大公約数は簡単に求められる

詳しいアルゴリズム書くのはめんどいからコード見て。これで $a,b$ の最大公約数が求まります。

def gcd(a,b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

定理の核： $\gcd (a,b) = \gcd (bk + r,b) = \gcd (r,b)$
ただし $a = bk + r(0 < r < a)$

コメント：最大公約数が簡単に計算できることくらいは知っておいたほうがよい。
アルゴリズムは調べれば出てくるし上のコードコピペしてもいいし、お好みで覚えて。

３．拡張ユークリッドの互除法　頻度「４」
RSA暗号に出てくるじゃん。つまり超重要。

定理1： $ax + by = \gcd (a,b)$ の整数解 $(x,y)は計算できる$

これはユークリッドの互除法から構成的に証明できるんだけど、めんどい。
汚いコードおいとくね。（拡張ユークリッドの互除法が入ってるpythonモジュールなくない？）

def extend_gcd(a,b):
    k_list=[]
    while b != gcd(a,b):
        r = a % b
        k_list.append((a - r) // b)
        a = b
        b = r
    k_list.reverse()
    y = 1
    x = 0
    for k in k_list:
        temp_y = y
        y = x - k * temp_y
        x = temp_y
    return [x,y]

ちなみに上のgcdのコードと一緒に使わないと動かないよ。

暗号的には次の応用が重要。（先にいえ）

定理２： $a$ と $N$ が互いに素であるならば
$ax \equiv 1 \bmod N$ の整数解 $x \bmod N$ は計算できる。

証明概略：上の定理1で $b=N$ としたものを考える。
$ax+Ny=\gcd (a,N)=1$ 。
最右辺と最左辺に対して $\bmod N$ をとれば定理2を得る。

コメント：RSAに出てくることもさることながら、この定理の便利なところは逆数が求まるところですね。
上記の $x=a^{-1} \bmod N$ を生かす問題がめちゃあります。

４． $N=pq$ のとき $a^{-1} \bmod N$ を $a^{-1} \bmod p$ として使っていい　頻度「2」
数式でそれっぽく書くとこう。

定理： $p | N$ なら $a \bmod N \equiv a \bmod p \pmod p$

証明概略： $kN+b=kqp + b$

コメント： $a^{-1} \bmod p$ を知りたいけど $p$ が秘密鍵でわからんって時に使えます。
$a^{-1} \bmod N$ は $N$ が公開鍵なので求められること多し。
言われりゃ当然なんだけど結構盲点。

５．フェルマーの小定理　頻度「２」
今のところそんなに見てないけどもっと活躍してもいい気がする。

定理： $a,p$ が互いに素なら $a^{p-1} \equiv 1 \pmod p$

証明ついでに整数論の常識として知っておくとよさそう（忘れてたがw）なものを証明しておく。
５．１　互いに素なら割ったら余りはバラバラ

定理：　 $a$ と $p$ が互いに素なら $a \bmod p,2a \bmod p,\cdots,(p−1)a \bmod p$ はすべて異なる

証明概略： $na \equiv ma \pmod p$ とすると $(n -m)a \equiv 0 \pmod p$ 。
$a,p$ は互いに素だから $n \equiv m \pmod p$ だがこれは $n \not \equiv m \pmod p$ に矛盾。

これを用いたフェルマーの小定理の証明

証明概略：全てのあまりがでるから $a*2a* \cdots (p-1)a \equiv (p-1)! \pmod p$
両辺 $(p-1)!$ でわる。

もういっこ
５．２　素数pの二項係数は１じゃなかったら $p$ の倍数

定理： $(x + y)^p \equiv x ^p + y ^p \pmod p$

証明概略： $k \neq 0,p$ のとき $p | \binom{p}{k}$ を示す。
$\binom{p}{k} = p \frac{(p -1)(p-2) \cdots (p - k + 1)}{k!}$ であるが $p$ は素数で $0 < k < p$ より $p$ の倍数。

後編は、オイラーの定理、平方剰余、coppersmith'sの定理、 $4n+3$ 型の二次合同式の解（だっけ？）などを予定してます。
まあちょっと難易度は上がるけどcoppersmith'sの定理とかは頻出なので、よければ後編もお付き合いください。

2019-09-08

N1CTF 2019 Crypto Writeup(+1) Crypto道場四[6/100]

writeup Crypto duck Crypto道場

どうも。duckです。
N1CTFも解いてました。

Cryptoが2題あったなか1題だけ解けた（悔しい）のでWriteup書きます。

Part3-BabyRSA
なんでPart3なんだとかツッコミはいろいろあるけど解いていきましょう。
配られたファイルはこちら。

暗号化
Dropbox - BabyRSA.py - Simplify your life
暗号文
Dropbox - flag.enc - Simplify your life

短いので暗号化のpythonファイルははっちゃいます。

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
from Crypto.Util import number
import random
from secret import flag
N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
e = 0x10001
m = number.bytes_to_long(flag)
with open('flag.enc', 'w') as f:
    while m:
        padding = random.randint(0, 2**1000) ** 2
        message = padding << 1 + m % 2
        cipher = pow(message, e, N)
        f.write(hex(cipher)+'\n')
        m /= 2

平文bitを下から順に1bitずつパディング入れながら暗号化してるだけですね。
Nがめちゃでかいのと、パディングもめちゃでかいのでこれどーすんのって感じです。

Crypto問題は困ったら（というかいつもだいたい）紙に起こしてみるようにしてます。
ということで数式になおしちゃうぞ☆。

$padding:p,random.randint...:r,message:M,cipher:c$ とおく。

$p=r^2$
$M=2p+m$
なので結局
$c=(2r^2+m)^e {\rm mod}N$ です。
重要なのがmは0or1ということです。

んんん？
mが0の時は大変なことが起きますね。
$(2^e)^{-1}c= (r^e)^2{\rm mod}N$
はい。平方剰余です。
平方剰余の相互法則がありますから
$x^2=a {\rm mod} b$
を満たす $x$ が存在するかはすぐに判定できます。

つまり今回は $(2^e)^{-1}c$ が平方剰余であるかどうかを調べると $m$ が0か1か判定できます。
計算にはSagemathを使いました。
コードはどっかに消えてしまったので見つかれば載せます。
すべてのchipherに対して平方剰余だったら0平方剰余でなかったら1を出力する用にfor文回すとかだったと思います。
下位ビットから求まっていくことに注意すれば解けました。

flag:N1CTF{You_can_leak_the_jacobi_symbol_from_RSA}

フラッグのjacobiはヤコビ記号のことです。平方剰余の時に出てきます。
ついでにいうとヤコビ記号の拡張としてルジャンドル記号もいます。たしか。

2019-09-08

TMCTF2019 Writeup Wildcard 100

writeup Crypto duck

どうも。duckです。
TMCTFやりました。

ぱっと見Cryptoがなくてテンション下がりましたが１題解けたのでWriteup書きます。

・Wildcard 100
配られたのは3と6の手書き画像が３万個くらいあるファイル。
Dropbox - data.zip - Simplify your life
こんなん。

f:id:falconctf:20190908184541j:plain — ３と６の狂気

問題文によると、
１．3と6の画像を分ける。
２．そのあとそれぞれのユニークなファイルを数える。
３．flagはTMCTF{3の画像の数_6の画像の数}

としろとのことなのでやりました。
MISCとかに近い感じですね。

１.3と6を分ける
人力で分けるのはつらすぎるので、問題文に書いてある通りクラスタリングアルゴリズムを使います。
まあ端的に言えば機械学習です。
いい感じのサイトを見つけたのでコードを使わせていただく。
scikit-learnで国旗画像をクラスタリングして似ているものを探す │ Web備忘録
modifyしたやつ。

import os
import shutil
import numpy as np
from PIL import Image
from skimage import data
from sklearn.cluster import KMeans

# 1. RGBに変換して保存する
for path in os.listdir('./data'):
    img = Image.open(f'./data/{path}')
    img = img.convert('RGB')
    img.save(f'./convert/{path}')

# 2. 3次元配列の画像データを2次元配列のデータに変換
array=np.array([path for path in os.listdir('./convert')])
feature = np.array([data.imread('./convert/'+path) for path in array])
feature = feature.reshape(len(feature), -1).astype(np.float64)

# 3. 学習(2種類のグループにクラスタリングする)
model = KMeans(n_clusters=2).fit(feature)

# 4. 学習結果のラベル
labels = model.labels_

# 5. 学習結果(クラスタリング結果の表示 + ラベルごとにフォルダ分け)
for label, path in zip(labels, os.listdir('./convert')):
    os.makedirs(f"./cluster/{label}", exist_ok=True)
    shutil.copyfile(f"./data/{path}",f"./cluster/{label}/{path}")
    print(label, path)

ちなみにこれサーキットラーンっていうライブラリ使ってます。
あとはてテンサーフローとかも有名ですよね。

まあそれはさておき、これで3と6のデータをよりわけることができましたとさ。
3が16768個で6が17254個でした。
はじめてやったけど教師なし学習ってこんなにきれいに分けられるのね。少しビビった。

２．ユニークなファイルを数える
どうすんだこれ。
バイナリで比較すりゃいいかと思って↓のコード書いた。

import numpy as np

def openread(path):
    a = open(path,"rb")
    img = a.read()
    a.close()
    return img

path='./0'
array=np.array([openread(path) for path in os.listdir(path)])
set = set(array)
print(len(set))

結果的にはこれでできてなかった。
phoenixによると、バイナリが違うのに画像として同じファイルが3の画像に一個あったらしいので
それを考慮して
flag:TMCTF{14962_347}

正直作問ミスかと思いました。phoenixがいてよかった。
引き続きN1CTFのWriteupも書かなきゃ。（終了まであと２時間あるけど諦め体制）

2019-09-05

SECCON Beginners CTF 2018 Crypto Writeup(+2) Crypto道場②[4/100]

writeup Crypto Crypto道場初心者向け duck

どうも。duckです。
happy!解くのは明日にさせてください。
昨日上げようとしてたやつ先にあげちゃいます。

1.[Warmup] Veni, vidi, vici
fileが３つあったらしい。

#part1
Gur svefg cneg bs gur synt vf: pgs4o{a0zber

#part2
Lzw kwugfv hsjl gx lzw xdsy ak: _uDskk!usd_u

#part3
{ʎɥdɐɹɓ0ʇdʎᴚ :sı ɓɐlɟ ǝɥʇ ɟo ʇɹɐd pɹıɥʇ ǝɥ⊥

part1,2はceaser暗号なので昔作ったpythonファイルにぶち込むとすぐ答えが出た。
(そのうちgitにあげる予定)

part3は自力で反転した。

flag:ctf4b{n0more_cLass!cal_cRypt0graphy}

2.RSA is Power

次のファイルが渡されたらしい。

RSA暗号ですね。

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

Nの桁数を数えてみたら77桁だった。bit数に換算すると
$77*\log_{10}2 \approx 256$
256bitとNが非常に小さいので素因数分解攻撃が有効である。

from Crypto.Util.number import long_to_bytes

def gcd(a,b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

#ax+by=gcd(a,b)の解[x,y]
def extend_gcd(a,b):
    k_list=[]
    while b != gcd(a,b):
        r = a % b
        k_list.append((a - r) // b)
        a = b
        b = r
    k_list.reverse()
    y = 1
    x = 0
    for k in k_list:
        temp_y = y
        y = x - k * temp_y
        x = temp_y
    return [x,y]

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

p=299681192390656691733849646142066664329
q=324144336644773773047359441106332937713
phi=(p - 1)*(q - 1)

d = int(extend_gcd(phi,E)[1]) % phi
print(long_to_bytes(pow(C,d,N)))

simpyを使ってたけど、素因数分解が1日たっても終わらない。
仕方ないのでsagemath入れたら数分で解けた。素晴らしい。

ctf4b{5imple_rs4_1s_3asy_f0r_u}

でたぞい！

2019-09-04

TWCTF 5TH 2019 Crypto Writeup(+1) Crypto道場③[5/100] happy!

writeup Crypto duck Crypto道場

どうも。duckです。
TWCTF Happy!のwriteup書きます。

flag.enc
Dropbox - flag.enc - Simplify your life
happy
Dropbox - happy - Simplify your life
pub.key
Dropbox - pub.key - Simplify your life
Gemfile
Dropbox - pub.key - Simplify your life
Gemfile.lock
Dropbox - Gemfile.lock - Simplify your life

おいおいGemfileなんて知らねえよって人は、bundllerでぐぐるといいです。
gem installしてもいいけど。

バイナリファイルが読めないので、以下のコードをhappyファイルの適当な場所にはりつけて
実行します。

def show_key()
        puts "n"
        puts @attr[:n]
        puts "e"
        puts @attr[:e]
        puts "p"
        puts @attr[:p]
        puts "q"
        puts @attr[:q]
        puts "d1"
        puts @attr[:d1]
        puts "d2"
        puts @attr[:d2]
        puts "cf"
        puts @attr[:cf]
end

pubkey = Key.import(File.binread("pub.key"))
pubkey.show_key()

Nとeは公開鍵だから当然としてcfも見れます。
これも公開鍵なんかなあと思ってたんですが、ほかの方のwriteup読むとどうやら見せちゃいけないやつらしいですね。
ほうほう。

コード読むと
$N=p*q^k$
で、pとqは700bit以上の整数らしいです。
Nとcfわかってるんだからbit数を数えればk求まるんじゃね？
(cfは $mod q^k$ だからだいたい $q^k$ くらいのbit数になる。)

というわけで数えたら、
N:2200とか
cf:1500くらい
だったので、kは2です。

ここでcfにkをぶち込むと
$cf \equiv p^{q*(q - 1) - 1} mod q ^2$
でした。
なんだこれオイラーの定理使えるじゃん。
（オイラーのトーシェント関数とかで調べて。オイラーの定理って名前の定理は死ぬほどあるので探すの大変です多分。）
$cf \equiv p^{-1} mod q ^2$
つまりこれが成り立ちます。

本番はここでギブアップ。
この先はcoppersmith's の定理を使うらしいです。

定理は書くのめんどうなので引用先をご覧ください。
要約すると
$f(x) \equiv 0 mod b$ となる解 $x_0$ （mod bじゃないのに注意）はある条件を満たしているときはすぐ求まるよということ。
しかもbがわからなくても大丈夫という意味不明さ。すうがくすごい。

今回は
$cf \equiv p^{-1} mod q ^2$
$p * cf \equiv 1 (mod q^2)$
$p - cf^{-1} \equiv 0 (mod q^2)$
であり、
$f(p) = p - cf^{-1}$ とするとこの定理が使える条件を満たします。

あっさり出ている $cf^{-1}(mod q^2)$ は $cf^{-1} (mod N)$ の値をぶち込んでおけばいいです。
よく考えるとわかります。

sagemathのsmall_root関数を使うとめでたくpが出ます。正確には候補ですが。
あとは $q^2=N/p$ からさくっとqを計算して
pとqがわかったら復号関数にぶち込みましょう。

わたしはgenerate_key(k,bits)関数の中のpとqを求めたやつにして、keyをつくって
そのkey とflag.encをprivate_decrypt(str, pad = true)にぶん投げて復号してもらいました。

flag = File.binread("flag.enc")
#第一引数は意味なし　k=2
key = Key.generate_key(1, 2)
File.binwrite("answer", key.private_decrypt(flag))

TWCTF{I_m_not_sad__I_m_happy_always}
解けた。

なんかtexの使い方忘れすぎてる。
modが斜体だし、cfはfにしか-1かかってないし。
どうやるんだっけね。気持ち悪い。
今度調べときます。

今日はN1CTFやるぞ。

引用：
TokyoWesterns CTF 5th 2019: Happy! (Crypto, 242 pts, 36 solves) | void main