Photo by Marek Pavlík on Unsplash

The Algorithm That’s Coming For RSA, And What’s Actually Inside It

ML-KEM isn’t just a new standard. It’s a different kind of math., here’s what it does and why it matters.

Let’s be honest about something. Most people in security have heard of post-quantum cryptography by now. They know NIST published standards. They know RSA is “eventually” a problem. And then they move on with their day, still running the same key exchange they’ve always run, because nothing has broken yet.

That’s a reasonable bet for today. It’s a terrible bet for data that needs to stay confidential for the next decade.

ML-KEM, standardized as FIPS 203 in August 2024, is the algorithm replacing RSA and ECDH for key exchange. Not eventually. Now. Chrome ships it, Cloudflare runs it, Signal added it to their protocol. The migration is already happening around you, and understanding what’s actually inside this algorithm is what separates the people leading that migration from the ones reacting to it. So here’s what’s inside it.

Why RSA Is Finished (Quantumly Speaking)

RSA works because factoring large numbers is hard. Given n = p × q, finding p and q when n is enormous takes classical computers an impractical amount of time. Elliptic curve cryptography has a similar story, the discrete logarithm problem on elliptic curves has no efficient classical solution.

Shor’s algorithm changes both of those sentences. Running on a sufficiently powerful quantum computer, it solves integer factorization and discrete logarithm in polynomial time. The quantum computer capable of breaking 2048 bit RSA doesn’t exist yet, but here’s the part that keeps threat analysts up at night.

Adversaries don’t need it yet. They’re collecting your encrypted traffic now and storing it. When the hardware catches up, and the trajectory of quantum computing suggests it will, they decrypt everything retroactively. This is harvest now, decrypt later.

ML-KEM’s security doesn’t rest on factoring or discrete logarithm, It rests on something structurally different.

The Math It’s Built On

ML-KEM’s hardness assumption is the Module Learning With Errors (M-LWE) problem. To understand it, start one level down.

Learning With Errors

Take a prime modulus q and a dimension n. Sample a secret vector s ∈ ℤⁿq and a matrix A ∈ ℤⁿˣⁿq uniformly at random. Then compute:

b = A·s + e (mod q)

where e is a small error vector coefficients drawn from a distribution with tiny standard deviation relative to q.

The problem: given (A, b), find s.

Without the error term, this is just linear algebra, trivially solvable. The noise is what makes it hard. And unlike factoring, there’s no known quantum algorithm that breaks LWE efficiently. That’s the foundation everything else is built on.

Moving Into Polynomial Rings

Plain LWE is slow, ML-KEM moves the problem into a polynomial ring to make it practical:

Rq = ℤq[x] / (xⁿ + 1)

where n = 256 and q = 3329. Elements here are polynomials with 256 coefficients, each reduced mod q, and polynomials themselves are reduced mod xⁿ + 1. The module structure adds a k × k matrix of these polynomials for ML-KEM-768, k = 3.

The core relation looks the same:

b = A ∘ s + e (mod q)

but now ∘ is polynomial multiplication in Rq, and everything operates over polynomials instead of integers.

Why NTT Matters

Multiplying two degree 255 polynomials naively is O(n²) which is too slow to be practical. ML-KEM uses the Number Theoretic Transform (NTT), the modular arithmetic version of the FFT ( Fast Fourier Transform), to get this down to O(n log n).

Because q = 3329 satisfies q ≡ 1 mod 2n, NTT works cleanly here. Polynomial multiplication becomes:

a · b = NTT⁻¹(NTT(a) ⊙ NTT(b))

where ⊙ is pointwise multiplication. This is what makes ML-KEM fast enough to run in TLS handshakes without noticeable latency overhead.

The Three Algorithms

ML-KEM is a Key Encapsulation Mechanism. It doesn’t encrypt your data, it establishes a shared secret that you then use as a symmetric key. Three algorithms, here’s how they work.

KeyGen: Making the Keys

Sample a k × k matrix A from a seed ρ via SHAKE-128. Sample a secret vector s and error vector e from a centered binomial distribution Bη₁ a noise distribution with small, tightly bounded coefficients. Compute:

t = A ∘ s + e (mod q)

The public key is (A, t). The private key is s. The error e is what binds them together without being recoverable from the public key alone.

