Is RSA-4096 Quantum Safe?

Technical Analysis

RSA-4096 is NOT quantum safe. **How RSA-4096 Works:** RSA-4096 operates identically to RSA-2048, using the same Rivest-Shamir-Adleman algorithm, but with a 4096-bit modulus instead of 2048 bits. This means the two secret prime numbers (p and q) are each approximately 2048 bits long, and their product n is 4096 bits. The larger modulus increases computational overhead — RSA-4096 key generation is roughly 8x slower than RSA-2048, and encryption/decryption operations are 4-7x slower, depending on implementation. Organizations sometimes deploy RSA-4096 under the assumption that "bigger keys are more secure." Against classical attacks, this is partially true: the General Number Field Sieve (GNFS) factoring algorithm scales sub-exponentially, meaning RSA-4096 is significantly harder to break classically than RSA-2048 — estimated to require hundreds of millions of years with current hardware versus "only" millions of years for RSA-2048. However, this classical security improvement creates a false sense of quantum security. Many compliance frameworks and security checklists recommend "use RSA-4096 for long-term security" without acknowledging that quantum computers invalidate this guidance entirely. **Quantum Vulnerability Explained:** Shor's algorithm exhibits linear scaling with RSA key size, not exponential. Doubling the RSA modulus from 2048 to 4096 bits only doubles the quantum resources required — approximately 8,000-20,000 logical qubits to break RSA-4096, compared to 4,000-10,000 for RSA-2048. In contrast, classical factoring scales sub-exponentially, so doubling key size provides exponential classical security gains but only linear quantum security gains. This means a quantum computer capable of breaking RSA-2048 would break RSA-4096 with minimal additional resources — roughly 2x more qubits and 2x more gate operations. Given that quantum computing capabilities are expected to scale exponentially via improved error correction and qubit fabrication, the gap between "can break RSA-2048" and "can break RSA-4096" may be measured in months, not years or decades. Furthermore, RSA-4096's larger key size introduces operational risks without quantum benefits: larger keys increase TLS handshake latency (critical for web performance), bloat certificate sizes (problematic for embedded devices and IoT), and consume more CPU cycles (higher cloud infrastructure costs). Organizations deploying RSA-4096 today as a "quantum mitigation" are paying performance penalties for no meaningful security gain against quantum adversaries. **Migration Path:** Do not deploy RSA-4096 as a quantum security strategy — it is not quantum-safe. Instead, migrate directly to NIST-standardized post-quantum algorithms: - **ML-KEM (FIPS 203)**: Replace RSA-4096 key exchange with ML-KEM-768 (192-bit security) or ML-KEM-1024 (256-bit security). These provide genuine quantum resistance with faster performance than RSA-4096. - **ML-DSA (FIPS 204)**: Replace RSA-4096 signatures with ML-DSA-65 or ML-DSA-87. While ML-DSA signatures are larger than RSA-4096 (2-4 KB vs. 512 bytes), they are quantum-safe and have faster signing/verification than RSA-4096. - **Hybrid Mode**: If backward compatibility is required, implement hybrid RSA-4096+ML-KEM key exchange or dual RSA-4096+ML-DSA signatures. This provides quantum protection while maintaining compatibility with legacy systems. Avoid "upgrading" from RSA-2048 to RSA-4096 as a post-quantum strategy. The performance costs are real; the quantum security benefits are illusory. **Industries at Risk:** Government agencies and defense contractors often mandate RSA-4096 for classified communications under outdated security guidelines written before quantum threats were widely understood. These organizations face the same HNDL risk as RSA-2048 users, but with false confidence from larger keys. NSA CNSA 2.0 explicitly deprecates all RSA key sizes (including 4096) by 2030, requiring migration to ML-KEM/ML-DSA. Certificate authorities and public key infrastructure (PKI) providers sometimes issue RSA-4096 root CA certificates with 20-30 year lifetimes (expiring 2040-2050) under the assumption that larger keys provide long-term security. These certificates will be vulnerable to quantum attacks within their validity period. CA/Browser Forum guidance now recommends against issuing new long-lived RSA certificates of any size. Enterprise security teams managing internal PKI, VPNs, and code signing infrastructure may have deployed RSA-4096 following outdated NIST SP 800-57 guidance that recommended 3072-bit RSA for "long-term protection beyond 2030." NIST IR 8547 (2024) supersedes this, recommending PQC migration for all RSA key sizes. **Timeline to Obsolescence:** - **2024-2025**: RSA-4096 offers no quantum security advantage over RSA-2048. Begin PQC migration planning. - **2029**: Global Risk Institute estimates 5-14% probability of CRQC capable of breaking both RSA-2048 and RSA-4096. - **2030**: NSA CNSA 2.0 deprecates RSA-4096 (along with all RSA key sizes) for key establishment. - **2035**: NIST IR 8547 disallows RSA-4096 for federal use. Expected to be cryptographically obsolete. Organizations should not waste resources deploying RSA-4096. Migrate directly to ML-KEM and ML-DSA.

Migration Guidance