How Shor’s Algorithm Breaks RSA, ECC, and Diffie-Hellman

At comparable classical security levels, elliptic-curve cryptography (ECC) can be easier to break with Shor’s algorithm than RSA because ECC achieves that security with much smaller parameters (e.g., P-256 vs RSA-3072). Whether ECC ‘falls before RSA’ in practice depends on what RSA key sizes are actually deployed (often RSA-2048) and on the attacker’s cost model (logical qubits, non‑Clifford depth, physical qubits, and wall time). At the logical-circuit level, published estimates include ~2,330 logical qubits and ~1.26×10¹¹ Toffoli gates for P-256 (ECDLP), versus ~1,409 logical qubits and ~6.5×10⁹ Toffoli gates for RSA‑2048 in a recent optimized factoring construction

At equivalent classical security levels (P-256 ≈ RSA-3072), the disparity becomes dramatic: ECC requires 2.6× fewer qubits and 148× fewer Toffoli gates than its RSA counterpart. Finite-field Diffie-Hellman and RSA are both broken by Shor-style quantum algorithms; they share major circuit primitives (notably modular exponentiation and phase estimation), but they are not literally the same problem and may differ in constant-factor resources under a given implementation.

All three cryptosystems reduce to a single quantum-solvable framework – the abelian hidden subgroup problem – meaning one algorithmic breakthrough threatens them simultaneously.

One algorithm, three cryptosystems: Shor’s hidden subgroup attack

RSA, elliptic curve cryptography, and Diffie-Hellman appear mathematically distinct, but Shor’s algorithm reveals a deep structural unity. All three cryptosystems rely on problems that are instances of the Hidden Subgroup Problem (HSP) over finite abelian groups. Integer factoring reduces to finding the period of $f(x) = a^x \bmod N$ in the multiplicative group (ℤ/Nℤ)×. The discrete logarithm problem (DLP) in a cyclic group G of order q reduces to an abelian HSP over ℤq×ℤq. For prime-field Diffie–Hellman with G=𝔽p×, q=p−1. For elliptic-curve groups, q is the (typically prime) order of the base point, and ECDLP likewise reduces to an HSP over ℤq×ℤq.

Shor’s quantum algorithm solves all abelian HSP instances in polynomial time by exploiting the Quantum Fourier Transform (QFT) to extract hidden periodicity from quantum superpositions. This statement refers to the abelian HSP; Shor’s approach does not generalize to arbitrary non-abelian HSP instances (which is why problems like lattice reduction are not known to have Shor-like polynomial-time quantum algorithms). The core circuit structure is consistent across all three attacks: prepare a superposition of inputs, compute the relevant group operation coherently, apply the QFT, then measure to obtain period information. What varies is the group operation circuit – modular exponentiation for RSA and finite-field DH, versus elliptic curve scalar multiplication for ECC – and this variation drives the dramatically different resource profiles.

This unification has a critical practical implication. At the algorithmic level, Shor’s approach applies broadly to factoring and discrete-log-based schemes; at the engineering level, however, different targets can require meaningfully different logical widths, non‑Clifford depths, repetition counts, and physical resources, so an early fault‑tolerant machine may threaten some parameter sets before others.. A cryptographically relevant quantum computer (CRQC) capable of solving any one of these problems possesses the fundamental architectural capability – sufficient logical qubits, gate fidelity, and coherent runtime – to threaten all three. The question is purely quantitative: how many qubits and gates does each specific target demand?

Breaking RSA: period-finding in the multiplicative group

The mathematical reduction

RSA security rests on the difficulty of factoring N=pq, the product of two large primes. Shor’s algorithm converts factoring into order-finding: choose a random a that is coprime to N, then find the smallest r such that a^r ≡ 1 (mod N). If r is even and a^(r/2) ≢ −1 (mod N), then gcd(a^(r/2)±1, N) yields non-trivial factors with high probability. The quantum speedup comes from using phase estimation to extract $r$ from the unitary operation $|y\rangle \mapsto |ay \bmod N\rangle$.

The quantum circuit has three principal components:

• First, a control (phase-estimation) register of approximately 2n qubits (for an n-bit modulus) is initialized into a uniform superposition via Hadamard gates.
• Second, the circuit coherently computes modular exponentiation into a work register (e.g., |x⟩|1⟩ ↦ |x⟩|a^x mod N⟩) using a sequence of controlled modular multiplications; this dominates the non‑Clifford cost. This is the computational bottleneck, accounting for the vast majority of gates.
• Third, the Quantum Fourier Transform extracts the period from the control register, yielding $r$ via continued fraction expansion.

