Shor's Algorithm: How Quantum Computers Break RSA

TL;DR

Shor's algorithm is a quantum algorithm that factors large integers in polynomial time, collapsing the classical sub-exponential difficulty of factoring into a polynomial-time quantum period-finding problem. This breaks RSA, and the analogous quantum algorithm for discrete logarithms breaks ECC — both foundations of today's TLS key exchange and certificate signatures.

The Classical Hardness Assumption

RSA's security rests on the assumption that factoring a large semiprime $n = p \cdot q$ is computationally infeasible. The best known classical algorithm, the General Number Field Sieve, runs in sub-exponential time:

For a 2048-bit RSA modulus, this remains far beyond the reach of any classical computer.

The Quantum Speedup

Shor's algorithm reformulates factoring as a period-finding problem. Given $n = p \cdot q$, it picks a random $a < n$ coprime to $n$ and uses the quantum Fourier transform to find the period $r$ of:

Once $r$ is found, $p$ and $q$ are recovered efficiently via $\gcd(a^{r/2} \pm 1,\ n)$. This period-finding step runs in $O((\log n)^3)$ time on a quantum computer — polynomial, compared to the classical algorithm's sub-exponential cost.

Why This Matters for TLS

TLS 1.3 key exchange (ECDHE) and certificate signatures (RSA, ECDSA) both rely on problems Shor's algorithm solves efficiently: integer factorization and the discrete logarithm problem. A cryptographically relevant quantum computer — one with enough stable logical qubits to run Shor's algorithm against a 2048-bit key — would retroactively break any traffic captured today under the "Harvest Now, Decrypt Later" threat model. This is the core motivation behind migrating to lattice-based schemes like ML-KEM.