What are the four steps of RSA key generation for a 3072-bit key in practice?

Choose two ~1536-bit primes, multiply them to get N, choose e coprime to φ(N), compute d as the modular inverse of e.

Step 1: Choose two large random primes $p$ and $q$

• Each ~1536 bits (~462 decimal digits, ~$10^{450}$)
• Must be roughly equal size
• $(p-1)$ and $(q-1)$ should contain large prime factors

Step 2: Compute $N = p \cdot q$

• Result is ~3072 bits (~924 decimal digits)

Step 3: Choose public exponent $e < \varphi(N) = (p-1)(q-1)$

• Must satisfy $\gcd(e, (p-1)(q-1)) = 1$
• Often a randomly chosen prime, or the standard $e = 65537$
• Warning: Small $e$ (like 3) is safe for signing but dangerous for encryption without padding!

Step 4: Compute $d \equiv e^{-1} \mod (p-1)(q-1)$

• Using the Extended Euclidean Algorithm
• Verify: $d \cdot e \equiv 1 \mod \varphi(N)$, i.e., $d \cdot e = r \cdot (p-1)(q-1) + 1$

Important (BSI 2023): Modulus N must be at least 3000 bits. The $d \equiv e^{-1}$ is computed mod $\varphi(N)$, NOT mod $N$ — this is a critical distinction!

Go deeper:

• Key size (Wikipedia) — how RSA, ECC and symmetric key lengths compare at equal security.
• BSI TR-02102-1 — Cryptographic Mechanisms (PDF) — the primary source for the 3000-bit recommendation.