Is RSA Dead? How It Works, Why It Matters, and What Comes Next

RSA is arguably the most important algorithm in the history of the internet. Every time you visit an HTTPS website, send an encrypted email, or verify a software update, there's a decent chance RSA is involved somewhere in the chain. It was invented in 1977, published as a paper by Rivest, Shamir, and Adleman (hence the name), and it's been securing digital communication for nearly 50 years.

And yet, the question "is RSA dead?" keeps coming up — in conference talks, in security audits, in engineering Slack channels. The answer is nuanced: RSA isn't dead today, but it's on a timeline. Understanding why requires understanding how it actually works, what makes it strong, and what specifically threatens it. This post covers all three, starting with the math you can verify with a calculator.

The Core Idea: Easy to Multiply, Hard to Factor

RSA's security rests on a single asymmetry: multiplying two large prime numbers together is trivial, but factoring the product back into those primes is computationally infeasible for large enough numbers.

You can verify this intuitively. Multiply 61 x 53. Easy — it's 3,233. Now, given just 3,233, figure out which two primes produce it. Without already knowing the answer, you'd need to try dividing by primes until something works. For a small number like 3,233, that's manageable. For a number with 617 digits (2048-bit RSA), it's beyond the capability of every computer on Earth working together for the age of the universe.

That asymmetry — easy in one direction, practically impossible in reverse — is what makes public-key cryptography possible.

RSA Step by Step (With Numbers You Can Check)

Let's build a working RSA keypair using intentionally tiny numbers. This is pedagogical — real RSA uses primes with hundreds of digits — but the math is identical.

Step 1: Choose Two Primes

Pick two prime numbers: p = 3 and q = 5.

Step 2: Compute n (the Modulus)

n = p × q = 3 × 5 = 15

This value

n

n

Step 3: Compute Euler's Totient

φ(n) = (p - 1) × (q - 1) = 2 × 4 = 8

The totient counts how many numbers less than

n

Step 4: Choose the Public Exponent (e)

Pick

e

1 < e < φ(n)

gcd(e, φ(n)) = 1

e

φ(n)

e = 7    (gcd(7, 8) = 1 ✓)

In practice, most implementations use

e = 65537

Step 5: Compute the Private Exponent (d)

Find

d

d × e ≡ 1 (mod φ(n))

d

e

d × 7 ≡ 1 (mod 8)
d = 7    (7 × 7 = 49 = 6 × 8 + 1 ✓)

With these tiny numbers,

d

e

d

e

The Keys

Public key:  (n = 15, e = 7)  → shared with everyone
Private key: (n = 15, d = 7)  → kept secret

Encrypting and Decrypting: Hands-On Examples

The formulas are simple:

Encrypt: ciphertext = message^e mod n
Decrypt: message = ciphertext^d mod n

Example 1: Encrypt the number 2

Encrypt:  2^7 mod 15
          2^7 = 128
          128 mod 15 = 8       (128 ÷ 15 = 8 remainder 8)
          Ciphertext = 8

Decrypt:  8^7 mod 15
          8^2 = 64,  64 mod 15 = 4
          8^4 = 4^2 = 16, 16 mod 15 = 1
          8^7 = 8^4 × 8^2 × 8^1 = 1 × 4 × 8 = 32
          32 mod 15 = 2 ✓      Original message recovered!

Example 2: Encrypt the number 7

Encrypt:  7^7 mod 15
          7^2 = 49,  49 mod 15 = 4
          7^4 = 4^2 = 16, 16 mod 15 = 1
          7^7 = 7^4 × 7^2 × 7^1 = 1 × 4 × 7 = 28
          28 mod 15 = 13
          Ciphertext = 13

Decrypt:  13^7 mod 15
          13^2 = 169, 169 mod 15 = 4
          13^4 = 4^2 = 16, 16 mod 15 = 1
          13^7 = 13^4 × 13^2 × 13^1 = 1 × 4 × 13 = 52
          52 mod 15 = 7 ✓      Original message recovered!

Example 3: Encrypt the number 4

Encrypt:  4^7 mod 15
          4^2 = 16,  16 mod 15 = 1
          4^7 = 4^(2×3) × 4^1 = 1^3 × 4 = 4
          Ciphertext = 4

Decrypt:  4^7 mod 15 = 4 ✓     (Same process — message recovered)

