RSA Algorithm

RSA Algorithm

1. Story in One Line (beginner!)

Multiply two big primes (seconds!) — unmultiplying takes universe-age (trapdoor!). Public locks with product; only prime-knowers unlock. Rivest-Shamir-Adleman, 1977 — still everywhere (keys ≥ 2048 bits!).

1. pick primes p = 3, q = 11
2. n = p × q = 33 (PUBLIC modulus!)
3. φ(n) = (p-1)(q-1) = 2 × 10 = 20 (SECRET count — needs p,q!)
4. pick e coprime to 20: e = 3 (PUBLIC exponent!)
5. find d with e×d mod 20 = 1: 3×7 = 21 ≡ 1 → d = 7 (PRIVATE!)
public = (e=3, n=33), private = (d=7, n=33)

4. Rules + Safety (exam traps!)

• $m < n$ (split message into chunks!). $e$ coprime to $φ(n)$ (else no $d$!).
• Textbook RSA is deterministic (same $m$ → same $c$!) — real uses RANDOM padding (OAEP!) + signatures use PSS!
• Small $e$, reused $n$, no padding → attacks (Håstad, related-message!). Use audited libraries, side-channel guards!
• Quantum Shor breaks factoring → post-quantum migration underway!

5. Exam Points

• Keygen + encrypt/decrypt toy ($p=3,q=11$) — 7-10 marks, #1 RSA question.
• $φ(n)$, $e$-coprime, $ed$ mod $φ = 1$ — 5 marks, most-error steps.
• Padding + 2048-bit + Shor — 3 marks, frequent viva.