A Post-Quantum Cryptography Primer: Shor, Grover, ML-KEM and the Hybrid Handshake

Post-quantum cryptography has moved from conference talks into default settings. Chrome and Firefox send a post-quantum key share in their TLS handshakes by default, OpenSSH 10.0 uses one by default, and OpenSSL 3.5 shipped the algorithms as first-class key types. This post is about what actually changed and what did not: which primitives a quantum computer breaks, which it merely dents, what the three NIST standards contain, and what the hybrid handshake looks like on the wire. Every command that prints output below was run on my machine.

What a quantum computer breaks

Shor's 1994 algorithm factors integers and computes discrete logarithms in polynomial time. The two problems look different but share the structure that matters: both reduce to finding the period of a function on an abelian group, and the quantum Fourier transform finds periods efficiently. For RSA, pick a random $a$ and find the order $r$ of $a$ modulo $N$; if $r$ is even and $a^{r/2}\not\equiv -1$, then

$$gcd(a^{r/2}-1,N)$$

is a non-trivial factor. For an elliptic-curve key $Q=kP$, the same period-finding subroutine applied to $(x,y)\mapsto xP+yQ$ recovers $k$. So RSA, finite-field Diffie–Hellman, DSA, ECDH, ECDSA, EdDSA and X25519 fall together. Every public-key primitive deployed at scale today is on that list.

How far away is such a machine? Gidney's 2025 estimate puts RSA-2048 within reach of fewer than a million noisy physical qubits running for under a week, down from the 20 million qubits of the 2019 estimate under the same error-correction assumptions. Today's devices have on the order of a thousand physical qubits with worse error rates, and nobody has factored a cryptographically interesting number. But one attack works today: harvest now, decrypt later. Traffic recorded in 2026 stays recorded, and a key exchange that a future machine can reverse exposes everything encrypted under it. That is why key exchange migrates first and signatures later: a forged signature only matters at the moment of verification, while confidentiality has to hold for the lifetime of the data.

What it only dents

Grover's 1996 algorithm searches an unstructured space of $N$ candidates in about $\sqrt{N}$ evaluations. Against a 128-bit AES key that is $2^{64}$ iterations, which on paper halves the security level. In practice the picture is far less dramatic. Each iteration is a full AES circuit evaluated coherently under error correction, the iterations are inherently sequential, and splitting the work across $k$ machines only gains a factor of $\sqrt{k}$ rather than $k$. NIST's own assessment is that Grover variants are unlikely to give an attacker any advantage for an attack that must finish within years or even decades. The practical rule is simple: symmetric primitives keep working, and doubling the key length restores the paper margin; asymmetric primitives need new mathematics.

The three standards

NIST finalised its first three post-quantum standards on 13 August 2024, after an eight-year public competition:

• FIPS 203, ML-KEM (formerly CRYSTALS-Kyber). A key-encapsulation mechanism built on Module Learning With Errors, with parameter sets ML-KEM-512, -768 and -1024 at NIST security categories 1, 3 and 5 (as hard as AES-128, -192 and -256 key search). This is the one in your browser.
• FIPS 204, ML-DSA (formerly CRYSTALS-Dilithium). A lattice signature scheme from the same family; ML-DSA-44, -65 and -87 target categories 2, 3 and 5. The general-purpose replacement for ECDSA and RSA signatures.
• FIPS 205, SLH-DSA (formerly SPHINCS+). A stateless hash-based signature scheme whose security rests on nothing but the hash function. Tiny keys, large signatures and slow signing make it the conservative choice for roots of trust and firmware signing rather than for TLS.

Two more are coming: FN-DSA (Falcon), a lattice scheme with smaller signatures but a floating-point implementation that is easy to get wrong, as draft FIPS 206, and HQC, a code-based KEM selected in March 2025 as a backup should the lattice assumption fail. NIST's draft transition plan, IR 8547, proposes deprecating the quantum-vulnerable RSA and elliptic-curve algorithms at the 112-bit security strength (RSA-2048, for example) after 2030 and disallowing all of them after 2035.

Why lattices: the one idea behind ML-KEM and ML-DSA

Learning With Errors asks you to recover a secret vector $\mathbf{s}$ from a random matrix $\mathbf{A}$ over ${\mathbb{Z}}_q$ and $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$, where $\mathbf{e}$ is small noise. Without the noise it is Gaussian elimination; with it, the best known algorithms, classical and quantum alike, are lattice-reduction methods whose cost grows exponentially in the dimension, and there is no hidden periodic structure for Shor's subroutine to exploit.

