SECCON CTF 2022 Quals Writeup

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

pqpq (crypto)

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

・p, q, r: 512ビット素数
・n = p * q * e
・e = 2 * 65537
・padding: nのビット長を8で割った値からflagの長さを引いた数の長さのランダム文字列
・m = bytes_to_long(padding + flag)
・c1p = pow(p, e, n)
・c1q = pow(q, e, n)
・cm = pow(m, e, n)
・c1 = (c1p - c1q) % n
・c2 = pow(p - q, e, n)
・e, n, c1, c2, cmを出力

式を変形してみる。

c1 = p^e - q^e mod n
c2 = (p-q)^e mod n

e2 = e // 2とする。
c2 = pow((p - q) ** 2, e2, n) = pow(p**2 + q**2, e2, n)
   = pow(p**2, e2, n) + pow(q**2, e2, n)
   = (pow(p, e, n) + pow(q, e, n)) % n
c1 = (pow(p, e, n) - pow(q, e, n)) % n

c1とc2からpow(p, e, n)、pow(q, e, n)を計算できる。

pow(p, e, n) = (c2 + c1) % n
pow(q, e, n) = (c2 - c1) % n

このことから以下により、p, q, rを求める。

p = GCD(pow(p, e, n), n)
q = GCD(pow(q, e, n), n)
r = n // (p * q)

次にm**2を通常のRSA暗号の復号方法で復号する。その後は、Tonelli-Shanks Algorithmを使って、p, q, rについて、平方剰余を求め、中国人剰余定理により復号する。

#!/usr/bin/env python3
from Crypto.Util.number import *
from sympy.ntheory.modular import crt
from re import *

def legendre(a, p):
    return pow(a, (p - 1) // 2, p)

def tonelli_shanks(a, p):
    if legendre(a, p) != 1:
        raise Exception("not a square (mod p)")

    q = p - 1
    s = 0
    while q % 2 == 0:
        q >>= 1
        s += 1

    for z in range(2, p):
        if legendre(z, p) == p - 1:
            break

    m = s
    c = pow(z, q, p)
    t = pow(a, q, p)
    r = pow(a, (q + 1) // 2, p)

    t2 = 0
    while True:
        if t == 0: return 0
        if t == 1: return r
        t2 = (t * t) % p
        for i in range(1, m):
            if t2 % p == 1:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        m = i
        c = (b * b) % p
        t = (t * c) % p
        r = (r * b) % p

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

e = int(params[0].split(' ')[-1])
n = int(params[1].split(' ')[-1])
c1 = int(params[2].split(' ')[-1])
c2 = int(params[3].split(' ')[-1])
cm = int(params[4].split(' ')[-1])

cp = (c2 + c1) % n
cq = (c2 - c1) % n

p = GCD(cp, n)
q = GCD(cq, n)
r = n // (p * q)
assert p * q * r

phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(e // 2, phi)
m2 = pow(cm, d, n)

ms = []
for i in [p, q, r]:
    m = tonelli_shanks(m2 % i, i)
    ms.append([m, i - m])

for mp in ms[0]:
    for mq in ms[1]:
        for mr in ms[2]:
            m = int(crt([p, q, r], [mp, mq, mr])[0])
            flag = long_to_bytes(m)
            if b'SECCON{' in flag:
                pattern = b'(SECCON{.+})'
                flag = search(pattern, flag).group(1).decode()
                print(flag)

SECCON{being_able_to_s0lve_this_1s_great!}