RSA vs ML-KEM: Post Quantum Cryptography Side-by-Side

TL;DR

RSA is broken by Shor's algorithm on any sufficiently large quantum computer. ML-KEM (FIPS 203) is NIST's standard replacement based on Module Learning With Errors. ML-KEM public keys and ciphertexts are larger than RSA's but operations are comparably fast or faster. Deploy hybrid ML-KEM+X25519 for new systems; migrate existing RSA usage on the NIST timeline.

Security Assumptions

Algorithm	Hard problem	Classical attack	Quantum attack
RSA-2048	Integer factorization	NFS (sub-exponential)	Shor's algorithm (polynomial, broken)
ML-KEM-768	Module Learning With Errors	BKZ-style lattice reduction (exponential)	No known polynomial quantum attack

Key and Ciphertext Sizes

Algorithm	Public key	Secret key	Ciphertext
RSA-2048	256 B	256 B+	256 B
RSA-3072	384 B	384 B+	384 B
ML-KEM-512	800 B	1632 B	768 B
ML-KEM-768	1184 B	2400 B	1088 B
ML-KEM-1024	1568 B	3168 B	1568 B

ML-KEM keys are 3-6x larger than RSA-2048. For a TLS handshake, this adds roughly 1-2 KB. Unmeasurable for most applications.

Performance

ML-KEM key generation, encapsulation, and decapsulation are all faster than equivalent RSA operations on modern CPUs. ML-KEM key generation is roughly 10x faster than RSA-2048 key generation. Decapsulation is comparable to RSA decryption.

The Hybrid Pattern

For defense in depth against unexpected attacks on either algorithm:

• Derive shared secret S1 via X25519.
• Derive shared secret S2 via ML-KEM.
• Combine: session_key = KDF(S1 || S2, context).

An attacker must break both to recover session_key. This is the Chrome/Signal/iMessage pattern.

When to Migrate

1. New TLS deployments: use hybrid X25519MLKEM768 today.
2. Long-lived RSA-encrypted data: prioritize migration before CRQC.
3. Code signing: migrate to ML-DSA or SLH-DSA on NIST IR 8547 timeline (deprecate by 2035).

Frequently Asked Questions

Is ML-KEM slower than RSA?

No. ML-KEM is typically faster than RSA-2048 for equivalent security strength. Key generation is 10x faster; encapsulation and decapsulation are comparable or faster.

Are ML-KEM keys too large for embedded systems?

1,088-byte ciphertexts for ML-KEM-768 fit within typical TLS handshake budgets. For severely constrained IoT, smaller PQC schemes may be needed but even ML-KEM-512 is deployable on most modern microcontrollers.

Can I replace RSA directly with ML-KEM?

For KEM (key exchange), yes, though hybrid deployment is preferred for belt-and-suspenders security. For signatures, RSA is replaced by ML-DSA or SLH-DSA, not ML-KEM.

When does NIST disallow RSA?

NIST IR 8547 (November 2024 draft) proposes deprecating RSA and other quantum-vulnerable algorithms by 2035 and disallowing thereafter for federal use.

Sources

1. FIPS 203 (ML-KEM)
2. NIST IR 8547

Related Articles

• ML-KEM Explained
• ECDH vs ML-KEM
• Hybrid Encryption
• Why RSA-2048 Will Break
• Shor's Algorithm