Phony (CryptoCTF 2025)

RSA Coppersmith small roots

Challenge overview

In this CTF challenge we are given the following encryption script, as well as a host and port to connect to.

#!/usr/bin/env python3

import sys, os
from Crypto.Util.number import *
from flag import flag

def die(*args):
        pr(*args)
        quit()

def pr(*args):
        s = " ".join(map(str, args))
        sys.stdout.write(s + "\n")
        sys.stdout.flush()

def sc():
        return sys.stdin.buffer.readline()

def keygen(nbit):
        p, q, r = [getPrime(nbit + (nbit >> 3) * _) for _ in range(3)]
        return p, q, r

def main():
        border = "┃"
        pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
        pr(border, " Welcome to the Phoney crypto-system task, a nice cryptosystem   ", border)
        pr(border, " that's so good, it's theoretically unbreakable because it exists", border)
        pr(border, " only in the realm of imagination!! Try the get the long flag :-)", border)
        pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
        global flag
        m = bytes_to_long(os.urandom(len(flag)) + flag + os.urandom(len(flag)))
        nbit = 512
        p, q, r = keygen(nbit)
        n, s, e = p * q * r, inverse(p, q * r) + p, 1234567891
        while True:
                pr(f"{border} Options: \n{border}\t[E]ncrypt the flag! \n{border}\t[P]ublic information \n{border}\t[Q]uit")
                ans = sc().decode().strip().lower()
                if ans == 'e':
                        assert m < n
                        c = pow(m, e, n)
                        pr(f'{c = }')
                elif ans == 'p':
                        pr(border, f'{n = }')
                        pr(border, f'{s = }')
                        pr(border, f'{q % p = }')
                elif ans == 'q':
                        die(border, "Quitting...")
                else:
                        die(border, "Bye...")

if __name__ == '__main__':
        main()  

By connecting to the host, we are given some parameters:

c = 6869860867050333958899459281380169365224860725191141490075681906921285491146868469402924407937586752602837270188417362698698432410645612767176659341773981474956667075905162196530581138090668035380527629936507938083351225221764373058697174991005915834617167971014590329567873587411280896708327508300000380436210779160971169732950060789651351851118197920235412555409856566771235934800199725530146544692622204638420681024709553733579632544440316928742635345488552585477308018879605401386083632773124260425537471704361270484
n = 7593182903146811406435471791518649687495414242882290735012260860376531253817852809889056324416625293328336902814033416817885049198231261658575996571173050362548418752191140228401121790728216545279595354039266794764391641456534625225792086731913555135968347381141768054313651417425174249608933255246607612139992917832326481150388513002349951254458456726813282961483706607801158152631829134593355178831985262912282527824542674089294563518520637393822269227734326318416000202832970945614787755290083730313250861320246580607
s = 408090971571018322541813922483180473677053198626231795703512988713148003287852666320118777537915800591251623270019431071055073761901852807133561327188793849601691060300945653929089492414728804506355613740171489217849409547504090029963007153700898456243760945317209450011285770935513349812984386394905043517448605752738202406721452527001589670740463592746693105274845
q % p = 9306850992856150821106831016751373801819672057267955676046215879463293889689158245940844448621629363248578706865630660666356930840954191009944889404229867

Recovering the prime factors

The service leaks three pieces of information besides the ciphertext $c$:

the composite modulus $n = p \cdot q \cdot r$
the integer $s = p + p^{-1}_{qr}$
the residue $r \equiv q \bmod p$

Because $s = p + p^{-1}_{\;qr}$ we have

\[\large \begin{align} \nonumber p^{-1}_{\;qr} &= s-p \\ \nonumber (s-p)\,p &\equiv 1\mod{qr} \end{align}\]

Multiplying by $p$ gives a relation that is zero modulo $n$:

\[\large \begin{align} \nonumber p\bigl((s-p)p-1\bigr) &\equiv 0 \mod{n} \\ \nonumber f(p)=p^{3}-s\,p^{2}+p &\equiv 0\mod{n} \end{align}\]

The prime $p$ is only $512$ bits, while $n$ is about $1728$ bits, so $p$ is a small root of the monic cubic

\[\large f(x)=x^{3}-s\,x^{2}+x\mod{n}\]

x = var('x')
f = x**3 - s*x**2 + x
bounds = {x: (0, 1 << 520)}

roots = cuso.find_small_roots(
    relations=[f],         
    bounds=bounds,
    modulus=n,               
)
assert roots, "no root found"

