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.

What a real private key actually stores

(n, d) is enough to decrypt, but it is the slow way, and no real key file stops there. A PKCS#1 private key also carries p, q, dp = d mod (p-1), dq = d mod (q-1) and qInv = q^-1 mod p. With those an implementation exponentiates modulo p and modulo q -- two half-size operations instead of one full-size one -- and recombines the halves with the Chinese Remainder Theorem. That is roughly a 4x speed-up on every decryption and every signature.

Do not let p and q sit close together

If |p - q| is small then the square root of n lands almost exactly between them, and Fermat's factorisation simply walks a upward from ceil(sqrt(n)) checking whether a*a - n is a perfect square. On a close pair it succeeds in milliseconds, on a 2048-bit modulus, with no cleverness at all. FIPS 186-5 requires |p - q| > 2^(nlen/2 - 100) for exactly this reason -- a generator that produces q by nudging p upward until it hits a prime is broken, however good its randomness was for p.