Several modern factoring constructions reduce the phase-estimation (input) width below the classic ~2n regime by using short-discrete-log / compressed period-finding variants (instead of recovering the full period in one shot), trading fewer qubits for additional repetitions and post-processing.

The resource estimation revolution: from 20 million to under 100,000 qubits

The trajectory of RSA-2048 quantum resource estimates over the past decade tells a story of relentless optimization. In 2021, Gidney and Ekerå published the landmark estimate of ~20 million physical qubits and 8 hours using surface codes, requiring approximately 6,189 logical qubits and 2.6 billion Toffoli gates. This assumed a planar nearest-neighbor superconducting architecture with characteristic physical error rate ~10⁻³, surface-code cycle time ~1µs, and classical reaction time ~10µs.

Recent work on approximate / residue-number modular arithmetic shows that factoring can trade fewer logical qubits for far more non‑Clifford work (Toffoli/T), by performing arithmetic over small coprime moduli and correcting approximation statistically. The key insight: instead of exact modular arithmetic requiring full-width $n$-bit registers, the computation uses residues modulo small coprime primes, tolerating controlled approximation errors corrected statistically.

Craig Gidney’s May 2025 preprint from Google Quantum AI synthesized these innovations into a practical construction achieving ~1,409 logical qubits, ~6.5 billion Toffoli gates, and fewer than 900,000 physical qubits – a 20× reduction from the 2021 estimate. Three techniques enabled this leap: approximate residue arithmetic (optimized to reduce Chevignard’s Toffoli penalty 100-fold), yoked surface codes for 3× denser idle qubit storage, and magic state cultivation replacing conventional distillation. The estimated wall-clock runtime is approximately 5 days.

Breaking ECC: scalar multiplication on elliptic curves

Adapting Shor’s algorithm for ECDLP

Given an elliptic curve E over a prime field with base point P and public key Q=xP, the attacker must recover the secret scalar x. Shor’s ECDLP variant uses two control registers of $n$ qubits each (for $n$-bit curve order), preparing a superposition $\sum_{a,b} |a\rangle|b\rangle$. A quantum oracle computes $|a\rangle|b\rangle|R\rangle \mapsto |a\rangle|b\rangle|R + aP + bQ\rangle$, and inverse QFTs on both registers extract the linear relationship that reveals $k$.

The critical difference from RSA lies in the group operation. Where RSA uses modular multiplication – $O(n^2)$ gates per operation – ECC requires elliptic curve point addition, which involves two field multiplications and one field inversion per addition, totaling $O(n^2 \log n)$ gates. This per-operation complexity is higher, but the key sizes are dramatically smaller: 256 bits for P-256 versus 2,048–3,072 bits for RSA at comparable classical security. Since the total circuit scales as $O(n^3)$ for both (the group operation is repeated $O(n)$ times), the smaller $n$ overwhelms the per-bit disadvantage.

The Roetteler et al. (2017) construction – the foundational reference – requires 9n+2⌈log⁡2(n)⌉+109n + 2\lceil\log_2(n)\rceil + 10 9n+2⌈log2​(n)⌉+10 logical qubits, yielding 2,330 for P-256. These registers hold two point coordinates (affine $x,y$) for both input and accumulator points, control registers, and ancillae for reversible modular arithmetic including Montgomery multiplication and binary GCD inversion.

Resource estimates across the literature

The ECC quantum resource landscape has evolved through several key papers:

Roetteler, Naehrig, Svore, and Lauter (2017) established the baseline. For P-256: 2,330 logical qubits, 1.26×10111.26 \times 10^{11} 1.26×1011 Toffoli gates. Their explicit comparison with RSA-3072 (the classical security equivalent) showed RSA requiring 6,146 qubits and $1.86 \times 10^{13}$ Toffoli gates – confirming that “for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA.”

Häner, Jaques, Naehrig, Roetteler, and Soeken (2020) improved the construction through windowing techniques and a reformulated binary Euclidean algorithm for modular inversion, reducing P-256 to approximately 2,124 logical qubits with a 119× improvement in T-gate count.

