Cryptography · Intermediate · 11 min read
How RSA Works: A Step-by-Step Worked Example
RSA protects a large part of the internet, yet its mathematics fits on one page. This tutorial builds a complete toy RSA system with small primes so every number can be checked by hand. Real systems use much larger numbers and padding; the toy version is for understanding only.
Key generation in four steps
Choose two distinct primes p and q and compute n = pq. Compute φ(n) = (p − 1)(q − 1). Choose a public exponent e with 1 < e < φ(n) and gcd(e, φ(n)) = 1. Finally compute the private exponent d as the inverse of e modulo φ(n), using the extended Euclidean algorithm. The public key is (n, e); the numbers p, q, φ(n) and d stay secret.
Encryption and decryption
A message is an integer m with 0 ≤ m < n. Encrypt with c = me mod n; decrypt with m = cd mod n. Both are modular exponentiations, computed with square-and-multiply so that even huge exponents are quick.
Why decryption works
Because ed ≡ 1 (mod φ(n)), we can write ed = 1 + kφ(n). Euler's theorem says mφ(n) ≡ 1 (mod n) when m is coprime to n, so med = m · (mφ(n))k ≡ m (mod n). The result also holds when m shares a factor with n, by checking modulo p and q separately.
Why it is hard to break, and why toy RSA is not secure
An attacker who knows n and e can compute d only by knowing φ(n), which is equivalent to factoring n. No efficient classical factoring method is known for numbers of 2048 bits. With tiny primes, however, n can be factored instantly. Real RSA also needs padding such as OAEP, because the plain version is deterministic and malleable.
Key formulas
n = pq, φ(n) = (p − 1)(q − 1)e·d ≡ 1 (mod φ(n))c = mᵉ mod n, m = cᵈ mod n
Solved example
Textbook example with p = 61 and q = 53
- n = 61 · 53 = 3233 and φ(n) = 60 · 52 = 3120.
- Choose e = 17. gcd(17, 3120) = 1, so e is valid.
- The extended Euclidean algorithm gives d = 2753, because 17 · 2753 = 46801 = 15 · 3120 + 1.
- Encrypt m = 65: c = 6517 mod 3233 = 2790.
- Decrypt: 27902753 mod 3233 = 65, the original message.
Practice questions
Try each question first, then open the answer.
1. Let p = 5, q = 11 and e = 3. Find n, φ(n) and d.
n = 55, φ(n) = 4 · 10 = 40 and d = 27, because 3 · 27 = 81 = 2 · 40 + 1.
2. With the key above, encrypt m = 9.
c = 9³ mod 55 = 729 mod 55 = 14, since 55 · 13 = 715 and 729 − 715 = 14.
3. Why can e = 4 not be used when φ(n) = 40?
gcd(4, 40) = 4, not 1, so e has no inverse modulo 40 and no private exponent exists.