Shor's Algorithm Explained: Why RSA and ECC Will Not Survive a Quantum Computer

In 1994, a mathematician at AT&T Bell Laboratories published an algorithm that, in principle, renders obsolete every form of public-key cryptography the internet currently depends on. Peter Shor's result was not a guess about future capabilities. It was a mathematical proof: on a quantum computer of sufficient size, integer factorisation and the discrete logarithm problem collapse from "computationally infeasible" to "afternoon job". RSA security rests on the first of those problems. Every form of elliptic curve cryptography rests on the second. Both fall to the same core technique.

The reason this article exists in 2026 rather than 1995 is hardware. Shor's algorithm requires a fault-tolerant quantum computer of a scale that does not yet exist. But "does not yet exist" and "will not arrive" are different statements, and the gap between them now has a reasonably well-constrained engineering estimate attached to it. What follows is an equation-free account of what Shor's algorithm actually does, which systems it affects, what it does not break, and what the NIST-standardised replacements look like. For the CISO audience interested in the migration calendar, see the companion article on the PQC migration timeline.

The Algorithm That Changes Everything About Public Key Cryptography

RSA was first published in 1978 by Rivest, Shamir, and Adleman. Its security claim is precise: given a public key that consists of a large number formed by multiplying two primes together, finding those two prime factors is computationally infeasible for a classical computer. Infeasible here is technical, not colloquial. For a 2048-bit RSA modulus, the best classical factoring algorithms would require more operations than there are atoms in the observable universe. The key is published. The door remains locked because no classical computer can find the combination.

Shor's algorithm opens that door by doing something no classical algorithm can: it exploits quantum superposition and interference to find the periodicity of a particular mathematical function, and that periodicity reveals the prime factors directly. The computation does not try all possible factors in sequence. It uses quantum interference to cancel out incorrect paths and amplify the correct one, arriving at the answer in a number of steps that grows roughly as the cube of the key size in bits. Double the key size, and the quantum attack becomes roughly eight times harder, not exponentially harder. That polynomial scaling is why key size increases cannot outrun Shor's algorithm.

Elliptic curve cryptography (ECC) protects a different problem. ECDSA signatures and ECDH key exchange depend on the elliptic curve discrete logarithm problem: given two points on an elliptic curve, one of which is a multiple of the other, finding the multiplier (the private key) is computationally infeasible for classical computers. Shor's algorithm solves the discrete logarithm problem directly, using the same quantum interference technique in a different configuration. A 256-bit elliptic curve key, as used in P-256 and the TLS 1.3 default, provides 128 bits of classical security. That security guarantee disappears on a CRQC running Shor's algorithm.

Shor's 1994 conference paper appeared at the 35th Annual Symposium on Foundations of Computer Science. The full formal result was published in the SIAM Journal on Computing in 1997. Both papers are publicly available. The result has been verified, extended, and optimised by subsequent research over thirty years. There is no credible scientific dispute about whether the algorithm works.

Why Today's Quantum Computers Cannot Run It Yet

Shor's algorithm requires fault-tolerant quantum computation. The quantum circuit for factoring a 2048-bit RSA key contains millions of operations, and each operation must be executed without accumulating errors that corrupt the output. Today's quantum computers cannot meet that requirement.

The current era of quantum hardware is characterised by NISQ (Noisy Intermediate-Scale Quantum) machines: systems with hundreds to low thousands of physical qubits operating at error rates far too high for fault-tolerant computation. IBM's Heron processor (deployed 2024) operates at 133 physical qubits with reduced error rates compared to prior IBM generations. Verify against IBM's current published specification before relying on this figure, as subsequent processor generations may have been deployed. Google's Willow chip, announced in December 2024, demonstrated a significant engineering milestone: below-threshold error correction at 105 physical qubits, meaning errors were suppressed rather than compounded as the system scaled. That milestone confirms the engineering trajectory. It does not change the hardware gap.