Gouzien, Ruiz, Le Régent, Guillaud, and Sangouard (2023) took a radically different architectural approach using repetition cat qubits rather than surface codes. Their 256-bit ECDLP estimate: 126,133 physical cat qubits and 9 hours of runtime. An updated 2024 estimate using LDPC cat codes reduced this further to approximately 38,581 cat qubits. The cat qubit approach exploits exponential bit-flip suppression, dispensing with the surface code’s $d^2$ area overhead.

Ha, Lee, and Heo (2024) in Nature Scientific Reports provided the first comprehensive physical qubit estimates for ECDLP under surface codes, finding approximately 5.8 million physical qubits for P-256 and explicitly confirming that “elliptic curve cryptography is more vulnerable to quantum computing attacks at the physical level” than RSA.

Breaking Diffie-Hellman: the RSA twin

Finite-field Diffie-Hellman relies on the discrete logarithm problem in the multiplicative group of $\mathbb{GF}(p)$ – a problem mathematically near-identical to RSA’s integer factoring from a quantum perspective. Gidney and Ekerå’s 2021 paper explicitly addressed both: “We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields.” The modular exponentiation circuits, register layouts, and QFT application are the same; only the classical post-processing differs. Consequently, DH-2048 requires the same quantum resources as RSA-2048, and DH-3072 matches RSA-3072.

Ephemeral Diffie-Hellman (DHE) provides no protection against a real-time quantum attack – if a CRQC exists when the key exchange occurs, ephemeral keys offer no advantage over static ones. However, DHE does mitigate Harvest-Now-Decrypt-Later (HNDL) attacks to a degree: because each session uses fresh keys, there is no long-lived private key whose compromise would retroactively decrypt all past sessions. The adversary must solve a separate DLP instance for each recorded session, rather than recovering a single static key.

ECDH – the elliptic curve variant that dominates modern deployments including TLS 1.3, WireGuard, and Signal – follows the ECDLP cost model, not the FFDLP model. This distinction is critical: ECDH with X25519 or P-256 requires quantum resources proportional to 256-bit operations, while classical DH-2048 requires resources proportional to 2,048-bit operations. ECDH is the more vulnerable target by a wide margin.

The quantitative picture: resource estimates compared

The following table synthesizes the best available estimates across algorithm families. All estimates assume surface code error correction with $p = 10^{-3}$ physical error rate unless noted.

Microsoft’s Azure Quantum Resource Estimator provides a particularly illuminating cross-platform comparison at the physical level. Under “reasonable” gate-based superconducting assumptions: ECC P-256 requires 5.87 million qubits and 21 hours versus RSA-2048’s 25.17 million qubits and 1 day. Under optimistic assumptions: 1.54 million and 11 hours versus 5.83 million and 12 hours. ECC consistently requires roughly 4× fewer physical qubits across every hardware scenario, despite P-256 being classically equivalent to RSA-3072 – which is even harder to factor than RSA-2048.

The historical trajectory of RSA-2048 physical qubit estimates reveals relentless compression: ~1 billion (2012) → 170 million (2017) → 20 million (2021) → 1 million (2025). If comparable optimization efforts were applied to ECDLP circuits – and they have not yet been, to the same degree – ECC estimates could compress similarly.

Why ECC falls before RSA: the quantum security inversion

There is a fundamental mismatch between classical and quantum complexity landscapes. Classical security equivalences exist because the best classical attacks scale differently for each problem. For RSA, the General Number Field Sieve runs in subexponential time $L_N[1/3, 1.923]$; for ECDLP, Pollard’s rho algorithm requires $O(\sqrt{r})$ operations where $r$ is the group order. Because ECDLP is classically harder per bit, the same security level (say, 128 bits) demands 256-bit ECC keys but 3,072-bit RSA keys.

Shor’s algorithm obliterates this advantage. Its complexity is polynomial in the bit-length for both problems – roughly $O(n^3)$ gates where $n$ is the key size. Since quantum resources scale with key size rather than classical security level, the 12:1 key-size ratio between RSA-3072 and P-256 translates directly into a massive quantum resource gap. Roetteler et al. quantified this precisely: P-256 needs 2,330 qubits versus RSA-3072’s 6,146 qubits (2.6× fewer), and $1.26 \times 10^{11}$ versus $1.86 \times 10^{13}$ Toffoli gates (148× fewer). The Toffoli count matters enormously because gates dominate both runtime and failure probability in fault-tolerant computation.

