Almost everything you trust online rests on two assumptions: that nobody can factor a very large number quickly, and that nobody can reverse an elliptic-curve operation quickly. RSA leans on the first, ECC on the second, and together they protect TLS sessions, VPN tunnels, software signatures, and the wallets behind every cryptocurrency.
Classical computers cannot crack either in any useful timeframe, which is exactly why both schemes have lasted for decades. A quantum computer changes the math. By exploiting structures that ordinary machines cannot see, the right quantum routine turns those impossibly hard problems into merely difficult ones, and from there into solved ones. This is how the security of RSA and ECC quietly developed an expiration date, and why understanding the mechanism matters before the hardware catches up.
Key Takeaways
- RSA and ECC are secure only because factoring and discrete logarithms are slow on classical computers.
- Shor’s method solves both problems in polynomial time, breaking public-key encryption and digital signatures.
- ECC actually falls with fewer qubits than RSA, making it the easier target despite its smaller keys.
- Grover’s search only weakens symmetric encryption; AES-256 and modern hashes stay safe by using larger sizes.
- Estimates to break RSA-2048 dropped from about 20 million qubits in 2019 to below one million by 2025.
The Two Algorithms That Matter
Of the many quantum routines studied since the 1990s, only two seriously threaten the cryptography in daily use, and they attack from opposite directions. The first, published by Peter Shor in 1994, dismantles public-key systems. The second, published by Lov Grover in 1996, chips away at symmetric ones. Anyone tracking the threat should start with how quantum algorithms like Shor’s and Grover’s actually operate, because the two have very different blast radii. Shor’s is the existential one; Grover’s is a manageable nuisance. The table below summarizes the split between them.
| Algorithm | Problem it solves | Speedup | Cryptography affected |
|---|---|---|---|
| Shor’s (1994) | Factoring and discrete logarithms | Exponential to polynomial | RSA, ECC, Diffie-Hellman |
| Grover’s (1996) | Unstructured key search | Quadratic (square root) | Symmetric ciphers and hashes |
How Shor’s Algorithm Breaks RSA
RSA, introduced in 1977, builds its security on a one-way street. Multiplying two large prime numbers to get a public modulus is trivial, but starting from that modulus and recovering the original primes, the task called factoring, is brutally hard for a classical machine. For a 2048-bit modulus, the best known classical methods would run longer than the age of the universe. Shor’s approach sidesteps brute force entirely. It reframes factoring as a period-finding problem, then uses a quantum Fourier transform to extract that period in one efficient sweep, drawing on superposition to evaluate countless possibilities at once and on interference to cancel the wrong answers. The result is a jump from exponential to polynomial time. What was effectively impossible becomes a computation measured in hours or days, and once the primes are known, every message that key is protected can be read and every signature it issued can be forged.
Why ECC Falls Even Faster
Elliptic-curve cryptography was supposed to be the sturdier successor. It delivers the same classical security as RSA with far smaller keys, which is why it guards modern web sessions, mobile devices, and the ECDSA signatures behind Bitcoin and most other blockchains. Its hardness rests on a different puzzle, the elliptic-curve discrete logarithm, but Shor’s method dispatches that one too, since factoring and discrete logs turn out to be two faces of the same underlying structure. The uncomfortable twist is that compactness works against it. Because the keys are smaller, the circuit needed to break a 256-bit curve calls for fewer logical qubits, roughly 2,300 in published estimates, than a 2048-bit RSA key does. Researchers have also noted that the same attack needs around a hundred times fewer quantum gate operations against elliptic curves than against RSA. In practical terms it is the easier target, which is sobering given how much infrastructure, including the way how public and private keys work for crypto wallets, depends on it.
Grover and the Symmetric Story
Symmetric encryption tells a calmer story. Ciphers such as AES do not rely on factoring or discrete logarithms; they rely on a key hidden somewhere in an enormous search space. Grover’s algorithm speeds up that search, but only quadratically, which roughly halves the effective key strength rather than collapsing it. A 128-bit key drops to about 64 bits of protection, which is uncomfortable, while a 256-bit key falls to roughly 128 bits, which remains far out of reach for any foreseeable machine. The remedy is simply to use longer keys, which is one reason why AES-256 beats AES-128 matters more than ever. Hash functions like SHA-256 and SHA-3 are touched in the same mild way and stay safe at current sizes. In short, the symmetric encryption that still holds up under this kind of attack keeps protecting everyday data, and the genuine danger remains Shor’s work, not Grover’s.
What It Actually Takes
None of this runs on the noisy, few-hundred-qubit machines that exist today. Breaking real keys needs a fault-tolerant computer with thousands of stable logical qubits, each assembled from many error-corrected physical ones. The largest numbers ever factored with the algorithm on genuine hardware are 15 and 21, which sounds reassuring until you watch how fast the estimates are moving. In 2019 a widely cited study put the cost of breaking RSA-2048 at about 20 million physical qubits running for eight hours. By May 2025 a follow-up had cut that to under one million qubits, a twentyfold reduction that came entirely from smarter algorithms and error correction rather than new hardware. The chart below traces the trajectory, and the direction is the whole point. Every improvement in error-correcting codes pulls the timeline forward, and none of those gains depends on a single hardware breakthrough.
What Breaks and What Survives
Most experts now place a cryptographically capable machine somewhere in the 2030s, with at least one major laboratory targeting 2029. It helps to separate the casualties from the survivors before then. Public-key systems built on integer factoring or discrete logs are the ones in real danger; symmetric ciphers and hashes mostly need bigger numbers, not new designs. The next table lays out the divide so you can see at a glance which parts of a typical stack need urgent attention and which can wait.
| System | Hard problem it relies on | Quantum threat | Status |
|---|---|---|---|
| RSA-2048 | Integer factoring | Shor’s | Broken |
| ECC / ECDSA (256-bit) | Elliptic-curve discrete log | Shor’s | Broken, and first to fall |
| Diffie-Hellman / ECDH | Discrete logarithm | Shor’s | Broken |
| AES-128 | Key search | Grover’s | Weakened |
| AES-256 | Key search | Grover’s | Safe |
| SHA-256 / SHA-3 | Preimage search | Grover’s | Safe |
The Fix Already Exists
The reassuring part is that defenders saw this coming. In August 2024 the United States standards body finalized its first three post-quantum algorithms, built on lattice and hash-based math that neither Shor’s nor Grover’s routine can unwind. These are the cryptographic standards built to resist them, and adoption is already underway across browsers, messaging apps, and chipsets. The urgency comes from what analysts call harvesting now to decrypt later: an attacker can record encrypted traffic today and simply wait for a capable machine, which means any data that must stay secret into the 2030s is effectively exposed already. That is why forward-looking teams are future-proofing devices against quantum threats now, pairing classical and post-quantum methods rather than waiting for a single clean switchover.
Frequently Asked Questions
Can quantum computers break RSA today?
No. On real hardware, the algorithm has only factored the numbers 15 and 21 so far. Breaking such a key requires a fault-tolerant machine with hundreds of thousands to millions of physical qubits, which does not yet exist. Most forecasts point to sometime in the 2030s, though the resource estimates keep falling.
Is ECC safer than RSA against quantum attacks?
No, and this surprises people. Elliptic-curve cryptography uses smaller keys for equivalent classical security, so the quantum circuit that breaks it needs fewer qubits and far fewer gate operations. On nearly every published estimate, ECC falls before RSA, which is why systems that depend on it deserve early attention.
Does Grover’s algorithm break AES?
Not in any practical sense. Grover’s algorithm provides only a quadratic speedup, which halves effective key strength. AES-128 weakens to roughly 64-bit security, but AES-256 retains around 128-bit security and stays well beyond reach. Using 256-bit keys and longer hashes neutralizes the concern.
What is harvest now, decrypted later?
It is the practice of capturing encrypted data today and storing it until a quantum computer can decrypt it. The threat is immediate for anything with a long shelf life, such as medical records, intellectual property, or state secrets, because that information is being copied while it is still protected only by vulnerable algorithms.
What should I actually do about it?
Start by finding every place your systems use public-key cryptography, prefer AES-256 and SHA-256 or stronger for symmetric work, and plan a move to the standardized post-quantum algorithms. Running classical and quantum-resistant methods side by side during the transition keeps services working without leaving a gap.
The Bottom Line
The story of RSA and elliptic-curve cryptography is not that they were poorly designed; they are elegant systems that held up for half a century against the only computers anyone had. The shift is that a different kind of machine attacks the exact structure their security depended on, turning slow problems into fast ones. Shor’s work is the real reckoning, ECC is the softer target, and Grover’s algorithm is the lesser worry that bigger keys already answer. The encryption protecting the internet is not broken yet, but the blueprint for breaking it is published, the numbers required keep shrinking, and the replacements are ready. The smart move is to understand the mechanism and migrate on your own schedule, well before someone else sets it for you.
References
- P. W. Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, Proc. 35th FOCS, 1994.
- C. Gidney and M. Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2019) — https://arxiv.org/abs/1905.09749
- C. Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits (2025) — https://arxiv.org/abs/2505.15917
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms, ASIACRYPT 2017.
- NIST, NIST Releases First 3 Finalized Post-Quantum Encryption Standards (13 August 2024) — https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards
