RSA Algorithm: Key Generation
You'll learn: How to generate a matching RSA public and private key pair from prime numbers.
The Process
RSA key generation transforms two secret prime numbers into a powerful cryptographic key pair. Think of it like creating a special lock and key from two master components—the lock (public key) can be shared with everyone, while only you keep the key (private key).
Step-by-Step Key Generation
1. Choose Two Large Primes
Select two distinct prime numbers, p and q. In practice, these are hundreds of digits long, but let's use small examples for clarity.
2. Calculate the Modulus
Compute n = p × q. This modulus becomes part of both your public and private keys. Its size determines encryption strength.
3. Calculate Euler's Totient
Calculate φ(n) = (p - 1) × (q - 1). This value counts how many numbers less than n are coprime to it—crucial for the trapdoor function you learned about.
4. Choose Public Exponent
Select e such that 1 < e < φ(n) and e is coprime to φ(n). Common choice: e = 65537 (it's prime and makes encryption efficient).
5. Calculate Private Exponent
Find d where (d × e) mod φ(n) = 1. This means d is the modular multiplicative inverse of e. This is the trapdoor—easy to create with p and q, nearly impossible to find without them.
The Result
- Public key: (n, e) — share freely
- Private key: (n, d) — keep secret
- Discard p, q, and φ(n) securely
Key Takeaway: RSA key generation uses prime factorization's one-way nature: multiplying primes is easy, but factoring their product back into primes is computationally infeasible, creating the mathematical trapdoor that secures the system.