The foundational result from Proos and Zalka (2003) established the ratio: “A 160-bit elliptic curve cryptographic key could be broken on a quantum computer using around 1,000 qubits while factoring the security-wise equivalent 1,024-bit RSA modulus would require about 2,000 qubits.” This 2:1 qubit ratio at equivalent classical security has remained consistent across two decades of refined estimates.

There is an important nuance. Recent optimizations to RSA factoring circuits (particularly Gidney’s 2025 work reducing logical qubits from ~6,189 to ~1,409) have narrowed the gap at common parameter sizes. With Gidney-optimized RSA and Roetteler-baseline ECC, RSA-2048 actually needs fewer logical qubits (1,409 versus 2,330) though vastly more Toffoli gates. Comparable optimization effort has not yet been applied to ECDLP circuits, suggesting the “true” optimized comparison would restore ECC’s disadvantage. The Gu et al. (2025) analysis found that with 2D-local constraints, 256-bit ECC needs only 1/13th the Toffoli gates of RSA-3072 despite requiring 2.25× more qubits in their specific construction.

The bottom line: a CRQC that has just barely crossed the threshold to solve 256-bit ECDLP may not yet be capable of factoring 2048-bit RSA integers. Organizations that migrated from RSA to ECC for classical efficiency gains may have inadvertently increased their quantum exposure.

Where these algorithms live: a deployment audit

The RSA footprint remains vast but is shifting

RSA persists as the dominant certificate algorithm in the web PKI: approximately 75% of TLS certificates still carry RSA public keys, though the trend is firmly toward ECDSA. The most popular cipher suite on the internet – ECDHE-RSA-AES128-GCM-SHA256 – uses RSA for authentication but ECDHE for key exchange, capturing 70% of observed connections. RSA-based key exchange (without forward secrecy) is functionally extinct, prohibited by TLS 1.3 which now covers about 75% of top websites per various estimates.

Beyond web TLS, RSA anchors enterprise infrastructure extensively. Microsoft Active Directory Certificate Services defaults to RSA key pairs. Windows code signing has traditionally required RSA via Authenticode. PGP/GPG defaults to RSA-3072 or RSA-4096 for key generation. On SSH, RSA and Ed25519 are approaching parity on GitHub (~48% each as of January 2025), but RSA dominates on GitLab (~76%) and Launchpad (~90%). Government PKI systems – US Federal PIV, EU eIDAS – still extensively issue RSA-2048 certificates.

ECC dominates every modern protocol

ECC’s deployment is staggering in breadth. TLS 1.3 mandates ECDHE for key exchange, and ~97–98% of all TLS key exchanges now use ECDHE, with X25519 (Curve25519) as the default key share in Chrome and most modern clients. Cloudflare Let’s Encrypt’s Certbot 2.0 switched to ECDSA P-256 certificates by default.

In the authentication layer, over 3 billion passkeys are in active use globally, all built on ECDSA P-256 (ES256) via the FIDO2/WebAuthn standard. Apple’s Secure Enclave and Android’s Keystore both use ECDSA P-256 for hardware-backed key operations. EMV chip payment cards increasingly use ECDSA for offline data authentication, and over 1 billion ePassports in circulation across more than 140 countries rely on ECDSA certificates.

The cryptocurrency ecosystem represents perhaps the largest single deployment of a single ECC curve: Bitcoin and Ethereum both use secp256k1 for all transaction signing. Bitcoin has generated over 1 billion cumulative addresses; Ethereum exceeds 300 million unique addresses. Every transaction on these networks is an ECDSA signature that a quantum computer could forge.

End-to-end encrypted messaging – Signal Protocol (used by Signal, WhatsApp’s 2+ billion users, and Facebook Messenger) – relies on X25519 ECDH for the Double Ratchet key agreement. WireGuard VPN uses X25519 exclusively. Apple code signing requires ECDSA P-256. IEEE 1609.2 specifies ECDSA P-256 for automotive V2X communications.

Diffie-Hellman: ECDH won, classical DH is fading

Classical finite-field DHE accounts for only 1–2% of TLS connections, vastly overshadowed by ECDHE’s 97–98% dominance. IPsec/IKEv2 deployments increasingly use ECDH groups (P-256, P-384) over classical DH groups. The practical Diffie-Hellman threat landscape is overwhelmingly an ECDH story, which means it follows the ECDLP cost model – the more vulnerable one.

Migration priorities: why ECC urgency is underappreciated

The standards are ready

