Day 1: Why Quantum Breaks Classical Crypto — Shor's Algorithm

Phase 3 · July 8, 2026

Agenda (2–3 hours)

• Read (60 min): NIST IR 8413 §1–2 (background and rationale); Scott Aaronson's "Quantum Computing Since Democritus" Ch. 10 (free online excerpt) OR Cloudflare's "A Relatively Easy to Understand Primer on Elliptic Curve Cryptography" + quantum section
• Study (60 min): Shor's algorithm at a conceptual level
• Challenge (45 min): Written explanation from first principles

The Classical Security Assumptions Under Threat

The asymmetry: symmetric crypto (AES, SHA) just needs larger keys. Public-key
crypto (RSA, ECDH, ECDSA) is fundamentally broken by quantum computers.
The same math that makes public-key crypto possible makes it quantum-vulnerable.

Why Factoring = Private Key Recovery

RSA security: given n = p × q (public), finding p and q is hard classically.
From p and q, you can derive the private key d.

Classical best: Number Field Sieve — sub-exponential but still impractical for 2048-bit.
Quantum (Shor's): polynomial time in the number of qubits.

For ECDH/ECDSA: Shor's also solves the elliptic curve discrete logarithm problem
in polynomial time. Given a public key Q = dP, find d.

Shor's Algorithm: Conceptual Structure

You don't need to implement this — you need to understand WHY it works.

Key insight: integer factoring can be reduced to period-finding.
Shor's finds the period of f(x) = a^x mod n using the Quantum Fourier Transform.

Classical period finding: exponential time (try every period)
Quantum period finding:   polynomial time (QFT exploits superposition + interference)

The QFT can simultaneously test all possible periods via quantum parallelism.
It finds the period in O(log² n) quantum operations.

Once you have the period, finding factors is a classical polynomial-time step.

Why This Isn't Imminent — But Is Urgent

Current state (2026): best quantum computers have ~1000–10,000 physical qubits.
Breaking RSA-2048 requires an estimated ~4000 logical qubits (millions of physical).

But: "harvest now, decrypt later" (HNDL) attacks don't need a quantum computer today.
An adversary records your encrypted traffic now, stores it, and decrypts it later
when a cryptographically-relevant quantum computer (CRQC) exists.

For data with a sensitivity lifetime > 10 years: the threat is real today.

For your team: satellite device identities, provisioning keys, and long-lived certificates
may fall into this category.

Practice Exercise

Read the Wikipedia article on Shor's algorithm (don't skip the math — skim for structure).
Then watch IBM's 5-minute YouTube explainer on quantum period finding.

Answer in writing: if Shor's algorithm requires ~4,000 logical qubits and current hardware
has ~10,000 noisy physical qubits — what is the missing piece? (Hint: error correction.)

Challenge Assignment

Write a 1-page threat assessment structured as:

Assets at risk in your provisioning service:

• List every piece of data your team's service encrypts or signs
• For each: what is its sensitivity lifetime? (minutes? years? decades?)

Classical crypto used today:

• ECDH for TLS key exchange, ECDSA for cert signatures — which specific curves?

Quantum threat applicability:

• Which assets have a sensitivity lifetime long enough to be at risk from HNDL today?
• What is the earliest plausible date for a CRQC? Cite a source.

This is the first section of your Phase 3 migration roadmap.

Resources

• NIST IR 8413: pubs.nist.gov — background on PQC standardization
• Scott Aaronson's blog: scottaaronson.blog — approachable quantum complexity writing
• "Harvest Now, Decrypt Later": CISA advisory on HNDL attacks