CODEGATE 2022 Writeup

Mon Feb 28 2022

2/26-27 に開催していた CODEGATE 2022 にチーム WreckTheLine で参加しました。結果は General division で 9th/141 でした。

Crypto 問にずっと挑戦してましたが、 Happy S-box がずっと解けないまま終わってしまった… SBox の扱いが全然わからない。 今回は writeup を提出しているのでこのブログではそれをそのまま貼っつけます。



10 solves

Let UU be UPPER, which is generated randomly once. menu1 generated ll such that U+lU + l is a prime. menu2 generated RSA's public key n=pqn = pq and ee where p=U+menu1()p = U + \mathrm{menu1()} and encryption of the flag cc by their key.

To decrypt a given encryption, we should find pp. To do this, we found UU first and ll such that p=U+lp = U + l then.

find U

Let us consider a prime PP. When UrmodPU \equiv r \mod P, the collected ll always satisfies lrmodPl \ne -r \mod P because otherwise U+l0modPU + l \equiv 0 \mod P, which means U+lU + l is not a prime. We can collect many ll, so we can know UmodPU \mod P when PP is relatively small (like < 1000). This is true to any prime PP. Therefore we can find UU using CRT. Note that it's also true that U0mod2216U \equiv 0 \mod 2^{216}

from Crypto.Util.number import long_to_bytes
from pwn import remote
from tqdm import tqdm

BITS = 512

io = remote("", 9001)
io.sendlineafter(b"> ", b"2")
io.recvuntil(b"n : ")
n = int(io.recvline())
io.recvuntil(b"c : ")
c = int(io.recvline())

lowers = []
for _ in tqdm(range(200)):
    io.sendlineafter(b"> ", b"1")
    io.sendlineafter(b"> ", b"10")
    for _ in range(10):

primes = prime_range(1000)

a_list = []
b_list = []
for prime in primes:
    s = set([lower % prime for lower in lowers])
    r = set(range(prime)) - s
    if len(r) == 1:
        a_list.append(prime - next(iter(r)))
b_list.append(1 << LOWER_BITS)
U = crt(a_list, b_list)

find p

Next we'll find pp where p=U+lp = U + l and ll is unknown. ll is much smaller than pp (ln1/4l \ll n^{1/4}). Therefore we can apply coppersmith's method to find small ll from nn. After finding ll, we can decrypt cc easily as a usual RSA.

PR.<x> = PolynomialRing(Zmod(n))
f = U + x
# The parameter needs tuning because p is not always p < n^0.476.
l = f.small_roots(beta=0.476, epsilon=0.015)[0]
p = U + l
q = n // p
phi = (p - 1) * (q - 1)
d = int(pow(e, -1, phi))
print(long_to_bytes(int(pow(c, d, n))))