The Post-Quantum Field Guide

LaMarr LabsLaMarr Labs

RSA vs ECC

15 min read

up:: Classical Cryptography MOC

RSA vs ECC

RSA and ECC are the two public-key families that carry nearly all of the internet’s key establishment and digital signatures. RSA rests on the difficulty of factoring a large modulus. ECC rests on the difficulty of the elliptic-curve discrete logarithm problem. ECC reaches the same classical security in far smaller keys, which is why it displaced RSA across high-volume systems.

Against a quantum computer the comparison inverts in a way most teams get backward. Shor’s algorithm solves both factoring and the discrete logarithm, so both families break completely, and the compactness that makes ECC efficient also makes it the cheaper target.

The short version:

  • They rest on different hard problems. RSA on integer factorization, ECC on the elliptic-curve discrete logarithm. Both are the structured mathematics Shor’s algorithm dismantles.
  • ECC reaches the same classical strength in far smaller keys. A 256-bit curve delivers about 128 bits of security, where RSA needs a 3,072-bit modulus for the same level, because the best classical attack on a well-formed curve costs about the square root of the group size.
  • ECC falls to a smaller quantum computer. Breaking a 256-bit curve was estimated at roughly 2,330 logical qubits in 2017 and 1,200 to 1,450 in a 2026 preprint, against roughly 20 million noisy qubits for RSA-2048 in a 2021 analysis and under a million in a 2025 estimate.
  • Migrating from RSA to ECC is a classical upgrade and a poor quantum hedge, because it moves an estate onto the algorithm that breaks on the smaller machine.
  • Both migrate to the same successors, ML-KEM for key establishment and ML-DSA or SLH-DSA for signatures, and both are disallowed for federal use after 2035.

Two safes rated to resist the same burglar for the same number of hours. One is a large steel cabinet, and the other achieves the identical rating in a box a fraction of the size through cleverer engineering, which is why the smaller one ended up in every branch office. A tool is now being developed that opens either by reading the lock’s internal geometry rather than by forcing it. Against that tool the size advantage becomes a disadvantage, because there is less geometry to read in the small box, and it opens sooner.

What is the difference between RSA and ECC?

The difference is the mathematical problem each stakes its security on, and every practical distinction follows from it. RSA’s security is that recovering the private key from a public modulus requires factoring that modulus into its prime components. ECC’s security is that recovering a private scalar from a public curve point requires solving the elliptic-curve discrete logarithm.

Because the best known classical attack on a well-chosen curve costs on the order of the square root of the group size, while factoring has substantially better classical algorithms available, ECC reaches any given security level in far fewer bits. That single fact drives the key sizes, the certificate sizes, the performance profiles, and, unexpectedly, the quantum resource estimates.

What is RSA?

RSA is the public-key cryptosystem published by Rivest, Shamir and Adleman at MIT in 1977, whose security rests on the difficulty of factoring a large semiprime modulus. It performs two jobs: key transport and key establishment on one side, and digital signatures on the other. NIST maps its modulus sizes to security strengths, with RSA-2048 at 112 bits and RSA-3072 at 128 bits.

Source: NIST SP 800-57 Part 1 Revision 5, “Recommendation for Key Management,” 2020, Table 2, csrc.nist.gov.

What is ECC?

ECC is the family of public-key constructions defined over the group of points on an elliptic curve over a finite field, where a private key is a secret scalar and the public key is a curve point computed by scalar multiplication. Its security is the elliptic-curve discrete logarithm problem.

It does the same two jobs through different members: ECDH and X25519 for key agreement, and ECDSA and Ed25519 for signatures. The curves split into two worlds, the NIST Weierstrass curves (P-256, P-384, P-521) specified in SP 800-186, and the Bernstein CFRG curves (Curve25519, Curve448) specified in RFC 7748.

Source: NIST, “Recommendations for Discrete Logarithm-Based Cryptography, Elliptic Curve Domain Parameters,” SP 800-186, February 2023, csrc.nist.gov.

RSA vs ECC at a glance