ML-KEM uses the module variant: the entries of $\mathbf{A}$ are polynomials in ${\mathbb{Z}}_q[x]/(x^{256}+1)$ with $q=3329$, and the three parameter sets use $k=2,3,4$ polynomials per vector, which is why the encapsulation keys are $384k+32$ bytes: 800, 1184 and 1568. Encapsulation encrypts a random 32-byte message under this problem and hashes it into the shared secret; the Fujisaki–Okamoto transform makes the result IND-CCA2, and decapsulation uses implicit rejection: an invalid ciphertext yields a pseudorandom secret derived from a private seed rather than an error, so there is no decryption-failure oracle.

ML-DSA works in a ring of the same form, with $q=8380417$. The signer samples a masking vector, computes a challenge from the commitment and the message, and rejects any candidate signature whose distribution would leak the secret key, which is why signing time varies and signatures are a few kilobytes.

Everything got bigger

The objects are large. The sizes below are the ones published in the three FIPS documents; the classical rows use the usual encodings (uncompressed points for P-256, raw modulus for RSA).

Key exchange gets away with this: one ML-KEM-768 exchange adds about 2.3 KB to a handshake, less than a single certificate. Signatures do not. A handshake carries several signatures and public keys (the handshake signature, the chain, Certificate Transparency SCTs), and replacing all of them with ML-DSA-44 adds on the order of 15 KB per connection, which is the main reason the web PKI still signs classically while key exchange has already moved.

A KEM is not Diffie–Hellman

Diffie–Hellman is symmetric: both sides publish a value and both combine. A KEM has three operations and a fixed direction. KeyGen produces an encapsulation key ek and a decapsulation key dk; Encaps(ek) produces a ciphertext and a fresh shared secret; Decaps(dk, ct) recovers the same secret. TLS 1.3 happens to fit this shape: the client's key_share carries ek, and the server's key_share carries ct, in the same two flights the protocol always had.

The group that browsers negotiate is X25519MLKEM768 (code point 0x11EC). The client share is the ML-KEM-768 encapsulation key followed by an X25519 public key, $1184+32=1216$ bytes; the server share is the ML-KEM ciphertext followed by its X25519 public key, $1088+32=1120$ bytes; and the shared secret is the ML-KEM secret concatenated with the X25519 secret, 64 bytes, fed into the TLS 1.3 key schedule in place of the ECDHE output. The ML-KEM half comes first so that the construction fits NIST's rules for key derivation with multiple secrets.

Why keep the X25519 half? Because the lattice assumption is young: two later-round NIST candidates, SIKE and Rainbow, fell to classical attacks in 2022, SIKE in about an hour on a laptop. A hybrid means a flaw in ML-KEM leaves you with exactly the X25519 security you had before, while a quantum computer leaves you with ML-KEM. The cost is about 2.3 KB per handshake and a ClientHello that no longer fits in one packet, which flushed out a generation of buggy middleboxes. Chrome and Firefox turned the hybrid on by default in late 2024, Go's crypto/tls followed in 1.24, OpenSSL 3.5 puts X25519MLKEM768 first in its default group list, and OpenSSH 10.0 made mlkem768x25519-sha256 its default key exchange.

Trying it with OpenSSL 3.5

OpenSSL 3.5 added ML-KEM, ML-DSA and SLH-DSA to the default and FIPS providers and taught pkeyutl to encapsulate and decapsulate. The transcripts below come from a 3.6 build on macOS; the commands have not changed since 3.5.

• Key encapsulation
• Signatures
• TLS handshake

