How Quantum Computers Break RSA and ECC

To understand why the quantum transition is urgent, you need to understand how a quantum computer breaks RSA and ECC. The answer is a single algorithm — Shor's algorithm — and it is one of the most consequential ideas in computer science.

The Problem: Factoring and Discrete Logs

RSA's security rests on integer factorization: given a large number n = p × q, finding p and q is hard for classical computers.

ECC's security rests on the discrete logarithm problem: given points on an elliptic curve, finding the multiplier is hard classically.

Both problems have no known efficient classical solution. For decades, that was enough.

Shor's Algorithm

In 1994, Peter Shor published a quantum algorithm that solves both factorization and discrete logarithms in polynomial time. In plain terms: a quantum computer running Shor's algorithm can break RSA and ECC efficiently.

The implications are staggering:

• A problem that would take a classical computer longer than the age of the universe becomes solvable in hours on a sufficiently large quantum computer.
• No key size helps — Shor's algorithm defeats RSA-2048 and RSA-4096 alike.
• The same algorithm breaks ECC, including the curves used in TLS, Bitcoin and secure messaging.

How It Works (Conceptually)

Shor's algorithm combines quantum superposition with a classical technique called the period-finding problem:

1. Use quantum superposition to evaluate a function at many inputs simultaneously.
2. Use the Quantum Fourier Transform to find the period of that function.
3. From the period, compute the factors (for RSA) or the discrete log (for ECC) with classical post-processing.

The quantum part finds the hidden structure; the classical part turns it into the key. The result is an efficient solution to problems that underpin most public-key cryptography.

What It Takes to Run

Shor's algorithm requires a fault-tolerant quantum computer with enough stable logical qubits:

• Breaking RSA-2048 is estimated to need thousands of logical qubits — which, with error correction, may require millions of physical qubits.
• Breaking common ECC curves needs fewer resources than RSA-2048, making ECC potentially vulnerable sooner.
• Today's machines have noisy physical qubits in the hundreds — far short — but the field is advancing.

Why This Is Urgent Now

Even though no machine can run Shor's algorithm at scale today:

• Harvest-now-decrypt-later: adversaries record encrypted traffic now to decrypt later.
• Migration takes years: large organisations need 5-10 years to migrate.
• Long-lived data: data encrypted today must often stay confidential beyond the expected arrival of a CRQC.

The combination means the threat is already active for long-lived data.

What Shor's Algorithm Does Not Break

Crucially, Shor's algorithm does not break symmetric encryption or hash functions:

• AES is only affected by Grover's algorithm, which gives a quadratic speedup — halving security, not breaking it. AES-256 retains ~128-bit quantum security.
• SHA-256 similarly retains ~128-bit quantum security.
• Post-quantum algorithms (ML-KEM, ML-DSA, SLH-DSA) rely on problems Shor's algorithm does not solve efficiently.

This is why the quantum transition is primarily about replacing public-key cryptography (RSA, ECC) while keeping strong symmetric encryption (AES-256).

The Defence

• Replace RSA and ECC key exchange with post-quantum or hybrid schemes.
• Replace RSA and ECDSA signatures with ML-DSA or SLH-DSA.
• Keep AES-256 for symmetric encryption.
• Use forward secrecy so recorded sessions cannot be mass-decrypted from a single key.
• Encrypt sensitive files independently with a zero-knowledge tool so transport-layer compromise does not expose them.

Bottom Line

Shor's algorithm is the reason the quantum transition exists. It turns the hard problems behind RSA and ECC into easy ones — efficiently, for any key size. We cannot uninvent it. The only defence is to stop relying on the algorithms it breaks, and to protect long-lived data with quantum-resistant cryptography before it is intercepted. The clock started in 1994; the deadline is approaching.