Lion Cipher Lab
Break textbook RSA from scratch (implement it, then defeat it -- and see why padding exists)
- Foundations
- Advanced
- ~90 min
- Free · no account required
Why it matters
RSA underpins the certificates, signatures, and key exchange that still run large parts of the internet -- and it is one of the most misused primitives in existence. 'Textbook' RSA, the version everyone first learns (c = m^e mod n with nothing else), is not a cipher: it is deterministic, malleable, and with a small public exponent it can leak the plaintext to anyone holding only the public key and a pocket calculator. Once you have implemented RSA yourself and then broken your own implementation four different ways, you will never again confuse 'the RSA math' with 'a secure encryption…
What you'll learn
- Implementing RSA from scratch: key generation, extended-Euclid modular inverse, encrypt/decrypt
- Why textbook (unpadded) RSA has no semantic security -- determinism and small-message brute force
- The RSA multiplicative homomorphism and ciphertext malleability
- The small-e (e=3) integer cube-root attack, plus Hastad's broadcast attack via CRT
- Why RSA-OAEP and RSA-PSS padding exist, and when to reach for ECC/Ed25519 instead
Steps in this lab
- What textbook RSA is, in one breath
- The maths you actually need (kept minimal)
- Set up a clean workspace
- Implement RSA from scratch
- Flaw 1: textbook RSA is deterministic (no semantic security)
- Flaw 2: the multiplicative homomorphism makes RSA malleable
- Attack: recover the plaintext with an e=3 integer cube root
- Attack: Hastad's broadcast (same message, three e=3 recipients)
- The defence: switch to RSA-OAEP + RSA-PSS and watch the attack fail
- The judgment call: when raw modexp shows up, and what to use instead