Lowkey RSA (L3AK 2025)

RSA Coppersmith small roots

Challenge overview

In this CTF challenge, we are given the following encryption script:

from Crypto.Util.number import *

def gen_primes(SIZE):
    p = random_prime(1 << (SIZE - 1), 1 << SIZE)
    while True:
        q = random_prime(1 << (SIZE - 1), 1 << SIZE)
        if p < q: 
            p, q = q, p
            if q < p < 2*q:
                break
    return p, q

nbits = 1024
flag = b"L3AK{<REDACTED>}"

R = RealField(nbits)
p, q = gen_primes(nbits//2)
N = p*q
phi = (p**4-1)*(q**4-1)
N_s = R(N**2)
N_ss = R(N**4)   
t = (2*N_ss-49*N_s + 2)/(4*N+170*N_s)

while True:
    d = randint(1, round(sqrt(t)) - 1)
    if gcd(phi-d, phi) == 1:
        break

e = inverse_mod(phi-d, phi)
c = pow(bytes_to_long(flag), e, N)
print(f"e = {e}\nN = {N}\nc = {c}")

As well as output.txt

e = 370641246943654763647982436393968410523035056803076571952063446221981054741105804986870907803130391736840420704227524827167178043545763070520011423497365360567040835216714988776285676818833967899487393611410406708467049153990487431775151667103817558875154145780446157545062795321820537740212495675608976163877567007753523774447008611976905578477758365862741282887079873779055623972564793977884741350325450634869927603664722967323341473363320613467433998603537242156610765948379449307405122629600556105209482040761323271134932553579828576227233549741862990693111061962892676568398083446001891012661453694340879845386900986024512140441823076068075531089610607812090402852586184229193699718454197060072575595570232588935191272416546819793045623275550409871218062357273309812154110783534714662063322116568964675372602159108306251453500390105034890229052958512010283429459687714879084097494098542745605324460172680461006303552579466987732938596341830436505942616479890554056163452471835707573885837976471753073413505028206370632139586750855217201926605743452826397576584492732225029497982216694648573014796836126574081158869231364821712046050068243878660143909750030922147254462228826952501087389154612318844202411291844150163167021
N = 10222014062768125922601962004686361136447658578111413896046596746110249358112354000488449664371774177977274016313103826803116662735101208575040021998413602496525815373151213550295992813258424882626853824039678993334143891154760939712139640336395595628492284893024078520796288685014103193630287988814952604029
c = 4323184196594280140760873888779221921406692838206184372853784052006066772207175604399047711017170078453742445880600303200397632746051500194774569530024097959399922254605516672962219900174336028512116159752401576376530557036245218800162889461620882177398454137759956927838320086276276377067055171421259852996

The encryption script implements an unusual RSA-like scheme where:

\[\large \phi(n) = (p^{4}-1)\cdot(q^{4}-1)\]

Recovering phi

We begin by expanding phi like so:

\[\large \begin{align} \nonumber \phi(n) &= (p^{4}-1)\cdot(q^{4}-1) \\ \nonumber \phi(n) &= N^{4}-(p^{4}+q^{4}) + 1 \end{align}\]

We rewrite $p^{4}+q^{4}$:

\[\large p^{4}+q^{4} = (p^{2}+q^{2})^{2}-2N^{2}\]

Which means:

\[\large \phi(n) = N^{4}-(p^{2}+q^{2})^{2} + 2N^{2} + 1\]

We refer to $p^{2}+q^{2}$ as the variable $u$. With $\phi(n)$ expanded, we can look at the following equation from the code:

\[\large \begin{align} \nonumber (\phi-d) \cdot e &= 1 &\mod \phi \\ \nonumber -d \cdot e &= 1 &\mod \phi \\ \nonumber d \cdot e &= -1 &\mod \phi \\ \nonumber d \cdot e +1&= 0 &\mod \phi \\ \nonumber e \cdot d + 1&= k\cdot \phi \\ \nonumber e \cdot d + 1 - k\cdot \phi &= 0 \\ \nonumber 1 - k\cdot \phi &= 0 &\mod e \\ \nonumber 1 - k\cdot (N^{4}-(p^{2}+q^{2})^{2} + 2N^{2} + 1) &= 0 &\mod e \\ \nonumber 1 - k\cdot (N^{4}-u^{2} + 2N^{2} + 1) &= 0 &\mod e \end{align}\]

With this polynomial, we can recover $k$ and $u$ using a bivariate coppersmith’s attack. We will have to know the bounds for both $k$ and $u$. Looking at $e \cdot d + 1 = k\cdot \phi$ again, we know $\phi$ and $e$ have around the same bit size, which means $d$ and $k$ will have around the same bit size. In the source code, we can see that:

t = (2*N_ss-49*N_s + 2)/(4*N+170*N_s)
d = randint(1, round(sqrt(t)) - 1)

so $k$ is bound by $t$. And since $u = (p^{2}+q^{2})$, we know $u$ is bounded by around $2N$. With all of this information, we can solve the bivariate polynomial in $k,u$ with coppersmith’s small roots:

P.<k,u> = PolynomialRing(ZZ)
f = 1 - k*(N^4 - u^2 + 2*N^2 + 1)
roots = small_roots(f.change_ring(Zmod(e)), (isqrt(t), 2*N), m=3, d=3, algorithm="resultants", lattice_reduction=flatter, verbose=True)
k,u = roots[0]

With $k$ and $u$, we recover $\phi = N^{4}-u^{2} + 2N^{2} + 1$ and $d$:

\[\large d = \frac{k\cdot \phi-1}{e}\]

And with the private key $d$ recovered, the encrypted flag $c$ can be decrypted:

print(long_to_bytes(pow(c, phi-d, N)))
# L3AK{L0wK3y_Th1S_RSA_i5_kiNda_ScuFf3D_LmA0}

Solve script

load('~/tools/coppersmith/lbc/lattice-based-cryptanalysis/lbc_toolkit/problems/small_roots.sage')
load('~/tools/coppersmith/lbc/lattice-based-cryptanalysis/lbc_toolkit/common/flatter.sage')
load('~/tools/coppersmith/lbc/lattice-based-cryptanalysis/lbc_toolkit/common/systems_solvers.sage')

from Crypto.Util.number import inverse, long_to_bytes

e = 370641246943654763647982436393968410523035056803076571952063446221981054741105804986870907803130391736840420704227524827167178043545763070520011423497365360567040835216714988776285676818833967899487393611410406708467049153990487431775151667103817558875154145780446157545062795321820537740212495675608976163877567007753523774447008611976905578477758365862741282887079873779055623972564793977884741350325450634869927603664722967323341473363320613467433998603537242156610765948379449307405122629600556105209482040761323271134932553579828576227233549741862990693111061962892676568398083446001891012661453694340879845386900986024512140441823076068075531089610607812090402852586184229193699718454197060072575595570232588935191272416546819793045623275550409871218062357273309812154110783534714662063322116568964675372602159108306251453500390105034890229052958512010283429459687714879084097494098542745605324460172680461006303552579466987732938596341830436505942616479890554056163452471835707573885837976471753073413505028206370632139586750855217201926605743452826397576584492732225029497982216694648573014796836126574081158869231364821712046050068243878660143909750030922147254462228826952501087389154612318844202411291844150163167021
N = 10222014062768125922601962004686361136447658578111413896046596746110249358112354000488449664371774177977274016313103826803116662735101208575040021998413602496525815373151213550295992813258424882626853824039678993334143891154760939712139640336395595628492284893024078520796288685014103193630287988814952604029
c = 4323184196594280140760873888779221921406692838206184372853784052006066772207175604399047711017170078453742445880600303200397632746051500194774569530024097959399922254605516672962219900174336028512116159752401576376530557036245218800162889461620882177398454137759956927838320086276276377067055171421259852996
R = RealField(1024)

N_s = R(N**2)
N_ss = R(N**4)   
t = Integer((2*N_ss-49*N_s + 2)/(4*N+170*N_s))

P.<k,u> = PolynomialRing(ZZ)
f = 1 - k*(N^4 - u^2 + 2*N^2 + 1)

roots = small_roots(f.change_ring(Zmod(e)), (isqrt(t), 2*N), m=3, d=3, algorithm="resultants", lattice_reduction=flatter, verbose=True)
k,u = roots[0]
k,u = ZZ(k),ZZ(u)
phi = N^4 - u^2 + 2*N^2 + 1
d = (k*phi - 1) // e
assert e*d+1 == k*phi

print(long_to_bytes(pow(c, phi-d, N)))
# L3AK{L0wK3y_Th1S_RSA_i5_kiNda_ScuFf3D_LmA0}