NIST finalized three post-quantum standards in August 2024: ML-KEM (FIPS 203) replaces ECDH/DH key exchange using Module-LWE lattice problems, ML-DSA (FIPS 204) replaces ECDSA/RSA digital signatures using Module-LWE/SIS, and SLH-DSA (FIPS 205) provides a conservative hash-based signature backup. FN-DSA (FALCON, expected FIPS 206) based on NTRU lattices is under review, and HQC – a code-based backup KEM – was selected in March 2025 with a final standard expected in 2027.

The timeline pressure is real

NSA’s CNSA 2.0 mandates for National Security Systems set hard deadlines: software/firmware signing must support CNSA 2.0 algorithms by 2025 and use them exclusively by 2030; web infrastructure by 2025/2033; traditional networking by 2026/2030; full transition by 2035. New NSS acquisitions must be CNSA 2.0 compliant by January 2027. International timelines converge similarly – Australia mandates no traditional asymmetric crypto beyond 2030, the UK targets full adoption by 2035, and the EU’s roadmap mirrors NIST’s.

The blind spot in migration planning

Most PQC migration playbooks prioritize RSA deprecation because RSA is older, more visible in legacy systems, and was already being phased out for performance reasons. This focus risks a dangerous blind spot on ECC, which is simultaneously more ubiquitous in modern systems and more quantum-vulnerable. Consider the HNDL threat: ECDHE key exchanges in TLS 1.3 protect session confidentiality, and these exchanges are the prime HNDL target – adversaries recording encrypted traffic today can decrypt it once a CRQC arrives. Since breaking ECDH P-256 requires fewer quantum resources than breaking RSA-2048, the HNDL window for ECC data is potentially shorter.

For digital signatures, the threat model is “trust-now-forge-later” (TNFL). ECDSA signatures on software updates, financial transactions, and legal documents could be forged retroactively, undermining the provenance of signed artifacts. With 3+ billion passkeys, over 1 billion cryptocurrency addresses, and every TLS 1.3 handshake depending on ECC, the attack surface is vast.

Organizations should conduct a dual-track cryptographic inventory that treats RSA and ECC migration with equal urgency. Key exchange migration (replacing ECDHE with ML-KEM hybrids) should take highest priority due to HNDL, followed by signature migration. IoT and embedded systems present the most severe challenges: many constrained devices lack over-the-air update capability and have 10–20+ year lifespans, meaning crypto-agility must be designed into new devices starting now.

Grover’s algorithm: the symmetric cipher footnote

Unlike Shor’s existential threat to public-key cryptography, Grover’s algorithm poses only a manageable quadratic speedup against symmetric ciphers. AES-256 retains an effective 128-bit security level under quantum attack – still astronomically large. AES-128 drops to an effective 64 bits, which is marginal but impractical to exploit because Grover’s iterations are inherently sequential and cannot be efficiently parallelized. Per ETSI’s 2025 analysis, even with 6,000 perfect logical qubits, breaking AES-256 via Grover would take roughly $10^{32}$ years. The simple mitigation – use AES-256, which CNSA 2.0 already mandates – resolves the symmetric threat entirely.

What matters now: the convergence of theory and engineering

The quantum threat to public-key cryptography is no longer a question of “if” but a narrowing question of “when.” The physical qubit estimates for RSA-2048 have compressed by four orders of magnitude in fourteen years – from 1 billion to a million – and the algorithmic optimizations driving this compression have not yet been fully applied to ECDLP circuits. Current quantum hardware sits at roughly 100–1,000 noisy qubits with best two-qubit gate fidelities of 99.5–99.9% in laboratory settings. The gap remains large, but the trajectory of both hardware and algorithmic improvement is consistently exceeding expert expectations.

Three insights should guide strategic planning.

• First, ECC and RSA face the same fundamental quantum vulnerability but ECC’s smaller keys make it the easier target – organizations cannot assume that migrating to ECC bought time.
• Second, key exchange migration is more urgent than signature migration because recorded ciphertext is already at risk, while signature forgery requires a CRQC to exist at the time of forgery.
• Third, the post-quantum standards and hybrid implementations are production-ready today.

The cruel paradox of post-quantum migration is that the cryptographic systems most praised for their classical efficiency – compact ECC keys, fast ECDH key exchange, elegant curve arithmetic – are precisely those most exposed to quantum attack. The same property that made 256-bit keys sufficient against classical adversaries makes them insufficient against quantum ones. Shor’s algorithm does not respect our classical security equivalences. It respects only the size of the numbers involved.