Challenge Overview#

Classic RSA decryption challenge where we’re given the public key parameters (n, e) and ciphertext (c), but need to factor n to find the private key.

Given Data#

n = 2144831537182691127226840733029608917028213290006813425996254255600138294915857888555028089760852947821230571957658788758912243893627426892642042247199424294789573427071703290644668266217757721636207129972073199609043937414663647879045094904418897021363777158941294486149117818217208033779367195636217363694694541
e = 65537
c = 1983234254934925761486284406677131831481570946662392531654817098945817202064275913205054573643771458003143250325225227419382435408653586301494982444166548588851767106811874491325904092340088285777126941515587285167887079578329783781806162085914505940944650957530660228135260917298087314905239242563505803779036874

Vulnerability Analysis#

The modulus n is 541 digits (approximately 1797 bits), which seems secure. However, the vulnerability is that one of the prime factors is very small.

Using Pollard’s rho factorization algorithm, we can quickly find:

• p = 12289 (only 14 bits - extremely small!)
• q = 174532633833728629443147589960908854831818153633885053787635629880392081936354291525350157845296846596243028070441760009676315720858281950739852082935912140515060088458922881491143971536964579839571660018884628497765801726313259653270819017366660999378613162905142361961845375394027832515206053839711722979469

Solution#

import math

n = 2144831537182691127226840733029608917028213290006813425996254255600138294915857888555028089760852947821230571957658788758912243893627426892642042247199424294789573427071703290644668266217757721636207129972073199609043937414663647879045094904418897021363777158941294486149117818217208033779367195636217363694694541
e = 65537
c = 1983234254934925761486284406677131831481570946662392531654817098945817202064275913205054573643771458003143250325225227419382435408653586301494982444166548588851767106811874491325904092340088285777126941515587285167887079578329783781806162085914505940944650957530660228135260917298087314905239242563505803779036874

# Pollard's rho factorization
def pollard_rho(n):
    if n % 2 == 0:
        return 2
    x, y, d = 2, 2, 1
    f = lambda x: (x * x + 1) % n
    while d == 1:
        x = f(x)
        y = f(f(y))
        d = math.gcd(abs(x - y), n)
    return d if d != n else None

# Factor n
p = pollard_rho(n)  # Returns 12289
q = n // p

# Calculate private key
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# Decrypt
m = pow(c, d, n)
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()
print(flag)  # SCSC26{sm4ll_pr1m3_1s_w34k}

That wraps up the qualification round. If anything’s unclear or you spot a better approach, hit me up. Happy hacking!