Walk through the complete RSA key generation, encryption, and decryption process.

Generate two primes p,q; compute N=pq and φ(N)=(p-1)(q-1); choose e coprime to φ(N); compute d=e⁻¹ mod φ(N). Encrypt: c=mᵉ mod N. Decrypt: m=cᵈ mod N.

* Key generation splits into a public key anyone uses to encrypt and a private key only the owner uses to decrypt. *

Key Generation:

1. Choose two large primes $p$ and $q$ (each ~1536 bits for 3072-bit RSA)
2. Compute $N = p \cdot q$ (the modulus)
3. Compute $\varphi(N) = (p-1)(q-1)$
4. Choose public exponent $e$ with $\gcd(e, \varphi(N)) = 1$
5. Compute private exponent $d \equiv e^{-1} \mod \varphi(N)$

Keys:

• Public key: $(e, N)$ — published
• Private key: $d$ (plus $p, q$ for optimization)

Encryption (Bob sends to Alice): $c \equiv m^e \mod N$ Decryption (Alice): $m \equiv c^d \mod N$

Why it works (proof via Euler): $c^d \equiv (m^e)^d \equiv m^{e \cdot d} \equiv m^{r \cdot \varphi(N) + 1} \equiv (m^{\varphi(N)})^r \cdot m \equiv 1^r \cdot m \equiv m \mod N$

Constraint: Message $m$ must satisfy $m < N$.

Go deeper:

• The RSA Encryption Algorithm — computing an example (Eddie Woo) — a full keygen-encrypt-decrypt worked by hand.
• RSA cryptosystem — key generation & operation (Wikipedia) — the same steps with the Euler-theorem correctness proof.