RSA-2048 Is Mathematically Doomed
RSA-2048 security depends on the assumption that factoring a 2048-bit composite number into its prime factors is hard. In 1994, Peter Shor proved that a sufficiently large quantum computer can factor integers in polynomial time. So the assumption is not merely under attack; it is provably false given enough quantum computing power. The only questions that remain are when a large enough quantum computer will exist and what replaces RSA in the meantime.
Why Bigger RSA Keys Do Not Help
Shor's algorithm scales as roughly O(n^3) in the number of bits n. Doubling the key size triples the quantum cost, which is not enough to matter. A quantum computer that can break RSA-2048 in a day can break RSA-4096 in roughly a week. Neither is a strategy. There is no RSA key size that is quantum-resistant.
Compare to classical attacks, where doubling the key size increases the attack cost exponentially under the General Number Field Sieve. Classical and quantum cryptanalysis scale fundamentally differently.
How Close Is the Quantum Computer That Does This?
Gidney and Ekera's 2021 analysis (arXiv:1905.09749) estimates approximately 20 million noisy physical qubits at 10^-3 gate error rate to factor RSA-2048 in 8 hours. Some newer analyses come in lower (a few million qubits with more efficient encodings), others higher.
As of April 2026 the state of the art is:
- IBM Condor (Dec 2023): 1,121 superconducting physical qubits
- Google Willow (Dec 2024): 105 qubits with below-threshold QEC
- Atom Computing (Oct 2023): 1,180 neutral-atom qubits
- Zuchongzhi 3.0 (Mar 2025): 105 superconducting qubits
- PsiQuantum target: ~1 million photonic qubits, late 2020s (company projection)
None break RSA today. Expert opinion (Global Risk Institute 2025 survey) places the 10-year likelihood of a Cryptographically Relevant Quantum Computer between 28 and 49 percent.
The Harvest Now Decrypt Later Problem
Even though RSA-2048 is not broken today, encrypted data protected by it may not be secret in 20 years. Nation-state adversaries with signals intelligence capabilities (cable taps, Internet backbone access) can record encrypted traffic now and decrypt once a CRQC exists. This is the Harvest Now Decrypt Later (HNDL) threat formalized in NSA and CISA joint guidance in August 2023.
Mosca's theorem formalizes this: if data-confidentiality lifetime X plus migration time Y exceeds CRQC arrival time Z, you should have started migrating already. For most regulated data with multi-decade lifetimes, the answer is already yes.
What Replaces RSA
NIST finalized FIPS 203 (ML-KEM) on August 13, 2024, standardizing Module-Lattice Key Encapsulation. ML-KEM replaces RSA-OAEP and RSA key transport. The three parameter sets map to NIST security categories 1, 3, and 5:
| ML-KEM | Security category | Public key | Ciphertext |
|---|---|---|---|
| ML-KEM-512 | 1 (AES-128 level) | 800 bytes | 768 bytes |
| ML-KEM-768 | 3 (AES-192 level) | 1,184 bytes | 1,088 bytes |
| ML-KEM-1024 | 5 (AES-256 level) | 1,568 bytes | 1,568 bytes |
ML-KEM is based on the Module Learning With Errors (MLWE) problem, a lattice problem not known to be solvable efficiently by either classical or quantum computers.
For signatures, FIPS 204 (ML-DSA) replaces RSA-PSS and RSA-PKCS#1. FIPS 205 (SLH-DSA) offers a hash-based alternative for conservative deployments. FIPS 206 (FN-DSA, draft) offers small signatures at the cost of implementation complexity.
Hybrid Migration
The practical path forward is hybrid: combine a classical algorithm like X25519 or RSA with a post-quantum algorithm like ML-KEM. An attacker must break both to recover the session key. This protects against three failure modes:
- A bug in the PQC implementation (classical side preserves security).
- A future mathematical breakthrough against lattice problems (classical side preserves security).
- A CRQC that breaks RSA or X25519 (PQC side preserves security).
Hybrid is what Signal (PQXDH, Sept 2023), Chrome (X25519MLKEM768, Nov 2024 default), iMessage (PQ3, Feb 2024), Cloudflare (>60 percent of human TLS traffic as of 2025), and AWS KMS have all deployed.
What You Should Do
- Inventory where RSA is used in your stack.
- Rank the inventory by data-confidentiality lifetime.
- Prioritize replacing RSA used for long-lived data encryption or signing.
- Deploy hybrid ML-KEM for anything new.
- Plan full migration on the CNSA 2.0 schedule (2027 new NSS, 2030 applications, 2035 full) even if you are not a federal agency, because it represents reasonable planning assumptions.
Frequently Asked Questions
Is RSA-4096 quantum-safe?
No. Shor's algorithm breaks RSA in polynomial time regardless of key size. Doubling the key size triples the quantum cost, which is not a defense. No RSA key size is quantum-safe.
What about RSA-15360?
Some standards suggested this as a post-quantum analogue to AES-256 strength under classical attack, but it is not post-quantum. Shor's algorithm scales polynomially; RSA-15360 is broken in slightly more time than RSA-2048.
When should I stop using RSA?
For anything with data-confidentiality lifetime greater than roughly 10 to 15 years, stop now. For short-lived signed messages (code-signing releases that expire in months), RSA is acceptable for now but should still migrate to ML-DSA on the NIST transition timeline.
Can I just use a hash-based signature?
Yes, for signatures. SLH-DSA (FIPS 205) is stateless and based only on hash function security. LMS (NIST SP 800-208) is stateful but more efficient. Neither replaces RSA for key exchange, which requires ML-KEM or HQC.
Sources
Related Articles
Protect Your Data Before Q-Day Arrives
QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.
Try QNSQYOriginally published at quantumsequrity.com/blog/why-rsa-2048-will-break.