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.
By the end you can
- Recover a private exponent from a factored modulus
- Choose an attack from the shape of n, e, and the number of ciphertexts
- Apply Fermat factorization, Wiener’s attack, and the common-modulus attack
- Explain why textbook RSA without padding enables attacks that padded RSA does not
1. Read
2. Use the tools
In the order they come up while solving. Each opens the workspace tab that runs it.
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.
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.
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.
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.
3. Try one now
Generated in your browser and checked in your browser. No account, nothing to download, and a fresh one whenever you want another.
Practice
generated here, checked here, no account and nothing to download
4. Practise on the real thing
Real picoCTF challenges that use these techniques, easiest first. 23 match in total - see the full index.
Checkpoint
Given three RSA challenges with different weaknesses, name the applicable attack for each before running anything, then verify.
Teaching note
Insist on the prediction step. A student who runs every attack until one succeeds has learned nothing about RSA; a student who says 'e is enormous, so Wiener' has learned the entire module.