RSA and the parameters that break it

Before the session

• Nothing to install. Students need a browser and https://ctfpal.com. Confirm the room can reach it once; after that it works offline.
• Read the lesson yourself first - about 14 minutes.
• Have one worked example ready to paste. The classroom link builder on the instructor page turns it into a URL that opens preloaded.

Objectives

Written as things a student can do afterwards, so they can be assessed rather than asserted.

1. Recover a private exponent from a factored modulus
2. Choose an attack from the shape of n, e, and the number of ciphertexts
3. Apply Fermat factorization, Wiener's attack, and the common-modulus attack
4. Read the parameters straight out of a PEM or DER key rather than out of the challenge text
5. Explain why textbook RSA without padding enables attacks that padded RSA does not

Running order (120 min)

Tools used

• 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.https://ctfpal.com/?tool=rsa-decrypt
• 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.https://ctfpal.com/?tool=fermat-factorization
• 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.https://ctfpal.com/?tool=wiener-attack
• 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.https://ctfpal.com/?tool=common-modulus-attack
• 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.https://ctfpal.com/?tool=hastad-broadcast-attack
• 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.https://ctfpal.com/?tool=modular-arithmetic-toolkit
• 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.https://ctfpal.com/?tool=asn1-x509-parser

Reading

• The RSA attack decision tree - 7 min. 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 - 7 min. 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.

Practice set

Real picoCTF challenges tagged with this module’s techniques, easiest first. Assign the first three in class and the rest as homework.

1. EVEN RSA CAN BE BROKEN??? - picoCTF 2025, easy
2. Shared Secrets - picoCTF 2026, easy
3. StegoRSA - picoCTF 2026, easy
4. basic-mod1 - picoCTF 2022, medium
5. basic-mod2 - picoCTF 2022, medium
6. ClusterRSA - picoCTF 2026, medium
7. Crack the Power - picoMini by CMU-Africa, medium
8. Dachshund Attacks - picoCTF 2021, medium
9. It's Not My Fault 2 - picoCTF 2021, medium
10. b00tl3gRSA2 - picoCTF 2019, hard
11. b00tl3gRSA3 - picoCTF 2019, hard
12. college-rowing-team - picoMini by redpwn, hard

Checkpoint (gradeable)

Given three RSA challenges with different weaknesses, name the applicable attack for each before running anything, then verify.

Deliberately a produced artefact rather than a quiz question: it is either there or it is not, which makes it fast to mark and hard to bluff. Every tool in ctfpal is deterministic, so two students who did the work correctly hand in the same value.

Where the room gets stuck

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.

• 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.

If a student wants the subject, not the answer

Chapter-level references, so a student can be pointed at twenty pages rather than at a book. Nothing here is required to complete the module.

• Designing Secure Software, Loren Kohnfelder. Chapter 5, Cryptography. Why padding exists at all, which is the single fact that turns most of these attacks from tricks into consequences.
• Attacking Network Protocols, James Forshaw. Chapter 7, Network Protocol Security. Public-key exchange as deployed, including what a protocol has to get right around the maths.

If you finish early

• Hand out a challenge from the cross-CTF index in this category - each one has published solutions to compare afterwards.
• Run the same input through Identify and let the class argue with the ranking. Disagreeing with a confidence score is where the technique actually lands.
• Ask a student to break their own example - construct an input that defeats the tool, and explain why.