04 · A lock

RSA

Raise to e to lock, to d to open. d lives in φ(n), and φ(n) lives in the factors. Public n is last chapter’s product.

In English

Everyone gets n and e (the padlock). Only you have d (the key), which you built from the secret factors of n. Anyone can lock a number by raising it to e. Only d opens it. Tiny n is a toy; 2048-bit n is the same algebra with a hardness assumption.

Try this: Pick a message, read the ciphertext, see it open with d. Change n. Notice d is different because the factors are.
Keep this: Lock with e, open with d. d comes from the factors of n.

Lab · lock with e, open with d

Public: n=55 · e=3
Private: p=5 q=11 · φ=40 · d=27

Message m = 8

c = mᵉ mod n = 8^3 ≡ 17

m = cᵈ mod n = 17^27 ≡ 8 · opens

c ≡ mᵉ (mod n), m ≡ cᵈ (mod n), with ed ≡ 1 (mod φ(n)). Euler’s theorem is why the inverse exists when gcd(m,n)=1. The toy keys satisfy the congruence; you can check ed mod φ.

Padding, OAEP, and “never encrypt raw m” are the engineering. The hardness assumption is still “do not factor n.” Volume III’s period lab is the quantum objection.