Shor's & Grover's Algorithms Explained

Quantum computers don't just run classical algorithms faster — they exploit quantum superposition and interference to solve certain problems exponentially faster. Two algorithms threaten most deployed cryptography: Shor's (breaks RSA/ECC) and Grover's (weakens symmetric/hash).

Shor's algorithm (1994) solves integer factorization and discrete logarithm in polynomial time on a quantum computer. This directly breaks RSA (based on factoring), Diffie-Hellman (discrete log mod p), and ECDH/ECDSA (elliptic curve discrete log).

The key ingredient in Shor's is the Quantum Fourier Transform (QFT) — an exponentially faster quantum version of the DFT. For period finding, QFT identifies the period of f(x) = a^x mod N, from which the factors of N are derived via GCD.

To factor N: (1) Choose random a < N, check gcd(a,N)=1. (2) Find period r of f(x)=a^x mod N using QFT. (3) With high probability, gcd(a^{r/2}±1, N) yields a non-trivial factor. Classical step is O(log N); quantum period-finding is O((log N)^3) — polynomial.

Classical factoring best: GNFS — sub-exponential O(exp((64/9 log N)^{1/3} log log N)^{2/3})). Shor's on a fault-tolerant quantum computer: polynomial O((log N)^3). RSA-2048 requires ~4000 logical qubits + ~10^9 gate operations. Today's NISQ computers have ~1000 noisy qubits — not yet a threat.

Grover's algorithm (1996) provides a quadratic speedup for unstructured search. For a search space of N items, classical algorithms need O(N) queries; Grover's needs O(√N). Applied to cryptography: breaks n-bit symmetric keys in O(2^{n/2}) instead of O(2^n).

AES-128: classical security 2^128, Grover's reduces to 2^64 — insecure against a large quantum computer. AES-256: 2^256 → 2^128 — still secure. Fix: double symmetric key sizes. SHA-256 collision resistance: 2^128 → 2^85 (birthday+Grover). SHA-256 preimage: 2^256 → 2^128 — OK.

Current NISQ quantum computers (IBM Heron: 133 qubits, Google Sycamore: 70 qubits) are too small and too noisy for cryptographically relevant computations. Estimates for RSA-2048 breaking: 2035-2050 with fault-tolerant quantum computers. Harvest-now-decrypt-later attacks are a current threat.

Adversaries collect encrypted traffic today and store it. When a quantum computer is available, they decrypt it retroactively. This makes long-lived secrets (classified government data, medical records) vulnerable today. PQC migration must start now for such data.

Lattice problems (LWE, SIS), code-based problems (McEliece), hash-based signatures (SPHINCS+), multivariate problems — no known polynomial-time quantum algorithm. These are the foundation of NIST post-quantum standards.

NIST PQC standards (ML-KEM, ML-DSA, SLH-DSA) were finalized in 2024. Organizations should: inventory current cryptographic usage, identify long-lived data, prioritize PQC deployment for key exchange (most urgent due to harvest-now-decrypt-later). Signatures have more time.

Shor's algorithm (polynomial time) breaks RSA, DH, and ECC. Grover's algorithm (quadratic speedup) halves symmetric key strength. Fix: migrate to NIST PQC standards (lattice-based). Next: CRYSTALS-Kyber KEM.