FireShell CTF 2019 Writeup

この大会は2019/1/27 1:00(JST)～2019/1/28 1:00(JST)に開催されました。
今回もチームで参戦。結果は 708点で570チーム中45位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome (RECON)

Rulesのページにフラグが書いてある。

F#{w3lc0m3_gUyS!!!!!FIr35h#L_ctF_@)!(}

Biggars (CRYPTO)

e, N, Cが与えられている。明らかにRSA暗号。
Nが非常に大きいため、e乗根をとって復号してみようとしたが、ダメだった。
試しにnを小さい素数で割っていくと多くの素数が出てくる。
Multi-Prime RSAの問題のようなので、その復号方式で復号する。

from Crypto.Util.number import *
import gmpy

def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)

    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * gmpy.invert(p, n_i) * p
    return sum % prod

with open('RkFLRUZMQUc.txt', 'r') as f:
    lines = f.readlines()

e = int(lines[0].strip().split(' = ')[1])
N = int(lines[1].strip().split(' = ')[1])
C = int(lines[2].strip().split(' = ')[1])

primes = []
for i in range(1, 300):
    if isPrime(i):
        primes.append(i)

divisors = {}
n = N
i = 0
while True:
    if n % primes[i] != 0:
        i += 1
    else:
        if primes[i] in divisors:
            divisors[primes[i]] += 1
        else:
            divisors[primes[i]] = 1
        n = n / primes[i]
    if i == len(primes):
        break

n_ary = []
a_ary = []
for p in divisors:
    k = divisors[p]
    pk = p ** k
    phi = pk * (p-1)/p
    d = gmpy.invert(e, phi)
    mk = pow(C, d, pk)
    n_ary.append(pk)
    a_ary.append(mk)

m = chinese_remainder(n_ary, a_ary)
flag = long_to_bytes(m)
print flag

F#{b1g_m0d_1s_unbr34k4bl3_4m_1_r1gh7?}