DimensionRSAECC
Hard problemInteger factorization of a large semiprime modulusElliptic-curve discrete logarithm problem
PublishedRivest, Shamir and Adleman, MIT, 1977Proposed independently in the mid-1980s; standardized curves in NIST SP 800-186 and RFC 7748
Key size for 128-bit classical strength3,072-bit modulus256-bit curve
Why the sizes differClassical factoring algorithms are substantially better than brute force, so the modulus must be largeThe best classical attack, Pollard’s rho, costs about the square root of the group size
Key agreementRSA key transportECDH and ECDHE, X25519
SignaturesRSA signatures, with PSS and PKCS#1 paddingECDSA, Ed25519, Ed448
Where it dominatesLegacy enterprise PKI, older TLS certificates, key transport in aging systemsModern TLS, SSH, secure messaging, VPNs, most new certificates
Known non-quantum failure modeUnsafe padding; textbook RSA without OAEP or PSSA predictable or reused ECDSA per-signature nonce leaks the private key directly
Quantum attackShor’s algorithm against factoringShor’s algorithm against the discrete logarithm
Estimated quantum costRSA-2048 at roughly 20 million noisy qubits over about 8 hours (2021), brought under a million in a 2025 estimateA 256-bit curve at roughly 2,330 logical qubits (2017), and 1,200 to 1,450 in a 2026 preprint
Which breaks on the smaller machineThe larger requirement of the twoECC, because it reaches the same classical strength in far fewer bits, so Shor’s circuit is smaller
NIST deprecationRSA-2048, at 112-bit strength, deprecated after 2030None. P-256 and Curve25519 are 128-bit strength, so the 2030 step does not reach them
NIST disallowanceEvery size disallowed after 2035Every curve disallowed after 2035
Post-quantum successor, key establishmentML-KEMML-KEM
Post-quantum successor, signaturesML-DSA, with SLH-DSA as the conservative optionML-DSA, with SLH-DSA as the conservative option
Transitional roleClassical half of a hybrid deployment where still in useClassical half of the deployed TLS hybrid groups, X25519MLKEM768 and SecP256r1MLKEM768

Source: M. Roetteler, M. Naehrig, K. M. Svore, K. Lauter, “Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms,” ASIACRYPT 2017, arxiv.org, for the 9n + 2⌈log₂ n⌉ + 10 formula and the 2,330-qubit figure; Google Quantum AI, Ethereum Foundation and Stanford, cryptocurrency whitepaper, March 2026, for the 1,200 to 1,450 range.

Source: C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, quantum-journal.org; C. Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” 2025, arXiv:2505.15917.

Source: NIST IR 8547 (initial public draft), “Transition to Post-Quantum Cryptography Standards,” 2024, csrc.nist.gov, for the deprecation and disallowance schedule.

How do they actually differ?

  1. The size gap comes from the quality of the classical attacks, rather than from one being stronger. Factoring has substantially better classical algorithms available than generic search, so RSA has to use a large modulus to stay ahead of them. A well-formed elliptic curve has no comparable shortcut, leaving Pollard’s rho at roughly the square root of the group size, so 256 bits of curve buys 128 bits of security. Both land at the same strength through different margins.

  2. The performance profiles differ by operation rather than overall. RSA verification with a small public exponent is fast, while RSA key generation and signing are comparatively expensive at modern modulus sizes. ECC operations are compact and quick across the board, and its small keys and signatures are what let it displace RSA in bandwidth-sensitive and high-volume systems.

  3. Their non-quantum failure modes are unrelated. RSA’s classic implementation failures are padding failures, which is why textbook RSA without OAEP or PSS is unsafe. ECC’s classic failure is nonce handling in ECDSA, where a predictable or reused per-signature nonce leaks the private key outright. Neither weakness transfers to the other family.

  4. The quantum comparison reverses the classical one. Shor’s circuit scales with the bit length it operates on. RSA’s modulus has to reach 3,072 bits for 128-bit strength against classical factoring, so its circuit is large. ECC reaches equivalent classical strength in 256 bits, so its circuit is smaller, and every published estimate puts the elliptic-curve attack on a substantially smaller machine than the RSA attack.

  5. Only one of them carries a 2030 date. RSA-2048 provides 112-bit strength, which places it in the tier NIST deprecates after 2030. P-256 and Curve25519 provide 128-bit strength, so they carry a single 2035 disallowance with no earlier deprecation step. An estate running RSA-2048 has an earlier clock than an estate on modern curves, for reasons of security strength rather than of family.

