up:: The Threat MOC
Breaking Today’s Cryptography
A quantum computer breaks today’s cryptography through exactly two algorithms, and they do wildly different amounts of damage. Shor’s algorithm efficiently factors large numbers and solves discrete logarithms, so it demolishes public-key cryptography (RSA, elliptic-curve, Diffie-Hellman) completely, private keys become recoverable from public ones. Grover’s algorithm only speeds up brute-force search by a square root, so it merely halves the strength of symmetric ciphers like AES-256 and hashes like SHA-256, which a longer key restores. That single difference, total collapse on one side and a manageable trim on the other, is the most useful thing in this whole section, because it’s why the post-quantum migration is urgent for some systems and almost a non-event for others.
Map of content
A short overview of how a quantum computer breaks today’s cryptography, and the index that routes you to every note in this section. Skim it to get oriented, then follow the links to go deep.
The short version:
- Two quantum algorithms matter for cryptography, and only two. Shor’s algorithm and Grover’s algorithm.
- Shor’s is the catastrophe. It solves factoring and the discrete logarithm efficiently, which are the exact hard problems public-key cryptography rests on. A capable quantum computer running Shor’s ends RSA, ECC, and DH outright.
- Grover’s is the nuisance. It gives a quadratic (square-root) speedup on blind search, which halves the effective strength of symmetric crypto. The fix is a bigger key, so AES-256 stays safe and SHA-256 stays useful.
- The honest headline runs deeper than “quantum breaks encryption.” Quantum shatters the public-key half and lightly dents the symmetric half.
- That asymmetry drives everything downstream. The transition is overwhelmingly a public-key migration, and symmetric primitives are part of the fix rather than the exposure.
An everyday way to picture the difference
Imagine your security rests on two kinds of locks. The first kind is a puzzle box whose secret is hidden inside a math riddle, and Shor’s algorithm is a key that reads the riddle and pops the box open in an afternoon, no matter how big the box. That’s public-key cryptography, and once the key exists, every one of those boxes is open. The second kind is a plain combination padlock with a huge number of settings and no shortcut, and Grover’s algorithm is an attacker who can try the settings faster, in about the square root of the usual number of guesses. Faster guessing is a real problem for a small padlock, and the answer is simple, reach for a padlock with far more settings. That’s symmetric cryptography, and doubling the size of the lock puts it back out of reach.
What is Shor’s algorithm?
Shor’s algorithm is a quantum algorithm, published by Peter Shor in 1994, that factors large integers and solves discrete logarithms in polynomial time, which is fast enough to break the public-key cryptography securing most of the internet. It works by converting factoring into a period-finding problem, then using the quantum Fourier transform to measure the hidden repeat-rate of a function directly instead of searching for it. That reframing is why the speedup is exponential rather than incremental. It’s a different way of asking the question, not a faster version of the old search.
The reach is total for the families it touches. Feed Shor’s algorithm a public RSA key and it hands back the private key by factoring the modulus. Feed it a public elliptic-curve point and it recovers the secret scalar. Everything built on those primitives, key exchange, digital signatures, and the certificates behind PKI and TLS, loses its guarantee at that moment.
Source: Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing 26(5), 1997, arXiv:quant-ph/9508027.
What is Grover’s algorithm?
Grover’s algorithm is a quantum search algorithm, published by Lov Grover in 1996, that finds a target inside an unstructured space of N possibilities in about √N steps instead of the up-to-N steps a classical brute-force search needs. That square-root relationship is called a quadratic speedup, and it’s provably close to the best any quantum algorithm can do for pure unstructured search. Grover doesn’t solve a cipher’s underlying math or find hidden structure. It just makes blind guessing faster.
In cryptography that quadratic speedup does one specific thing, it halves the effective security of a symmetric key or a hash. A key with n bits has 2^n possible values, and Grover cuts the search to about 2^(n/2) tries, which is the same as cutting the bits of security in half. So the effect is a smaller security margin, restored by a bigger parameter, rather than a collapse.
Source: Lov K. Grover, “A fast quantum mechanical algorithm for database search,” 1996, arXiv:quant-ph/9605043.
Why does one break everything and the other barely matter?
The two algorithms deliver completely different kinds of speedup, and that difference decides the entire shape of the migration:
- Shor’s gives an exponential speedup against structured math. Public-key cryptography rests on two problems with rich hidden structure, factoring and the discrete logarithm, and Shor’s dissolves that structure, removing the hard problem the whole scheme stands on rather than merely shrinking a key’s strength. So RSA, ECC, and Diffie-Hellman fall completely and have to be replaced with new post-quantum algorithms.
- Grover’s gives only a quadratic speedup against blind search. Symmetric ciphers and hashes have no mathematical shortcut to exploit, so the only quantum attack is faster guessing, and a square-root gain just halves the margin. AES and SHA-256 keep working with larger parameters.
The deeper reason sits underneath both. Quantum computers are spectacular at problems that hide a periodic or algebraic structure and ordinary at problems that hide nothing, which is why factoring falls and brute force only bends. That’s the whole asymmetry, and it’s why the risk models put public-key confidentiality and trust first, and why the transition is mostly a public-key story. For the deepest treatment of which primitives sit on which side, see Quantum-Vulnerable Algorithm.
Shor’s vs Grover’s, side by side
The clean contrast between the two algorithms is worth keeping in one place:
| Property | Shor’s algorithm | Grover’s algorithm |
|---|---|---|
| Speedup | Exponential | Quadratic (square-root) |
| Attacks | Structured math (factoring, discrete log) | Unstructured brute-force search |
| Hits | Public-key crypto (RSA, ECC, DH) | Symmetric crypto (AES) and hashes (SHA-256) |
| Effect | Total break, private key recoverable | Halves effective strength |
| Fix | Replace the algorithm | Use a bigger key or hash |
| Published | Peter Shor, 1994 | Lov Grover, 1996 |
Sources: Shor, arXiv:quant-ph/9508027; Grover, arXiv:quant-ph/9605043; NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, csrc.nist.gov/pubs/ir/8105/final.
What actually breaks, and what survives?
Sorting your cryptography into these buckets is the first useful move in any migration, because the bucket decides the work. Public-key algorithms in the top rows get replaced with a post-quantum standard, and symmetric algorithms in the lower rows get upsized or kept as is:
| Algorithm | Quantum attack | Verdict | Response |
|---|---|---|---|
| RSA (encryption and signatures) | Shor’s | Broken | Replace (ML-KEM / ML-DSA) |
| DH / DHE | Shor’s | Broken | Replace (ML-KEM) |
| ECDH, ECDSA, Ed25519 | Shor’s | Broken | Replace (ML-KEM / ML-DSA) |
| AES-128 | Grover’s | Weakened to ~64-bit | Move to AES-256 |
| AES-256 | Grover’s | ~128-bit, safe | Keep |
| SHA-256 | Grover’s | ~128-bit preimage, fine for most | Keep, SHA-384 for high assurance |
| SHA-3 | Grover’s | Mostly safe | Keep |
The pattern is the whole point. Everything Shor’s touches is public-key and has to be replaced, and everything Grover’s touches is symmetric and carries forward at a larger size. NIST’s transition guidance (NIST IR 8547) treats the quantum-vulnerable public-key algorithms as slated for deprecation and disallowance on a published schedule, while the symmetric primitives continue at appropriate key sizes.
Source: NIST, NISTIR 8105, csrc.nist.gov/pubs/ir/8105/final; NIST IR 8547 (initial public draft), 2024, csrc.nist.gov/pubs/ir/8547/ipd.
How big a quantum computer does it take?
Breaking real key sizes with Shor’s algorithm takes thousands of logical (error-corrected) qubits, which today translates to somewhere between one million and twenty million noisy physical qubits, depending on the construction. That logical-versus-physical gap is the reason no CRQC exists yet, since a single trustworthy logical qubit is built from hundreds to thousands of error-prone physical ones. The most-cited peer-reviewed resource estimates:
| Target | Attack | Logical qubits | Physical qubits | Runtime | Source |
|---|---|---|---|---|---|
| RSA-2048 | factoring | ~6,100 | 20 million noisy | 8 hours | Gidney and Ekerå, 2021 |
| RSA-2048 | factoring (optimized) | not stated | under 1 million noisy | under 1 week | Gidney, 2025 |
| ECC P-256 | discrete log | 2,330 | millions after correction | not stated | Roetteler et al., 2017 |
Two things stand out. Elliptic-curve cryptography is an easier quantum target than RSA at comparable classical strength, because its shorter keys need fewer logical qubits, so ECC falls first against a quantum attacker. And the physical-qubit estimate keeps dropping as the engineering improves, from twenty million in 2019 to under a million by 2025, so the threshold is a moving research target rather than a fixed wall. As of 2026, leading quantum processors have reached the low thousands of physical qubits, far below what any of these attacks require. The bottleneck is error correction and circuit depth, not raw qubit count, which is why headline qubit-count records don’t move cryptographic risk.
Sources: Craig Gidney and Martin Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, arXiv:1905.09749. Craig Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” 2025, arXiv:2505.15917. Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter, “Quantum resource estimates for computing elliptic curve discrete logarithms,” 2017, arXiv:1706.06752.
Why migrate now if the machine doesn’t exist?
Because the exposure is created today and the fix takes years to deploy, the clock started well before any machine can run the attack. Three facts drive the schedule:
- Harvested data is exposed retroactively. Encrypted traffic recorded today decrypts the day a CRQC arrives. If your data has to stay confidential for a decade, its risk window opened the moment it crossed the wire. This is the logic of Mosca’s theorem: when secrecy lifetime plus migration time exceeds the time until a CRQC, you’re already late. The exposure is called Harvest Now, Decrypt Later.
- The replacements are standardized and available. The public-key functions Shor’s breaks have named successors. ML-KEM replaces RSA and elliptic-curve key exchange, and ML-DSA with SLH-DSA replaces RSA and ECDSA signatures.
- The deadlines are written down. NIST IR 8547 deprecates RSA and elliptic-curve cryptography by 2030 and disallows them by 2035, and CNSA 2.0 sets a parallel timeline for national-security systems, requiring AES-256 and SHA-384 on the symmetric side.
The practical response is to make systems quantum-resistant before the machine exists, using crypto-agility so algorithms can be swapped without rebuilding everything, and hybrid deployments that run a classical and a post-quantum algorithm together so security holds even if one is later found weak.
Source: NIST, “Transition to Post-Quantum Cryptography Standards,” NIST IR 8547 (initial public draft), 2024, csrc.nist.gov/pubs/ir/8547/ipd.
Common misconceptions
- “Quantum breaks all encryption.” It breaks public-key cryptography. Symmetric encryption (AES-256) and hashing (SHA-256) survive with larger parameters, so the transition is overwhelmingly about the public-key layer.
- “Shor’s and Grover’s are basically the same threat.” They’re the two most-conflated ideas in quantum crypto. Shor’s dissolves the math public-key rests on and forces replacement, and Grover’s only halves symmetric strength, which a bigger key restores.
- “A qubit-count record means RSA is about to fall.” The metric that matters is error-corrected logical qubits with enough circuit depth. Today’s thousands of noisy physical qubits sit far below the millions needed, so raw counts on noisy machines aren’t CRQC progress.
- “RSA is stronger than elliptic-curve crypto, so it lasts longer.” Against a quantum attacker the opposite holds. ECC needs fewer logical qubits to break, so ECC P-256 falls before RSA-2048.
- “Grover breaks AES.” Grover halves AES’s brute-force resistance, so AES-128 drops to about 64 bits (worth moving off of) and AES-256 drops to about 128 bits, which stays safe. There’s no new symmetric algorithm family required.
- “There’s nothing to do until a quantum computer exists.” Harvested data is exposed retroactively and migration takes years, so waiting for the machine guarantees you finish too late for anything already collected.
Questions people ask
What are the only two quantum algorithms that matter for cryptography? Shor’s algorithm and Grover’s algorithm. Shor’s breaks public-key cryptography by solving factoring and discrete logarithms, and Grover’s weakens symmetric cryptography by speeding up brute-force search. A handful of other quantum attacks exist against special legacy constructions, but these two carry the whole mainstream story.
Does a quantum computer break AES-256? No. AES-256 is symmetric, so the only quantum attack is Grover’s, which halves its effective strength to about 128 bits, which stays comfortably safe. A machine able to run Shor’s against RSA is nowhere near able to run Grover’s against AES-256 at scale.
Which is more dangerous, Shor’s or Grover’s? Shor’s, by far. It fully breaks the public-key cryptography behind TLS, PKI, and digital signatures, while Grover’s only forces bigger symmetric keys. Shor’s means new algorithms, and Grover’s means larger parameters.
How many qubits does it take to break RSA-2048? Peer-reviewed estimates put it at roughly 6,100 logical qubits, realized as about 20 million noisy physical qubits in a 2021 construction, dropping to under a million physical qubits in a 2025 optimization (arXiv:1905.09749, arXiv:2505.15917). Every one has to be error-corrected, which is the hard part.
Why is symmetric encryption safe when public-key isn’t? Public-key cryptography hides its secret inside a structured math problem (factoring, discrete log) that Shor’s algorithm solves directly. Symmetric ciphers have no such structure, so the only quantum attack is faster brute force, and a square-root speedup is manageable with a longer key.
If no machine can run these attacks, why migrate now? Because of harvest-now-decrypt-later and lead time. Data recorded today decrypts once a CRQC arrives, and a full migration across a large estate takes years. Mosca’s theorem formalizes it: if secrecy lifetime plus migration time is longer than the time to a CRQC, you’re already exposed.
Which of my systems are actually at risk? Anything relying on RSA, ECC, or Diffie-Hellman for key exchange or signatures, which is the urgent public-key half, plus any symmetric layer using undersized keys like AES-128 or legacy ciphers. Modern AES-256 and appropriately sized hashes already carry the margin they need. Sorting your estate this way is what a cryptographic inventory is for.
Go deeper
The two algorithms and what they hit:
- Shor’s Algorithm: the exponential attack that demolishes public-key cryptography by solving factoring and discrete logarithms.
- Grover’s Algorithm: the quadratic attack that halves symmetric strength, fixed by a longer key.
- Quantum-Vulnerable Algorithm: the full map of which algorithms fall completely, which only weaken, and what each is replaced with.
- Post-Quantum RSA: why a bigger RSA key is not the answer to Shor’s algorithm.
Narrow quantum attacks on symmetric constructions:
- Simon’s Algorithm: the period-finding algorithm behind Shor’s, which in a quantum-query model breaks specific constructions like Even-Mansour.
- Offline Simon’s Algorithm: the more realistic variant that drops the superposition-query requirement, still only against those specific constructions, not AES.
Where the threat leads next: the machine that finishes the job is the Cryptographically Relevant Quantum Computer (CRQC); the models that turn this into a dated risk picture live in the risk models; the standardized replacements are the new standards; and how to actually roll them out is the transition.
Everything here is the map, given freely. When your team needs this turned into a cryptographic inventory and a dated plan for your own systems, that’s the work I do, and there’s an alignment briefing for it.
Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.