DEV Community

Quantum Sequrity
Quantum Sequrity

Posted on • Originally published at quantumsequrity.com

Why Quantum Computers Threaten Classical Encryption

#postquantumcryptography #harvestnowdecryptlater #cybersecurity #security

Why Quantum Computers Threaten Classical Encryption

Education

Why Quantum Computers Threaten Classical Encryption

12 min read

The Foundation of Modern Encryption

Nearly every secure communication on the internet today relies on a small set of mathematical problems that are extraordinarily difficult for classical computers to solve. Online banking, email encryption, VPNs, HTTPS, code signing, and secure messaging all depend on the assumption that these problems will remain hard to crack. That assumption is about to be challenged.

To understand the quantum threat, you first need to understand what classical encryption actually relies on. There are two major categories of hard problems at the heart of modern public-key cryptography:

Integer Factorization (RSA)

RSA, the most widely deployed public-key algorithm, relies on the difficulty of factoring the product of two large prime numbers. Given two primes p and q, computing their product n = p * q is trivial. But given only n, finding p and q is computationally infeasible when n is sufficiently large (2048 bits or more). The best known classical algorithms for factoring, such as the General Number Field Sieve, require sub-exponential time. For RSA-2048, this translates to an estimated computational effort that would take billions of years on the fastest supercomputers.

Discrete Logarithm Problem (DH, ECDH, ECDSA, DSA)

Diffie-Hellman key exchange, elliptic curve Diffie-Hellman (ECDH), ECDSA, and DSA all rely on variants of the discrete logarithm problem. In the finite field setting, given a generator g, a prime p, and a value g^x mod p, finding x is computationally hard. The elliptic curve variant replaces modular arithmetic with operations on points of an elliptic curve, where finding the scalar multiplier from a known base point and result point is similarly intractable. ECC achieves equivalent security to RSA with much smaller key sizes: a 256-bit ECC key provides roughly the same security as a 3072-bit RSA key.

These mathematical problems have served as the bedrock of internet security for decades. RSA was published in 1977. Diffie-Hellman was described in 1976. ECC gained widespread adoption in the 2000s. All of them share one critical vulnerability: they can be solved efficiently by a sufficiently powerful quantum computer.

Shor's Algorithm: Breaking Public-Key Cryptography

In 1994, mathematician Peter Shor published a quantum algorithm that factors integers and computes discrete logarithms in polynomial time. This was a theoretical bombshell. On a classical computer, factoring a 2048-bit number is practically impossible. On a quantum computer running Shor's algorithm, it becomes feasible.

Shor's algorithm works by exploiting quantum mechanical properties, specifically superposition and entanglement, to find the period of a modular exponential function. Once the period is known, classical number theory can extract the prime factors. The key insight is that quantum computers can evaluate many possibilities simultaneously through superposition, and quantum interference amplifies the correct answers while canceling out wrong ones.

What does "polynomial time" mean in practice? For factoring, the best classical algorithms run in sub-exponential time, roughly proportional to e^(n^1/3) where n is the bit length. Shor's algorithm runs in time proportional to n^3. The difference is staggering. Doubling the key size from 2048 to 4096 bits makes classical factoring dramatically harder, but only modestly increases the work for Shor's algorithm.

What Shor's Algorithm Breaks
RSA (all key sizes), DSA, ECDSA, ECDH, Diffie-Hellman, and any cryptosystem whose security depends on integer factorization or discrete logarithms. Increasing key sizes does not help: Shor's algorithm scales polynomially regardless of key length.

It is important to be precise: Shor's algorithm requires a fault-tolerant quantum computer with a sufficient number of logical qubits. Current quantum computers are noisy and error-prone, with qubit counts in the low thousands. Running Shor's algorithm against RSA-2048 is estimated to require several thousand logical qubits, which in turn require millions of physical qubits due to error correction overhead. We are not there yet, but progress is steady.

Grover's Algorithm: Weakening Symmetric Encryption

Published in 1996 by Lov Grover, Grover's algorithm provides a quadratic speedup for unstructured search problems. In the context of cryptography, this means a brute-force search over a key space of size N takes only sqrt(N) operations on a quantum computer instead of N operations on a classical computer.

The practical impact on symmetric encryption is straightforward: Grover's algorithm effectively halves the security level. AES-128, which provides 128 bits of security against classical attacks, provides only 64 bits of security against a quantum attacker. Sixty-four bits is well within brute-force range and therefore insecure.

