Shor's algorithm breaks RSA and ECC

The security of RSA, Diffie-Hellman and elliptic-curve cryptography (ECC) rests on problems that our classical computers cannot solve quickly. A large enough quantum computer changes everything.

Shor's algorithm

In 1994, Peter Shor published an algorithm that, on a quantum computer, factors a large number and solves the discrete logarithm in polynomial time.

This is a breakthrough. The best classical factoring algorithms are sub-exponential: doubling the key size makes the problem astronomically harder. Shor, on the other hand, brings these problems to their knees in a time that grows only as a polynomial in the size of the number.

Yet all of the asymmetric cryptography deployed today rests precisely on these two problems:

• RSA relies on the difficulty of factoring n = p × q;
• Diffie-Hellman and ECC rely on the difficulty of the discrete logarithm.

A large enough fault-tolerant quantum computer would break them all.

What survives: symmetric cryptography

Symmetric cryptography (AES) and hash functions (SHA-2, SHA-3) are not broken, only weakened.

Grover's algorithm (1996) speeds up a brute-force search: it finds a key among N possibilities in roughly sqrt(N) attempts instead of N. This halves the effective security in bits.

Sécurité effective face à Grover
--------------------------------
AES-128  ->  ~64 bits  (jugé insuffisant)
AES-256  -> ~128 bits  (jugé sûr)

The fix is simple and well known: double the key size. Moving from AES-128 to AES-256 restores a comfortable margin. Grover offers only a quadratic gain, not an exponential one: it does not undermine the principle of symmetric cryptography.

The table that sums up the threat

Primitive	Type	Quantum attack	Verdict
RSA	asymmetric	Shor	broken
Diffie-Hellman	asymmetric	Shor	broken
ECC	asymmetric	Shor	broken
AES-128	symmetric	Grover	weakened
AES-256	symmetric	Grover	safe (doubled keys)
SHA-256	hash	Grover	weakened
SHA-512	hash	Grover	safe

The fault line is clear: asymmetric cryptography collapses, symmetric cryptography holds by enlarging the keys.

In summary

Shor's algorithm would break RSA, Diffie-Hellman and ECC in polynomial time on a quantum computer. Symmetric ciphers and hashes are only weakened by Grover, which halves the effective security: AES-256 keeps about 128 bits and remains safe. That is why the urgent migration concerns asymmetric cryptography, replaced by post-quantum cryptography.