The Breakthrough of Public Key Cryptography
Before RSA, all encryption was symmetric — both sender and receiver needed the same secret key. The revolutionary insight of public-key cryptography, independently discovered by Diffie-Hellman and RSA in the 1970s, was that encryption and decryption could use different keys. Anyone can encrypt a message with your public key, but only you can decrypt it with your private key. This solved the ancient key distribution problem: you no longer need a secure channel to share a secret before communicating securely.
The Mathematics Behind RSA
RSA's security rests on a beautiful mathematical asymmetry. Multiplying two large primes is easy — your phone can multiply 617-digit numbers in milliseconds. But given only the product, finding the original factors is computationally infeasible for large numbers. The algorithm: choose primes p and q, compute n = p × q and φ(n) = (p-1)(q-1). Find e coprime to φ(n) — this is the public key. Compute d = e⁻¹ mod φ(n) — this is the private key. To encrypt message M: C = M^e mod n. To decrypt: M = C^d mod n. Euler's theorem guarantees this round-trip works.
Real-World RSA: Scale and Implementation
The primes in this simulation are tiny — real RSA uses primes with 300+ digits each, producing a modulus n with 617+ digits (2048 bits). At this scale, the best known classical factoring algorithms (General Number Field Sieve) would take longer than the age of the universe. In practice, RSA rarely encrypts messages directly — it encrypts a random symmetric key (like AES-256), and that key encrypts the actual data. This hybrid approach combines RSA's key distribution advantage with AES's speed.
The Quantum Threat
In 1994, Peter Shor showed that a quantum computer could factor large numbers exponentially faster than any classical algorithm. A sufficiently large quantum computer — estimated at around 4,000 logical qubits — could break RSA-2048. While such machines don't yet exist, the threat has spurred the development of post-quantum cryptography. NIST standardized lattice-based algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium) in 2024 as quantum-resistant replacements. The migration from RSA to post-quantum encryption is one of the largest infrastructure transitions in computing history.