SECCON 2020 Online CTF Writeup

この大会は2020/10/10 15:00(JST)～2020/10/11 15:00(JST)に開催されました。
今回もチームで参戦。結果は1678点で579チーム中14位でした。
自分で解けた問題をWriteupとして書いておきます。

koharu (crypto)

pの剰余環上でPQを因数分解する。多項式でなく、整数でも同じような定理があるが、試してみると、以下のことが成り立つことが分かった。

・C = (S * S) % PQ の場合
　power_mod(C, (NP-1)//2, P) = 1
・C =  (S * S * R) % PQ の場合
　power_mod(C, (NP-1)//2, P) = NP - 1

このことを使って、1ビットずつフラグを構成していく。

#!/usr/bin/env sage
#### from output.txt ####
p = 4832823609987476353
PQ = 2475361839038406994*x^128 + 1816580044636445865*x^127 + 771106714052997910*x^126 + 2532248969060743840*x^125 + 157159147928168793*x^124 + ... + 2337193413394346074
c = [2027712907546344021*x^127 + 2302822347078959804*x^126 + 596638239593512636*x^125 + 3973727976183683295*x^124 + ...
#########################
PR = PolynomialRing(GF(p), 'x')
n = PR(PQ)
P, Q = n.factor()
P, Q = P[0], Q[0]
NP = p**P.degree()
NQ = p**Q.degree()

bin_flag = ''
for i in range(len(c)):
    C = PR(c[i])
    print '[+]', bin_flag
    if power_mod(C, (NP-1)//2, P) == 1:
        bin_flag = '1' + bin_flag
    else:
        bin_flag = '0' + bin_flag

while True:
    if len(bin_flag) % 8 != 0:
        bin_flag = '0' + bin_flag
    else:
        break

flag = ''
for i in range(0, len(bin_flag), 8):
    flag += chr(int(bin_flag[i:i+8], 2))

print flag

SECCON{p01y-p01y-p3r0-p3r0-hy0ukun-p3r0p3r0}

Survey (misc)

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

SECCON{Thank you for playing SECCON 2020 Online CTF}