Shor, Grover and What Actually Breaks — Quantum-Safe: Foundations

The quantum threat is not that every secret suddenly becomes readable. It is narrower, sharper, and easier to plan for than that. Two quantum algorithms matter most for cryptography: Shor’s algorithm and Grover’s algorithm. Shor’s algorithm is the severe one: it breaks the public-key systems used to exchange keys and prove identity, including Rivest-Shamir-Adleman (RSA), elliptic-curve cryptography (ECC), and Diffie-Hellman. Grover’s algorithm is the manageable one: it gives a speed-up against brute-force search, so symmetric encryption such as the Advanced Encryption Standard (AES) and hash functions need larger sizes, not wholesale replacement.

The threat is specific, not magical

A quantum computer is not simply a faster classical computer. It helps only when a problem can be shaped so that quantum interference amplifies useful answers and suppresses wrong ones. Most everyday computing does not fit that pattern. Unfortunately, two very important cryptographic problems do.

Shor’s algorithm, published in 1994 by Peter Shor, targets the mathematical structure behind the main public-key systems in use today. Grover’s algorithm, published in 1996 by Lov Grover, speeds up unstructured search, which includes trying possible symmetric keys one by one.

That difference is the whole story. Public-key cryptography depends on certain problems being practically irreversible. Shor makes those reversals efficient. Symmetric cryptography depends on the key space being too large to search. Grover makes the search shorter, but not short enough if the key sizes are chosen well.

📌

The useful split. Shor changes which cryptographic algorithms we can trust; Grover mostly changes how large some parameters should be.

Shor breaks public-key math; Grover only dents symmetric key search.

Shor’s algorithm is the total break

RSA is built on factoring. It is easy to multiply two large prime numbers together, but it is extremely hard for a classical computer to recover those primes from the product when the numbers are large enough. That one-way quality is what lets a public RSA key be shared openly while the private key remains protected.

Shor’s algorithm turns factoring into a problem of finding a repeating pattern, often called a period. Quantum computers are unusually good at extracting that kind of pattern when the problem is prepared correctly. With enough reliable qubits and error correction, the private structure behind the public RSA key is no longer hidden.

The same deeper idea also breaks discrete logarithm problems. That matters because Diffie-Hellman key exchange, elliptic-curve Diffie-Hellman, and elliptic-curve digital signatures rely on discrete logarithms in different mathematical settings. The surface details differ, but Shor reaches the same hidden structure.

⚠️

No partial safety. For RSA, Diffie-Hellman, and elliptic-curve cryptography, a cryptographically relevant quantum computer means the public-key protection is effectively gone.

Shor recasts factoring as period-finding, which quantum computers do well.

Why bigger public keys do not solve it

A natural first reaction is to ask whether we can keep RSA or elliptic-curve cryptography by making the keys much larger. That works against many classical attacks because the defender can often increase the workload faster than the attacker can benefit. It does not work well against Shor.

The reason is growth rate. Classical factoring and discrete-log attacks become rapidly harder as key sizes grow. Shor’s algorithm grows much more gently: in technical terms, it runs in polynomial time for the relevant problems. Polynomial time does not mean instant, and the quantum computer must still be very large and fault-tolerant, but it does mean that merely inflating today’s public keys is not a durable defense.

In practice, trying to save RSA with enormous key sizes would create unusable performance and bandwidth costs while still resting on a mathematical problem that Shor is designed to solve. The repair is not bigger RSA. The repair is different public-key mathematics, which is the purpose of post-quantum cryptography.

Grover’s algorithm is the mild dent

Grover’s algorithm is about search. If there are N possible answers and no useful structure to guide you, a classical computer may need to try a large fraction of them. Grover reduces the work to roughly the square root of N.

For symmetric encryption, that means a brute-force key search becomes cheaper. A key with 128 bits of classical security behaves roughly like it has 64 bits against an ideal Grover search. That is a meaningful reduction, but it is not a collapse. If the key is 256 bits, Grover reduces the effective search strength to about 128 bits, which remains beyond practical reach.

This is why AES survives the quantum transition. AES-128 may not be the conservative long-term choice for all high-value data in a quantum-risk model, but AES-256 is widely available, standardized, and already used in many systems. The algorithm does not need to be abandoned; the key size needs to be chosen with quantum search in mind.

✅

The simple fix. For symmetric encryption, doubling the key size restores the security margin lost to Grover’s square-root speed-up.

Hashes bend, but they do not snap

A hash function turns data into a fixed-size fingerprint. Hashes are used for integrity checks, digital signatures, password storage designs, software distribution, certificates, and many other security tasks. Quantum search affects some hash goals in the same broad way it affects symmetric keys: it reduces the cost of finding an input that matches a chosen output.

For preimage resistance, Grover’s algorithm roughly halves the effective strength. A 256-bit hash output gives about 128 bits of quantum search resistance for that goal. If an application needs a larger long-term margin, it can use longer outputs such as those available in the Secure Hash Algorithm 2 family (SHA-2) or the Secure Hash Algorithm 3 family (SHA-3).

Collision resistance, where the attacker wants any two inputs with the same hash, has its own classical and quantum details. The practical planning answer is still similar: avoid short hash outputs, use modern approved hash functions, and choose output lengths that match the lifetime and value of the data.

