What a quantum computer actually breaks
Shor’s algorithm ends RSA, finite-field Diffie–Hellman and elliptic curves; Grover’s algorithm does much less than the headlines suggest
On this page — 7 sections
- Two algorithms, two very different effects
- The asymmetric column, which is where the damage is
- The symmetric column, and why the headline is wrong
- Primitive by primitive
- Why hash-based and symmetric constructions are comparatively durable
- The real operational shock is size
- What we will not state as settled fact
“Quantum computers break all encryption” is false, and repeating it makes the real problem harder to fund. Two quantum algorithms matter for cryptography, and they have very different effects. One collapses the security of every asymmetric primitive in mainstream use. The other shaves a square root off the cost of brute-force search, which is a real but survivable degradation. Knowing which is which tells you where to spend.
Two algorithms, two very different effects
Shor’s algorithm, published in 1994, gives an efficient method for integer factorisation and for computing discrete logarithms in finite fields and elliptic-curve groups. Those three problems are the entire security basis of the public-key cryptography deployed today. When the problem is efficiently solvable, the primitive built on it is not weakened. It is finished.
Grover’s algorithm, published in 1996, searches an unstructured space of size N in about the square root of N steps. Applied to a symmetric key or a hash pre-image, that is a quadratic speed-up. A quadratic speed-up against a 256-bit key leaves an adversary facing work on the order of 2^128, and it does so only with a very long serial computation that parallelises poorly. This is the difference between a break and a discount.
- Shor’s algorithm
- Factoring and discrete logarithms. Effect: structural break of RSA, finite-field DH and ECC. Mitigation: replace the primitive.
- Grover’s algorithm
- Unstructured search, including key search and hash pre-images. Effect: quadratic cost reduction. Mitigation: choose a larger parameter.
The asymmetric column, which is where the damage is
Everything in this group depends on one of the two problems Shor solves, so everything in this group goes together. There is no ordering in which RSA falls and elliptic curves survive.
- RSA, for both encryption and signatures, rests on the difficulty of factoring a large modulus.
- Finite-field Diffie–Hellman, including the older TLS and IKE groups, rests on the discrete logarithm problem in a multiplicative group.
- Elliptic-curve cryptography rests on the discrete logarithm problem in a curve group. This covers ECDH, X25519, ECDSA and Ed25519, and it covers the curve-based components inside protocols that do not advertise them.
Elliptic curves are, if anything, the more fragile case. Their small key sizes come from the difficulty of the underlying problem for classical attackers, and Shor removes exactly that advantage. A 256-bit curve is a smaller quantum computation than a 2048-bit modulus, not a larger one.
The symmetric column, and why the headline is wrong
Symmetric ciphers, message authentication codes and hash functions are not built on factoring or discrete logarithms. They are built on confusion, diffusion and iteration, and no known quantum algorithm exploits that structure. What remains is generic search, and generic search is what Grover accelerates.
This is why AES-256 and SHA-384 remain sensible selections under a quantum threat model, and why the NSA’s CNSA 2.0 suite continues to specify them alongside the new post-quantum algorithms rather than replacing them. It is also why the claim that quantum computing ends all encryption should make you doubt whoever said it.
The cheap wins are in this column
Raising a cipher from AES-128 to AES-256, or a digest from SHA-256 to SHA-384, is a parameter change rather than a protocol migration. It rarely touches key formats, certificate profiles or wire sizes. Do this work while the asymmetric migration is still being scoped, not after.
Primitive by primitive
| Primitive | What quantum computing does to it | Practical consequence | Replacement direction |
|---|---|---|---|
| RSA (encryption and signatures) | Shor recovers the private key from the public modulus | Recorded sessions become readable; signatures become forgeable; certificate chains lose their meaning | ML-KEM (FIPS 203) for key establishment, ML-DSA (FIPS 204) for signatures |
| Finite-field Diffie–Hellman | Shor solves the discrete logarithm | A captured handshake yields the session key it negotiated | ML-KEM, run in hybrid with the existing group during transition |
| ECDH and X25519 | Shor solves the elliptic-curve discrete logarithm, with less work than an equivalent RSA modulus | Passive capture today becomes decryptable plaintext later | Hybrid X25519 plus ML-KEM now, ML-KEM alone once the estate allows |
| ECDSA and Ed25519 | Same discrete-logarithm break; the published public key is sufficient | Code signing, device identity, mutual TLS and PKI roots all lose their guarantee | ML-DSA (FIPS 204); SLH-DSA (FIPS 205) for long-lived roots |
| AES-128 | Grover gives at best a quadratic speed-up in key search | Margin thinner than most policies now accept, though not a break | AES-256 |
| AES-256 and ChaCha20 | Grover only; the residual margin stays large | No algorithm change required | Keep; concentrate effort on key management instead |
| SHA-256 | Quadratic speed-up on pre-image search; a smaller reduction against collisions | Adequate for most uses, tight where a signature must remain valid for decades | SHA-384 or SHA-512 where the governing standard calls for it |
| Hash-based signatures (SLH-DSA) | Security reduces to hash pre-image and collision resistance, which degrade only quadratically | Conservative and durable, at the cost of large signatures | FIPS 205, for firmware and trust anchors |
Why hash-based and symmetric constructions are comparatively durable
The durability argument is about how much mathematical structure a primitive exposes. Shor works because factoring and discrete logarithms have periodic structure that a quantum Fourier transform can extract. A well-designed block cipher or hash function is engineered to expose no such structure, which is why the best known quantum attack against it is still generic search.
SLH-DSA inherits that property deliberately. Its security rests on the hash function rather than on a number-theoretic assumption or on the newer lattice assumptions, so it survives a future cryptanalytic result against lattices. That makes it the right choice for keys that must be trusted for a very long time and are rarely used, such as firmware roots and offline trust anchors. The cost is signature size and signing state management, which is why it is a poor fit for high-volume TLS.
Durable is not permanent
Nothing here is a claim of information-theoretic security. Symmetric primitives can and do fall to classical cryptanalysis, which is why SHA-1 and 3DES were withdrawn. Durability here means resistant to the specific quantum algorithms known today, and that is a narrower statement.
The real operational shock is size
Teams expect the hard part to be cryptographic. In practice the disruptive change is dimensional. Post-quantum keys, ciphertexts and signatures are substantially larger than the elliptic-curve objects they replace, and a great deal of deployed software has size assumptions baked into it.
- An X25519 public key is 32 bytes. An ML-KEM-768 encapsulation key is 1,184 bytes, and its ciphertext 1,088 bytes, per FIPS 203.
- An ECDSA P-256 signature is 64 bytes. An ML-DSA-65 signature is 3,309 bytes, per FIPS 204.
- SLH-DSA signatures run from roughly 7 kB upward depending on parameter set, per FIPS 205.
- Certificate chains grow accordingly, which pushes handshakes past single-packet and single-frame assumptions and into extra round trips on lossy links.
- Fixed-width database columns, hardware security module object limits, smart-card storage, embedded firmware slots and protocol fields with 16-bit length prefixes are all common failure points.
This is why we measure before recommending. Proving the latency, handshake-size and throughput impact on your own traffic profile is a separate exercise from choosing an algorithm, and it is covered in Proving the performance impact.
What we will not state as settled fact
You will see a specific number of qubits quoted as the requirement to break RSA-2048. Treat every such figure as an estimate attached to a set of assumptions, because that is what it is. Published estimates differ by orders of magnitude depending on the physical error rate assumed, the error-correcting code chosen, the logical-to-physical qubit ratio that follows, and the tolerated total runtime. Estimates have also moved downward as circuit optimisations improved, which means the current figure is a snapshot rather than a bound.
Our position: the resource estimate is not the load-bearing part of the argument. The timing arithmetic in The migration window, with the arithmetic works from ranges, not from a single number, and reaches a conclusion for long-horizon data under any plausible input.
- Logical-qubit estimate for RSA-2048
- [PLACEHOLDER: current published logical-qubit estimate with citation and stated error-correction assumptions]
- Reported physical-qubit counts in current hardware
- [PLACEHOLDER: latest vendor-announced physical qubit counts with dates and sources]
Out of scope
We do not forecast quantum hardware progress, we do not run our own resource estimates, and we do not publish a qubit-count countdown. AutoPQC classifies the cryptography on your estate against published standards. Predicting the state of quantum engineering is not something we are equipped to do, and we will not pretend otherwise.