Shor, Grover & What Actually Breaks

Four articles built the ladder: keys, the two encryption families, the quantum machine, and its three strange ideas. Now we point that machine at cryptography — and remarkably, only two recipes matter, each named for its discoverer.

Shor’s algorithm: the total break

In 1994, mathematician Peter Shor found a quantum recipe that solves the exact “one-way street” underneath public-key cryptography. Recall the mailbox: its safety rested entirely on the belief that nobody can take a large number and quickly recover the two primes that were multiplied to make it — a task called factoring.

For a classical computer, factoring a number of the size RSA uses is so slow that all the world’s supercomputers running together for longer than the age of the universe would not finish. Shor’s algorithm arranges the quantum engine — superposition, entanglement, interference — so that the wrong factors cancel and the right ones ring out. The task collapses from “effectively impossible” to “a matter of hours” on a large enough quantum computer.

And it isn’t only RSA. The same hidden mathematical structure (a “periodicity” Shor’s method uncovers) sits underneath elliptic-curve cryptography (ECC) and Diffie–Hellman key exchange too. So one algorithm topples the entire public-key family at once.

What is that “periodicity”? If you keep multiplying a number by itself and take the remainder each time, the results eventually fall into a repeating cycle — and the length of that cycle secretly reveals the factors. Finding the cycle length is hopeless for a classical computer, but it is exactly what a quantum computer’s interference is good at surfacing. That single trick — turning factoring into cycle-finding — is why Shor’s effort grows only polynomially (roughly with the number of digits) rather than exponentially. “Polynomial” is the technical word for efficient: the work rises gently enough that bigger keys can’t outrun it.

Why a bigger key can’t save RSA

A natural hope: if quantum computers factor today’s numbers, just use much bigger numbers. It doesn’t work. Shor’s method stays efficient as the numbers grow — its effort rises only gently with size, while the security you’d need rises far faster. To outrun a quantum computer you’d need keys so gigantic they’d be unusable, and even then only briefly. This is why the response can’t be “bigger RSA” — it has to be different maths entirely, built on one-way streets Shor can’t reverse. That is precisely what the NIST standards in The New Rulebook provide.

Grover’s algorithm: the mild dent

In 1996, Lov Grover found a quantum recipe for searching. If you must find one needle in an unsorted haystack of N items, a classical computer may have to check up to N straws. Grover’s algorithm finds it in roughly the square root of N tries.

“Square root” sounds dramatic — and for some tasks it is a real speed-up — but for cryptography it is surprisingly gentle. Attacking symmetric encryption like AES by brute force means searching the haystack of all possible keys. Grover square-roots that effort. The crucial point is what “square-rooting” does to key strength: it effectively halves the number of security bits. A 128-bit key drops to about 64 bits of quantum-effort — uncomfortable; a 256-bit key drops to about 128 bits — still far beyond reach.

Why doubling the size fixes symmetric

So the fix is almost embarrassingly simple: double the key length. Move from AES-128 to AES-256 and the haystack grows so enormously that even Grover’s square-root shortcut lands an attacker right back where they started — comfortably, durably safe. No new algorithm, no new maths; just a bigger, already-standard key.

The same mild logic covers hash functions — the algorithms that produce a fixed “fingerprint” of data (like SHA-256). Grover-style attacks are blunted by using a longer output (e.g. SHA-384/512). Symmetric cryptography and hashing therefore survive the quantum era with only modest, well-understood adjustments.

The scorecard: what breaks, what bends

Notice the clean line: everything Shor touches is public-key and must be replaced; everything Grover touches is symmetric or hashing and merely needs bigger sizes. That is the entire quantum threat to cryptography, on one page.

You’ve finished the foundations

Take a breath — you now understand the quantum threat more precisely than most professionals. To recap the whole Foundations ladder:

• Security lives in the key, not a hidden method (Article 1).
• Two families: symmetric lockbox and public-key mailbox (Article 2).
• A quantum computer is a strange specialist, not a faster everything-machine (Article 3).
• It runs on superposition, entanglement, measurement plus interference (Article 4).
• Shor breaks public-key; Grover only dents symmetric (this article).

Everything that follows builds on this one split. The Threat explains why it’s urgent today — the “harvest now, decrypt later” attack — and exactly what falls when public-key falls: certificates, TLS, identity, PKI.

Shor’s algorithm

Quantum method that efficiently factors large numbers and solves related problems — breaks RSA, ECC, Diffie–Hellman.

Grover’s algorithm

Quantum search that roughly square-roots brute-force effort — halves symmetric key strength; fixed by doubling key size.

Factoring

Recovering the prime numbers multiplied to make a given number — RSA’s one-way street.

Hash function

An algorithm producing a fixed-length fingerprint of data (e.g. SHA-256); only mildly affected by quantum.

RSA (Rivest–Shamir–Adleman)

The classic public-key algorithm, named after its inventors; broken by Shor.

ECC (Elliptic-Curve Cryptography)

Public-key crypto built on elliptic curves; smaller keys than RSA, also broken by Shor.

Diffie–Hellman (DH)

The classic public-key key-exchange method; broken by Shor.

AES (Advanced Encryption Standard)

The mainstream symmetric cipher; only halved by Grover, so a bigger key restores safety.

What to carry forward

• Shor = total break of public-key (RSA/ECC/DH) → must be replaced; bigger keys don’t help.
• Grover = mild dent to symmetric/hashing → just use bigger sizes (AES-256).
• The clean rule: public-key replaced, symmetric enlarged.
• This split is the foundation of every later part — the standards, the assessment, the migration.

Next up — The Threat: Harvest now, decrypt later — why an attacker recording your encrypted data today already threatens secrets that must last years. (See the series catalogue for the roadmap.)

Understand it in your own words

Paste into any AI assistant to check yourself:

I just finished the "foundations" of the quantum threat to cryptography.
Quiz me one question at a time, correcting me gently:

1. What does Shor's algorithm do, and which cryptography does it break?
   Why can't I just use a bigger RSA key to escape it?
2. What does Grover's algorithm do? Why is "square-root speed-up" only a
   MILD problem for AES?
3. What's the simple fix that keeps symmetric encryption (AES) and hashes
   safe against Grover?
4. State the clean rule: which whole family must be REPLACED, and which
   just needs BIGGER sizes?
5. Why does this one split drive the entire post-quantum migration?