RSA decryption and attack runner
Paste n, e, and c and let ctfpal choose the attack: trial division, Fermat, Pollard’s rho, Wiener, common modulus, or Hastad broadcast. Arbitrary-precision, in-browser.
Open in ctfpalEvery CTF RSA challenge is a question about which parameter was chosen badly. Textbook RSA is not breakable; the challenges are breakable because p and q are close, or e is 3, or d is small, or the same message went out under two moduli. Reading the parameters tells you which attack applies before you run anything.
The decision tree
| What you see | Attack |
|---|---|
n under ~256 bits | Just factor it - trial division or Pollard’s rho |
p and q visibly close in size | Fermat factorization |
e very large, near n | Wiener’s attack - d is small |
e = 3 and a small message | Integer cube root of c, no factoring needed |
e = 3 with 3+ ciphertexts, different n | Hastad broadcast |
Same n, two different e | Common modulus |
| Two moduli sharing a factor | GCD of the two moduli - instant |
The free win: shared factors
If a challenge hands you two moduli, compute gcd(n1, n2) before anything else. If two keys were generated with a broken random number generator they may share a prime, and the GCD hands you that prime in microseconds regardless of key size. This is not a toy - it has been found repeatedly in real internet-wide TLS surveys.
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi) # Python 3.8+ modular inverse
m = pow(c, d, n)
print(m.to_bytes((m.bit_length() + 7) // 8, 'big'))Common questions
- How large an n can be factored in a browser?
- Pollard’s rho comfortably handles moduli with a small factor regardless of total size, and general factoring is practical to roughly 60-70 digits. Beyond that, a CTF challenge intends a structural weakness rather than raw factoring - find the weakness.
Part of a module
5. RSA and the parameters that break it
Work the RSA decision tree - small modulus, close primes, tiny exponent, shared modulus - and learn to read a key for its weakness.
Practise on real challenges
Go deeper
- The RSA attack decision treeRSA challenges are not solved by knowing every attack - they are solved by reading the parameters and picking the one attack that matches. A decision tree from e and n to Fermat, Wiener, Hastad, common modulus, and the oracle attacks.
Related tools
Fermat factorization for close RSA primes
Factor an RSA modulus whose primes were generated too close together. Fermat’s method finds them in a handful of steps where trial division never would.
Wiener’s attack on small RSA private exponents
Recover a small private exponent d from n and e using continued fractions. Works whenever d is below roughly the fourth root of n.
Hastad broadcast attack on RSA
Recover a message sent to several recipients under a small public exponent, using the Chinese remainder theorem and an exact integer root.
RSA common modulus attack
Recover a plaintext encrypted twice under the same modulus with two coprime exponents, using the extended Euclidean algorithm. No factoring needed.