Chapter 23 — Why quantum computers break today's public-key crypto

What a quantum computer actually is (enough to reason about it)

   Classical bit:  0 or 1.
   Qubit:          a superposition -- amplitudes for BOTH 0 and 1 at once.

   n qubits represent 2^n amplitudes simultaneously. A quantum algorithm
   manipulates all of them in parallel, then uses INTERFERENCE to make the
   wrong answers cancel out and the right answer stand out when measured.

   This is NOT "tries every answer at once and picks one". Measurement
   collapses to a single value. The art is arranging the interference so
   that value is the one you want, with high probability.

It is not a faster classical computer. It's fast at a narrow set of problems with the right structure — and factoring and discrete-log have exactly that structure (periodicity).

Shor's algorithm — the crypto-breaker

Peter Shor showed in 1994 that a quantum computer can find the period of a function exponentially faster than any known classical method. Factoring and discrete-log both reduce to period-finding.

   PROBLEM                    CLASSICAL BEST           QUANTUM (Shor)
   -------                    --------------           --------------
   Factor a 2048-bit RSA      ~ 10^20 years            hours to days*
     modulus                   (sub-exponential)        (polynomial)
   Discrete log (DH)          same ballpark            same -- broken
   Elliptic-curve discrete    ~ 2^128 operations       broken; needs FEWER
     log (ECC)                                          qubits than RSA

   * on a cryptographically-relevant quantum computer (CRQC) that does
     not yet exist publicly. Recent resource estimates: under ~1 million
     noisy qubits for RSA-2048. Today's largest devices: ~1000-1500 qubits,
     far too noisy. The gap is large -- but engineering, not physics.

The consequence is total, not partial. A bigger RSA key doesn't help — Shor scales polynomially. RSA-4096 buys you almost nothing over RSA-2048 against a quantum attacker. ECC is worse off per bit: P-256 needs fewer logical qubits to break than RSA-2048.

Grover's algorithm — the mild one

Grover's algorithm searches an unstructured space of size N in about sqrt(N) steps. Applied to symmetric crypto and hashes:

   AES-128:  2^128 brute force  ->  ~2^64 quantum   -- UNCOMFORTABLE
   AES-256:  2^256 brute force  ->  ~2^128 quantum  -- STILL FINE

   SHA-256 preimage: 2^256      ->  ~2^128 quantum  -- STILL FINE
   SHA-256 collision: 2^128     ->  ~2^85 quantum   -- fine (and Grover
                                    barely helps collisions in practice)

The fix is trivial: double the key size. Use AES-256, SHA-384/SHA-512. That's the entire post-quantum story for symmetric crypto — which is why this guide told you to pick AES-256 back in Chapter 13.

   +------------------------------------------------------------------+
   |  QUANTUM IMPACT SUMMARY                                           |
   |                                                                  |
   |  Public-key (RSA, DH, ECDH, ECDSA, EdDSA)  ->  BROKEN. Replace.   |
   |  Symmetric (AES)                           ->  use 256-bit. Done. |
   |  Hashes (SHA-2, SHA-3)                     ->  use >= 384-bit     |
   |                                                output. Done.      |
   +------------------------------------------------------------------+

"Harvest now, decrypt later" — why this is urgent today

You might think: "no quantum computer exists, so I have years." For confidentiality, that reasoning is wrong.

   1. TODAY:  an adversary records your encrypted traffic (or steals
              encrypted backups) and stores it. Cheap. Nation-states are
              widely assumed to be doing this at scale already.

   2. LATER:  a CRQC arrives (estimates cluster around the 2030s).

   3. THEN:   they run Shor on the recorded key exchanges, recover the
              session keys, and decrypt everything from step 1
              retroactively.

This is HNDL (harvest now, decrypt later), also called store-now-decrypt- later. The question that matters:

Does any data you send today still need to be secret in 2035?

Health records, state secrets, source code, legal documents, long-lived credentials, biometric templates — yes. For those, the migration deadline is now, not "when quantum computers arrive".

For signatures and authentication, HNDL doesn't apply the same way — a signature forged in 2035 can't retroactively authenticate a 2026 TLS handshake. So signature migration is important but less time-critical than key exchange.

The official timelines