Why Quantum Computers Are Different
Classical computers — every laptop, server, and supercomputer today — process information as bits: 0 or 1. A quantum computer uses qubits, which can exist in a superposition of 0 and 1 simultaneously. This allows quantum computers to explore many possible solutions to a problem in parallel, making them extraordinarily powerful for specific types of mathematical problems.
The security of almost all asymmetric cryptography in use today — RSA, ECC, Diffie-Hellman — rests on mathematical problems that are computationally infeasible for classical computers:
- RSA relies on the difficulty of integer factorization: given a very large number (e.g., 2048 bits), find its prime factors. A classical computer would take longer than the age of the universe to factor a 2048-bit RSA key.
- ECC relies on the elliptic curve discrete logarithm problem: given points on an elliptic curve, find the scalar that maps one to another.
Shor's Algorithm: The Cryptographic Threat
In 1994, mathematician Peter Shor discovered a quantum algorithm — Shor's Algorithm — that can solve both integer factorization and discrete logarithm problems in polynomial time on a quantum computer. This means a sufficiently powerful quantum computer could break RSA-2048 in hours or days, not billions of years.
The key phrase is "sufficiently powerful." Breaking RSA-2048 would require a quantum computer with millions of stable, error-corrected logical qubits. As of 2024, the most advanced quantum computers have thousands of noisy physical qubits, which is far short of what's needed. But the trajectory of progress is real, and the cryptographic community is not waiting.
Q-Day: The Hypothetical Inflection Point
Q-Day refers to the future date when a quantum computer powerful enough to break current public-key cryptography becomes operational. The exact timeline is debated — estimates range from 10 to 30 years — but the threat is taken seriously enough that governments and standards bodies are acting now.
The most urgent concern is "harvest now, decrypt later" attacks: adversaries (nation-states) are already capturing and storing encrypted internet traffic today, with the intention of decrypting it once Q-Day arrives. Sensitive data with a long secrecy requirement — classified government communications, medical records, trade secrets — is already at risk.
What Is and Isn't Threatened
| Cryptographic System | Quantum Threat | Reason |
|---|---|---|
| RSA (asymmetric) | Broken by Shor's | Factoring problem solved efficiently |
| ECC (asymmetric) | Broken by Shor's | Discrete log problem solved efficiently |
| Diffie-Hellman (key exchange) | Broken by Shor's | Discrete log problem |
| AES-128 (symmetric) | Weakened — effectively AES-64 | Grover's algorithm halves key strength |
| AES-256 (symmetric) | Secure — effectively AES-128 | Grover's algorithm still leaves 128-bit security |
| SHA-256 (hashing) | Largely secure | Grover's reduces collision resistance, but SHA-256 retains adequate security |
| SHA-3 / SHA-512 | Secure | Sufficient security margin against Grover's |
Grover's Algorithm is a separate quantum algorithm that provides a quadratic speedup for searching unsorted data — effectively halving the bit-strength of symmetric keys and hash functions. This is why AES-256 (not AES-128) is recommended for long-term security, and why SHA-256 remains acceptable while MD5/SHA-1 are not.