Why Quantum Computers Break Encryption
A quantum computer doesn't break encryption by being a faster classical computer. It breaks encryption by solving specific mathematical problems — the very problems that encryption is built on — using completely different physics. Here's the exact mechanism, explained from scratch.
Encryption is Built on "Hard" Math Problems
Modern asymmetric cryptography (RSA, ECC, Diffie-Hellman) isn't secure because of secrecy — it's secure because the underlying math problems are computationally hard.
A "hard" problem in cryptography means: easy to compute in one direction, but computationally infeasible to reverse. Like grinding coffee beans — easy to grind, effectively impossible to un-grind.
The two problems that most of modern cryptography rests on:
Integer Factoring
Easy: Multiply two primes: 61 × 53 = 3,233
Hard: Given 3,233, find its prime factors.
RSA security: the public key contains a number that's the product of two enormous primes. The private key is derived from those primes. If you can factor the public key, you can compute the private key.
With 2048-bit RSA numbers, factoring would take more time than the age of the universe on a classical computer.
Discrete Logarithm
Easy: Compute g^x mod p given g, x, p
Hard: Given g^x mod p and g and p, find x.
ECC and Diffie-Hellman security: the public key is the result of scalar point multiplication. Finding the original scalar (the private key) from the public point is the elliptic curve discrete logarithm problem.
No classical algorithm can do this efficiently for the key sizes used in practice.
Why Classical Computers Can't Break These
The best classical algorithms for factoring large numbers (General Number Field Sieve) have sub-exponential time complexity. For a 2048-bit RSA key:
- About 10⁶¹⁷ operations required
- The world's fastest supercomputer does ~10¹⁸ operations per second
- The estimated time: vastly longer than the current age of the universe (13.8 billion years)
How Quantum Computers Are Different
Classical computers use bits — 0 or 1. Quantum computers use qubits that can exist in superposition (both 0 and 1 simultaneously) and can be entangled (linked pairs where measuring one instantly determines the other).
These properties allow quantum algorithms to explore many possible solutions simultaneously — not by running parallel processes, but through the quantum mechanical phenomenon of interference. Good answers interfere constructively (amplifying their probability); bad answers interfere destructively (suppressing their probability).
Which Cryptographic Algorithms Are at Risk?
The pattern is clear: asymmetric algorithms (RSA, ECC, DH) are completely broken. Symmetric algorithms and hash functions are weakened but survivable with larger key sizes.
When Will This Actually Matter?
Today's quantum computers are noisy, error-prone, and have too few qubits to break real cryptographic key sizes. Breaking RSA-2048 would require millions of high-quality logical qubits — far beyond current capability.
Current best estimates
- Breaking RSA-2048: Estimated to require ~4,000 logical (error-corrected) qubits, or ~20 million physical qubits. Current leaders have a few thousand noisy physical qubits.
- Timeline: Most expert estimates place "cryptographically relevant quantum computers" (CRQCs) at 10–20 years away. Some say sooner.
- But: Long-lived secrets (classified government data, medical records, financial transaction records) collected today may still be sensitive in 20 years. This is why we need to act now.
Frequently Asked Questions
Can we just use RSA-4096 to stay ahead of quantum computers?
No. Bigger classical keys don't help against Shor's algorithm because the quantum speedup is qualitative, not quantitative. Shor's algorithm factors numbers in polynomial time (roughly O(n³)) on a quantum computer, while the best classical algorithms are sub-exponential. Doubling the key size does not double the quantum computation needed — it increases it modestly, but the gap remains overwhelming. Post-quantum cryptography replaces the mathematical problem entirely.
Does symmetric encryption like AES need to change?
Not fundamentally. Grover's algorithm provides a square-root speedup for search, halving the effective security of symmetric ciphers. AES-128 drops to 64-bit quantum security (concerning). AES-256 drops to 128-bit quantum security (considered adequate). The fix is simple: use AES-256 instead of AES-128. No algorithm change is needed — just a key size upgrade.
Why not just wait until quantum computers are actually a threat?
Three reasons: (1) Migrating cryptography takes years — upgrading libraries, firmware, hardware, protocols, and standards across global infrastructure is a decade-long project. (2) "Harvest now, decrypt later" — adversaries are collecting encrypted data today to decrypt when quantum computers arrive. (3) NIST standards are already finalized, so there's no reason to wait. The migration has already started.
Frequently Asked Questions
What will I learn here?
This page covers the core concepts and techniques you need to understand the topic and progress confidently to the next lesson.
How should I use this page?
Start with the overview, then follow the section links to deepen your understanding. Use the table of contents on the right to jump to specific sections.
What should I read next?
Use the navigation below to continue to the next lesson or explore related topics.