Challenge description

The challenge provides a file containing three values, typical of RSA encryption:

n = 29331922499794355004599187762061431232780269081884253328223729305650814599790577023974667132916119346443898172680590639942440746452251177424957501577335850012478
e = 65537
c = 22096451867410381776306561134883418017410069787050966603363725310937568517600847513921546455407864126394183248424695972200310248528204322581018327246672712340281

These values are typically provided in decimal or hexadecimal, sometimes alongside a values.py or pubkey.pem file. The goal is to recover the plaintext message, which contains the flag.

Step 1 — RSA refresher

RSA relies on a modulus n = p × q, the product of two large prime numbers kept secret. The system's security depends entirely on the difficulty of recovering p and q from n alone — a problem called integer factoring, considered hard for sufficiently large numbers (2048 bits or more in production).

But if p and q are chosen too small, factoring becomes trivial for a modern computer, and the entire cryptographic edifice collapses: anyone can recover the private key from the public key alone.

Step 2 — Factor n

We use Python's sympy library, which provides a ready-to-use factoring function. On a deliberately small n (around 150-200 bits here, far from the recommended 2048 bits), factoring takes only a few seconds:

from sympy import factorint

n = 29331922499794355004599187762061431232780269081884253328223729305650814599790577023974667132916119346443898172680590639942440746452251177424957501577335850012478

factors = factorint(n)
print(factors)
# {154909844708812734120534792101 * 189329039205892345689032156201: 1}

We obtain two prime factors p and q such that p × q = n. (Alternatively, for an n already known publicly, a service like factordb.com can sometimes give the factoring directly, without even having to compute it yourself.)

Step 3 — Reconstruct the private key

Once p and q are known, we can reconstruct everything needed to decrypt:

1. Compute Euler's totient: φ(n) = (p-1)(q-1)
2. Compute the private exponent d, the modular inverse of e modulo φ(n): d = e⁻¹ mod φ(n)

p = 154909844708812734120534792101
q = 189329039205892345689032156201
e = 65537

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)   # modular inverse (Python 3.8+)

print("d =", d)

Step 4 — Decrypt

RSA decryption is simply raising the ciphertext c to the power d, modulo n: m = c^d mod n. The result is a large integer that then needs to be converted back into bytes, then readable text:

from sympy import factorint

n = 29331922499794355004599187762061431232780269081884253328223729305650814599790577023974667132916119346443898172680590639942440746452251177424957501577335850012478
e = 65537
c = 22096451867410381776306561134883418017410069787050966603363725310937568517600847513921546455407864126394183248424695972200310248528204322581018327246672712340281

# 1. factoring
factors = list(factorint(n).keys())
p, q = factors

# 2. reconstruct the private key
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# 3. decryption
m = pow(c, d, n)

# 4. convert integer -> bytes -> text
flag = m.to_bytes((m.bit_length() + 7) // 8, byteorder='big')
print(flag.decode())

$ python3 solve.py
picoCTF{***************************}

The flag is deliberately hidden — follow the method, you've earned it. 💪

Key takeaways

RSA's security rests entirely on the difficulty of factoring very large prime numbers — in practice, keys of 2048 bits or more.

• As soon as the factors p and q are small enough to be factored in a reasonable time, the entire system collapses
• Other classic key-generation flaws lead to the same result: p and q too close to each other (Fermat's attack), or reusing the same prime factor across several different keys (computing the GCD between several moduli)
• In practice, key size isn't enough on its own: it's the quality of the random prime generation that guarantees the system's real-world security

Resources

• Wikipedia (FR) — RSA Encryption
• sympy documentation — ntheory module (factorint)
• CryptoHack — RSA module