• $ openssl list -kem-algorithms | grep -i kem
    SecP384r1MLKEM1024 @ default
    { 2.16.840.1.101.3.4.4.1, id-alg-ml-kem-512, ML-KEM-512, MLKEM512 } @ default
    { 2.16.840.1.101.3.4.4.2, id-alg-ml-kem-768, ML-KEM-768, MLKEM768 } @ default
    { 2.16.840.1.101.3.4.4.3, id-alg-ml-kem-1024, ML-KEM-1024, MLKEM1024 } @ default
    X25519MLKEM768 @ default
    X448MLKEM1024 @ default
    SecP256r1MLKEM768 @ default
  
  $ openssl genpkey -algorithm ML-KEM-768 -out mlkem768.pem
  $ openssl pkey -in mlkem768.pem -pubout -out mlkem768_pub.pem
  $ openssl pkeyutl -encap -inkey mlkem768_pub.pem -pubin -out ct.bin -secret ss_enc.bin
  $ openssl pkeyutl -decap -inkey mlkem768.pem -in ct.bin -secret ss_dec.bin
  $ wc -c ct.bin ss_enc.bin ss_dec.bin
      1088 ct.bin
        32 ss_enc.bin
        32 ss_dec.bin
  $ cmp ss_enc.bin ss_dec.bin && echo "shared secrets match"
  shared secrets match
  

  The ciphertext is exactly the 1088 bytes FIPS 203 specifies for ML-KEM-768, and both sides hold the same 32-byte secret. openssl pkey -text shows that the private key file stores the 64-byte seed from which the whole expanded key is re-derived.

• $ openssl genpkey -algorithm ML-DSA-65 -out mldsa65.pem
  $ openssl pkey -in mldsa65.pem -pubout -out mldsa65_pub.pem
  $ printf 'hello, post-quantum world\n' > msg.txt
  $ openssl pkeyutl -sign -inkey mldsa65.pem -in msg.txt -out msg.sig
  $ wc -c msg.sig
      3309 msg.sig
  $ openssl pkeyutl -verify -pubin -inkey mldsa65_pub.pem -in msg.txt -sigfile msg.sig
  Signature Verified Successfully
  

  There is no -digest option: ML-DSA signs the message itself ("pure" mode), and since 3.5 pkeyutl no longer needs -rawin for key types that have no prehash variant. Swap ML-DSA-65 for SLH-DSA-SHA2-128s and the signature grows to 7856 bytes.

• $ openssl s_client -connect cloudflare.com:443 -groups X25519MLKEM768 </dev/null 2>/dev/null \
      | grep -E "Negotiated|Cipher is|^Protocol"
  Negotiated TLS1.3 group: X25519MLKEM768
  New, TLSv1.3, Cipher is TLS_AES_256_GCM_SHA384
  Protocol: TLSv1.3
  

  Without -groups the 3.5 default list already offers X25519MLKEM768 first, so this is what a stock client negotiates against a server that supports it. Against a server that does not, the same command prints a classical group instead, and pinning -groups X25519MLKEM768 alone makes it fail, which is a quick way to audit your own endpoints.

What to do about it

• Inventory first. Find where RSA and elliptic curves are used and which data must stay confidential past 2035; recorded session traffic is the urgent case.
• Key exchange now. For TLS and SSH this is usually a library upgrade rather than a redesign. Verify with openssl s_client as above or ssh -Q kex.
• Symmetric keys are fine. Prefer AES-256 where it costs nothing; otherwise leave them alone.
• Signatures on a schedule. Long-lived roots of trust, secure boot and firmware are the place to start, with SLH-DSA or the stateful hash-based schemes of SP 800-208; the web PKI is still working out how to carry the extra kilobytes.
• Design for agility. Code that assumes a public key is 32 bytes, a signature fits in 72, or a ClientHello fits in one packet breaks on contact with these algorithms.

WARNING

Use a maintained library (OpenSSL 3.5+, BoringSSL, Go's standard library, liboqs for experiments) rather than reference code from a paper: the 2023 KyberSlash timing bugs were in reference implementations, and decapsulation must be constant-time for implicit rejection to mean anything. And deploy the hybrid, not bare ML-KEM; the point of the construction is that you never have to guess which half fails first.

Further reading

• NIST, FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard, FIPS 204, Module-Lattice-Based Digital Signature Standard and FIPS 205, Stateless Hash-Based Digital Signature Standard, the source of every size in this post.
• NIST, IR 8547 (draft), Transition to Post-Quantum Cryptography Standards, the 2030 and 2035 timeline, and the PQC project FAQ on why Grover matters less than it looks.
• IETF, draft-ietf-tls-ecdhe-mlkem, which defines X25519MLKEM768, and draft-ietf-tls-hybrid-design, the general framework.
• OpenSSL, 3.5 final release announcement and the openssl-pkeyutl(1) manual for the -encap and -decap options.
• Craig Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits, 2025.
• Peter Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, and Lov Grover, A fast quantum mechanical algorithm for database search.
• Cloudflare, The state of the post-quantum Internet, and OpenSSH, Post-quantum cryptography in OpenSSH.