The Crypto
Threat
Explained

Algorithm 1

Shor's Algorithm (1994)

Peter Shor's 1994 polynomial-time quantum algorithm for integer factorization and the discrete logarithm problem is the primary cryptographic threat. It does not merely speed up existing attacks — it fundamentally changes the complexity class.

What it solves

Shor's algorithm solves two related problems in polynomial time:

• Integer factorization: Given N = p × q, find p and q. This is the basis of RSA security.
• Discrete logarithm problem (DLP): Given g and g^x mod p, find x. This is the basis of Diffie-Hellman (DH), DSA, and — over elliptic curves — ECDH and ECDSA.

Classical complexity vs. quantum complexity

Classically, the best known algorithm for factoring an n-bit number is the General Number Field Sieve (GNFS), which runs in sub-exponential time O(exp(n^{1/3})). For RSA-2048, this requires roughly 2^112 operations — infeasible. Shor's algorithm factors the same number in O(n³) quantum operations — polynomial. The security assumption collapses entirely.

Which algorithms are broken

Algorithm 2

Grover's Algorithm (1996)

Lov Grover's 1996 algorithm provides a quadratic speedup for unstructured search. Given a black-box function f(x) = 1 for exactly one secret x, a classical computer needs O(N) evaluations to find x; Grover's algorithm needs O(√N).

Impact on symmetric cryptography

For symmetric ciphers and hash functions, the relevant attack is a brute-force key search over a keyspace of size 2^n. Grover's reduces this from 2^n to 2^{n/2}:

Practical note on Grover's

Unlike Shor's, Grover's speedup is quadratic, not exponential. Doubling the key length (e.g., AES-128 → AES-256) fully restores the security margin. The response to Grover's is straightforward: use AES-256, use SHA-384+, use longer HMAC keys. There is no need for exotic new symmetric algorithms.

Active threat

Harvest Now, Decrypt Later

The most operationally urgent threat does not require a quantum computer to exist today. It requires only that adversaries believe one will exist within the data's useful lifetime.

The attack model

A nation-state adversary intercepts and records encrypted traffic today — TLS handshakes, VPN sessions, encrypted emails, healthcare records, intellectual property transfers. The data is stored at scale. When a CRQC becomes available, the attacker decrypts it retroactively. The initial capture is cheap and persistent. The decryption capability is the only time-gated element.

Evidence of HNDL activity

Multiple US government advisories have confirmed that this threat model is credible and active. The NSA's 2022 CNSA 2.0 guidance explicitly states: "NSA is concerned about the threat of a 'harvest now, decrypt later' strategy." CISA's 2023 quantum-readiness guidance repeats this warning. Intelligence community assessments (unclassified versions) confirm nation-state adversaries are collecting encrypted data at scale.

What data is at risk

• State secrets and classified communications (highest priority)
• Financial transaction records, healthcare data, legal communications (long retention requirements)
• Intellectual property in R&D, drug development, defense
• Personal communications and metadata (surveillance targets)
• Certificate authority private keys and HSM-protected secrets (if not air-gapped)

Planning framework

Mosca's Inequality

Michele Mosca formulated the key planning inequality that governs whether an organization is currently at risk:

Applying the framework

Example: A financial institution holds transaction records that must remain confidential for 20 years (X = 20). Their legacy core banking system will take 8 years to migrate (Y = 8). If a CRQC arrives in 2033 (Z = 8 years from now), then X + Y = 28 > Z = 8: they are already at risk, and migration should have begun years ago.

Most enterprises estimating honestly will find they are in this position. That is why NIST, NSA, ENISA, and BSI all recommend beginning migration immediately, regardless of the precise CRQC timeline.

Full reference

Quantum-Vulnerable vs. Quantum-Safe Algorithms