Shor, Grover And What Quantum Computers Actually Break

Headlines often say quantum computers will “break encryption”. That is half right, and the half that is wrong leads organisations to waste effort in some places and underinvest in others. Two quantum algorithms matter for cryptography, and they have very different effects.

Shor’s algorithm breaks the public-key algorithms used for key exchange and signatures. Grover’s algorithm speeds up brute-force guessing, which weakens symmetric encryption and hash functions without breaking them. This article explains each one in plain terms and sets out what NIST, the US standards body, says to do about them.

Shor’s Algorithm: A Shortcut Through The Hard Maths

As the previous article explained, RSA depends on factoring being hard, and Diffie-Hellman and elliptic curve cryptography depend on discrete logarithms being hard. On a normal computer, the best known methods for these problems slow down dramatically as the numbers get bigger, which is why a 2048-bit RSA key is safe from classical attack.

In a paper first posted in 1995, Peter Shor described quantum algorithms that solve both factoring and discrete logarithms in polynomial time.¹ In plain language, the effort grows gently as keys get longer instead of exploding. Making the key bigger therefore buys very little protection. An organisation cannot escape Shor’s algorithm by moving from RSA-2048 to RSA-4096; it has to move to different mathematics.

That is why NIST groups RSA, ECDSA, EdDSA, finite field Diffie-Hellman and ECDH together as quantum-vulnerable. Its draft transition plan proposes deprecating the 112-bit security versions after 2030 and disallowing all of them after 2035.² The plan is still an initial public draft as of October 2026.

The catch is scale. Shor’s algorithm needs a large, error-corrected quantum computer, often called a cryptographically relevant quantum computer (CRQC). NIST’s November 2024 draft states that no such machine exists yet.² How large it would need to be is covered in How Many Qubits To Break RSA, and the Inside Shor’s Algorithm article walks through the steps without equations.

Grover’s Algorithm: Faster Guessing, Not A Shortcut

Symmetric ciphers such as AES and hash functions such as SHA-256 do not rely on factoring or discrete logarithms. The generic way to attack them is to try keys or inputs until one works. In 1996 Lov Grover published a quantum search method that finds a marked item among N possibilities in roughly the square root of N steps, compared with about N divided by two on average for a classical search.³

Applied to a 128-bit key, a square-root speed-up means something on the order of 2 to the power 64 quantum steps instead of 2 to the power 128 classical guesses. That sounds dramatic, but 2 to the power 64 is still a vast number of operations, each of which has to run on an error-corrected quantum machine. The effect is that a symmetric key loses some margin. It does not become breakable the way RSA does.

NIST’s position follows from this. Its draft says the symmetric standards are “significantly less vulnerable to known quantum attacks” than the public-key standards, and that every approved symmetric primitive (a basic building block such as a cipher or hash function) offering at least 128 bits of classical security is believed to meet at least its lowest post-quantum security category.² NIST does not expect to transition away from these standards as part of the post-quantum migration. The only symmetric options it plans to drop are a few at the 112-bit level, which it will disallow in 2030.²

How NIST Measures Post-Quantum Strength

NIST anchors its post-quantum security scale on the symmetric algorithms themselves. Category 1 is defined as being at least as hard to break as a key search on AES-128. Category 3 matches AES-192 and Category 5 matches AES-256. Categories 2 and 4 use collision searches on 256-bit and 384-bit hash functions, with SHA-256 and SHA3-384 as the examples.²

That choice tells you something. NIST would not use AES-128 as the floor for its new quantum-resistant algorithms if it thought AES-128 itself was about to fall to quantum attack. In the same draft, SHA-256 rates Category 2 for collision resistance and Category 5 for preimage resistance.² A collision attack looks for any two inputs that produce the same hash, while a preimage attack has to find an input matching one particular hash, which is a much harder task. That is why the same function earns two different ratings.

What This Means In Practice

The practical lesson is to put effort where the break is. An inventory that flags every use of AES as a quantum risk will bury the real problems. The urgent work is finding where RSA, Diffie-Hellman and elliptic curve algorithms are used for key exchange and signatures, then planning their replacement.

For symmetric cryptography, the job is housekeeping: retire 112-bit options and legacy algorithms that were already weak, and use 256-bit keys where data has a long shelf life. That is a configuration change in most systems. Replacing public-key algorithms, by contrast, touches protocols, certificates, hardware and partners, which is why it takes years.

The difference also shapes timing. Data protected by a quantum-vulnerable key exchange can be recorded now and decrypted later, which is the subject of Harvest Now, Decrypt Later.