ML-KEM.KeyGen():
    ρ, σ  ← random_bytes(64)
    A     ← ExpandA(ρ)                  // k×k matrix, NTT domain
    s, e  ← SampleNoise(σ, η₁)          // small secret and error
    t     ← A ∘ s + e  (mod q)
    ek    ← Encode(t, ρ)                // public key
    dk    ← Encode(s) || ek || H(ek) || z   // z is for implicit rejection
    return (ek, dk)

Encapsulate: Sender Side

The sender has your public key. They want to establish a shared secret without transmitting it directly. Sample a random 256 bit message m. Hash it with H(ek) using SHA3–512:

(K̄, r) = G(m || H(ek))

Use r to sample fresh noise vectors r, e₁, e₂. Then compute:

u = Aᵀ ∘ r + e₁ (mod q)

v = tᵀ ∘ r + e₂ + Decompress(m) (mod q)

The ciphertext is compressed versions of u and v. The shared secret is derived from K̄ and H(c).

ML-KEM.Encaps(ek):
    m          ← random_bytes(32)
    (K̄, r)    ← G(m || H(ek))
    (A, t)     ← Decode(ek)
    r, e₁, e₂ ← SampleNoise(r, η₂)
    u          ← Aᵀ ∘ r + e₁ (mod q)
    v          ← tᵀ ∘ r + e₂ + Decompress(m) (mod q)
    c          ← Compress(u, dᵤ) || Compress(v, dᵥ)
    K          ← KDF(K̄ || H(c))
    return (c, K)

The Compress step is where a small precision trade-off happens coefficients are rounded to fewer bits to shrink the ciphertext. The error terms have to be small enough that this rounding doesn’t destroy the signal on the other end.

Decapsulation: Getting the Secret Back

You receive ciphertext c. You have private key s. Decompress c back to u and v. Compute:

m’ = Compress(sᵀ ∘ u − v, 1)

Why does this work? Because sᵀu ≈ sᵀ(Aᵀr + e₁) = (As)ᵀr + sᵀe₁ ≈ tᵀr (since t = As + e and the errors are small). So:

sᵀu − v ≈ tᵀr − (tᵀr + e₂ + Decompress(m)) = −Decompress(m) + tiny noise

Round it and you recover m. Then re-run encapsulation with m’ and check if the result matches c.

ML-KEM.Decaps(dk, c):
    (s, ek, h, z) ← Decode(dk)
    (u, v)        ← Decompress(c)
    m'            ← Compress(sᵀ ∘ u - v, 1)
    (K̄', r')     ← G(m' || h)
    c'            ← Encaps_internal(ek, m', r')
    if c' == c:
        return KDF(K̄' || H(c))        // legitimate ciphertext
    else:
        return KDF(z || H(c))          // implicit rejection

That last branch, implicit rejection, deserves attention. If the ciphertext doesn’t check out, ML-KEM doesn’t return an error. It returns a pseudorandom value that looks like a valid key but isn’t. This kills chosen ciphertext attacks that try to use decryption failures as an oracle to extract your private key.

What You Actually Do With This

Cryptographic agility is the first conversation to have. If the systems you’re protecting hardcode RSA or ECDH with no abstraction layer, the fix isn’t a config change, it’s an architectural one. That conversation is easier to have before an incident than after.

During the transition, run hybrid. NIST recommends combining ML-KEM with a classical algorithm ECDH-P256 or X25519 and XORing the shared secrets. Security holds as long as either algorithm is unbroken. TLS 1.3 is already doing this with X25519MLKEM768.

When evaluating vendors, ask which parameter set they implement, whether it’s hybrid or pure PQC, and whether their implementation is constant time. Lattice schemes are vulnerable to timing side channels if the NTT or noise sampling leaks through execution time. “Quantum-safe” on a product sheet means nothing without those answers.

Classify data by how long it needs to stay secret. Ephemeral session data is low risk. Health records, financial history, legal archives, anything with a 10+ year confidentiality requirement, that’s where harvest now decrypt later is already a live threat, and that’s where the migration needs to start.

The Bottom Line

The standard is finalized. The deployments are live. The threat driving it isn’t hypothetical, it’s operational, just on a longer timeline than most threats you deal with day to day.

ML-KEM works because noise in high-dimensional polynomial rings is hard to remove without the private key, and that hardness holds against quantum attack. Every implementation decision in FIPS 203, the ring structure, the NTT, the compression parameters, implicit rejection exists to make that guarantee hold in practice, not just in theory.

Knowing the math means you can evaluate implementations, catch shortcuts, and speak with authority when the migration decisions land on your desk.