What Makes RSA and ECC Vulnerable to Quantum Attack

Most treatments of the quantum threat to cryptography open with some variation of "quantum computers are very powerful." That framing is accurate in a general sense and useless as a risk assessment tool. The question that matters for a security architect is not whether quantum computers are powerful in the abstract, but whether a specific quantum algorithm exists that solves the specific mathematical problem your cryptographic system depends on. For RSA and ECC, such an algorithm exists. It is called Shor's algorithm, first published by Peter Shor in 1994. For AES-256, no equivalent algorithm exists. The threat is not uniform across your cryptographic estate. It is targeted.

That distinction is the entire point of this article. I have sat in briefings where CISOs treat the quantum migration as a single undifferentiated programme: "replace all encryption." That framing leads to misallocated resources and a migration sequencing that can leave the highest-risk systems last. RSA-2048 key exchange running in your TLS handshakes today is categorically more exposed than AES-256 session encryption. Both use cryptography. Only one is broken by Shor's algorithm.

What follows is a technical explanation of why RSA and ECC are specifically vulnerable to quantum attack, why symmetric encryption is not, what the practical risk looks like for data encrypted today, and what the standardised replacements are. I will not explain what a qubit is. If you are reading this, you already know. What I will do is be precise about the mathematics, because the mathematics is exactly where the popular accounts go wrong.

RSA and the Integer Factoring Problem

RSA security rests on one mathematical problem: given a large semiprime N = p × q (where p and q are large primes), find p and q. For RSA-2048, N has 617 decimal digits. Rivest, Shamir, and Adleman established this in their foundational 1978 paper in Communications of the ACM. The security assumption is not that factoring is impossible in principle. It is that factoring at relevant key lengths is computationally infeasible on classical hardware within any timeframe that matters.

That assumption has held for classical computers. The best known general-purpose algorithm for integer factorisation is the General Number Field Sieve (GNFS), with sub-exponential complexity approximately exp(c × (log N)^1/3 × (log log N)^2/3). For RSA-2048, GNFS would require roughly 10²² to 10²⁴ classical operations. Kleinjung et al. factored a 768-bit RSA modulus in 2010, a landmark result requiring approximately two years of distributed computing across hundreds of machines. RSA-768 is not RSA-2048. The gap between them is not linear. At 2048 bits, GNFS is not a foreseeable threat on any classical hardware.

Shor's algorithm changes the calculation entirely. Shor showed in 1994 (FOCS Proceedings, later published in SIAM Journal on Computing in 1997) that integer factorisation is solvable in polynomial time on a quantum computer: O((log N)² (log log N) (log log log N)) quantum gate operations. For RSA-2048, this is proportional to roughly (2048)²: millions of operations rather than 10²². That reduction from exponential to polynomial is not an incremental improvement. It is a categorical change.

The mechanism is quantum period-finding. Given the function f(x) = a^x mod N, the function is periodic, and finding its period r leads directly to the factors of N. A classical computer cannot find the period efficiently because evaluating the function at sufficiently many points requires exponential work. A quantum computer finds the period via the Quantum Fourier Transform (QFT), which exploits quantum interference to identify the period in polynomial time, as Nielsen and Chuang detail in their standard reference text. The hardness argument for RSA on classical hardware depends on the absence of efficient period-finding. Shor's algorithm is efficient period-finding.

The logical qubit requirement for running Shor's algorithm on RSA-2048 is 4,099 logical qubits, per Beauregard's 2003 circuit minimisation result (arXiv:quant-ph/0205095): 2n+3 qubits for an n-bit modulus, n=2048. The gap between logical and physical qubit requirements is substantial, and the physical qubit estimates have been falling sharply. For the current best estimates of how many physical qubits a fault-tolerant machine would actually need, see How Official Advice on the Quantum Threat to RSA Has Changed Since 1994, which tracks that trajectory in detail.

ECC and the Elliptic Curve Discrete Logarithm Problem

ECC and RSA are not the same problem. This matters, because one common misconception is that Shor's algorithm breaks RSA by being generally good at cryptanalysis, and ECC falls as collateral damage. That is not what happens. ECC relies on a structurally different hardness assumption from RSA, and Shor's algorithm solves that problem too, through the same underlying mechanism.

