Cryptanalysis

Quantum Computing &
Cryptanalysis

Two quantum algorithms reshape what codes can be broken. Shor's algorithm makes it easy to crack the mathematics behind almost all of today's public-key encryption β€” the digital locks protecting websites, banks, and cryptocurrencies (it factors integers and computes discrete logarithms in polynomial time, an exponential speedup over any known classical method). Grover's algorithm speeds up brute-force guessing, but only enough that doubling key lengths restores safety (a quadratic speedup: roughly √N tries instead of N). The result: asymmetric systems like RSA and ECC must be replaced entirely, while symmetric systems just need bigger keys.

Shor's Algorithm Grover's Algorithm Quantum Fourier Transform Period Finding RSA Broken in Polynomial Time ECC Broken in Polynomial Time

How Quantum Algorithms Threaten Classical Cryptosystems

πŸ”‘Shor's Algorithm and Public-Key Cryptography

RSA keeps secrets safe because of a lopsided piece of arithmetic: multiplying two enormous prime numbers is easy, but working backwards β€” recovering the primes from their product β€” is practically impossible for ordinary computers.

EASY β€” MULTIPLY
p Γ— q = N
Instant, even for 600-digit numbers
HARD β€” FACTOR
N β†’ p, q
Best classical method is sub-exponential (General Number Field Sieve, Ln[β…“, 1.923]) β€” RSA-2048 is beyond any foreseeable classical hardware

In 1994 Peter Shor showed that a quantum computer could do that reverse step quickly, by converting factoring into a pattern-finding problem that quantum machines are naturally good at (period finding via the Quantum Fourier Transform, in O((log N)Β³) time β€” polynomial rather than sub-exponential).

The same trick breaks the other big family of public-key systems, which rely on a different "easy one way, hard the other" problem (the discrete logarithm problem, or DLP, underpinning Diffie-Hellman key exchange and all elliptic curve cryptography). Both problems share the same underlying mathematical structure (they are instances of the Hidden Subgroup Problem over abelian groups), so one sufficiently large, reliable quantum computer would render every one of these simultaneously and completely insecure:

RSA DSA Diffie-Hellman ECDSA ECDH EdDSA
HOW BIG A MACHINE WOULD IT TAKE?

Early analyses said millions of physical qubits. A March 2026 paper (Cain, Xu, King and colleagues, arXiv:2603.28627) showed that advances in high-rate quantum error-correcting codes shrink this to as few as ~10,000 reconfigurable atomic qubits. With 26,000 such qubits, a standard elliptic-curve key (P-256) could fall in a few days; factoring RSA-2048 would take roughly ten to a hundred times longer at that scale.

πŸ”Grover's Algorithm and Symmetric Cryptography

Grover's algorithm (1996) speeds up pure guessing: to find one right answer among N possibilities, a quantum computer needs only about the square root of N attempts instead of N (O(√N) oracle queries). Against encryption with no shortcut other than trying every key, this effectively halves the key length.

N
CLASSICAL TRIES
β†’
√N
QUANTUM TRIES
AES-128
⚠ ~64-bit effective
Within reach of a quantum adversary
AES-256
βœ“ ~128-bit effective
Remains computationally infeasible
SHA-256
βœ“ ~128-bit preimage
Adequate security margin retained

The fix is simple: use longer keys and hashes. No symmetric primitive is fundamentally broken.

A proven speed limit: no quantum algorithm can search faster than Grover's (Bennett, Bernstein, Brassard, and Vazirani proved the quadratic speedup is optimal for unstructured search). So symmetric cryptography faces a bounded, well-characterised threat β€” unlike the existential threat to asymmetric systems.

Shor's Algorithm β€” Conceptual Pipeline

From Factoring to Period Finding

STEP 1 Β· CLASSICAL β€” REDUCTION

An ordinary computer converts factoring into finding a repeating pattern. Pick a random number a and look at the sequence of powers of a, keeping only remainders after dividing by N (the function f(x) = ax mod N); this sequence repeats with some period r. Knowing r usually reveals the factors (if r is even and ar/2 β‰’ βˆ’1 (mod N), then gcd(ar/2 Β± 1, N) yields a non-trivial factor).

STEP 2 Β· QUANTUM β€” PERIOD FINDING

