The RSA Setup: Choosing Primes
What you'll learn: How to select two large distinct primes p and q and compute their product n = pq as the modulus for RSA encryption.
Why This Matters
In public-key cryptography, RSA relies on the practical difficulty of factoring large numbers. The security of the entire system hinges on how we choose our building blocks: two prime numbers.
Choosing the Primes
The first step in RSA setup is selecting two large, distinct prime numbers, conventionally called p and q. Here's what "large" means in practice:
- Each prime should be hundreds or thousands of digits long (in real-world applications, 1024-bit or 2048-bit primes are common)
- The primes must be distinct: p ≠ q
- They should be randomly chosen to prevent attackers from guessing them
Think of p and q as the secret ingredients in a recipe. Once mixed together, it's nearly impossible for anyone to reverse-engineer the original components from the final dish.
Computing the Modulus
Once you've chosen p and q, compute their product:
n = pq
This number n is called the RSA modulus. It will be public—everyone can see it—but factoring it back into p and q is computationally infeasible when the primes are large enough.
Why This Works
The modulus n becomes the foundation for all RSA operations. Its totient φ(n) = (p − 1)(q − 1) drives the relationship between encryption and decryption (thanks to Euler's Theorem, which you've already studied). However, computing φ(n) is easy only if you know p and q—the secret factors.
Key Takeaway: RSA setup begins by choosing two large distinct primes p and q, then computing n = pq as the public modulus; the security depends on keeping p and q secret while n is public.