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

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, Hastad, common modulus, and the oracle attacks.

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. StegoRSA - picoCTF 2026, easy
3. ClusterRSA - picoCTF 2026, medium
4. Crack the Power - picoMini by CMU-Africa, medium
5. Dachshund Attacks - picoCTF 2021, medium
6. john_pollard - picoCTF 2019, medium
7. Mind your Ps and Qs - picoCTF 2021, medium
8. Mini RSA - picoCTF 2021, medium
9. No Padding, No Problem - picoCTF 2021, medium
10. Related Messages - picoCTF 2026, medium
11. rsa_oracle - picoCTF 2024, medium
12. Small Trouble - picoCTF 2026, medium

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.

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.