PicoCTF 2024 — miniRSA [Cryptography]

Challenge Overview

**Category:** Cryptography | **Points:** 300

Given: public key with e = 3, a large n, and ciphertext c. No padding.

The Vulnerability

Standard RSA: c = m^e mod n

If e = 3 and m^3 < n, the modular reduction never activates:

c = m^3  (plain integer arithmetic)
m = ∛c

Just take the integer cube root.

Solution

from gmpy2 import iroot

c = 2205316413931134031074603746928247799030155221252519872650082379...

m, exact = iroot(c, 3)

if exact:
    print(bytes.fromhex(hex(m)[2:]).decode())
else:
    print("Not exact — try Coppersmith or Hastad")

picoCTF{e_sh0uldnt_b3_sma11_9c3a4b2d}

Why This Breaks RSA

RSA's security depends on the hardness of factoring n. But this attack doesn't factor anything — it exploits that the encryption itself is just integer math when:

1. e is tiny (3, 5, 17)

2. m^e < n (no modular wrap)

3. No OAEP/PKCS1v1.5 padding

Defenses

• Use e = 65537 (standard, large enough)
• Always apply OAEP padding
• Never encrypt the same message to multiple recipients with small e (Håstad broadcast attack)

*gmpy2.iroot(n, k) returns (root, is_exact) — the boolean check is important: if not exact, the message wrapped around mod n and you need a different approach.*