RSA Key Generation

The full algorithm:

1. Pick two random distinct primes p, q (each ~k/2 bits for a k-bit modulus).
2. n = p * q
3. φ(n) = (p - 1) * (q - 1)
4. Pick e (public exponent) coprime to φ(n). Common: e = 65537.
5. d = e^-1 mod φ(n)         (private exponent)
6. Public key:  (n, e)
   Private key: (n, d)        (or full: p, q, d, etc. for fast exponentiation)

Why e = 65537? It's the Fermat number F_4 = 2^16 + 1 = 65537. Properties:

• Coprime to most φ(n) values
• Has only 2 set bits → fast exponentiation (just 17 multiplications)
• Large enough to defeat low-exponent attacks

Older RSA used e = 3, which was attacked when used naively (Coppersmith attack). 65537 is the modern default.

Example with toy numbers:

p = 61, q = 53
n = 3233
φ(n) = 60 * 52 = 3120
e = 17 (coprime to 3120)
d = 2753 (since 17 * 2753 ≡ 1 mod 3120)

Public:  (3233, 17)
Private: (3233, 2753)

For RSA-2048: p, q ~1024 bits each. n is 2048 bits (~617 decimal digits).

Modern minimum: 2048-bit. Recommended for new keys: 3072 or 4096-bit.