How Encryption Works, and Why All of It Has to Be Replaced by 2035

Encryption is usually explained as hiding, the least interesting part of it. The hard problem is this: two parties who have never met, with no shared secret and no private channel, must agree on a key while everything they say is being copied. The answer found in 1976 rests on arithmetic that is cheap one way and expensive the other. A quantum computer running the right algorithm would make the expensive direction cheap — which is why, as of 27 October 2026, the mathematics behind almost every connection on the internet has an official expiry date.

A lock made of arithmetic

Multiplying two 135-digit primes takes a laptop no time at all. Recovering those primes from the product is the same problem run backwards, and nobody knows a fast way to do it. Public-key cryptography is built out of gaps like that: publish the product, keep the primes, and the gap between the directions is the lock.

How wide is the gap? On 19 September 2026 Stephen A. Weis published the two factors of RSA-896, a 270-digit, 896-bit number from the old RSA Factoring Challenge — the largest ever split in public. It took up to 2,048 H100 GPUs, a little over ten days, and the general number field sieve ported to graphics cards. He is explicit that the result “does not impact the security of deployed RSA-2048 keys”. Six years earlier the record was RSA-250, 250 digits, on 28 February 2020: twenty digits in six years is the pace of classical progress, and 2048-bit keys sit far past the end of it.

Whitfield Diffie and Martin Hellman opened their November 1976 paper with “We stand today on the brink of a revolution in cryptography”, and named what they wanted: a key agreed without a secure channel, and “the equivalent of a written signature”. Those are still the two jobs — and only one is in immediate trouble.

Two jobs, one time bomb

In a modern connection the two jobs use different keys. Key establishment produces a session key that protects one conversation and is then thrown away; authentication uses a long-lived key, in a certificate, to prove the server is who it claims. One gives confidentiality, the other identity.

The difference matters because of a threat with an ugly name: harvest now, decrypt later. Anyone with storage can record encrypted traffic today and keep it until a machine exists that can open it. Anything whose value outlasts the wait — medical records, state secrets, your 2026 bank statements — is already exposed by a computer that does not yet exist.

Signatures do not work that way. A forged certificate is only useful at the moment of the handshake, so authentication stays safe as long as the algorithm is sound when it is used. NIST notes this, then notes why it is no comfort: moving authentication takes longer, because certificates are issued, bought, installed and trusted by a chain of people who must act in order.

NIST’s planning rule is Mosca’s theorem: if the years your data must stay secret plus the years your migration takes exceed the years until a capable quantum computer exists, you are already late.

What Shor’s algorithm changes

Peter Shor’s 1994 result, presented at FOCS that November, is not a faster search. It is a quantum algorithm that finds the period of a function, which turns factoring and discrete logarithms into problems solvable in time polynomial in the number of digits. Both hard problems behind today’s public-key cryptography — RSA’s factoring and the elliptic-curve discrete logarithm — fall to the same trick. They were never two independent bets.

What does not fall is symmetric encryption, the ciphers that scramble the message once the key is agreed. The best quantum attack there is Grover’s algorithm, which searches a space of keys in roughly the square root of the steps — and square roots are survivable: double the key length and you are back where you started. NIST’s position is that Grover gives “little or no advantage in attacking AES”, that “AES 128 will remain secure for decades to come”, and that applications can keep AES at 128, 192 or 256 bits.

So the threat is precise, not general. It breaks the handshake, not the cipher.

How far away the machines are

Nobody has built one. The useful question is what it would take, and the best current answer is Craig Gidney’s May 2025 paper: fewer than a million noisy physical qubits, under a week, to factor a 2048-bit RSA key, assuming a 0.1 percent gate error rate and a one-microsecond error-correction cycle. The number is notable for how fast it moved: his own 2019 estimate, on the same assumptions, was twenty million qubits.

Against that, the hardware. Google’s Willow chip, announced on 9 December 2024, has 105 physical qubits, and its result was not a computation but a milestone in error correction — the first chip below the threshold where adding qubits makes the encoded qubit better rather than worse. The gap between 105 and a million is four orders of magnitude. The threat is an engineering project with no delivery date; the migration is a ten-to-twenty-year job NIST says has to start now anyway.

What replaces it, and what it costs

NIST ran an open competition for eight years, assessing 82 submissions from 25 countries, and published the first three standards on 13 August 2024: FIPS 203 (ML-KEM, for key establishment, formerly CRYSTALS-Kyber), FIPS 204 (ML-DSA, for signatures, formerly CRYSTALS-Dilithium) and FIPS 205 (SLH-DSA, a hash-based backup signature on unrelated mathematics, in case lattices prove flawed).

The lattice schemes rest on a different hard problem. Instead of hiding primes they hide a small amount of noise added to a system of equations: recovering the secret means finding the noise, the Module Learning With Errors problem, for which no quantum algorithm is known.

The bill comes in bytes. An ML-KEM-768 encapsulation key is 1,184 bytes and its ciphertext 1,088, where an X25519 public key is 32 bytes. An ML-DSA-65 signature is 3,309 bytes against RSA-2048’s 256. Those extra kilobytes travel in every handshake and every certificate chain, which is why migration is slow in exactly the places already tight. NIST has since selected HQC as an alternative key-establishment scheme on unrelated mathematics.

The dates

NIST IR 8547, finalised on 27 October 2026, sets the schedule. Every quantum-vulnerable public-key algorithm under NIST standards — RSA, ECDSA and EdDSA signatures, finite-field and elliptic-curve Diffie-Hellman, RSA key establishment — is deprecated after 2030 and disallowed after 2035. Deprecated means you may use it and are told not to; disallowed means it is out.

For the US government the deadlines are earlier and binding. Executive Order 14412, signed on 22 June 2026, requires federal high-value and high-impact systems to use post-quantum key establishment by 31 December 2030 and post-quantum signatures by 31 December 2031, and obliges covered contractors to comply by the end of 2030. Agencies must also support TLS 1.3 by 2 January 2030 — a protocol published in 2018.

What has already moved

More than most people would guess. Cloudflare reported on 7 April 2026 that over 65 percent of human traffic reaching its network is already post-quantum encrypted, and set 2029 for full post-quantum security including authentication: ML-DSA to origin servers from mid-2026, Merkle Tree Certificates for visitor connections from mid-2027. Signal has used PQXDH since 19 September 2023, combining X25519 with CRYSTALS-Kyber so an attacker must break both.

That combining is the standard design. The key exchange now in general use is X25519MLKEM768, IANA group 0x11ec: the old elliptic curve and the new lattice run side by side with their outputs mixed, so the session holds unless both halves fail — a hedge against the new mathematics turning out to be wrong.

Eight Georgian sites, measured

Theory is cheap, so I checked. On 12 November 2026 I opened eight Georgian sites in Chromium and read the key exchange the browser’s own TLS stack negotiated: gov.ge, my.gov.ge, rs.ge, nbg.gov.ge, tbcbank.ge, bankofgeorgia.ge, libertybank.ge and parliament.ge. All eight negotiated TLS 1.3 with X25519MLKEM768 and AES-128-GCM — already post-quantum on the half that harvest-now-decrypt-later threatens. Then I read their certificates. All RSA, 2048 bits: the algorithm deprecated after 2030 and disallowed after 2035.

That split is the honest state of the transition, in Georgia and nearly everywhere else. The key exchange upgraded itself, because it lives in browsers and hosting platforms that update without asking; nobody in Tbilisi had to decide anything. The certificate is bought, issued, installed and renewed by named people on a schedule, and it will not change until one of them changes it.

The half that arrived for free is finished. The half somebody has to sign for has nine years.