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

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

Crypto

PrimeGenerator

10 solves

Let $U$ be UPPER, which is generated randomly once. menu1 generated $l$ such that $U + l$ is a prime. menu2 generated RSA’s public key $n = pq$ and $e$ where $p = U + \mathrm{menu1()}$ and encryption of the flag $c$ by their key.

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

find U

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

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


BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS

io = remote("15.164.247.87", 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):
        lowers.append(int(io.recvline()))

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(prime)
a_list.append(0)
b_list.append(1 << LOWER_BITS)
U = crt(a_list, b_list)

find p

Next we’ll find $p$ where $p = U + l$ and $l$ is unknown. $l$ is much smaller than $p$ ($l \ll n^{1/4}$). Therefore we can apply coppersmith’s method to find small $l$ from $n$. After finding $l$, we can decrypt $c$ 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))))

codegate2022{ef9fdfaae10f7afe84bea52307966a9e}