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
- Read the parameters straight out of a PEM or DER key rather than out of the challenge text
- Explain why textbook RSA without padding enables attacks that padded RSA does not
1. Read
The RSA attack decision tree
RSA 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, Håstad, common modulus, and the oracle attacks.
Side channels: when how long it took is the answer
Timing attacks against string comparison and modular exponentiation, error messages that distinguish too much, size and cache oracles, and the statistical discipline that separates a real signal from network noise.
2. Use the tools
In the order they come up while solving. Read what each one does, or go straight to 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.
Open it in the workspace - 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.
Open it in the workspace - 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.
Open it in the workspace - 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.
Open it in the workspace - 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.
Open it in the workspace - Modular arithmetic and number theory toolkit
Modular inverse, Chinese remainder theorem, Tonelli-Shanks square roots, Jacobi symbols, and integer nth roots - arbitrary precision, in the browser.
Open it in the workspace - ASN.1 and X.509 certificate parser
Decode DER and PEM structures, walk the ASN.1 tree, and read certificate fields, extensions, and embedded public keys.
Open it in the workspace
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.
4. Practise on the real thing
Real picoCTF challenges that use these techniques, easiest first. 32 match in total - see the full index.
Common mistakes
The wrong turns this topic reliably produces. Written as the mistake rather than the rule, because the rule is easy to agree with and easy to walk straight past.
- Running every attack until one succeeds. The parameters name the attack, and a student who cannot say which one before running it has not learned the module.
- Trying to factor a 2048-bit modulus. If n is that size the weakness is elsewhere - a small e, a shared factor with another key, or a padding oracle.
- Forgetting that e and d are symmetric in the maths but not in the attacks: a huge e is the signature of a small d, which is Wiener's whole premise.
- Converting the recovered integer to a decimal string. The plaintext is bytes: render it big-endian, drop the leading zeros, and a result that looked like a failed attack usually turns out to be the flag.
- Taking an integer root with floating point when e is tiny. The answer is exact only if raising it back reproduces the ciphertext, and without that check an off-by-one root is indistinguishable from m having wrapped n.
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.
Go deeper
The lessons above are written to get you through a challenge. These go after the subject instead. Each one opens our notes on that chapter - what it argues, what to take from it and where it stops - so this is somewhere to read now rather than a book to buy first. Nothing here is affiliate-linked or sold by us.
Chapter 5, Cryptography
Designing Secure Software - Loren Kohnfelder
Why padding exists at all, which is the single fact that turns most of these attacks from tricks into consequences.
Chapter 7, Network Protocol Security
Attacking Network Protocols - James Forshaw
Public-key exchange as deployed, including what a protocol has to get right around the maths.
Every book the curriculum cites has a page in the library.