What cryptography must do
Cryptography gives confidentiality, integrity, authentication and non-repudiation. There are three practical families:
| Family | Examples | Security rests on | Quantum impact |
|---|---|---|---|
| Symmetric ciphers and MACs | AES, ChaCha20, HMAC | Shared secret key; no shortcut better than search | Grover: quadratic speed-up; double key length (AES-256) |
| Hash functions | SHA-2, SHA-3 | Preimage and collision resistance | Grover on preimages; collisions need about $2^{n/3}$ quantum work |
| Public-key encryption and signatures | RSA, Diffie–Hellman, ECDH, ECDSA | Factoring, discrete logarithm, elliptic-curve discrete logarithm | Shor: polynomial time. Broken. |
Shannon’s one-time pad is the only classically proven information-theoretically secure cipher, but needs a random key as long as the message and used once. The key distribution problem (how to share that key) is what public-key cryptography solved computationally, and what QKD solves physically.
RSA with small numbers
RSA picks primes $p,q$, sets $n=pq$ and $\varphi(n)=(p-1)(q-1)$, picks $e$ with $\gcd(e,\varphi)=1$ and $d\equiv e^{-1}\pmod{\varphi}$. Public key $(e,n)$; private key $(d,n)$. Encrypt $c=m^e\bmod n$, decrypt $m=c^d\bmod n$.
Real RSA uses 2048–4096-bit moduli. Security assumes recovering $p,q$ from $n$ is infeasible. Key generation needs large primes, found with probabilistic primality tests such as Miller–Rabin (below).
Discrete logarithms and Diffie–Hellman
In the multiplicative group $\mathbb Z_p^*$ with generator $g$, the forward map $x\mapsto g^x\bmod p$ is easy (square-and-multiply) but the inverse, the discrete logarithm, is believed hard classically. Toy example: modulo 17 with $g=3$, $3^4=81\equiv13$, so $\log_3 13=4$.
Diffie–Hellman: Alice sends $g^a$, Bob sends $g^b$, both compute $g^{ab}$. Elliptic-curve versions (ECDH, ECDSA) rely on the elliptic-curve discrete logarithm. Best classical attacks are sub-exponential for $\mathbb Z_p^*$ (number-field sieve) and fully exponential ($\sim\sqrt{\text{group size}}$) for generic or elliptic-curve groups. Both problems fall into the hidden subgroup problem family that Shor’s algorithm solves.
Primality testing and Miller–Rabin
Primality testing (is $n$ prime?) is far easier than factoring (find the factors). For odd $n$, write $n-1=2^s d$ with $d$ odd. For a base $a$, $n$ is a strong probable prime if
This works because modulo a prime the only square roots of 1 are $\pm1$. If $n$ is composite, at most $\tfrac14$ of the bases are “strong liars”, so $k$ random bases give error probability at most $4^{-k}$, and the error is one-sided (“composite” answers are always correct). Cost is $O(k\log^3n)$. Example: $n=341=11\cdot31$ passes the plain Fermat test to base 2, but with $340=4\cdot85$ we get $2^{85}\equiv32$ and $32^2\equiv1\pmod{341}$, a non-trivial square root of 1, so 341 is exposed as composite. The deterministic AKS test (2002) proves polynomial-time primality but is slower in practice.
Shor’s algorithm
Shor (1994) factors $N$ in polynomial time, roughly $O((\log N)^3)$ gate operations, by reducing factoring to order finding:
- Pick random $a$ coprime to $N$.
- Quantum phase estimation with the QFT finds the period $r$ of $f(x)=a^x\bmod N$.
- If $r$ is even and $a^{r/2}\not\equiv-1$, then $\gcd(a^{r/2}\pm1,N)$ yields non-trivial factors with good probability.
The same period-finding idea solves discrete logarithms in any finite abelian group, including elliptic-curve groups. Hence RSA, DH, ECDH, ECDSA and EdDSA all fall.
Resources. Early estimates needed ~20 million noisy qubits for RSA-2048; a 2025 analysis by Gidney reports under one million noisy qubits and about a week. Today’s machines are far from this scale, but estimates keep falling.
Grover and symmetric cryptography
Grover search finds a marked item among $N$ in $O(\sqrt N)$ queries (provably optimal). Against a $k$-bit key this costs about $2^{k/2}$ operations, but Grover parallelises poorly and has large overheads, so AES-256 is widely considered quantum-safe and AES-128 acceptable for now. Quantum computers do not break one-time pads or information-theoretic MACs.
Harvest now, decrypt later
An adversary can record encrypted traffic today and decrypt it once a quantum computer exists. Mosca’s inequality: if data must stay secret for $x$ years, migration takes $y$ years, and a cryptographically relevant quantum computer arrives in $z$ years, you are at risk when $x+y>z$. This is why key exchange is migrated first and why QKD and post-quantum cryptography are both being deployed before large quantum computers exist.