Use modern hash families such as SHA-2 or SHA-3 rather than obsolete hashes.
Prefer longer outputs for long-lived or high-value integrity guarantees.
Review places where hashes are embedded inside signatures, certificates, tokens, and software update systems.
Do not treat all hash uses alike; password hashing, file integrity, and signature hashing have different threat models.

The scorecard: what breaks and what bends

The clean dividing line is public-key versus symmetric. Public-key systems based on factoring or discrete logarithms are broken by Shor and must be replaced. Symmetric encryption and hashes are weakened by quantum search and need conservative sizes.

RSA is broken by Shor and should be replaced with post-quantum key establishment or signatures where RSA is used today. Finite-field Diffie-Hellman and elliptic-curve Diffie-Hellman are broken by Shor and must be replaced for key agreement. Elliptic-curve signatures are broken by Shor and must be replaced for authentication and code signing. AES is affected by Grover but remains suitable at 256-bit key sizes. Hash functions are affected mainly through search-related attacks and should use adequate output lengths.

The practical consequence is important: the data encrypted in bulk with strong symmetric algorithms may remain safe, but the public-key handshake that protected the symmetric key may not. If an attacker can break the public-key exchange, they may recover the session key and then read the captured traffic. That is why Transport Layer Security (TLS), Public Key Infrastructure (PKI), certificates, and identity systems are central to quantum-safe migration.

Public-key systems break under Shor; symmetric and hashes only need sizing.

What this means for real decisions

For leaders and practitioners, this article turns an abstract quantum topic into a set of concrete choices. The first decision is not which quantum computer will arrive when. The first decision is which of your systems depend on RSA, Diffie-Hellman, or elliptic-curve cryptography for confidentiality, authentication, signing, or trust.

The second decision is data lifetime. Some information loses value in days. Some remains sensitive for decades. Long-lived secrets face a harvest-now, decrypt-later risk: an adversary can record encrypted traffic today and wait for a future quantum computer to break the public-key exchange that protected it.

The third decision is agility. Systems that can swap algorithms cleanly are far easier to move to post-quantum cryptography. Systems with hard-coded algorithms, old devices, unmanaged certificates, or brittle vendor dependencies will need more planning.

Inventory where RSA, Diffie-Hellman, elliptic-curve cryptography, AES, and hash functions are used.
Classify data by how long it must remain confidential or trustworthy.
Move high-value symmetric encryption toward AES-256 where appropriate.
Prefer longer modern hash outputs for long-lived integrity needs.
Plan replacement of vulnerable public-key cryptography with standards-based post-quantum cryptography.

⚠️

Do not wait for certainty. Migration work can begin before a cryptographically relevant quantum computer exists because discovery, testing, vendor coordination, and certificate replacement all take time.

Quantum readiness comes down to inventory, data lifetime, and agility.

What to carry forward

The foundation is now in place. Keys matter because security lives in the key, not in a secret algorithm. Symmetric and public-key cryptography do different jobs. Quantum computers are specialized machines, not universal accelerators. Shor and Grover show exactly where that specialization matters.

The most useful sentence to remember is this: Shor breaks today’s dominant public-key cryptography, while Grover mainly asks us to use larger symmetric keys and hash outputs. That sentence explains why the post-quantum project focuses so heavily on key exchange, signatures, certificates, TLS, PKI, and software signing.

The next layer is urgency. Once public-key cryptography is breakable, old captured traffic, long-lived certificates, identity systems, firmware signatures, and archived data all deserve a fresh look. The quantum-safe journey starts with knowing which locks are actually at risk.

✅

The core verdict. Replace vulnerable public-key cryptography; keep symmetric cryptography and hashes, but size them conservatively.

Key takeaways

Shor’s algorithm breaks RSA, Diffie-Hellman, and elliptic-curve cryptography by efficiently solving the hard problems they rely on.
Bigger RSA or larger elliptic-curve keys are not a durable answer because Shor’s attack scales efficiently with problem size.
Grover’s algorithm speeds up brute-force search, roughly halving the effective security bits of symmetric keys and some hash uses.
AES-256 remains a strong practical choice in a quantum-risk model because Grover still leaves about 128 bits of search effort.
Public-key systems must migrate to post-quantum cryptography, while symmetric encryption and hashes mainly need conservative sizes.
The most urgent planning work is discovery: find where vulnerable public-key cryptography sits in TLS, PKI, identity, signing, applications, and devices.

Glossary

Shor’s algorithm: A quantum algorithm that efficiently solves factoring and discrete logarithm problems, breaking widely used public-key cryptography.
Grover’s algorithm: A quantum algorithm that speeds up unstructured search, including brute-force key search, by roughly taking the square root of the work.
Rivest-Shamir-Adleman (RSA): A public-key cryptographic system whose security depends on the difficulty of factoring a large number into its prime factors.
Elliptic-curve cryptography (ECC): A family of public-key methods based on elliptic-curve discrete logarithm problems, used for key agreement and digital signatures.
Diffie-Hellman: A key exchange method that lets two parties create a shared secret over an open network, traditionally relying on a discrete logarithm problem.
Advanced Encryption Standard (AES): A widely used symmetric encryption algorithm for protecting bulk data with a shared secret key.
Hash function: An algorithm that turns data into a fixed-size fingerprint used for integrity, identification, and many security protocols.
Public Key Infrastructure (PKI): The system of certificates, certificate authorities, policies, and software used to bind public keys to identities.
Transport Layer Security (TLS): The protocol that protects many network connections by authenticating endpoints and establishing encrypted sessions.