PicoCTF Mind Your Ps and Qs Writeup — Factor a Weak RSA Modulus

#ctf #security #cryptography

The challenge provides an RSA modulus n, a public exponent e, and a ciphertext c. Since n is deliberately chosen small (and therefore quickly factorable), we recover its two prime factors p and q, which lets us reconstruct the private key and decrypt the message.

Platform: picoGym
Category: Cryptography
Points: 300 pts
Difficulty: Intermediate
Technique: RSA, factoring a weak modulus

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:

Compute Euler's totient: φ(n) = (p-1)(q-1)
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{***************************}

🚩 picoCTF{ flag intentionally hidden }

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

Originally published on CTFdojo — join the CTFdojo Discord to discuss writeups and get notified about new ones.

DEV Community