The quantum threat to cryptography: Shor's and Grover's algorithms
In short: A large, error-corrected quantum computer running Shor's algorithm could break RSA, elliptic curve cryptography and Diffie-Hellman, which protect most key exchange and digital signatures today. Grover's algorithm only weakens symmetric ciphers and hashes, so larger key sizes are enough. The fix for public-key cryptography is to move to post-quantum algorithms.
What is at risk and why
Almost every secure connection you make relies on public-key cryptography. TLS uses it to agree session keys, VPNs use it to authenticate peers, software updates use it for signatures, and PKI certificates bind identities to keys. The most widely used public-key algorithms are RSA, Diffie-Hellman (DH) and elliptic curve cryptography (ECC), including ECDH and ECDSA. Their security rests on maths problems that are very hard for classical computers: factoring large numbers and computing discrete logarithms.
A sufficiently large, error-corrected quantum computer, often called a cryptographically relevant quantum computer (CRQC), would make those problems easy. No such machine is publicly known to exist today, and estimates of when one might appear differ widely. Security agencies nevertheless treat the threat as serious, because migrating cryptography takes many years.
Shor's algorithm
In 1994 Peter Shor showed that a quantum computer could factor large numbers and solve discrete logarithms in polynomial time, an exponential improvement on the best known classical methods. Practically, that means:
- An RSA private key could be derived from its public key.
- Elliptic curve and finite-field Diffie-Hellman key exchanges could be broken, exposing session keys.
- ECDSA and RSA signatures could be forged, undermining certificates and code signing.
Making RSA keys longer does not help meaningfully, because Shor's algorithm scales efficiently. The answer is to replace these algorithms with ones built on different maths, which is what post-quantum cryptography provides. Published estimates of the quantum resources needed to break RSA-2048 have fallen as algorithms improve, but they remain far beyond any machine available today.
Grover's algorithm
In 1996 Lov Grover described a quantum algorithm that searches an unstructured space quadratically faster than classical brute force. Against a symmetric key of n bits, it reduces the work from about 2n to about 2(n/2) steps, in theory. In practice the speed-up is smaller still, because Grover's algorithm is hard to run in parallel and needs long, error-free computation. The usual guidance is therefore simple: prefer AES-256 where long-term protection matters, and use hash functions such as SHA-256 or SHA-384 with adequate output sizes.
Which systems are most exposed
| Use | Algorithm today | Quantum risk | Urgency |
|---|---|---|---|
| TLS and VPN key exchange | ECDHE, DH | Recorded traffic could be decrypted later | High: act now |
| Long-lived signatures (firmware, root CAs) | RSA, ECDSA | Forgery once a CRQC exists | High for long-lived devices |
| Short-lived authentication | ECDSA, RSA | Only matters once a CRQC exists | Medium |
| Stored data encryption | AES | Limited; use 256-bit keys | Low |
Key exchange is urgent today because of harvest now, decrypt later: adversaries can record encrypted traffic now and decrypt it once quantum capability exists. Signatures matter later for most uses, but devices with long lifetimes, such as industrial controllers or vehicles, need quantum-safe roots of trust built in before they ship.
Tip: a handy exam summary is "Shor breaks, Grover weakens". Public-key algorithms must be replaced; symmetric algorithms need adequate key sizes.
Practice
Why does doubling the RSA key size not solve the quantum threat?
What effect does Grover's algorithm have on AES-256?
Why is key exchange more urgent than signatures for most organisations?
Key takeaways
- Shor's algorithm would break RSA, DH and elliptic curve cryptography.
- Grover's algorithm only weakens symmetric ciphers and hashes; use AES-256.
- No cryptographically relevant quantum computer is publicly known today.
- Key exchange is urgent because of harvest now, decrypt later.
- The fix for public-key cryptography is post-quantum algorithms, not longer keys.
Original content written by Mohamed Fayas for FM TecHub. © 2026 FM TecHub. You're welcome to share a link to this page; please don't copy the text elsewhere without permission.