Skip to content
PQC Portal
ไทย

Step 2 of 4

The threat

Which cryptography a quantum computer breaks, how big a machine it would take, and why recorded traffic is already at risk.

Written by

  1. Step 1: Quantum basics
  2. Step 2: The threat
  3. Step 3: The fix
  4. Step 4: The cost & where to start

Two algorithms, very different impact

Public-key cryptography rests on problems like factoring and discrete logarithms. A quantum algorithm from 1994 solves both efficiently.

Shor

Shor's algorithm (1994)

Factors integers and computes discrete logarithms in polynomial time. That breaks RSA, Diffie-Hellman and elliptic-curve cryptography outright. Bigger keys don't help.

Grover

Grover's algorithm (1996)

Searches without structure with a quadratic speedup. In theory it halves the security level of a symmetric key; in practice it parallelises poorly. 256-bit keys are the standard answer.

Broken by Shor
  • RSA
  • Diffie-Hellman
  • ECDH / X25519
  • ECDSA
  • EdDSA
Reduced margin
  • AES-128
Considered quantum-resistant
  • AES-256
  • SHA-2 / SHA-3
  • ML-KEM
  • ML-DSA
  • SLH-DSA

Harvest now, decrypt later

An adversary doesn't need a quantum computer today. Recording encrypted traffic is cheap, and storage lasts. Anything that must stay secret for years is already exposed.

SenderReceiverAttacker's storageyears laterQuantum computerreadable
  1. 1Traffic is recorded todayAn attacker copies encrypted traffic between two parties. It can't be read yet, but storing it is cheap.
  2. 2The data waitsRecordings can sit in storage for years. Anything that must stay secret that long is already exposed.
  3. 3Q-DayA quantum computer able to break today's public-key cryptography becomes available to the attacker.
  4. 4Old secrets are openedShor's algorithm breaks the recorded classical key exchange, so the stored traffic can be decrypted. Post-quantum key exchange used today prevents this.

Mosca's inequality

X + Y > Z ?

If X + Y > Z, data you send today will still be sensitive when it can be decrypted.

No margin: you finish exactly when protection is needed.

Nobody knows Z. Published estimates vary widely; pick your own.

Key exchange is urgent because of harvest-now-decrypt-later. Signatures can't be harvested the same way, but long-lived roots of trust and firmware signing keys need years of lead time.

Technical deep dive

Shor's algorithm reduces factoring N to finding the period r of f(x) = aˣ mod N. The quantum Fourier transform finds r efficiently; gcd(a^(r/2) ± 1, N) then usually gives a factor. A variant solves discrete logarithms, including on elliptic curves.

Published estimates need fewer logical qubits to break 256-bit elliptic curves than RSA-2048, because ECC keys are much smaller.

Grover finds a marked item among N in about √N steps, and the steps are sequential. NIST's post-quantum security categories use AES-128 key search as the baseline for the lowest category.

Mosca's inequality, from Michele Mosca: x = how long data must stay secret, y = how long migration takes, z = time until a cryptographically relevant quantum computer. If x + y > z, act now.