However, AES-256, with 256 bits of classical security, would still provide 128 bits of security against quantum attacks. 128 bits of security remains far beyond any feasible brute-force attack, classical or quantum. This is why the cryptographic community considers AES-256 to be quantum-safe, provided the key is properly generated and managed.

The same logic applies to hash functions. SHA-256 provides 128 bits of collision resistance against quantum attackers (down from 128 bits classically, since collision search benefits from a different quantum speedup). SHA-3 and BLAKE3 with 256-bit outputs similarly remain secure. The general guidance is to double the output size of symmetric primitives to maintain the same security margin against quantum attacks.

Which Algorithms Are Vulnerable?

The quantum threat is not uniform. It specifically targets public-key (asymmetric) algorithms whose security is based on factoring or discrete logarithms. Here is the breakdown:

Broken by Quantum Computers

  • RSA (all key sizes: 1024, 2048, 3072, 4096) -- integer factorization, broken by Shor's algorithm
  • DSA -- discrete logarithm in finite fields, broken by Shor's algorithm
  • ECDSA (P-256, P-384, P-521) -- elliptic curve discrete logarithm, broken by Shor's algorithm
  • ECDH / X25519 -- elliptic curve Diffie-Hellman, broken by Shor's algorithm
  • Diffie-Hellman (classical, finite field) -- discrete logarithm, broken by Shor's algorithm
  • Ed25519 / Ed448 -- elliptic curve signatures, broken by Shor's algorithm

Resistant to Quantum Computers (with sufficient key/output sizes)

  • AES-256 -- 128-bit quantum security via Grover's, still considered safe
  • AES-192 -- 96-bit quantum security, considered adequate
  • SHA-3 (256-bit and above) -- reduced but still sufficient security margins
  • SHA-512 -- adequate collision resistance against quantum
  • BLAKE3 (256-bit output) -- 128-bit quantum collision resistance
  • HMAC with 256-bit+ keys -- unaffected by known quantum algorithms beyond Grover's

The critical takeaway: symmetric algorithms and hash functions survive the quantum transition with larger key/output sizes. Public-key cryptography based on factoring or discrete logs does not survive at any key size. For a deeper introduction to the algorithms designed to replace them, see our guide on what post-quantum cryptography is.

Timeline: When Will This Happen?

Predicting when a cryptographically relevant quantum computer (CRQC) will exist is inherently uncertain. Estimates vary widely among experts:

  • Conservative estimates (15-20+ years): Many physicists and engineers point to the enormous engineering challenges of building fault-tolerant quantum computers at scale. Error correction overhead, qubit stability, and manufacturing consistency remain fundamental obstacles.
  • Aggressive estimates (5-10 years): Some researchers and industry leaders believe rapid advances in qubit quality, error correction codes, and hybrid architectures could accelerate timelines significantly. Quantum computing investment has grown substantially, with major programs funded by governments and technology companies worldwide.

The honest answer is that nobody knows for certain. But this uncertainty itself is part of the threat. NIST noted in its report on post-quantum cryptography (NIST IR 8105, published in 2016) that the transition to quantum-resistant algorithms would take years or decades to complete across the global IT infrastructure. Waiting for certainty about quantum computing timelines means starting the migration too late.

The "Harvest Now, Decrypt Later" Threat

Even if large-scale quantum computers are a decade or more away, there is an immediate and concrete threat that exists today. It is called "Harvest Now, Decrypt Later" (HNDL), also known as "Store Now, Decrypt Later."

How HNDL Works
An adversary intercepts and stores encrypted communications today, while they are still protected by classical encryption. The adversary archives this data and waits. When a sufficiently powerful quantum computer becomes available, they use Shor's algorithm to recover the encryption keys and decrypt everything they have collected. The data does not need to be valuable today. It only needs to be valuable when it is eventually decrypted.

Consider what types of data remain sensitive for years or decades: classified government communications, long-term trade secrets, medical records, legal documents, financial data, intellectual property, and personal information subject to privacy regulations. All of this data, if encrypted today with RSA or ECC alone, is potentially harvestable.

Nation-state intelligence agencies have the storage capacity, network access, and strategic motivation to conduct HNDL operations at scale. This is not speculative; multiple government cybersecurity agencies have publicly warned about this threat. We cover this topic in detail in our post on the Harvest Now, Decrypt Later attack.

Why Organizations Must Act Now

The argument for immediate action does not depend on quantum computers arriving tomorrow. It depends on three factors:

1. Migration Takes Years