The most authoritative published estimate of what Shor's algorithm actually requires comes from Gidney and Ekerå (2021), published in the journal Quantum. Their analysis, using optimised circuit designs under current physical error rate assumptions, concludes that breaking RSA-2048 would require approximately 20 million physical qubits operating for around eight hours. Twenty million. Current best hardware is at 133. Google Willow's below-threshold result at 105 qubits is the necessary precondition for scaling towards fault tolerance, but the distance between the precondition and the destination remains measured in orders of magnitude.

The Gidney-Ekerå estimate is not a ceiling. It represents a specific optimised implementation under specific noise assumptions. As quantum engineering improves, that figure may decrease. Research into more efficient error correction codes and more compact quantum circuits continues. The 20 million figure is the best current public benchmark, not the best achievable figure for hardware designs that do not yet exist.

Every RSA and ECC Deployment in the World Is Affected

The systems at risk are not obscure legacy protocols. They are the cryptographic layer on which the current internet operates.

RSA is used in TLS/HTTPS certificate signatures, encrypted email (S/MIME and PGP), VPN authentication using certificate-based IKEv2, code signing, and document signing. The consequences for PKI specifically are covered in the article on what PKI is and how quantum computers break it. RSA-2048 and RSA-4096 are equally broken by Shor's algorithm on a CRQC. RSA-4096 requires approximately eight times more quantum resources than RSA-2048 to factor (cubic scaling), but that overhead is within the capacity of a sufficiently large fault-tolerant quantum computer. Neither size is quantum-safe.

ECC is used wherever RSA is used, and in several places where RSA is not. TLS 1.3 moved away from RSA key exchange almost universally in favour of ECDHE. ECDSA is the dominant signature algorithm in modern PKI hierarchies. P-256, P-384, X25519, and X448 are all affected. Shor's algorithm solves the elliptic curve discrete logarithm problem, so all of these fall.

Finite-field Diffie-Hellman, used in older TLS 1.2 configurations, IKEv1, and some SSH server configurations, is also broken by Shor's discrete logarithm variant. Organisations that migrated from RSA key exchange to DHE as a "more forward-secure" option carry the same quantum exposure. NIST IR 8547 (November 2024) formally designates RSA, ECDH, ECDSA, DSA, and finite-field Diffie-Hellman for deprecation on this basis.

The "all key sizes are affected" point deserves emphasis because a common response to quantum risk briefings is "we use RSA-4096, so we are safer". Safer by a factor of eight, perhaps, measured in quantum resources. Not safe in any practical sense on a CRQC.

What Shor's Algorithm Does Not Break

AES is fine. SHA-2 is fine. SHA-3 is fine. The quantum threat to symmetric encryption comes from a different algorithm, Grover's algorithm, which provides a quadratic speedup for searching over an unstructured space. Grover's algorithm reduces the effective bit security of a symmetric cipher by half: AES-256 provides approximately 128 bits of effective quantum security, which remains computationally infeasible. AES-128 provides approximately 64 bits of effective quantum security under Grover, which is more concerning for high-value long-term data; AES-256 is the recommended minimum for post-quantum symmetric security.

The practical implication for TLS is structural: the vulnerability is at the key exchange and signature layer, not the session encryption layer. In a TLS session, the bulk data is encrypted with AES. The key exchange (RSA or ECDHE) establishes the AES session key. Shor's algorithm breaks the key exchange, recovers the AES session key, and the AES-encrypted session content becomes readable. The AES encryption itself is not broken; the mechanism that protects the AES key is. Symmetric encryption does not save you if the key establishment is quantum-vulnerable.

Hash functions used in certificate chains, code signing verification, and HMAC constructions are similarly resistant to Shor's algorithm. Post-quantum cryptography is principally a problem of replacing asymmetric algorithms. SLH-DSA (FIPS 205), one of the four NIST-standardised post-quantum signature algorithms, is itself built on hash function security rather than algebraic structure, providing a signature scheme whose quantum resistance reduces to the resistance of the underlying hash function.

The Clock Is Already Running: Harvest Now, Decrypt Later