Where do they agree?

  1. Both are broken by the same algorithm. Shor’s solves integer factorization and the discrete logarithm in polynomial time on a fault-tolerant quantum computer, which is a structural break of the core assumption in each case rather than an erosion of margin.

  2. Neither is helped by a bigger parameter. RSA-4096 and P-521 raise the classical margin and the quantum cost without approaching quantum safety, because Shor’s requirement grows only polynomially with bit length. Resizing buys larger keys and slower operations today against a threat that keeps getting cheaper.

  3. Both do the same two jobs and migrate to the same successors. Key establishment goes to ML-KEM and signatures go to ML-DSA or SLH-DSA, regardless of which family was there before.

  4. Both are disallowed for federal use after 2035, aligning with the government-wide migration target in National Security Memorandum 10.

  5. Neither is threatened by Grover’s algorithm. Grover speeds up brute-force search quadratically, which dents symmetric ciphers and leaves the public-key break entirely to Shor’s.

  6. Both survive the transition as the classical half of a hybrid deployment, which is why X25519 and P-256 appear inside the deployed TLS hybrid groups rather than being switched off on day one.

Which one breaks first?

ECC, on the smaller machine, and the margin is large. The 2017 resource estimate gives the logical-qubit requirement for a curve over an n-bit field as 9n + 2⌈log₂ n⌉ + 10, which works out to roughly 2,330 logical qubits for P-256 with a circuit on the order of 10¹¹ Toffoli gates. The March 2026 preprint from Google Quantum AI, the Ethereum Foundation and Stanford brings that to 1,200 to 1,450 logical qubits on a machine of fewer than 500,000 physical qubits, running in 18 to 23 minutes at a 0.1% physical error rate.

Set against RSA-2048 at roughly 20 million noisy qubits over about 8 hours in the 2021 analysis, and under a million noisy qubits in the 2025 estimate, the elliptic-curve attack needs the smaller machine in every published comparison. Both figures describe hardware nobody has built, and the ordering between them is the durable part.

The consequence for planning is the point teams most often invert. A migration from RSA onto ECC reads as modernization and, measured against a quantum adversary, moves an estate onto the algorithm that falls sooner. ECC remains an excellent classical upgrade, and the durable move is to migrate the public-key layer to post-quantum standards rather than to shuffle between quantum-vulnerable families.

When is each the right answer today?

ECC is the right classical answer for new work. Its compact keys, small signatures and fast operations suit modern TLS, SSH, secure messaging and constrained devices, and it is where the ecosystem has converged. Nothing about the quantum comparison argues for choosing RSA over ECC in a new classical design.

RSA persists where an installed base requires it. Older enterprise PKI, legacy key transport and long-lived embedded systems still speak RSA, and replacing it with ECC inside those systems can be a reasonable interim step for classical reasons such as performance and certificate size.

Neither is the right answer for anything whose confidentiality or trust has to outlast the migration. The replacements are ML-KEM for key establishment and ML-DSA or SLH-DSA for signatures, deployed today through hybrid groups that keep a classical component while the post-quantum half carries the new protection.

Why do people confuse the comparison?

Because ECC’s classical advantages are real and easy to state, and they get carried across a boundary where they stop applying. Smaller keys, faster handshakes and shorter certificates are genuine wins against a classical attacker, and the natural inference is that the newer, tighter, more efficient family must also be the more future-proof one.

The inference fails because efficiency against a classical attacker and cost to a quantum attacker are driven by the same variable, bit length, in opposite directions. Fewer bits means a cheaper classical defense and a cheaper quantum attack. Holding both facts at once is what turns “we modernized to ECC” from a conclusion into a starting point.