The quantum computer finds that period. It evaluates the sequence for all inputs at once (a superposition over all x in {0, …, 22nβˆ’1}, with f(x) computed into an ancilla register), then applies the Quantum Fourier Transform β€” think of it as a pattern detector β€” and measures. The measurement points to the period (a value close to a multiple of 22n/r, from which r is extracted with the continued-fractions algorithm).

STEP 3 Β· CLASSICAL β€” POST-PROCESSING

An ordinary computer finishes the job, turning the period into the factors (computing gcd(ar/2 Β± 1, N)). If it gets unlucky it retries with a different random a β€” success typically comes within one or two attempts (the success probability per attempt is at least 1 βˆ’ 1/2kβˆ’1, where k is the number of distinct prime factors of N).

Key insight: everything except Step 2 is easy classically. Finding the period the ordinary way means checking an astronomical number of values; the quantum step replaces all that with a single pattern-reading measurement over a superposition of every function value at once. That substitution is the entire exponential speedup.

The Quantum Fourier Transform

Quantum Fourier Transform circuit β€” Hadamard and controlled-rotation gates acting on n qubits
This circuit is the "pattern detector" at the heart of Shor's algorithm: it converts a hidden repetition spread across the qubits into something a single measurement can read off directly. Technically, each qubit receives a Hadamard gate followed by progressively finer controlled-phase rotations (Rk = diag(1, e2Ο€i/2ᡏ)), and the qubit order is swapped at the end β€” mapping computational basis states to their Fourier-dual representation for efficient extraction of periodicities. Source: Wikipedia β€” "Quantum Fourier transform"

Cryptographic Vulnerabilities Exposed by Quantum Computation

Cryptosystem Hard Problem Quantum Attack Complexity Status
RSA Integer factorisation Shor's β†’ period finding via QFT O((log N)Β³) βœ— Broken
Diffie-Hellman Discrete logarithm (DLP) Shor's β†’ DLP variant O((log p)Β³) βœ— Broken
ECDSA / ECDH / EdDSA Elliptic curve DLP Shor's β†’ ECDLP variant O((log n)Β³) βœ— Broken
DSA Discrete logarithm Shor's β†’ DLP variant O((log p)Β³) βœ— Broken
AES-128 Key search (brute force) Grover's β†’ √N speedup O(2⁢⁴) ⚠ Weakened
AES-256 Key search (brute force) Grover's β†’ √N speedup O(2¹²⁸) βœ“ Adequate
SHA-256 Preimage resistance Grover's β†’ √N speedup O(2¹²⁸) βœ“ Adequate
SHA-3-256 Preimage resistance Grover's β†’ √N speedup O(2¹²⁸) βœ“ Adequate

Quantum Cryptanalytic Techniques

πŸ”‘

Shor's Algorithm

Factors integers and computes discrete logarithms in polynomial time by reducing both problems to quantum period finding (via the QFT). Completely breaks RSA, DSA, DH, and all standard elliptic curve schemes. Published by Peter Shor in 1994; demonstrated on 15 (IBM, 2001) and 21 (photonic, 2012).

πŸ”

Grover's Algorithm

Speeds up unstructured search β€” finding one answer among N with only about √N tries (optimal O(√N) queries; provably no quantum algorithm can do better). Halves effective key length of symmetric ciphers and hash functions. Mitigation: double key sizes (AES-256, SHA-512).

πŸ“

Hidden Subgroup Problem

The mathematical generalisation underlying Shor's algorithm. Efficient quantum solutions exist for the "well-behaved" cases (HSP over abelian groups, covering factoring and DLP). The harder cases (non-abelian groups β€” relevant to lattice and graph isomorphism problems) remain open, which is one reason lattice-based PQC is considered quantum-resistant.

⚑

Emerging Approaches β€” and Hype

In March 2026 the "JVG algorithm" claimed RSA-2048 could fall to just ~5,000 qubits; the cryptography community quickly identified fatal flaws and the claim is widely regarded as debunked. The genuine progress is quieter: better error correction and circuit compilation have cut qubit estimates from millions to hundreds of thousands (Google, ECDLP-256) and even ~10,000 (atom arrays). The threat advances through engineering, not miracle algorithms.

