Quantum Computing and Cryptography: What Breaks, What Survives, What Comes Next

Shor's Algorithm: The Breaker of Public Keys

In 1994, Peter Shor showed that a quantum computer could factor integers and compute discrete logs in polynomial time: $O((\log N)^3)$ gate operations. Classical algorithms take sub-exponential time: $O(e^{(\log N)^{1/3}})$ for the General Number Field Sieve.

Demo: Shor's Algorithm Factoring RSA-15 End-to-End

Here's a complete Qiskit implementation factoring $N = 15$ using $a = 7$. This is the "Hello World" of quantum cryptanalysis. We find the period $r$ of $7^x \bmod 15$, then classically derive factors $3$ and $5$.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, transpile
from qiskit.circuit.library import QFT
from qiskit_aer import AerSimulator
from math import gcd
import numpy as np

"""
Shor's Algorithm: Factor N = 15 using base a = 7
Goal: Find period r such that a^r ≡ 1 mod N
Then factors = gcd(a^(r/2) ± 1, N) if r is even and a^(r/2) ≠ -1 mod N
"""

N = 15
a = 7

# Step 1: Classical pre-checks
assert gcd(a, N) == 1, "a must be coprime to N"
print(f"Factoring N={N} with base a={a}")

# Step 2: Determine register sizes
# Counting register: n qubits, where 2^n >= N^2 for good success probability
# For N=15, n=4 gives 2^4=16 >= 15, but 8 is safer. We'll use 8.
n_count = 8  # counting qubits for QFT phase estimation
n_target = 4  # ceil(log2(N)) = 4 qubits to represent 0..14

q_count = QuantumRegister(n_count, 'count')
q_target = QuantumRegister(n_target, 'target')
c_out = ClassicalRegister(n_count, 'out')
qc = QuantumCircuit(q_count, q_target, c_out)

# Step 3: Initialize superposition on counting register
# |0> -> H^n -> (|0> + |1>)^n / sqrt(2^n)
# This creates equal superposition over all 2^n basis states
qc.h(q_count)
qc.barrier()

# Step 4: Initialize target register to |1>
# We need |1> so that U|y> = |a*y mod N>
qc.x(q_target[0])
qc.barrier()

# Step 5: Controlled Modular Exponentiation U: |x>|y> -> |x>|a^x * y mod N>
# This is the expensive part. We implement U^(2^j) controlled by count[j]
# For N=15, a=7: powers cycle 7,4,13,1 every 4. So period r=4
# We manually build controlled multiplications for 7, 7^2=4, 7^4=1, 7^8=1

def c_amod15(qc, control, target, a_pow):
    """
    Controlled multiplication by a_pow mod 15.
    Hardcoded for N=15. Real implementation needs generic modular multipliers.
    """
    if a_pow == 7:
        # |x> -> |7x mod 15>
        qc.swap(target[2], target[3], control=control)
        qc.swap(target[1], target[2], control=control)
        qc.swap(target[0], target[1], control=control)
    elif a_pow == 4:  # 7^2 mod 15
        qc.swap(target[1], target[3], control=control)
        qc.swap(target[0], target[2], control=control)
    elif a_pow == 13:  # 7^3 mod 15
        qc.swap(target[0], target[3], control=control)
        qc.swap(target[1], target[3], control=control)
        qc.swap(target[2], target[3], control=control)
    # a_pow == 1 is identity, do nothing

# Apply controlled-U^(2^j) for j = 0..n_count-1
for j in range(n_count):
    power = pow(a, 2**j, N)  # a^(2^j) mod N
    c_amod15(qc, q_count[j], q_target, power)

qc.barrier()

# Step 6: Inverse Quantum Fourier Transform on counting register
# QFT extracts the phase, which encodes s/r where s is random
qc.append(QFT(n_count, inverse=True), q_count)
qc.barrier()

# Step 7: Measure counting register
qc.measure(q_count, c_out)

# Step 8: Simulate
simulator = AerSimulator()
compiled = transpile(qc, simulator)
result = simulator.run(compiled, shots=1024).result()
counts = result.get_counts()

print(f"Measurement results: {counts}")

# Step 9: Classical post-processing - extract period r
# Most frequent measurement m estimates s/r where m/(2^n) ≈ s/r
measured = int(max(counts, key=counts.get), 2)
print(f"Most frequent measurement: {measured}")

# Find r using continued fractions: measured / 2^n = s/r
from fractions import Fraction
frac = Fraction(measured, 2**n_count).limit_denominator(N)
s, r = frac.numerator, frac.denominator
print(f"Estimated s={s}, r={r}")

# Step 10: Check if we got a useful r
if r % 2 == 0:
    cand1 = gcd(pow(a, r//2) - 1, N)
    cand2 = gcd(pow(a, r//2) + 1, N)
    factors = [f for f in [cand1, cand2] if 1 < f < N]
    if factors:
        print(f"Success! Factors of {N}: {factors}")
    else:
        print(f"r={r} failed: a^(r/2) ≡ -1 mod N. Retry with different a.")
else:
    print(f"r={r} is odd. Retry with different a.")

# Expected output: r=4, factors [3, 5]

Grover's Algorithm: The Quadratic Speedup

Lov Grover's 1996 algorithm searches an unsorted database of $N$ items in $O(\sqrt{N})$ operations instead of $O(N)$. For cryptography, this means brute-force key search gets a quadratic speedup.

Impact on symmetric crypto: Double your key length and you're fine. AES-256 remains secure for decades even post-quantum. The real threat is to asymmetric primitives where we exchange those keys.

Post-Quantum Cryptography: What Comes Next

NIST completed its first PQC standardization round in 2024. These algorithms run on classical computers but rely on math problems even quantum computers can't solve efficiently.

Harvest Now, Decrypt Later (HNDL)

The most urgent threat isn't future key exchange. It's encrypted data intercepted today and stored until quantum computers exist. If your data must stay secret for $X$ years, and quantum computers arrive in $Y$ years, you need to migrate if $X > Y$.

Who should worry now: Governments, healthcare (HIPAA 50+ years), financial services, infrastructure operators, anyone with trade secrets or PII that needs >10 year confidentiality.

Who can wait: Ephemeral TLS sessions for cat videos, short-lived API tokens, data with <5 year value window. But remember: key exchange today protects data tomorrow.

BB84 & Quantum Key Distribution

Quantum mechanics doesn't just threaten crypto. It enables new primitives. BB84, invented by Bennett and Brassard in 1984, lets two parties create a shared secret with security guaranteed by physics, not math.

Practical take: QKD is real and deployed for high-security links. But for most organizations, PQC algorithms running on classical infrastructure are the pragmatic path. Use QKD for crown jewels, PQC for everything else.

Migration Guide: Crypto Agility

Don't rip-and-replace. Build crypto agility: the ability to swap algorithms without rewriting applications. NIST and NSA recommend hybrid modes during transition.

Common Myths