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.

Japanese:

## 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
n, p0, q0 = get_params()
n_top = n >> (1002 - add_length)
assert n_top.bit_length() == 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


### 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}