The security of ECC rests on the elliptic curve discrete logarithm problem (ECDLP). Given a point G on an elliptic curve over a finite field, and a second point Q = kG (where k is a scalar and the multiplication is elliptic curve point addition applied k times), find k. Computing Q from k and G is efficient. Running the calculation in reverse, finding k from Q and G, is not, classically. Koblitz (1987, Mathematics of Computation) and Miller (1985, CRYPTO) independently proposed using this asymmetry as the basis for public-key cryptography.

The best classical algorithm for ECDLP is Pollard's rho algorithm, with complexity O(√n) group operations, where n is the prime order of the subgroup. For P-256 (the curve used in most deployed ECDH and ECDSA implementations), n is approximately 2²⁵⁶, giving roughly 2¹²⁸ classical operations. Pollard first described this in Mathematics of Computation in 1978. At 2¹²⁸ operations, classical attack is computationally infeasible.

Shor's algorithm also solves ECDLP in polynomial time. The reduction works because computing the discrete logarithm on an elliptic curve reduces to finding the period of a related function over the curve's group structure. The specific quantum circuit differs from the RSA case, but the algorithmic principle is identical: quantum period-finding via the QFT, exploiting structure that has no efficient classical counterpart. Proos and Zalka (2003, Quantum Information and Computation, arXiv:quant-ph/0301141) formalised the reduction and produced the first circuit estimates. Roetteler et al. (2017, arXiv:1706.06752) gave a more optimised circuit analysis.

The logical qubit requirement for Shor's algorithm on P-256 is approximately 2,330 logical qubits per the Proos-Zalka 2003 estimate. In terms of physical qubits, the best current estimate from Banegas et al. (2021, arXiv:2105.12132) places the count below 500,000 physical qubits under comparable error correction assumptions to the RSA estimates. That is a lower hardware threshold than RSA-2048 in absolute terms. ECC offers smaller keys than RSA at equivalent classical security levels (256-bit ECC versus 3,072-bit RSA for 128-bit classical security), but that compactness provides no quantum advantage. Both fall to Shor's algorithm. The quantum threat is not a function of key length.

The structural insight is this: RSA depends on factoring; ECC depends on discrete logarithm over elliptic curves; these are genuinely different mathematical problems with different classical hardness arguments. The reason both fall to Shor's algorithm is not coincidence. Both problems have periodic structure that quantum interference can exploit. The classical hardness of both depends on the absence of efficient period-finding on classical hardware. Shor's algorithm is efficient period-finding. Both problems share that structural vulnerability.

For the full picture of how migration deadlines and ECDH deprecation are tracked across regulatory bodies, see NIST FIPS 203, 204, and 205: What They Mean for Your Migration.

Diffie-Hellman: The Same Problem in a Different Field

Elliptic curve Diffie-Hellman (ECDH) is already covered by the ECDLP analysis above. Classical Diffie-Hellman key exchange (finite-field DH, as used in TLS 1.2 DHE cipher suites with 2048-bit or 4096-bit prime groups) uses the standard discrete logarithm problem in a prime finite field. Shor's 1994 result covers this case directly. The algorithm solves DLP in a prime field in polynomial time by the same period-finding mechanism as the RSA and ECDLP cases.

DSA (the Digital Signature Algorithm) also relies on DLP in a prime field. It is vulnerable via the same route. FIPS 186-5 has deprecated DSA; NIST IR 8547 (Initial Public Draft, November 2024) disallows DSA after 2035. ECDSA (Elliptic Curve DSA) uses ECDLP and is equally vulnerable.

The practical implication: the vulnerable class of algorithms covers all public-key and key-exchange systems built on integer factorisation or discrete logarithm, whether in prime finite fields or on elliptic curves. RSA, ECDH, ECDHE, classical DH, DSA, and ECDSA all fall. This is not a vulnerability in RSA-the-encryption-algorithm specifically. It is a vulnerability in the underlying mathematical assumptions shared by the entire public-key infrastructure on which most modern secure communications depends.

AES and Grover's Algorithm: Weakened, Not Broken

Grover's algorithm (Grover 1996, STOC) solves the unstructured search problem in O(√N) quantum operations versus O(N) classical operations. Applied to a brute-force key search, this produces a quadratic speedup: a symmetric key that requires 2^k classical operations to brute-force requires 2^k/2 quantum operations. AES-128 goes from 2¹²⁸ to 2⁶⁴ effective quantum security. AES-256 goes from 2²⁵⁶ to 2¹²⁸.

