Why Quantum Computers Threaten Cryptography

Why Quantum Computers Threaten Cryptography

The internet runs on cryptography. Every HTTPS connection, every encrypted message, every digital signature, every cryptocurrency transaction, every software update relies on mathematical problems believed to be hard for classical computers. "Hard" here means "would take longer than the age of the universe to solve with the best classical algorithm on the biggest classical computer." Public-key cryptography is the entire trust layer of the modern digital world, and it all rests on that assumption.

Quantum computers change the picture dramatically, not by being faster classical machines, but by running algorithms that attack those specific hard problems with polynomial-time solutions. That is the short version. The longer version is what this lesson is about.

RSA and the Factoring Problem

RSA encryption, invented in 1977, is built on a single simple observation: multiplying two large primes is easy, factoring their product is hard. Multiplying two 1024-bit primes p and q takes milliseconds on a laptop. Factoring their product N = p·q takes longer than the age of the universe with the best known classical algorithm (the general number field sieve).

Shor's algorithm, published by Peter Shor in 1994, factors N in polynomial time on a quantum computer. It does this by converting the factoring problem into a period-finding problem, and quantum interference can find periods exponentially faster than any classical method. A fault-tolerant quantum computer with roughly 4000 logical qubits could break 2048-bit RSA in hours.

Elliptic Curve Cryptography (ECC)

ECC is the workhorse of modern TLS, Bitcoin, SSH, Signal, and a long list of other protocols. Its security relies on the elliptic curve discrete logarithm problem, given points P and Q on a curve, find the integer k such that Q = k·P.

Shor's algorithm also solves ECDLP in polynomial time. Worse, ECC keys are shorter: a 256-bit elliptic curve key offers roughly the same classical security as 3072-bit RSA, but is easier to attack with a quantum computer. A machine with roughly 2000 logical qubits would be enough.