RSA: How the Math Actually Works

Number Theory & Cryptographic Math

Chapter 9 · RSA: How the Math Actually Works

No new mathematics appears in this chapter. Every tool RSA needs was already built — divisibility (Ch.2), modular arithmetic (Ch.3), the Euclidean algorithm (Ch.4), modular inverses (Ch.5), primality testing (Ch.6), fast exponentiation (Ch.7), and Euler's theorem (Ch.8). This chapter is pure assembly.

Key Generation, Step by Step

1 — Choose two distinct primes (Ch.6)

Pick p and q — real systems use primality testing on hundreds-of-digit candidates; this chapter's worked example uses p=11, q=13 for full traceability.

2 — Compute the modulus n = pq

n = 11 × 13 = 143. This becomes part of both the public and private key.

3 — Compute φ(n) = (p−1)(q−1) (Ch.8)

φ(143) = 10 × 12 = 120. This value stays secret — it's the entire reason factoring n would break the system (see the security section below).

4 — Choose e with gcd(e, φ(n)) = 1 (Ch.4)

e = 7. Checked directly: gcd(7, 120) = 1 — this is exactly Chapter 4's own GCD check, and it's what guarantees the next step's inverse will actually exist (Chapter 5's own existence condition).

5 — Compute d = e⁻¹ mod φ(n) (Ch.5)

Running the extended Euclidean algorithm on (7, 120): d = 103. Verified directly: 7 × 103 mod 120 = 721 mod 120 = 1.

6 — Publish and keep secret

Public key: (n, e) = (143, 7) — shared with anyone. Private key: (n, d) = (143, 103) — kept secret. p, q, and φ(n) are also destroyed or kept secret — they're no longer needed once d is computed.

Encryption and Decryption

Both are just Chapter 7's own fast modular exponentiation

Encrypt: c = m^e mod n, using the public key. Decrypt: m = c^d mod n, using the private key. Nothing else — the entire "encryption algorithm" is a single call to the exact function Chapter 7 built.

Verified directly — the full round trip, m=9

Encrypt: c = 9⁷ mod 143 = 48. Decrypt: m = 48¹⁰³ mod 143 = 9 — the original message, recovered exactly. Confirmed for five more messages: m=2→c=128→2, m=5→c=47→5, m=10→c=10→10, m=20→c=136→20, m=50→c=41→50 — every single one round-trips correctly.

Why It Works: The Actual Proof, Not an Assertion

By construction (step 5), ed ≡ 1 (mod φ(n)) — meaning ed = 1 + kφ(n) for some integer k. Decrypting an encrypted message:

The full derivation, using only Chapter 8's own theorem

c^d = (m^e)^d = m^(ed) = m^(1 + kφ(n)) = m × (m^φ(n))^k. By Euler's theorem (Chapter 8), m^φ(n) ≡ 1 (mod n) whenever gcd(m,n)=1 — so (m^φ(n))^k ≡ 1^k = 1 (mod n), leaving c^d ≡ m × 1 = m (mod n). Decryption recovers the original message because Chapter 8's theorem guarantees it — not by coincidence, and not because the specific numbers above happened to work out.

An honest edge case

The proof above technically requires gcd(m, n) = 1. Testing m=11 against this exact key (gcd(11,143)=11, since 11 is one of the actual prime factors of 143) — the round trip still works (c=132, decrypts back to 11). Real RSA is correct for every message in [0,n), not just coprime ones, via a more careful argument (the Chinese Remainder Theorem, applied separately mod p and mod q) — deliberately left out of this course's own stated scope (Chapter 1). The Euler's-theorem proof above is complete and honest for the coprime case, which is the overwhelming majority of real messages.

Security: Why Factoring n Breaks Everything

Anyone who can factor the public n back into p and q can recompute φ(n) = (p−1)(q−1) directly, then run Chapter 5's own extended Euclidean algorithm to compute d exactly as the key's own owner did — completely breaking the private key. This is Chapter 1's own multiply-vs-factor asymmetry, made concrete: n is public precisely because computing it from p and q is instant, while the reverse — factoring n back into p and q — is (for large enough primes) computationally infeasible with any known method. Every piece of this course has been building toward exactly this one sentence.

Toy RSA in Code

def extended_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    return old_r, old_s

def generate_keys(p, q, e):
    n = p * q
    phi_n = (p - 1) * (q - 1)
    g, x = extended_gcd(e, phi_n)
    assert g == 1, "e must be coprime with phi(n)"
    d = x % phi_n
    return (n, e), (n, d)   # public key, private key

def encrypt(m, public_key):
    n, e = public_key
    return pow(m, e, n)

def decrypt(c, private_key):
    n, d = private_key
    return pow(c, d, n)

pub, priv = generate_keys(11, 13, 7)
c = encrypt(9, pub)
m = decrypt(c, priv)
print(pub, priv, c, m)   # (143, 7) (143, 103) 48 9

Hands-On Exercises

Exercise 1

Generate a full RSA key pair for p=5, q=11, using e=3. Show every step (n, φ(n), the gcd check, and d via the extended Euclidean algorithm), then encrypt and decrypt m=4, confirming the round trip.

📄 View solution

Exercise 2

For p=7, q=13 (so n=91, φ(n)=72), a colleague proposes e=6. Explain why this choice is invalid, then choose a valid e, compute the corresponding d, and encrypt/decrypt m=6 to confirm it works.

📄 View solution

Exercise 3

Using this chapter's own correctness proof, explain in your own words each of the three substitutions that turn c^d into m — specifically, where ed = 1 + kφ(n) comes from, and where Euler's theorem is actually used in the derivation.

📄 View solution

Chapter 9 Quick Reference

Key generation: pick primes p,q → n=pq → φ(n)=(p−1)(q−1) → choose e coprime to φ(n) → d=e⁻¹ mod φ(n)
Encrypt: c = m^e mod n. Decrypt: m = c^d mod n — both are Chapter 7's own fast modular exponentiation
Correctness is Euler's theorem (Ch.8), applied directly to ed ≡ 1 (mod φ(n)) — not an assumption
Verified round trip for 6 different messages with the same key pair, all correct
Security rests entirely on Chapter 1's own multiply-vs-factor asymmetry: computing n from p,q is instant; reversing it isn't
Next chapter: Capstone — building a toy RSA implementation