Shor vs Grover: what breaks and what only weakens

The quantum threat to cryptography comes down to two algorithms with very different consequences. Confusing them leads to bad decisions — either panic about AES, or complacency about RSA. Keeping them straight tells you exactly where to spend effort.

Shor's algorithm: the structural break

Peter Shor's 1994 algorithm efficiently solves integer factorization and the discrete logarithm problem on a quantum computer. Those are the precise problems RSA, Diffie-Hellman, and elliptic-curve cryptography rely on being hard. A cryptographically relevant quantum computer running Shor's algorithm can therefore derive a private key from its public key, forging signatures and opening key exchanges. This is not a weakening you can patch with bigger keys — doubling an RSA key size is trivially absorbed by the algorithm's speedup, so the entire family has to be replaced.

Grover's algorithm: the quadratic dent

Lov Grover's 1996 algorithm speeds up unstructured search, letting a quantum computer find a secret among N possibilities in roughly the square root of N steps instead of N. Applied to a symmetric key, that roughly halves the effective security level — a 128-bit key offers something like 64 bits of quantum resistance. Crucially, this is a fixable weakening: move from AES-128 to AES-256 and you are comfortably back above any practical threat, because Grover's quadratic speedup is far gentler than Shor's exponential one. Hash functions are similarly addressed with longer outputs.

Why this shapes the migration order

Because Shor's break is total, every RSA and elliptic-curve deployment is in scope. Because harvest-now-decrypt-later applies to confidentiality, key exchange protecting long-lived data comes first, with signatures following. And because Grover only dents symmetric crypto, you do not need to rip out AES — a common and costly misconception. The threat is precise, and so is the response.