Side-Channel Aware
Q3 capstone: implement RSA in Sage, then break it three ways.
Scenario
Thirty-nine weeks in. Pinter through field theory, Boneh-Shoup Part I rigorously read, RSA and Diffie-Hellman implemented in Sage from scratch, library publishing pipeline working. The Q3 capstone is a deliberate-vulnerability RSA. You implement RSA three ways with three different bugs, then break each one. The point is not that you can do RSA; it's that you can break a wrong RSA, which is what real cryptanalysis looks like.
Success criteria
- Three RSA toy implementations in Sage, each with a documented vulnerability.
- Three working attacks: small-e (Håstad's broadcast attack with three recipients), common-modulus (two recipients with shared N and coprime e), Wiener attack (small d with continued fractions).
- Each attack writes the recovered plaintext or factored modulus to the notebook output.
- A short 'attacker's chair' writeup per attack: how you'd have spotted the vulnerability if you encountered it in a real audit.
- Notebook committed to crypto-curriculum/capstones/q3/.
The three vulnerabilities
- Small e (e = 3). Three recipients receive the same plaintext message encrypted under three different RSA public keys, all with e = 3. Use Håstad’s broadcast attack via the Chinese Remainder Theorem to recover the plaintext.
- Common modulus. Two recipients share modulus N (a textbook bug) but have coprime exponents e1, e2. Recover the plaintext using the extended Euclidean algorithm to find Bezout coefficients.
- Wiener attack. A user has chosen d small (relative to N) for performance reasons. Recover d using continued-fraction expansion of e/N.
Each attack already exists in textbook form. The capstone is to implement each from scratch, in Sage, with the math worked rather than libraried.
Why three attacks not one
Cryptography fails at the weakest construction. If you have only seen RSA work in one canonical configuration, you will not recognize a wrong RSA in the wild. The three attacks above all derive from real production CVEs in real systems shipped by reputable engineers. The capstone is the inoculation.
The writeup
Each attack gets a 200-word attacker’s chair writeup: what’s the giveaway in a code review, what’s the cheap fix, what’s the right fix. This prose lands closer to a security audit report than to academic mathematics. Practice for the journalism artifact’s threat-model document in Q4.