What You Just Built
RSA key generation is exactly the seven steps above, and nothing more: pick two primes, multiply them, compute the totient, choose a public exponent coprime to the totient, derive its modular inverse as the private exponent, and you have a complete key pair. Real-world RSA uses primes hundreds of digits long instead of two small ones, purely so that factoring n back into p and q is computationally infeasible — the algorithm itself is identical to what you just did by hand.
Why Each Step Matters
| Step | Purpose |
|---|---|
| Choosing p, q | Their product n is public, but n's factorization must stay secret — this is RSA's entire security foundation |
| Computing φ(n) | Defines the group structure that makes encryption and decryption mathematical inverses of each other |
| Choosing e coprime to φ(n) | Guarantees e has a modular inverse — without this, step 5 would be impossible |
| Deriving d | d undoes exactly what e does, because d and e are modular inverses mod φ(n) — this is the mathematical guarantee that decryption recovers the original message |
Why Real RSA Uses Enormous Primes
The security of everything you just built rests entirely on one fact: given n, finding p and q is hard. With n around 150 to 900 (as in this lab), factoring it takes a computer microseconds. Real RSA uses primes hundreds of digits long specifically so that n becomes computationally infeasible to factor with any known classical algorithm — at least until a large enough quantum computer runs Shor's algorithm, which factors n in polynomial time regardless of size. That's the entire reason NIST standardized ML-DSA (Dilithium) and ML-KEM (Kyber): they don't rely on factoring at all, so Shor's algorithm doesn't apply to them.
Want to see that comparison directly? Try the Quantum Threat Simulator, or practice the underlying operations more with the Modular Arithmetic Trainer.