Quantum Cryptanalysis: What Actually Breaks

Shor's algorithm breaks today's public-key cryptography — RSA and elliptic curves — completely. It uses their hidden math structure to get an exponential speedup. Symmetric ciphers and hash functions mostly survive. Grover's algorithm only halves their security bits, so AES-256 and SHA-256 stay safe. Both attacks are proven theory. But running them at real key sizes needs error-corrected machines far beyond any hardware that exists today.

What does a quantum computer actually break?

Modern cryptography comes in two families.

Public-key (asymmetric) cryptography includes RSA, Diffie-Hellman, and elliptic-curve schemes like ECDSA and X25519. It lets two people who have never met agree on secrets or check signatures. Its safety rests on certain hard math problems. One is factoring huge numbers. Another is computing discrete logarithms. That means 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 includes block ciphers like AES and hash functions like SHA-256. It assumes only that the best attack is about brute force: trying keys until one works.

An everyday example: public-key crypto is like a mailbox with a slot. Anyone can drop a letter in, but only the owner has the key to open it. Symmetric crypto is like a shared house key: both people hold the same one. Where the picture breaks: a real mailbox can be pried open with a crowbar. Crypto is safe only because the math "crowbar" would take too long — and a quantum computer changes how long for some locks.

The quantum threat is lopsided. Shor's algorithm solves factoring and discrete logarithms in polynomial time. That means the cost grows like a modest power of the key length, not exponentially. So it kills RSA and elliptic curves at any practical key size, once a large enough machine exists.

Against symmetric crypto, the best known general quantum attack is Grover's algorithm. It speeds up brute-force search only quadratically. A search over N options takes about √N steps instead of N. Quadratic sounds dramatic. The worked example below shows why it usually isn't.

Both results are proven theory. The algorithms are mathematically correct. What is nowhere near existing is hardware that can run them at real key sizes. This chapter works both halves honestly, using the filter from chapter 1. Verified speedup? Yes. Then count the full cost.