We participated in N1CTF as ./Vespiary and took 7th place last week. I solved 'checkin (crypto)' challenge so write its solution.

I write the solution in English because N1CTF admin reqeusted top 10 teams to submit their writeup.

The winning teams (including top 10 teams) MUST provide detailed writeup within 24h after the contest ends.

From: https://ctf2021.nu1l.com/

Normally, I write CTF solutions in Japanese, so if you want to read this article in Japanese, feel free to ask me (via Twitter: @Xornet_Euphoria).

Japanese:

いつもなら日本語でWriteup書いてるんですけど、上記の通り今回は上位10チームに対してWriteupを書くよう言われているので英語で書きました。もし、日本語で書いて欲しかったら書きますのでTwitterで@Xornet_Euphoriaまで気軽にリプを飛ばしてください(フォロー外へのDMは解放してないです)。

Problem §

We were given the following script.

from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p*q
x = 2021*p+1120*q
h = (inverse(x,n)+x)%n
e = 65537
c = pow(bytes_to_long(flag), e, n)

print('n =', n)
print('c =', c)
print('h =', h)
print('p0 =', p >> 490)

# n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
# c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
# h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
# p0 = 4055618

It looks like a normal RSA challenge with some hints(h and p0):

$$ \begin{aligned} x &\coloneqq 2021p + 1120q \cr h &\coloneqq (\frac 1x + x) \mod n \cr p0 &\coloneqq p \gg 490, \end{aligned} $$

where $\gg$ means right bit shift.

Solution §

I know 22 leading bits of $p$, so some leading bits of $q$ are known too. In my calculation and experiments, 21 leading bits of $q$ are recovered. Using these known bits, I rewrote $p,q$ as follows.

$$ \begin{aligned} p &= p_0 \times 2^{490} + p_1 \cr q &= q_0 \times 2^{491} + q_1 \end{aligned} $$

And $x$.

$$ \begin{aligned} x &= 2021p + 1120q = (2021p_0 \times 2^{490} + 1120q_0 \times 2^{491}) + (2021p_1 + 1120q_1) \cr &= x_0 + x_1 \end{aligned} $$

Now, $x_0$ is known and $x_1$ is unknown. The latter size is about $2^{490} \times 2^{11} + 2^{491} \times 2^{10} \approx 2^{502} \lt N^{1/2}$

From the definition of $h$, $x$ is one of the roots of $f(x) = x^2 - xh + 1 \mod n$. By substituting $x$ to $x_0 + x_1$, a polynomial that has $x_1$ as a root appears and its degree is 2. So we can use Coppersmith's Attack!!

I used Sagemath's implementation with X=2^505 and epsilon=1/75. It took about 1 hour.

Now, we get $x = x_0 + x_1 = 2021p + 1120q$ and already know $2021p \times 1120q = 2021\times 1120N$. So solving the quadratic equation $(y - 2021p)(y - 1120q)=y^2 - xy + 2021\times 1120 N = 0$ for $y$, we can get $2021p,1120q$ (and $p,q$ of course). After that, the flag can be decrypted.

Code §

Calculating leading bits of q §

This code includes unused parts. They are for experiments.

def get_params():
    n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
    p0 = 4055618  # 1111011110001001000010
    # q0 = 3006358  # 1011011101111110010110 <- 下2桁の正確性が無い
    q0 = 0b101101110111111001010

    return n, p0, q0


def exploit():
    n, p0, _ = get_params()
    n_top = n >> 1002
    assert n_top.bit_length() == 22
    for q0 in range(2**21, 2**22):
        top = (p0*q0) >> 22
        if n_top == top:
            print(q0)


# for experiments
def add_bits(add_length):
    n, p0, q0 = get_params()
    n_top = n >> (1002 - add_length)
    assert n_top.bit_length() == 22 + add_length
    for add_b in range(2**add_length):
        p_top = (p0 << add_length) + add_b
        for q0 in range(2**(21+add_length), 2**(22+add_length)):
            top = (p_top*q0) >> (22 + add_length)
            if n_top == top:
                # print(f"{p_top=} : {bin(p_top)}")
                print(f"   {q0=} : {bin(q0)}")



if __name__ == "__main__":
    exploit()
    # q0 = 3006358
    # add_length = 5
    # add_bits(add_length)

Coppersmith's Attack(Sagemath) §

def get_params():
    n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
    h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
    p0 = 4055618
    q0 = 0b101101110111111001010

    return n, h, p0, q0


def exploit():
    n,h,p0,q0 = get_params()
    R = Zmod(n)
    PR.<x> = PolynomialRing(R)
    _x = 2021*p0*2^490 + 1120*q0*2^491 + x
    f = (_x^2 - _x*h + 1).monic()
    roots = f.small_roots(X=2^505, epsilon=1/75)
    print(roots)


if __name__ == "__main__":
    exploit()

Decryption §

xcrypto is my crypto library. xcrypto.rsa.p_plus_q_to_pq calculates $p,q$ from $N=pq, p+q$. In this challenge, I used it to calculate $2021p, 1120q$ from $2021\times 1120 N, x$.

from xcrypto.rsa import dec, p_plus_q_to_pq, dec_pq
from Crypto.Util.number import long_to_bytes


def get_params():
    _x = 7279473437564993427256268527891542563557232159626049883951364173102121134158423609775502464752174435483615142675582269470774951285125088232851515513237
    n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
    c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
    p0 = 4055618  # 1111011110001001000010
    # q0 = 3006358  # 1011011101111110010110 <- 下2桁の正確性が無い
    q0 = 0b101101110111111001010

    return (_x, n, c, p0, q0)


def decrypt():
    _x, n, c, p0, q0 = get_params()
    p0 = p0 * 2**490
    q0 = q0 * 2**491
    print(p0.bit_length())
    print(q0.bit_length())
    x = 2021 * p0 + 1120 * q0 + _x

    _n = 2021*1120*n
    p, q = p_plus_q_to_pq(_n, x)
    if p % 2021 == 0:
        p //= 2021
        q //= 1120
    elif p % 1120 == 0:
        p //= 1120
        q //= 2021

    assert p*q == n

    m = dec_pq(c, p, q, 65537)
    print(long_to_bytes(m))



if __name__ == "__main__":
    decrypt()

Flag §

n1ctf{093fd4c4-5cc9-427e-98ef-5a04914c8b4e}