COMPFEST CTF 2021 Writeup - よっちんのブログ

この大会は2021/9/12 17:00(JST)～2021/9/13 17:00(JST)に開催されました。
今回もチームで参戦。結果は1097点で232チーム中29位でした。
自分で解けた問題をWriteupとして書いておきます。

Sanity Check (Misc)

問題にフラグが書いてあった。

COMPFEST13{Welcome_to_CTF_COMPFEST_13}

Promotional Video (Misc)

字幕にフラグが表示されるが早くで読めない。http://video.google.com/timedtext?type=list&v=047T5AZpOiIにアクセスして字幕情報を見る。

<transcript_list docid="15244354765009271330">
<track id="0" name="" lang_code="en" lang_original="English" lang_translated="English" lang_default="true"/>
</transcript_list>

http://video.google.com/timedtext?hl=en&lang=en&name=&v=047T5AZpOiIにアクセスする。

<transcript>
<text start="0" dur="5">Don't forget to follow our social media and visit our website (link in description)</text>
<text start="5" dur="0.001">C</text>
<text start="5.502" dur="0.001">O</text>
<text start="6.307" dur="0.001">M</text>
<text start="6.407" dur="0.001">P</text>
<text start="7.507" dur="0.001">F</text>
<text start="7.607" dur="0.001">E</text>
<text start="7.707" dur="0.001">S</text>
<text start="8.807" dur="0.001">T</text>
<text start="9.907" dur="0.001">1</text>
<text start="10.007" dur="0.001">3</text>
<text start="10.107" dur="0.001">{</text>
<text start="10.207" dur="0.001">c</text>
<text start="10.307" dur="0.001">4</text>
<text start="10.407" dur="0.001">p</text>
<text start="10.507" dur="0.001">t</text>
<text start="11.607" dur="0.001">U</text>
<text start="11.707" dur="0.001">r</text>
<text start="11.807" dur="0.001">3</text>
<text start="11.907" dur="0.001">_</text>
<text start="12.007" dur="0.001">T</text>
<text start="12.107" dur="0.001">h</text>
<text start="12.207" dur="0.001">3</text>
<text start="12.307" dur="0.001">_</text>
<text start="12.407" dur="0.001">F</text>
<text start="12.507" dur="0.001">l</text>
<text start="12.607" dur="0.001">4</text>
<text start="12.707" dur="0.001">g</text>
<text start="12.807" dur="0.001">_</text>
<text start="12.907" dur="0.001">c</text>
<text start="13.007" dur="0.001">b</text>
<text start="13.107" dur="0.001">1</text>
<text start="13.207" dur="0.001">2</text>
<text start="13.307" dur="0.001">1</text>
<text start="13.407" dur="0.001">7</text>
<text start="13.507" dur="0.001">b</text>
<text start="13.607" dur="0.001">c</text>
<text start="13.707" dur="0.001">c</text>
<text start="13.807" dur="0.001">d</text>
<text start="13.907" dur="0.001">}</text>
</transcript>

COMPFEST13{c4ptUr3_Th3_Fl4g_cb1217bccd}

Snab? Yes, Snab (Cryptography)

sはp + qの2乗なので、sの平方根をとれば、p + q (= p_q とする) がわかる。また以下の式より、phiもわかる。

phi = (p - 1) * (q - 1) = n - (p + q) + 1 = n - p_q + 1

さらにGCD(pow(s, 3) - a, b) = rと推測できる。以上により復号する。復号結果は以下の通り。

#Snab says good job! But you're not done yet
flag = findme
halfa = ''.join([flag[i] for i in range (0, len(flag), 2)])
halfb = ''.join([flag[i] for i in range (1, len(flag), 2)]
p = bytes_to_long(bytes(halfa, encoding = 'utf-8'))
q = bytes_to_long(bytes(halfb, encoding = 'utf-8'))
r = 0
while (not(isPrime(p) and isPrime(q))):
    p += 1
    q += 1
    r += 1

p, qの値からそれぞれrだけ引けば、元のp, qがわかりhalfa, halfbを求められる。あとは交互に構成していけば、フラグになる。qを求めるには以下のことを使う。

b = (s - q * (2 * p + q)) * r
  = (s - 2 * n - q**2)  * r
　　　　↓
q**2 = s - 2 * n - (b // r)

from Crypto.Util.number import *
import gmpy

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

e = int(params[0])
s = int(params[1])
n = int(params[2])
a = int(params[3])
b = int(params[4])
c_list = eval(params[5])

p_q = int(gmpy.root(s, 2)[0])
assert pow(p_q, 2) == s

phi = n - p_q + 1
d = inverse(e, phi)
r = GCD(pow(s, 3) - a, b)

m_list = []
for c in c_list:
    mr = pow(c, d, n)
    m_list.append(mr // r)

for m in m_list:
    msg = long_to_bytes(m).rstrip()
    print msg
print

q = int(gmpy.root(s - 2 * n - (b // r), 2)[0])
p = n // q
assert p * q == n

p = p - r
q = q - r
halfa = long_to_bytes(p)
halfb = long_to_bytes(q)

flag = ''
for i in range(len(halfa)):
    flag += halfa[i]
    flag += halfb[i]

print flag

実行結果は以下の通り。

#Snab says good job! But you're not done yet
flag = findme
halfa = ''.join([flag[i] for i in range (0, len(flag), 2)])
halfb = ''.join([flag[i] for i in range (1, len(flag), 2)]
p = bytes_to_long(bytes(halfa, encoding = 'utf-8'))
q = bytes_to_long(bytes(halfb, encoding = 'utf-8'))
r = 0
while (not(isPrime(p) and isPrime(q))):
    p += 1
    q += 1
    r += 1

Cool! You did it! {y0U_d1DnT_3xpEcT_t0_FinD_pQ_4s_a_fl4g_DiD_y0u_7e1877a801}

COMPFEST13{y0U_d1DnT_3xpEcT_t0_FinD_pQ_4s_a_fl4g_DiD_y0u_7e1877a801}