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
    UPPER_BITS = 296
    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))))