This last example is interesting: the ciphertext equals the plaintext. This happens because 4 shares a factor with 15 (both are divisible by... well, by nothing coprime-breaking here — it's actually because 4^2 ≡ 1 mod 15). With real RSA keys, this kind of collision is astronomically unlikely due to the key size, but it's a useful reminder that toy examples have toy limitations.

How RSA Is Actually Used

In practice, RSA is almost never used to encrypt data directly. It's too slow for bulk encryption — encrypting a 1MB file with RSA would take orders of magnitude longer than with AES. Instead, RSA is used for two things:

Key exchange: Encrypt a short symmetric key (like an AES-256 key) with RSA, send it to the recipient, and then use the fast symmetric cipher for the actual data. This is how TLS 1.2 historically worked (TLS 1.3 moved to Diffie-Hellman exclusively).

Digital signatures: Hash a message, then encrypt the hash with your private key. Anyone with your public key can decrypt the hash and verify the message hasn't been tampered with. This is how code signing, certificate chains, and email signing work.

Why RSA Might Be on Borrowed Time

The Classical Threat: Key Sizes Keep Growing

In 1991, a 330-bit RSA key was first factored. By 2020, a 829-bit key was factored (RSA-250). The trend is clear: as computers get faster and factoring algorithms improve, the minimum safe key size keeps increasing. Today's recommendation is 2048-bit minimum, with 4096-bit for long-term security. In the 1990s, 512-bit was considered strong.

This isn't a crisis — we can always use bigger keys. But bigger keys mean slower operations. A 4096-bit RSA signature is roughly 8x slower than a 2048-bit one. At some point, the performance cost of keeping RSA secure becomes a practical concern.

The Quantum Threat: Shor's Algorithm

This is the real danger. In 1994, mathematician Peter Shor published a quantum algorithm that can factor large numbers in polynomial time. On a sufficiently powerful quantum computer, Shor's algorithm would break RSA of any key size — not by trying harder, but by making the underlying hard problem easy.

The key word is "sufficiently powerful." Current quantum computers have on the order of 1,000-1,500 qubits. Breaking RSA-2048 with Shor's algorithm is estimated to require roughly 4,000 error-corrected logical qubits, which translates to millions of physical qubits with current error rates. Nobody is close to that today.

But "not today" isn't the same as "never." The intelligence community operates on the assumption that adversaries are recording encrypted traffic now, intending to decrypt it later when quantum computers mature. This is called a "harvest now, decrypt later" attack, and it's the reason the cryptography community is urgently migrating away from RSA for long-term secrets.

What's Replacing RSA

In 2024, NIST finalized its first set of post-quantum cryptographic standards:

• ML-KEM (formerly CRYSTALS-Kyber) for key encapsulation — replacing RSA and ECDH key exchange
• ML-DSA (formerly CRYSTALS-Dilithium) for digital signatures — replacing RSA and ECDSA signatures
• SLH-DSA (formerly SPHINCS+) as a backup signature scheme based on hash functions

These algorithms are designed to resist both classical and quantum attacks. They're based on mathematical problems (lattice problems, hash functions) that quantum computers don't solve efficiently.

Chrome, Firefox, and Cloudflare have already deployed experimental support for hybrid key exchange using ML-KEM alongside traditional X25519. The migration is happening now — it's just gradual.

What You Should Do Today

If you're choosing between RSA and ECDSA for a new system: Pick ECDSA (or better, EdDSA / Ed25519). ECDSA gives equivalent security to RSA with much shorter keys and faster operations. Ed25519 is simpler and avoids the implementation pitfalls of ECDSA. Neither is quantum-safe, but both are better choices than RSA for current use.

If you're maintaining a system that uses RSA: Ensure you're using 2048-bit keys minimum. If your data has a secrecy requirement beyond 2030, consider 4096-bit or start planning the migration to post-quantum algorithms. Check what your TLS library supports — OpenSSL 3.x already includes experimental post-quantum support.

If you're protecting data that must remain secret for 20+ years: The harvest-now-decrypt-later threat applies to you. Start evaluating hybrid approaches that combine classical and post-quantum algorithms, so you're protected regardless of when quantum computers become practical.

The Verdict

RSA isn't dead. It's still securing a significant portion of internet traffic, and it remains unbroken by classical computers at current key sizes. But it's on a countdown. The quantum threat isn't a question of "if" but "when," and the cryptography community has already built the replacements.

The practical takeaway: don't panic, but don't ignore it either. Use strong key sizes today, prefer elliptic curve cryptography for new systems, and start planning for post-quantum migration. The organizations that handle this transition smoothly will be the ones that started planning before it was urgent.