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

どうも。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)))