Step-by-Step Guide: Migrating from RSA and ECDH to ML-KEM

Migrating key exchange to post-quantum algorithms is less a single cutover than a series of small, reversible changes. This guide lays out a phased approach that works for most engineering organizations. It focuses on key establishment (ML-KEM), which is the part most exposed to harvest-now-decrypt-later attacks. Signature migration follows a different path and is covered separately in Post-Quantum Digital Signatures.

Phase 1: Discover (weeks 1 to 6)

Build a list of everywhere public-key key exchange happens. Typical places:

• TLS on load balancers, API gateways, CDNs and service meshes
• Internal service-to-service mTLS
• VPNs (IPsec/IKEv2, WireGuard, SSL VPN) and SSH
• Message brokers, databases and storage clients using TLS
• Application code calling RSA or ECDH directly (for example key wrapping)
• Third-party SaaS where you do not control the endpoint

For each, record the algorithm, key size, library and version, owner, and the sensitivity and lifetime of the data it protects. Details are in Building a Cryptographic Inventory.

Phase 2: Prioritize

Score each item on two axes: data lifetime (how long must it stay confidential) and exposure (can an adversary record the traffic). Long-lived data on internet-facing links goes first. Internal links inside a tightly controlled network come later. Also flag blockers: embedded devices, old appliances and vendor software that cannot be upgraded.

Phase 3: Make it configurable

Before changing algorithms, ensure you can change them without code changes:

• Move algorithm and group names into configuration.
• Store an algorithm identifier next to any data you encrypt or wrap, so mixed generations can coexist.
• Wrap crypto calls behind one internal interface rather than scattering library calls (see crypto-agility patterns).

Phase 4: Upgrade the stack

Hybrid support depends on your TLS library and termination points:

Pin your minimum library versions in dependency files and container base images so a rebuild does not silently downgrade.

Phase 5: Pilot in staging, then a small production slice

Enable the hybrid group X25519MLKEM768 on a non-critical endpoint. Then verify:

# Confirm which group was negotiated (OpenSSL 3.5+)
openssl s_client -connect staging.example.com:443 -groups X25519MLKEM768 </dev/null 2>/dev/null | grep -i "negotiated\|group"

Watch for three failure types:

• Handshake failures from middleboxes that mishandle a larger ClientHello.
• Latency changes on high-loss or mobile links, since handshakes are larger.
• Monitoring gaps: confirm logs record the negotiated group so you can measure adoption.

Phase 6: Roll out gradually

Use percentage-based rollouts or per-region flags. Keep classical-only fallback available for clients that do not advertise a hybrid group, since TLS negotiation handles this automatically. Do not remove fallback until telemetry shows effectively no legacy clients on that endpoint.

Phase 7: Measure and retire

Track the share of connections using a hybrid group per service. Once that is near-complete and vendors support it, schedule removal of RSA key transport and static ECDH options. Retire what you can, document exceptions, and review your inventory quarterly because new services reintroduce old defaults.

Rollback plan

Every phase needs a defined rollback: a configuration flag, a previous security policy on the load balancer, or the prior container image. Test the rollback in staging. A migration that cannot be reversed in minutes will be avoided by cautious teams.

Pitfalls we see repeatedly

• Forgetting internal mTLS and only upgrading the public edge.
• Hardcoding cipher or group names in application code.
• Treating a library upgrade as done without confirming what actually gets negotiated.
• Not involving vendors early; some appliances need firmware that takes months to arrive.