RSA Key Generation: Selecting Primes and Computing Parameters
You'll learn the step-by-step process of creating an RSA key pair from scratch.
Now that you understand RSA's mathematical foundation, let's walk through actually generating keys. RSA key generation follows a precise recipe—miss a step or choose poor parameters, and the entire system becomes vulnerable.
The Six-Step Generation Process
Step 1: Choose two large primes, p and q
Select two distinct, random prime numbers. For real security, these should be hundreds or thousands of digits long. The security of everything depends on keeping these secret.
Step 2: Compute n = p × q
Multiply your primes together. This value n becomes your modulus—it appears in both your public and private keys and defines the size of numbers you can encrypt.
Step 3: Compute φ(n) = (p - 1)(q - 1)
Calculate Euler's totient function. This tells you how many numbers less than n are coprime to it. Keep φ(n) secret—revealing it is as bad as revealing p and q.
Step 4: Select public exponent e
Choose a number e where 1 < e < φ(n) and e is coprime to φ(n) (their greatest common divisor is 1). Commonly, e = 65537 is used—it's prime, makes encryption fast, and works for most cases.
Step 5: Compute private exponent d
Find d such that (d × e) mod φ(n) = 1. This is called the modular multiplicative inverse of e. Value d must stay absolutely secret—it's your private key.
Step 6: Package the keys
Your public key is (n, e). Your private key is (n, d). Some implementations also keep p, q, and other values for optimization.
Key Takeaway: RSA key generation requires selecting random primes p and q, computing modulus n and totient φ(n), choosing public exponent e, then calculating private exponent d—each step builds the cryptographic relationship between your public and private keys.