Modern public-key cryptographic systems derive their security from mathematical problems that are computationally infeasible to solve on classical computers given appropriate key sizes. RSA encryption and digital signatures rely on the integer factorization problem: given the product of two large prime numbers, finding the original factors is computationally infeasible when the numbers are large enough. A 2048-bit RSA key provides security because factoring a 617-digit semiprime using the most efficient known classical algorithms would require computational resources vastly exceeding current capability, estimated to require billions of years on the fastest available hardware.
Elliptic Curve Cryptography (ECC), used in ECDSA signatures and ECDH key exchange, relies on the elliptic curve discrete logarithm problem (ECDLP): given two points P and Q on an elliptic curve where Q = kP, finding the scalar multiplier k is computationally infeasible for appropriately chosen curves and key sizes. A 256-bit ECC key provides roughly equivalent security to a 3072-bit RSA key while requiring far less computational overhead. Both RSA and ECC are widely deployed throughout internet infrastructure: in TLS certificates, SSH keys, code signing certificates, DNSSEC, and secure messaging protocols.
- RSA security basis: integer factorization problem — computationally infeasible for large key sizes on classical hardware
- ECC security basis: elliptic curve discrete logarithm problem — infeasible on classical computers
- 2048-bit RSA: currently secure against classical attacks; 3072-bit recommended for new deployments
- 256-bit ECC: provides roughly equivalent security to 3072-bit RSA with much lower computational overhead
- Both RSA and ECC are used in TLS, SSH, code signing, DNSSEC, and secure messaging protocols
In 1994, mathematician Peter Shor published a quantum algorithm that solves the integer factorization problem in polynomial time on a quantum computer, compared to the sub-exponential time required by the best classical algorithms. This means a quantum computer running Shor's algorithm could factor the large integers that protect RSA keys exponentially faster than any classical computer. Shor's algorithm also solves the discrete logarithm problem, breaking both classic Diffie-Hellman key exchange and elliptic curve cryptography. The implications are profound: every public-key cryptographic system in widespread use today — RSA, ECC, and Diffie-Hellman — would become broken once a sufficiently powerful quantum computer exists.
The required quantum computer is called a cryptographically relevant quantum computer (CRQC), and it does not yet exist. Running Shor's algorithm to break a 2048-bit RSA key would require a quantum computer with thousands of error-corrected logical qubits. Current quantum hardware is in the noisy intermediate-scale quantum (NISQ) era, with systems of hundreds to low thousands of physical qubits that are far too error-prone to implement the large-scale error correction required for Shor's algorithm. Expert consensus estimates that a CRQC capable of breaking 2048-bit RSA could emerge within 10-15 years, though significant technical challenges remain, and this timeline carries considerable uncertainty in both directions.
- Shor's algorithm: solves integer factorization in polynomial time — breaks RSA and Diffie-Hellman
- Shor's algorithm also solves the discrete logarithm problem — breaks ECC
- CRQC requirement: thousands of error-corrected logical qubits — not yet achievable
- Current quantum hardware: NISQ era systems — insufficient for cryptographically relevant attacks
- Expert timeline estimate: CRQC within 10-15 years — with significant uncertainty in this estimate
Not all cryptography is equally threatened by quantum computers. Symmetric encryption algorithms like AES and hash functions like SHA-256 are not broken by Shor's algorithm. Instead, they are affected by Grover's algorithm, which provides a quadratic speedup for unstructured search problems. Applied to brute-force key search, Grover's algorithm effectively halves the security level of a symmetric key: AES-128 security is reduced from 128-bit to approximately 64-bit effective security against a quantum attacker, and AES-256 is reduced from 256-bit to approximately 128-bit effective security. The mitigation for symmetric cryptography is therefore straightforward: use larger key sizes where feasible.
AES-256 with 128-bit quantum security is considered adequate for the foreseeable future — 128-bit security remains computationally infeasible even with quantum acceleration. SHA-256 and SHA-3 hash functions are similarly analyzed as maintaining adequate security levels against quantum attacks with their current output sizes. The primary cryptographic migration challenge is therefore in public-key cryptography — key encapsulation, digital signatures, key agreement, and certificate-based identity systems — not in bulk data encryption or hashing. Organizations can prioritize their migration efforts accordingly.
- AES-128: quantum security reduced from 128-bit to approximately 64-bit — upgrade to AES-256 now
- AES-256: quantum security approximately 128-bit — considered adequate for long-term use
- SHA-256: quantum security approximately 128-bit — adequate; no immediate migration required
- Public-key cryptography (RSA, ECC, DH): directly broken by Shor's algorithm — requires full migration
- Priority: focus migration efforts on public-key cryptography, not symmetric encryption
The harvest now decrypt later (HNDL) threat is an active concern that does not require a CRQC to exist today — it requires only that adversaries with the necessary resources believe a CRQC will exist within the confidentiality period of the data they are collecting. Nation-state intelligence agencies are widely assessed to be intercepting and storing encrypted network traffic today with the intent to decrypt it once a CRQC becomes available. This threat is particularly relevant for data that must remain confidential for 10 or more years: classified government information, long-term corporate trade secrets, personal health records, financial data, and diplomatic communications.
The HNDL threat means that the urgency of post-quantum migration is not defined by the expected availability date of a CRQC alone, but by the combination of that date and the required confidentiality period of sensitive data. If your most sensitive data must remain confidential for 15 years and a CRQC might be available in 10, migration should begin immediately. For TLS connections protecting transaction data with a short-term confidentiality requirement, the urgency is lower — but the migration effort for pervasive TLS infrastructure is enormous, requiring years of planning and implementation even when started today.
- HNDL: adversaries store encrypted traffic now to decrypt after a CRQC becomes available
- Nation-state intelligence agencies are assessed to be implementing HNDL collection programs now
- Risk equation: CRQC timeline + data confidentiality period determines migration urgency
- Highest risk: classified government data, long-term trade secrets, health records, financial data
- Begin post-quantum migration for long-lived sensitive data immediately regardless of CRQC timeline
After an eight-year standardization process that began in 2016, NIST finalized three post-quantum cryptographic standards in August 2024. ML-KEM (Module Lattice-based Key Encapsulation Mechanism), published as FIPS 203, is based on the Module Learning With Errors (MLWE) lattice problem and provides a post-quantum-secure key encapsulation mechanism suitable for replacing ECDH and RSA key exchange in TLS and other protocols. ML-KEM was previously known as CRYSTALS-Kyber during the standardization process. It is designed for efficient implementation and provides IND-CCA2 security.
ML-DSA (Module Lattice-based Digital Signature Algorithm), published as FIPS 204, is also based on the MLWE lattice problem and provides post-quantum digital signatures suitable for replacing ECDSA and RSA-PSS in TLS certificates, code signing, and other digital signature applications. SLH-DSA (Stateless Hash-based Digital Signature Algorithm), published as FIPS 205 and formerly known as SPHINCS+, is based on well-understood hash function security assumptions rather than lattice problems, providing an independent security basis as a conservative alternative. During the transition period, hybrid approaches that combine classical algorithms (such as ECDH) with post-quantum algorithms (such as ML-KEM) in a single key exchange provide security against both classical and quantum adversaries simultaneously.
- ML-KEM (FIPS 203, formerly CRYSTALS-Kyber): post-quantum key encapsulation based on MLWE lattice problem
- ML-DSA (FIPS 204, formerly CRYSTALS-Dilithium): post-quantum digital signatures based on MLWE lattice
- SLH-DSA (FIPS 205, formerly SPHINCS+): hash-based signatures with conservative security assumptions
- Hybrid key exchange: combine ECDH + ML-KEM to protect against both classical and quantum adversaries
- TLS 1.3 hybrid: X25519 + ML-KEM-768 is the emerging standard for post-quantum TLS key exchange
A post-quantum cryptographic migration begins with a comprehensive inventory of all cryptographic dependencies in your organization's systems. This includes TLS certificates and the CAs that issue them, SSH key types used for server administration, code signing keys and certificate chains, API authentication mechanisms, database encryption keys, VPN protocols, and any custom cryptographic implementations. The inventory phase reveals the scope of the migration and identifies which systems are most critical to migrate first. Systems that protect long-lived sensitive data should be prioritized over systems protecting transient data.
Crypto-agility — the architectural design principle of building systems so that cryptographic algorithms can be upgraded without requiring complete system redesign — should be adopted for all new development and retrofitted into existing systems as they are updated. Crypto-agile systems specify algorithms and key types in configuration rather than hardcoding them, making algorithm transitions significantly less disruptive when future changes are required. For TLS infrastructure, migrate to using TLS libraries that support hybrid post-quantum key exchange (OpenSSL 3.2+ and BoringSSL both support experimental hybrid modes). Monitor NIST guidance for recommended algorithms, key sizes, and transition timelines as the standardization landscape continues to evolve.
- Step 1: inventory all cryptographic dependencies — TLS, SSH, code signing, VPN, API auth
- Step 2: prioritize migration by data sensitivity and required confidentiality period
- Step 3: adopt crypto-agility in all new system development and major system updates
- Step 4: upgrade TLS libraries to versions supporting hybrid post-quantum key exchange
- Step 5: establish migration timeline aligned with your data's confidentiality requirements