09 — Asymmetric
RSA — The Math
Security rests on the hardness of factoring the product of two large primes.
How RSA actually works — diagram + math
How RSA actually works: primes → modulus → exponent pair → public encryption, private decryption. Signatures run the same machine backwards.
# The numbers on the diagram (p=5, q=11):
n = 55 φ(n) = 40 e = 3 d = 27 # 3·27 = 81 = 2·40 + 1 ✓
Encrypt: c = 14³ mod 55 = 2744 − 49·55 = 49
Decrypt: m = 49²⁷ mod 55 = 14 ✓ # square-and-multiply, O(log d) steps
# Why it works (Euler): e·d = 1 + k·φ, so
m^(e·d) = m^(1+k·φ) = m · (m^φ)^k ≡ m · 1^k = m (mod n)
# Attacker holds (e,n,c) = (3,55,49) but needs d → needs φ → must factor n.
Key generation
1. Pick two large primes p, q (1024+ bits each)
2. Compute n = p · q
3. Euler totient φ(n) = (p − 1)(q − 1)
4. Choose public exp. e with 1 < e < φ(n), gcd(e, φ(n)) = 1
5. Private exponent d = e⁻¹ mod φ(n) (modular inverse)
Public key = (e, n)
Private key = (d, n)
Encryption & decryption
# Encrypt m (0 ≤ m < n)
c = m^e mod n
# Decrypt c
m = c^d mod n
# Why it works: e·d ≡ 1 (mod φ(n)) by construction;
# Euler's theorem: m^φ(n) ≡ 1 (mod n) when gcd(m,n)=1,
# so m^(e·d) = m^(1+k·φ(n)) ≡ m (mod n)
Worked example (tiny numbers)
p = 5, q = 11
n = 55, φ(n) = 4·10 = 40
e = 3 # gcd(3,40)=1 ✓ (common choice 65537 also coprime here)
Finding d with Extended Euclid — full steps
# Need d with 3·d ≡ 1 mod 40. Euclid first:
40 = 3·13 + 1
3 = 1·3 + 0 → gcd = 1 ✓
# Back-substitute:
1 = 40 − 3·13
→ (−13)·3 ≡ 1 mod 40
→ d = −13 mod 40 = 27
Check: 3·27 = 81 = 2·40 + 1 ✓
Public key = (3, 55)
Private key = (27, 55)
# Encrypt m = 14 with square-and-multiply:
14² = 196 mod 55 = 196 − 3·55 = 196 − 165 = 31
14³ = 31·14 = 434 mod 55 = 434 − 7·55 = 434 − 385 = 49
c = 49
# Decrypt: 49²⁷ mod 55. Binary 27 = 11011; repeated squaring
# (square each step, multiply when bit = 1) collapses to:
m = 49²⁷ mod 55 = 14 ✓
Square-and-multiply (how computers do it)
To compute a^e mod n, scan bits of e left→right: square each step, multiply by a when the bit is 1. Cost O(log e) multiplies — feasible even for 2048-bit exponents.Security & notes
- Attacker must factor
n→ p, q → φ(n) → d. Factoring is sub-exponential but hard for 2048+ bit n - Signatures swap roles:
σ = H(m)^d mod n, verifyH(m) ?= σ^e mod n - Padding is essential: OAEP for encryption, PSS for signatures (raw "textbook RSA" leaks structure)
- Never use small
e=3without padding, never reusenacross users, never encryptm ≥ n
Practical sizes
1024-bit: broken by nation-states. 2048-bit: current floor. 3072-bit: recommended new. Post-quantum: Shor's algorithm breaks RSA — hence NIST PQC (Kyber, Dilithium).Exam one-liner:
n=pq, φ=(p-1)(q-1), ed≡1 mod φ, encrypt m^e, decrypt c^d.