The common over-correction here is to say "Grover's is less threatening than Shor's, so symmetric encryption is basically fine." That framing is incomplete. AES-128 at 2⁶⁴ effective security is below the threshold NIST and the NSA consider acceptable for quantum-resistant systems. That is not a theoretical concern. NIST SP 800-57 Part 1 Rev 5 and NIST IR 8547 both specify that AES-128 is not recommended for new systems where quantum resistance is required. The NSA's CNSA 2.0 (September 2022) specifies AES-256 explicitly. AES-128 has already influenced standards. It is a real, quantified, acted-upon concern.

AES-256 under Grover's algorithm has an effective quantum security of 128 bits, which is considered sufficient. AES-256 is not broken by a quantum computer. Its security margin is halved. Bennett, Bernstein, Brassard, and Vazirani proved in 1997 (SIAM Journal on Computing) that Grover's algorithm is optimal for unstructured search: no quantum algorithm can do better than O(√N) for this problem class without additional structure. So doubling the key length from AES-128 to AES-256 fully restores the security margin. The fix is known and already specified.

SHA-256 has its effective quantum security reduced to 128 bits under Grover's; SHA-384 to 192 bits. Both remain within acceptable bounds for quantum-resistant systems, per NIST IR 8547. The NSA's CNSA 2.0 specifies SHA-384 as the minimum hash function for National Security Systems. SHA-3 is structurally unaffected by either Shor's or Grover's algorithm.

The critical distinction that the diagram above makes visual: Shor's algorithm exploits mathematical periodicity in RSA and ECC. There is no equivalent periodic structure in AES or SHA. Grover's algorithm applies generically to any key search, providing a quadratic but not exponential speedup. Doubling the symmetric key length restores the security margin fully. No such fix exists for RSA and ECC. You cannot double an RSA key and stay ahead of Shor's algorithm, because the vulnerability is structural, not quantitative. Increasing key length in an RSA system only changes the constant in a polynomial algorithm, not the algorithm's complexity class.

For the complete NIST deprecation schedule across RSA, ECC, AES, and SHA, see NIST FIPS 203, 204, and 205: What They Mean for Your Migration.

What This Means for Data Encrypted Today

The threat is not only forward-looking. A CRQC (cryptographically relevant quantum computer) does not need to exist today for today's RSA and ECDH-protected data to be at risk.

Harvest-now-decrypt-later (HNDL) is the operational threat model that makes this concrete. Nation-state adversaries with the collection infrastructure and the analytical patience to exploit it are presumed to be collecting encrypted TLS traffic now, storing it, and waiting for a CRQC to decrypt it retrospectively. The NSA, NIST, CISA, NCSC, and ANSSI have all endorsed HNDL as a credible threat model in primary source documents. The specific exposure: data whose confidentiality requirement extends beyond the likely Q-Day window. For genomic records, long-term legal documents, intelligence source identities, and classified material with multi-decade sensitivity requirements, that window is already a problem at current CRQC timeline estimates.

RSA key transport and ECDH key exchange are the most directly affected. A TLS session negotiated today using RSA key transport or ECDH key agreement can be retrospectively decrypted by any adversary who captured the handshake and subsequently obtains CRQC access. The AES session encryption protecting the session content is not the weakness. The key exchange establishing the session key is. An adversary who captures the handshake today gets the AES session key when the CRQC arrives, and the session content follows.

Forward secrecy provides limited protection here. ECDHE (ephemeral ECDH) does not store long-term RSA private keys, which limits the exposure of signatures. But the ephemeral ECDH key exchange itself still relies on ECDLP, and Shor's algorithm applied to the captured handshake recovers the session key regardless. Forward secrecy prevents retrospective decryption by an adversary who later compromises the server's long-term private key. It does not prevent retrospective decryption by an adversary who runs Shor's algorithm on the captured ephemeral key exchange.

The migration priority implication that follows from this: key exchange mechanisms (RSA key transport, ECDH, ECDHE) should be migrated before RSA/ECDSA digital signatures. A signature can only be forged by an adversary with a live CRQC, which does not currently exist. Key exchange data can be attacked retrospectively from captures made today. The NCSC's "Preparing for Quantum-Safe Cryptography" guidance (2020) and NSA CNSA 2.0 both prioritise key exchange migration on this basis. NIST SP 1800-38, the enterprise migration guidance, operationalises the same sequencing.

