Leaky RSA - ASCIS CTF 2022

August 18, 2025 - 6 mins read

Intro

This is a challenge from ASCIS CTF 2022 I upsolved using cuso when I was learning the coppersmith method.

Source code

from secret import flag

Kbits1 = 120
Kbits2 = 493

p = random_prime(2^512-1, false, 2^511)
q = random_prime(2^512-1, false, 2^511)
N = p*q
e = 0x10001

# Wait this is illegal
Pdigits = p.digits(2)
leaky_p = [0]*19 + Pdigits[19:Kbits1] + [0]*19 + Pdigits[Kbits1+19:Kbits2]
# leaks 19 -> kbits1 lsbs , then kbits1+19 -> kbits2 msbs
# f(x,y,z) = x + (digists from 19 to kbits1)* 2 ^ 19 + y ^ 2^kbit    s1 + (sum of the digits from kbits1+19 to kbits2) * 2 ^ (kbits1 + 19) + z *  2 ^ (kbits2)

c = pow(flag, e, N)
print(f"(c, e, N) = {(c, e, N)}")
print(f"leaky = {leaky_p}")

# (c, e, N) = (26332525917536404445261335188023824835582728456010807789427648382546117992477286201354477933620634042162778383500347554403856479653121560047163571802966352911016989944196656213695292273900862199180497043773236377160608017101154863030724519304212930989627167943539496731959903689581119612196554873637719776156, 65537, 107953240319236322637058433940161528510672490103418517617520324178241611238072198345853818249768509790971608169523056348162590719063088182552103689228188347112141257514135750575118448199789749158885349374251834100136760987321248910344201579746268207678856824451563937881565576119683013793260110227648499602781)
# leaky = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]

Solution

from Crypto.Util.number import *
import cuso
from sage.all import *
bits1 = 120
Kbits2 = 493

(c, e, N) = (26332525917536404445261335188023824835582728456010807789427648382546117992477286201354477933620634042162778383500347554403856479653121560047163571802966352911016989944196656213695292273900862199180497043773236377160608017101154863030724519304212930989627167943539496731959903689581119612196554873637719776156, 65537, 107953240319236322637058433940161528510672490103418517617520324178241611238072198345853818249768509790971608169523056348162590719063088182552103689228188347112141257514135750575118448199789749158885349374251834100136760987321248910344201579746268207678856824451563937881565576119683013793260110227648499602781)
leaky = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]

Kbits1 = 120
Kbits2 = 493


leaky_p = leaky

x,y,z = var('x' , 'y' , 'z')

f = x +\
 (2**19)*sum([2**i * leaky_p[19+i] for i in range(Kbits1-19)]) +\
 (2**Kbits1)*y +\
 (2**(Kbits1+19))*sum([2**i * leaky_p[19+Kbits1+i] for i in range(Kbits2-(Kbits1+19))]) + \
 (2**(Kbits2))*z


relations = [f]
bounds = {
    x: (0, 2 ** 19),
    y: (0, 2 ** 19),
    z: (0, 2 ** (512 - Kbits2))
}

roots = cuso.find_small_roots(relations, bounds, modulus = "p",
    modulus_multiple = N,
    modulus_lower_bound = 2**511,
    modulus_upper_bound = 2**512-1
)

print(f"roots = {roots}")

p = roots[0]["p"]
q = N // p
flag = pow(c, inverse_mod(e, (p-1)*(q-1)), N)
print(f"flag = {long_to_bytes(flag)}")

Flag : ASCIS{C0nGratulation_s0_Y0u_D0_kNow_about_H3rm4nN_M4y_730EF6498A3B0441B43400367B788817413F5A65A3900E2976D071232A2FC827}