RSA Encryption: The Mathematics of Large Primes

Q: Why can't an attacker compute the private key from the public key?

The private exponent d is the modular inverse of the public exponent e with respect to φ(n) = (p−1)(q−1), and φ(n) can only be computed if you know the prime factors p and q of n. Without factoring n — believed to require exponential time as the number of digits grows — an attacker cannot recover φ(n) and therefore cannot derive d.

Q: How secure is RSA-2048 against classical computers?

The best known classical attack, the General Number Field Sieve, would take an estimated ~10^18 years on the world's fastest computer to factor a 2048-bit RSA modulus — far longer than the age of the universe. RSA-2048 is the current standard for TLS key exchange, and RSA-4096 provides an even larger security margin.

Q: Does quantum computing break RSA?

Shor's algorithm factors large integers in polynomial time on a sufficiently large quantum computer and would break RSA. Cracking RSA-2048 is estimated to require roughly 4,000+ logical (millions of physical) qubits; today's quantum computers have around 1,000 noisy physical qubits. NIST standardised lattice-based post-quantum algorithms (ML-KEM, ML-DSA) in 2024 as a hedge against this future threat.

Public keys and the factorisation trapdoor

Before RSA, secure communication needed a pre-shared secret, exchanged in person. Public-key cryptography, published by Rivest, Shamir and Adleman in 1977, eliminates that: everyone publishes a public key that anyone can use to lock a message, but only the holder of the matching private key can unlock it. The lock is one-way — easy to apply, computationally infeasible to reverse — thanks to the integer factorisation trapdoor: multiplying two large primes is instant, but factoring their product is believed to need exponential time in the number of digits. All the arithmetic happens modulo n, "clock arithmetic" where only the remainder matters, which creates a finite cyclic group in which exponentiation is easy but the reverse (the discrete logarithm) is hard.

Euler's theorem and key generation

The heart of RSA is Euler's theorem: for any m coprime to n, m^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient — the count of integers up to n coprime to n. For n = p×q (two distinct primes), φ(n) = (p−1)(q−1), and computing it requires knowing the prime factors — the key insight that makes RSA secure. Key generation: choose two large distinct primes p, q (each ~617 decimal digits for 2048-bit RSA); compute n = p×q and φ(n); choose a public exponent e coprime to φ(n), typically e = 65537; compute the private exponent d = e⁻¹ mod φ(n) via the Extended Euclidean Algorithm; publish (n, e) and keep (n, d) secret, destroying p, q, and φ(n).

Encryption, decryption, and why it works

To encrypt a message m < n with the public key, compute c = mᵉ mod n. To decrypt, compute m = c^d mod n — and because ed ≡ 1 (mod φ(n)), Euler's theorem guarantees m^(ed) ≡ m (mod n), so the original message pops back out exactly. A worked toy example: p=61, q=53, n=3233, φ(n)=3120, e=17, d=2753. Encrypting m=65 gives c = 65¹⁷ mod 3233 = 2790, and decrypting 2790²⁷⁵³ mod 3233 returns 65.

n = p·q             φ(n) = (p−1)(q−1)         e·d ≡ 1 (mod φ(n))
Encrypt:  c = m^e mod n        Decrypt:  m = c^d mod n
2048-bit RSA GNFS factoring time: ~10^18 years on today's fastest hardware

Security today, and the quantum threat

The best known classical attack, the General Number Field Sieve, would take roughly 10¹⁸ years to factor a 2048-bit modulus on the world's fastest computer — RSA-2048 is today's TLS-certificate standard, with RSA-4096 offering a decades-longer margin. Elliptic Curve Cryptography achieves equivalent security with far shorter keys (ECC-256 ≈ RSA-3072), which is why TLS 1.3 prefers ECDHE for key exchange. The real long-term threat is quantum: Shor's algorithm factors integers in polynomial time on a sufficiently large quantum computer, and cracking RSA-2048 is estimated to need 4,000+ logical qubits versus today's ~1,000 noisy physical qubits. NIST standardised lattice-based post-quantum algorithms — ML-KEM and ML-DSA — in 2024 as the industry's hedge against that future.

Frequently asked questions

Why can't an attacker compute the private key from the public key?

The private exponent d is the modular inverse of the public exponent e with respect to φ(n) = (p−1)(q−1), and φ(n) can only be computed if you know the prime factors p and q of n. Without factoring n — believed to require exponential time as the number of digits grows — an attacker cannot recover φ(n) and therefore cannot derive d.

How secure is RSA-2048 against classical computers?

The best known classical attack, the General Number Field Sieve, would take an estimated ~10^18 years on the world's fastest computer to factor a 2048-bit RSA modulus — far longer than the age of the universe. RSA-2048 is the current standard for TLS key exchange, and RSA-4096 provides an even larger security margin.

Does quantum computing break RSA?

Shor's algorithm factors large integers in polynomial time on a sufficiently large quantum computer and would break RSA. Cracking RSA-2048 is estimated to require roughly 4,000+ logical (millions of physical) qubits; today's quantum computers have around 1,000 noisy physical qubits. NIST standardised lattice-based post-quantum algorithms (ML-KEM, ML-DSA) in 2024 as a hedge against this future threat.

Try it live

Everything above runs in your browser — open RSA Key Exchange and step through choosing two primes, computing n and φ(n), finding e and d, and encrypting/decrypting a message with the resulting keypair. Nothing is installed, nothing is uploaded.

▶ Open RSA Key Exchange simulation