For a deeper analysis of the HNDL threat model, see HNDL In Motion: The Harvest-Now-Decrypt-Later Threat. For the practical question of how to map your deployed algorithms before beginning migration, see Cryptographic Inventory: Where to Start. On the timing question of when a CRQC might become operational, see Q-Day: What It Is and When It Might Arrive.

The Replacement Algorithms

NIST published three final post-quantum cryptographic standards in August 2024. These are operational standards, available for deployment now.

FIPS 203 specifies ML-KEM (Module-Lattice Key Encapsulation Mechanism, standardised from CRYSTALS-Kyber). ML-KEM replaces RSA key transport and ECDH/ECDHE key exchange. FIPS 204 specifies ML-DSA (Module-Lattice Digital Signature Algorithm, standardised from CRYSTALS-Dilithium). ML-DSA replaces RSA and ECDSA digital signatures. FIPS 205 specifies SLH-DSA (Stateless Hash-Based Digital Signature Algorithm, standardised from SPHINCS+). SLH-DSA is an alternative signature algorithm based on hash functions rather than lattices, providing a diversity of hardness assumptions.

The security of ML-KEM and ML-DSA rests on the hardness of lattice problems, specifically variants of the Learning With Errors (LWE) and Module-LWE problems. No efficient quantum algorithm is currently known for these problems. Neither Shor's algorithm nor Grover's algorithm provides a structural speedup against LWE; both depend on the periodic or search structure that lattice problems do not share. Peikert's 2016 survey in Foundations and Trends in Theoretical Computer Science covers the hardness landscape in detail. The absence of a known quantum algorithm for LWE is an inferred claim from the current state of knowledge, not a proof of security, and it is why ANSSI and BSI both mandate hybrid deployment rather than pure post-quantum transition.

The hybrid mandate from ANSSI and BSI is worth taking seriously. Both agencies recommend deploying classical algorithms (ECDH or RSA) simultaneously with post-quantum algorithms (ML-KEM), such that security holds even if one of the two schemes is later found to have a weakness. ANSSI's position paper (March 2022) and its follow-up (October 2023) make this a requirement for ANSSI-certified sensitive applications. BSI TR-02102-1 Version 2026-01 specifies the same approach for German regulated sectors. The rationale is sound: post-quantum algorithms have had less cryptanalytic scrutiny than RSA and ECC, which have been studied intensively for decades. Hybrid deployment is the technically conservative position and the one with the most optionality if the post-quantum landscape shifts.

NIST IR 8547 (Initial Public Draft, November 2024) sets the formal deprecation schedule: RSA-2048 and ECDH P-256 deprecated for new federal systems after 2030, and disallowed entirely after 2035. For organisations in scope of US federal requirements, which includes a significant portion of the global defence supply chain, the 2030 date is the new procurement threshold. For a complete breakdown of FIPS 203, 204, and 205 parameter sets and implementation guidance, see NIST FIPS 203, 204, and 205: What They Mean for Your Migration.

What to Do Next

You now understand the specific structural weakness in RSA and ECC that Shor's algorithm targets, why it does not apply to AES-256, and why data protected by RSA or ECDH key exchange today carries retrospective risk under the HNDL threat model. The next question is practical: which systems in your organisation are running these algorithms, and when do the regulatory deprecation deadlines apply to you?

The QSECDEF Algorithm Sunset Timer is the most direct tool for that question. Input your current algorithm deployments, select your jurisdiction and sector, and the tool maps each algorithm against the relevant regulatory deprecation dates from NIST IR 8547, NSA CNSA 2.0, NCSC's three-phase roadmap, BSI TR-02102-1, and ANSSI. If you have not yet mapped your deployed algorithms, the cryptographic inventory is the prerequisite step. The Cryptographic Inventory: Where to Start article covers the methodology for organisations at the beginning of that process.

The 2030 deprecation deadline for RSA-2048 is not aspirational for US federal systems or their supply chains, and it is the de facto benchmark for regulated sectors across Europe under NIS2 implementing guidance. For organisations that have not started a migration programme, the inventory and prioritisation work needs to begin now. A migration programme that takes three years to complete needs to be underway before Q-Day, not initiated in response to it.

QSECDEF membership provides ongoing threat intelligence on the quantum migration landscape as qubit estimates, regulatory guidance, and algorithm security findings evolve. The migration picture will keep moving. The deprecation schedule will not.