TSG CTF 2021 Writeup

この大会は2021/10/2 16:00(JST)~2021/10/3 16:00(JST)に開催されました。
今回もチームで参戦。結果は709点で775チーム中49位でした。
自分で解けた問題をWriteupとして書いておきます。

Sanity Check (Warmup)

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

TSGCTF{Tokyo2020_was_held_in_2021_so_TSGCTF2021_was_held_in_2020???}

Beginner's Crypto 2021 (Crypto)

暗号化のスクリプトが添付されている。

from secret import e
from Crypto.Util.number import getStrongPrime, isPrime

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
phi = (p - 1) * (q - 1)

with open('flag.txt', 'rb') as f:
    flag = int.from_bytes(f.read(), 'big')

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)

c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)

print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')

以下の部分に注目する。

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

e, e + 2, e + 4は必ずどれかが3の倍数。このため、すべてが素数になるのはe = 3しかない。あとはe1, e2を算出し、Common Modules Attackで復号できる。

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

def commom_modules_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy2.gcdext(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = inverse(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = inverse(c2, n)
 
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    x = (v*w) % n
    return x

p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743

N = p * q
phi = (p - 1) * (q - 1)

e = 3
e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)

m = commom_modules_attack(c1, c2, e1, e2, N)
flag = long_to_bytes(m).decode()
print(flag)
TSGCTF{You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!}

Survey (Cooldown)

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

TSGCTF{Thank_you_for_your_participation!}