CakeCTF 2022 Writeup

この大会は2022/9/3 14:00(JST)~2022/9/4 14:00(JST)に開催されました。
今回もチームで参戦。結果は1439点で713チーム中19位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome (welcome)

Discordに入り、#announcementチャネルのメッセージを見ると、フラグが書いてあった。

CakeCTF{p13a53_tast3_0ur_5p3cia1_cak35}

frozen cake (warmup, crypto)

暗号処理は以下の通り。

・m: フラグの数値化
・p, q: ランダム512ビット素数
・n = p * q
・n, pow(m, p, n), pow(m, q, n), pow(m, n, n)を出力
a = pow(m, p, n)
b = pow(m, q, n)
c = pow(m, n, n)

とすると、以下が成り立つ。

pow(a, q, n) = c
pow(b, p, n) = c

さらに以下が成り立つ。

pow(a, q, q) = pow(a, q - 1, q) * pow(a, 1, q) = pow(a, 1, q) = a % q
pow(b, p, p) = pow(b, p - 1, p) * pow(b, 1, p) = pow(b, 1, p) = b % p

以上を踏まえると、以下が成り立つ。

c % p = pow(b, p, p) = b % p
c % q = pow(a, q, q) = a % q

つまり b - c はpの倍数となるため、nとの最大公約数がpとなりnを素因数分解することができる。あとはどれかの式で通常通り復号すればよい。

#!/usr/bin/python3
from Crypto.Util.number import *

with open('output.txt', 'r') as f:
    params = f.read().splitlines()

n = int(params[0].split(' ')[-1])
a = int(params[1].split(' ')[-1])
b = int(params[2].split(' ')[-1])
c = int(params[3].split(' ')[-1])

p = GCD(b - c, n)
q = n // p
assert n == p * q and isPrime(p) and isPrime(q)

phi = (p - 1) * (q - 1)
d = inverse(p, phi)
m = pow(a, d, n)
flag = long_to_bytes(m).decode()
print(flag)
CakeCTF{oh_you_got_a_tepid_cake_sorry}

brand new crypto (crypto)

暗号処理の概要は以下の通り。

・pubkey, privkey = keygen()
 ・p, q: 512ビット素数
 ・n = p * q
 ・phi = (p-1)*(q-1)
 ・以下、繰り返し
  ・a: phi未満のランダム整数
  ・b = phi + 1 - a
  ・s: phi未満のランダム整数
  ・t = -s*a * inverse(b, phi) % phi
  ・bとphiの最大公約数が1の場合、繰り返しを終了
 ・(s, t, n), (a, b, n)を返却
・c = []
・flagの各文字について、以下の処理を実行
 ・c1, c2 = enc(m, pubkey)
  ・r: n未満ランダム整数
  ・c1 = m * pow(r, s, n) % n
  ・c2 = m * pow(r, t, n) % n
  ・c1, c2を返却
 ・(c1, c2)をcに追加
・pubkey, cを出力

c2, c2について、式を変形していく。

c1 = m * pow(r, s, n) % n
c2 = m * pow(r, t, n) % n
    ↓
C1 = c1 * inverse(m, n) % n
C2 = c2 * inverse(m, n) % n
pow(C1, t, n) = pow(pow(r, s, n), t, n) = pow(r, s * t, n)
              = pow(pow(r, t, n), s, n) = pow(C2, s, n)

これが成り立つmをブルートフォースで求める。

#!/usr/bin/env python3
from Crypto.Util.number import *

with open('output.txt', 'r') as f:
    params = f.read().splitlines()

(s, t, n) = eval(params[0])
c = eval(params[1])

flag = ''
for (c1, c2) in c:
    for m in range(32, 127):
        C1 = c1 * inverse(m, n) % n
        C2 = c2 * inverse(m, n) % n
        if pow(C1, t, n) == pow(C2, s, n):
            flag += chr(m)
            break
print(flag)
CakeCTF{s0_anyway_tak3_car3_0f_0n3_byt3_p1aint3xt}

Survey (survey)

アンケートに答えたら、フラグが表示された。

CakeCTF{ar3_y0u_5ati5fi3d_with_thi5_y3ar5_cak3?}