Classical vs Quantum Approaches to Cryptanalysis

Aspect Classical Cryptanalysis Quantum Cryptanalysis
Factoring (RSA-2048) GNFS β€” sub-exponential; estimated 10²⁴+ operations; infeasible Shor's β€” O(nΒ³) gate complexity; feasible with ~10k–1M physical qubits, depending on architecture
Discrete log (DH-2048) Index calculus β€” sub-exponential; comparable to factoring Shor's DLP variant β€” polynomial time; same qubit requirements
ECDLP (P-256) Pollard's rho β€” O(2¹²⁸); infeasible Shor's ECDLP variant β€” polynomial; ~26k atomic qubits, days (Cain et al. 2026)
AES-128 key search Brute force β€” O(2¹²⁸); infeasible Grover's β€” O(2⁢⁴); potentially feasible but hardware-intensive
SHA-256 preimage Brute force β€” O(2²⁡⁢); infeasible Grover's β€” O(2¹²⁸); infeasible (adequate security margin)
Nature of speedup Algebraic/structural exploitation (e.g., lattice sieving, index calculus) Shor's: exponential; Grover's: quadratic (provably optimal)
Hardware requirement Classical CPUs/GPUs/ASICs; mature fabrication Fault-tolerant quantum processor; error correction overhead
Current feasibility Fully operational at all relevant scales Largest genuine Shor's factorisation to date: 21 (2012); cryptographic scale still years away

Qubit Estimates for Cryptographically Relevant Attacks

How Close Is the Threat?

The practical timeline for quantum cryptanalysis depends on three factors: how many qubits a machine has, how error-prone they are, and how fast its gates run. As error correction improves, the physical qubit requirements drop rapidly β€” five orders of magnitude over two decades of research.

RSA-2048
~10,000 atomic qubits
Runtime 10–100Γ— longer than P-256 at that scale (Cain et al., 2026); down from ~1M qubits with surface codes
ECC P-256
~26,000 atomic qubits β†’ days
Or minutes on <500k superconducting qubits (Google, 2026); smaller key β†’ lower quantum complexity than RSA
AES-128 (GROVER)
2⁢⁴ quantum operations
Theoretically feasible but requires serial depth; NIST MAXDEPTH constraints limit parallelism
AES-256 (GROVER)
2¹²⁸ quantum operations
Remains computationally infeasible even for quantum adversaries β€” adequate security margin
Exponential vs Quadratic: the critical distinction in quantum cryptanalysis. Shor's algorithm provides an exponential speedup β€” it doesn't just make attacks faster, it makes previously impossible attacks trivially easy. Grover's algorithm provides a quadratic speedup β€” it makes attacks faster but not categorically different. This is why asymmetric cryptography must be replaced entirely, while symmetric cryptography need only increase key sizes.

Quantum Cryptanalysis Timeline

Year Milestone Significance
1994 Shor's algorithm published Polynomial-time factoring and DLP on quantum computer β€” theoretical end of RSA/ECC
1996 Grover's algorithm published Optimal quadratic speedup for unstructured search β€” symmetric keys effectively halved
2001 IBM factors 15 with 7-qubit NMR First physical demonstration of Shor's algorithm; proof of concept only
2012 21 factored with photonic qubits Largest integer factored by Shor's; still far from cryptographic relevance
2019 Google achieves quantum supremacy 53-qubit Sycamore; random circuit sampling β€” not cryptanalytic but hardware milestone
2024 NIST publishes PQC standards FIPS 203/204/205 β€” migration from quantum-vulnerable algorithms begins formally
2025 RSA-2048 estimate drops below 1M qubits; NIST selects HQC Gidney (Google) shows factoring RSA-2048 in under a week with fewer than one million noisy qubits; HQC chosen as fifth PQC algorithm (backup KEM to ML-KEM)
2026 Google Quantum AI: ECDLP-256 in <500k physical qubits ~20Γ— reduction in physical qubits for breaking ECC, minutes runtime; responsible disclosure via zero-knowledge proof; 2029 PQC migration deadline announced
2026 Shor's with ~10,000 atomic qubits Cain et al. show cryptographic-scale Shor's possible on reconfigurable atom arrays with high-rate error-correcting codes