Transitioning an organization's cryptographic infrastructure is not a software update. It involves inventorying every system that uses public-key cryptography, updating protocols, replacing certificates, testing interoperability, and retraining staff. For large enterprises and government agencies, this process takes 5 to 15 years. NIST began its post-quantum cryptography standardization process in 2016, and the first standards (FIPS 203, FIPS 204, and FIPS 205) were finalized on August 13, 2024 -- an eight-year effort just for standardization alone.

2. Data Has a Long Shelf Life

If your encrypted data needs to remain confidential for 10, 20, or 30 years, and a quantum computer could emerge within that window, then that data is already at risk. The protection window of your encryption must exceed the combined time until a quantum computer exists plus the time to actually perform the decryption. For many types of sensitive data, this calculation already fails.

3. Compliance Is Moving

Regulatory and compliance frameworks are beginning to incorporate post-quantum requirements. Organizations that wait will face both security risk and compliance gaps. The U.S. government has already directed federal agencies to begin transitioning to post-quantum cryptography.

The NIST Post-Quantum Solution

Recognizing the quantum threat, NIST launched its Post-Quantum Cryptography Standardization Process in 2016, evaluating submissions from researchers worldwide. After multiple rounds of analysis and public review, NIST finalized three standards on August 13, 2024:

  • FIPS 203 (ML-KEM) -- Module-Lattice Key Encapsulation Mechanism, replacing RSA/ECDH for key exchange. Based on the hardness of the Module Learning With Errors problem. See our detailed explanation of how ML-KEM works.
  • FIPS 204 (ML-DSA) -- Module-Lattice Digital Signature Algorithm, replacing RSA/ECDSA/DSA for digital signatures. Also based on lattice problems.
  • FIPS 205 (SLH-DSA) -- Stateless Hash-Based Digital Signature Algorithm, providing a conservative alternative for signatures based purely on hash function security.

These algorithms are designed so that no known quantum algorithm can break them efficiently. Their security is based on mathematical problems (lattice problems for ML-KEM and ML-DSA, hash function properties for SLH-DSA) that are believed to be hard for both classical and quantum computers. For a complete walkthrough of these standards, see our NIST FIPS 203/204/205 guide.

The Hybrid Approach: Belt and Suspenders

Because post-quantum algorithms are relatively new compared to classical algorithms that have been studied for decades, many security experts recommend a hybrid approach: combining a post-quantum algorithm with a classical algorithm so that the system remains secure even if one of them is broken.

For example, combining ML-KEM (quantum-resistant) with X25519 (classically proven) for key exchange means an attacker must break both the lattice problem and the elliptic curve discrete logarithm problem. If quantum computers never materialize, X25519 provides tried-and-true security. If they do, ML-KEM provides the quantum resistance. Neither failure mode leaves data exposed.

This is the approach QNSQY takes for all encryption operations. We discuss the rationale in depth in our post on why hybrid encryption matters.

What You Should Do Today

Regardless of when you believe quantum computers will arrive, the following steps reduce your risk:

  1. Inventory your cryptographic dependencies. Know which systems use RSA, ECC, DH, DSA, and similar algorithms. Identify where keys are exchanged, where signatures are verified, and where long-term secrets are stored.
  2. Prioritize data by sensitivity and lifespan. Data that must remain confidential for 10+ years is at the highest risk from HNDL attacks and should be migrated first.
  3. Begin adopting post-quantum or hybrid encryption for new systems. New deployments should use NIST-standardized algorithms (ML-KEM, ML-DSA) in hybrid mode with classical algorithms.
  4. Encrypt stored data with quantum-resistant algorithms. Files and archives encrypted today with RSA or ECC alone are vulnerable. Re-encrypting with hybrid PQC provides long-term protection.
  5. Follow NIST guidance. NIST IR 8105 and the FIPS 203/204/205 standards provide authoritative guidance on algorithm selection and migration planning.

Summary

Classical public-key encryption, the kind that protects nearly all internet communications today, is built on mathematical problems that quantum computers can solve efficiently. Shor's algorithm breaks RSA, ECC, DH, and DSA. Grover's algorithm weakens symmetric encryption but does not break it at 256-bit key sizes. The timeline for a cryptographically relevant quantum computer is uncertain, but the "Harvest Now, Decrypt Later" threat means data encrypted today is already at risk. NIST has published new post-quantum standards to address this. The migration will take years. The time to start is now.

Sources

Related Articles

Protect Your Data Against Quantum Threats

QNSQY uses ML-KEM + X25519 hybrid encryption by default, providing quantum resistance today.

Originally published at quantumsequrity.com.

Top comments (0)