RSA Modular Math Cheat Sheet
Extended Euclidean + successive squaring — course canonical example
Key generation (p=11, q=17)
- n = p×q = 187
- φ(n) = (p−1)(q−1) = 10×16 = 160
- Choose e=19 (gcd(e,φ)=1)
- Find d = e⁻¹ mod φ = 59
Extended Euclidean (e=19, φ=160)
When B=0, d = coefficient from prior row. Check: 19×59 = 1121 ≡ 1 (mod 160).
Successive squaring — encrypt M=21, e=19, n=187
Decrypt check
M = 98⁵⁹ mod 187 = 21
Template for any exam problem
- Compute φ(n) from primes
- Run Extended Euclidean table until remainder = 0 → read d
- Write e in binary; square-and-multiply mod n for C = M^e mod n