p = int(roots[0][x])
print(f"p = {p:#x}")
# p = 0xda7a510e37d4c24fbed858e74371c3b199b7163f04e87be5cc36345419443a48ae80c16a4634b2754b543326e30ac45d35e13a20274a94bd662ea96f7d7121b9

Once $p$ is known, the extra leak $q\bmod p$ lets us write

\[\large \begin{align} \nonumber q &= p \cdot k + r \\ \nonumber r &= q \bmod p \end{align}\]

Here $k < 2^{64}$ because $q$ is $576$ bits, only $64$ bits longer than $p$. Substituting into $n$ shows that the linear polynomial

\[\large g(k)=p\,k+r\equiv 0 \mod{q}\]

This can also be easily solved using cuso:

f = p * x + q_mod_p
bounds = {x: (0, 1 << 64)}

roots = cuso.find_small_roots(
    relations        = [f],
    bounds           = bounds,
    modulus          = "q",    
    modulus_multiple = n/p,      
    modulus_lower_bound = 1 << 560  
)
assert roots, "no root found"

q  = int(roots[0]["q"]) 

From here, its just standard RSA decryption.

q  = int(roots[0]["q"]) 
r = n/(p*q)
e   = 1234567891
phi = (p-1)*(q-1)*(r-1)
d   = pow(e, -1, phi)
print(bytes.fromhex(f"{pow(c,d,n):x}"))

b'ax\x90\xda\xea\xefa\x9f\xce\xb8&n\x85~\xf4\xbe\xef|\x9eF\xc4x\xa039\xf1\x8a=\xdf\x10\x17\x96\x97\xe3h@\xb6\xae\xea\xf3\x84K\x03\x9a\xb4\xe6i\xd8\x04CCTF{c0UlD_b3_ReCoVEr3d_v!4_Coppersmiths_m3ThOd?}_(\x9a\x9e\x9b,\xbb\xde\x15\xf3\x0fP\x1e\xbc\xd5C\x1au\x1b3d\x18\x15X$^\x83\x17\xbd\xa3&\xb9\xa7H\xe0\x19Y\xf7\x8f0`\xd6J`\xf7\xd22\xfb\xd8'

So the flag is CCTF{c0UlD_b3_ReCoVEr3d_v!4_Coppersmiths_m3ThOd?}

Solve script

import cuso

c = 6869860867050333958899459281380169365224860725191141490075681906921285491146868469402924407937586752602837270188417362698698432410645612767176659341773981474956667075905162196530581138090668035380527629936507938083351225221764373058697174991005915834617167971014590329567873587411280896708327508300000380436210779160971169732950060789651351851118197920235412555409856566771235934800199725530146544692622204638420681024709553733579632544440316928742635345488552585477308018879605401386083632773124260425537471704361270484
n = 7593182903146811406435471791518649687495414242882290735012260860376531253817852809889056324416625293328336902814033416817885049198231261658575996571173050362548418752191140228401121790728216545279595354039266794764391641456534625225792086731913555135968347381141768054313651417425174249608933255246607612139992917832326481150388513002349951254458456726813282961483706607801158152631829134593355178831985262912282527824542674089294563518520637393822269227734326318416000202832970945614787755290083730313250861320246580607
s = 408090971571018322541813922483180473677053198626231795703512988713148003287852666320118777537915800591251623270019431071055073761901852807133561327188793849601691060300945653929089492414728804506355613740171489217849409547504090029963007153700898456243760945317209450011285770935513349812984386394905043517448605752738202406721452527001589670740463592746693105274845
q_mod_p = 9306850992856150821106831016751373801819672057267955676046215879463293889689158245940844448621629363248578706865630660666356930840954191009944889404229867

x = var('x')
f = x**3 - s*x**2 + x
bounds = {x: (0, 1 << 520)}

roots = cuso.find_small_roots(
    relations=[f],         
    bounds=bounds,
    modulus=n,               
)
assert roots, "no root found"

p = int(roots[0][x])
print(f"p = {p:#x}")

f = p * x + q_mod_p
bounds = {x: (0, 1 << 64)}

roots = cuso.find_small_roots(
    relations        = [f],
    bounds           = bounds,
    modulus          = "q",    
    modulus_multiple = n/p,      
    modulus_lower_bound = 1 << 560  
)
assert roots, "no root found"

q  = int(roots[0]["q"]) 
r = n/(p*q)
e   = 1234567891
phi = (p-1)*(q-1)*(r-1)
d   = pow(e, -1, phi)
print(bytes.fromhex(f"{pow(c,d,n):x}"))