Common misconceptions

  1. “We moved from RSA to ECC, so we’re modern and covered.” ECC is a classical efficiency upgrade, and against a quantum adversary it moves an estate onto the algorithm that breaks on the smaller machine. Both families are on NIST’s replacement schedule with the same 2035 disallowance.

  2. “ECC is more secure than RSA.” At matched parameters they sit at the same NIST security strength, with P-256 and RSA-3072 both at 128 bits. ECC reaches that level more efficiently rather than more securely.

  3. “RSA-4096 buys real quantum runway.” Shor’s requirement grows only polynomially with bit length, so a larger modulus adds qubits and runtime to an attack that better hardware keeps making cheaper. It costs performance today for margin that does not hold.

  4. “Quantum computers break RSA but ECC is fine.” Shor’s algorithm solves both factoring and the discrete logarithm. Every ECC curve, including Curve25519 and secp256k1, is fully broken.

  5. “RSA and ECC have different deadlines because they are different families.” The deadlines follow security strength rather than family. RSA-2048 carries a 2030 deprecation because it provides 112-bit strength, and P-256, Curve25519 and RSA-3072 all sit at 128 bits with a single 2035 disallowance.

  6. “Switching families counts as a post-quantum migration.” Moving between RSA, ECC and any parameter within them stays inside Shor’s reach. A post-quantum migration leaves both families for ML-KEM and ML-DSA or SLH-DSA.

Questions people ask

Is ECC more secure than RSA? At matched security strengths they are equivalent, with P-256 and RSA-3072 both providing 128 bits classically. ECC’s advantage is efficiency, reaching that strength in 256 bits where RSA needs 3,072.

Why are ECC keys so much smaller? The best known classical attack on a well-formed curve, Pollard’s rho, costs about the square root of the group size, so 256 bits of curve gives 128 bits of security. Factoring has substantially better classical algorithms available, so RSA needs a much larger modulus to stay ahead of them.

Which one does a quantum computer break first? ECC, on a substantially smaller machine. A 256-bit curve was estimated at roughly 2,330 logical qubits in 2017 and 1,200 to 1,450 in a 2026 preprint, against roughly 20 million noisy qubits for RSA-2048 in 2021 and under a million in a 2025 estimate.

Should I migrate from RSA to ECC? For classical reasons such as performance, certificate size and ecosystem support, ECC is the better modern choice. It advances a post-quantum migration not at all, so it should be planned as an efficiency project rather than counted as quantum risk reduction.

Do RSA and ECC have the same replacement? Yes. Key establishment in either family goes to ML-KEM, and signatures in either family go to ML-DSA, with SLH-DSA as the conservative option for long-lived and firmware signing.

Does RSA have an earlier deadline than ECC? RSA-2048 does, because it provides 112-bit strength and therefore falls in the tier deprecated after 2030. RSA-3072 and above, along with P-256 and Curve25519, carry a single 2035 disallowance.

Is secp256k1 different because Bitcoin uses it? Only in that it is a Koblitz curve outside the NIST-approved set. It rests on the same elliptic-curve discrete logarithm at 128-bit classical strength, so Shor’s algorithm breaks it exactly as it breaks P-256.

Can I keep using either during the migration? Yes, as the classical component of a hybrid deployment. The deployed TLS hybrid groups pair X25519 or P-256 with ML-KEM so the session holds as long as either half does.

Which has worse real-world implementation failures? They fail differently. RSA’s classic failures are padding-related, which is why OAEP and PSS matter. ECC’s classic failure is ECDSA nonce handling, where a repeated or predictable nonce leaks the private key directly, and it has broken real systems.

The map is free and I keep it that way. When the question becomes where each of these families actually sits across an estate and in what order they come out, that’s the work I do at LaMarr Labs.

Go deeper

Last verified 2026-08-10 · Maintained by Addie LaMarr, LaMarr Labs.

Graph View

Backlinks