The quantum threat: Shor and Grover
Why cryptography is migrating to post-quantum algorithms
How it works
A large, fault-tolerant quantum computer running Shor's algorithm could solve factoring and discrete logarithms efficiently, breaking RSA, Diffie-Hellman, ECDH, ECDSA and EdDSA. Grover's algorithm gives only a quadratic speedup for brute-force search, which is commonly summarised as halving the effective key strength of symmetric ciphers, so doubling key length (AES-256) restores the margin. No such machine is publicly known to exist yet, but encrypted data captured today could be decrypted later ('harvest now, decrypt later').
Strengths
- Symmetric cryptography and hashes survive with larger keys and outputs.
- NIST published replacement public-key standards (FIPS 203, 204 and 205) in August 2024.
Weaknesses and known attacks
- All widely deployed public-key encryption, key exchange and signatures are affected by Shor's algorithm.
- Migration takes years because algorithms are embedded in hardware, protocols and certificates.
Use it for
- Planning: build a cryptographic inventory and design for crypto-agility
- Prioritising long-lived secrets for hybrid post-quantum key exchange
Don't use it for
- Assuming symmetric encryption must be replaced; it needs larger keys, not new algorithms
Exam tip
Shor breaks asymmetric (RSA, DH, ECC). Grover weakens symmetric and hashes, so use AES-256 and larger hash outputs. 'Harvest now, decrypt later' is why migration starts before quantum computers arrive.