Quantum Cryptanalysis: What Actually Breaks

Shor's algorithm breaks today's public-key cryptography — RSA and elliptic curves — outright, because it exploits their hidden mathematical structure with an exponential speedup. Symmetric ciphers and hash functions largely survive: Grover's algorithm only halves their effective security bits, so AES-256 and SHA-256 remain safe. Both attacks are proved theory, but running them at cryptographic scale requires error-corrected machines far beyond any hardware that exists today.

What does a quantum computer actually break?

Modern cryptography splits into two families. Public-key (asymmetric) cryptography — RSA, Diffie-Hellman, elliptic-curve schemes like ECDSA and X25519 — lets two parties who have never met agree on secrets or verify signatures. Its security rests on specific math problems: factoring huge numbers, or computing discrete logarithms (undoing repeated multiplication in a finite group — a fixed, closed set of values where multiplying any two of them always lands on another value in the set). Symmetric cryptography — block ciphers like AES and hash functions like SHA-256 — assumes only that the best attack is roughly brute force: trying keys until one works.

The quantum threat is asymmetric in every sense. Shor's algorithm solves factoring and discrete logarithms in polynomial time — the cost grows like a modest power of the key length rather than exponentially — which kills RSA and elliptic curves at any practical key size, once a large enough machine exists. Against symmetric crypto the best known generic quantum attack is Grover's algorithm, which speeds up brute-force search only quadratically: a search over N possibilities takes about √N steps instead of N. Quadratic sounds dramatic; the worked example below shows why it usually is not.

Both results are proved theory — the algorithms are mathematically correct. What is not close to existing is hardware that can run them at cryptographic sizes. This chapter works both halves honestly, using the evaluation filter from chapter 1: verified speedup, yes — then count the full end-to-end cost.