The cryptographically relevant quantum computer (CRQC) required to run Shor's algorithm at RSA-2048 scale does not exist today. The threat is real but not immediate. That framing, however, misses the current exposure: Harvest Now, Decrypt Later (HNDL).

An adversary with bulk traffic collection capability can capture TLS sessions, VPN tunnels, and encrypted email today and store them for later decryption. The sessions are encrypted under RSA or ECDHE key exchange right now. When a CRQC eventually exists, Shor's algorithm breaks that key exchange retroactively, recovering the session keys, and the stored sessions become readable. The adversary does not need to break the encryption in real time. They need storage capacity and patience.

The NSA noted this attack mode explicitly in its 2021 Quantum Computing and PQC FAQ. The ODNI Annual Threat Assessment for 2023 documented Chinese state-sponsored collection operations against US government and critical infrastructure communications. HNDL is not a hypothetical adversary capability; it is a documented collection practice applied to communications that happen to be currently indecipherable. For any data whose confidentiality requirement extends beyond the Q-Day window (the Global Risk Institute's 2024 Quantum Threat Timeline Report puts the central estimate at roughly fifty percent probability by 2034 to 2035, verify against current source before relying on this figure), the HNDL exposure is present-tense. The QSECDEF HNDL Risk Calculator helps quantify this exposure against specific data retention and confidentiality requirements.

What Replaces RSA and ECC

In August and October 2024, NIST published four post-quantum cryptographic algorithms as final standards, completing an eight-year evaluation process that involved global cryptographic research community input.

ML-KEM (FIPS 203) replaces RSA and ECDH for key encapsulation and key exchange. Its security rests on the hardness of the Module Learning With Errors (MLWE) problem, a lattice-based problem with no known efficient classical or quantum algorithm. ML-KEM was the submission algorithm Kyber; the FIPS name is the authoritative identifier.

ML-DSA (FIPS 204) replaces ECDSA and RSA signatures in general-purpose contexts. SLH-DSA (FIPS 205) is a stateless hash-based signature scheme, the conservative option for high-assurance contexts where long-term verifiability matters more than signature size or speed. FN-DSA (FIPS 206) addresses constrained environments requiring compact signatures. Together, ML-DSA and SLH-DSA cover the full range of enterprise signing use cases previously handled by RSA and ECDSA.

The immediate deployment path for TLS does not require waiting for full PQC migration. Hybrid key exchange combines a classical algorithm (X25519 or P-384) with ML-KEM in a single TLS handshake, specified in IETF RFC 9496 (the X-Wing Hybrid KEM). The hybrid scheme is secure if either component holds. For HNDL exposure, hybrid TLS provides protection from the point of deployment onwards: traffic captured after hybrid deployment requires a quantum attack on ML-KEM, not just on ECDHE. Google Chrome and Cloudflare deployed ML-KEM-768 hybrid key exchange in production TLS from 2023 onwards. The engineering is deployed and validated.

Why Using a Bigger ECC Key Does Not Help

The polynomial scaling property of Shor's algorithm makes key size a delay, not a defence. Roetteler et al. (ASIACRYPT 2017) estimated that breaking a 256-bit elliptic curve key requires approximately 2,330 logical qubits and 485 billion Toffoli gates. The maximum elliptic curve size in common deployment is 521 bits (P-521), which increases the quantum cost by a factor of roughly twenty compared to P-256. That is a marginal change in the context of a fault-tolerant quantum computer already capable of breaking P-256. NIST IR 8547 deprecates all ECC key sizes currently in use, explicitly including the larger ones.

The distinction matters because quantum-safe algorithms are not just longer versions of classical algorithms. ML-KEM, ML-DSA, SLH-DSA, and FN-DSA are different mathematical structures entirely: lattice problems, hash functions, and error-correcting codes whose security does not reduce to integer factorisation or discrete logarithm. There is no known algorithm, classical or quantum, that solves the Module Learning With Errors problem efficiently. The security guarantee is structurally different, not just numerically larger. Upgrading from P-256 to P-521 while waiting for "bigger quantum computers to catch up" is a bet on hardware not scaling. Migrating to ML-KEM changes the security foundation.