Step-by-Step: Migrating from RSA to NIST Post-Quantum Cryptography

Migrating from RSA to NIST post-quantum cryptography is the most consequential cryptographic transition since the move from DES to AES. Unlike the DES-to-AES migration, which addressed symmetric encryption with a relatively contained set of changes, the RSA-to-PQC migration touches every system that uses public-key cryptography: TLS, code signing, document signing, email encryption, VPN, SSH, and API authentication. The scope is broad, but the path is well-defined.

This guide provides a practical, step-by-step migration plan that any engineering team can execute. It assumes you are starting from a typical enterprise environment that uses RSA-2048 or RSA-4096 for signatures and key exchange, with ECDSA P-256 or P-384 as a secondary algorithm.

Step 1: Establish Your Cryptographic Inventory

Before you can migrate, you must know what to migrate. A cryptographic inventory identifies every system, service, library, and protocol that uses RSA, ECDSA, ECDH, or other quantum-vulnerable algorithms.

Start with TLS configurations. Every web server, load balancer, API gateway, and reverse proxy has a TLS configuration that specifies cipher suites. Document the cipher suites in use, the certificate types (RSA vs ECDSA), and the TLS library version.

Continue with certificate infrastructure. Identify all certificate authorities (internal and external), all issued certificates, their key types and sizes, their expiration dates, and the systems they protect. Include code signing certificates, email certificates, and client certificates.

Then examine application-level cryptography. Many applications use RSA or ECDSA directly for token signing (JWTs), data encryption, key wrapping, or digital signatures. These integrations are often harder to find because they are embedded in application code rather than server configuration.

Finally, document your key management infrastructure. Hardware security modules (HSMs), key management services (KMS), and secrets management tools all contain or protect RSA keys. These systems need to support ML-KEM and ML-DSA key types before the broader migration can proceed.

Step 2: Prioritize by Risk

Not all systems carry equal quantum risk. Prioritize based on two factors: the sensitivity horizon of the data (how long must it remain confidential?) and the exposure to interception (is the traffic likely to be captured by a sophisticated adversary?).

The highest priority systems are those that combine long sensitivity horizons with high interception probability: inter-organizational communication, government-facing APIs, financial transaction systems, and healthcare data exchanges. Enable hybrid key exchange on these systems first.

Internal systems with short data sensitivity horizons can be migrated later, aligned with normal infrastructure refresh cycles.

Step 3: Enable Hybrid Key Exchange

Hybrid key exchange is the first and most impactful migration step. It protects against harvest-now-decrypt-later for all new TLS sessions without breaking backward compatibility.

Hybrid mode combines a classical key exchange (X25519 or ECDHE P-256) with a post-quantum key exchange (ML-KEM-768). The session key derives from both shared secrets, ensuring security under both classical and quantum assumptions.

To enable hybrid key exchange: upgrade your TLS library to a version supporting ML-KEM (OpenSSL 3.x with oqs-provider, BoringSSL, or AWS-LC), configure the server to offer hybrid cipher suites (e.g., X25519Kyber768), test with major browsers and clients, and monitor handshake success rates and latency metrics.

This step typically takes days to weeks, not months. It is a configuration change, not a code change.

Step 4: Implement Post-Quantum Signatures

After securing key exchange, migrate digital signatures to ML-DSA (FIPS 204). This protects against signature forgery by quantum computers.

Start with code signing and software distribution. Sign packages with both RSA and ML-DSA signatures (dual signing). Verifiers that support ML-DSA check the PQ signature; others fall back to RSA. This provides backward compatibility during the transition.

Continue with API authentication. Add ML-DSA signatures to authentication tokens. The H33-74 overlay approach provides this as a simple API call: send the payload, receive a 74-byte three-family PQ attestation.

Then update document signing, email signing (S/MIME), and any other application-level signature operations.

Step 5: Test Thoroughly

Post-quantum algorithms are larger and sometimes slower than their classical counterparts. Thorough testing is essential before production deployment.

Test handshake performance under load. ML-KEM adds approximately 2 KB to TLS handshakes. At high connection rates, measure whether this impacts connection establishment throughput.

Test interoperability with all clients. Some older clients, embedded devices, and IoT systems may not support hybrid key exchange. Identify these systems and plan for their migration or replacement.

Run Known Answer Tests (KATs) for all PQ implementations. KATs verify that the implementation produces correct outputs for known inputs. An implementation that passes functional tests but fails KATs may have subtle bugs that compromise security.

Test rollback procedures. If a PQ implementation causes issues in production, you need the ability to disable it quickly and revert to classical-only operation. Document the rollback procedure and test it before deployment.

Step 6: Plan for Rollback

Every migration step should include a rollback plan. For hybrid key exchange, rollback means disabling the hybrid cipher suite and reverting to classical-only. This is a server configuration change that takes effect immediately.

For dual-signed packages, rollback means distributing packages signed with only the RSA signature. The RSA signing infrastructure remains operational throughout the transition.

For the H33-74 attestation overlay, rollback means disabling the attestation middleware. The underlying application is unaffected because the overlay is additive, not replacing any existing functionality.

Step 7: Set a Migration Timeline

Based on your inventory and prioritization, set a realistic migration timeline:

Month 1: Complete cryptographic inventory. Enable hybrid key exchange on highest-priority systems.

Months 2-3: Enable hybrid key exchange on all remaining external-facing systems. Begin dual signing for code and software distribution.

Months 3-6: Deploy PQ attestation overlay for highest-priority data flows. Begin certificate infrastructure migration.

Months 6-12: Complete certificate migration. Deploy PQ signatures across all application-level signing operations. Enable hybrid key exchange on internal systems.

Months 12-24: Deprecate classical-only cipher suites. Complete HSM and KMS migration to PQ key types. Update procurement requirements to mandate PQ support.

This timeline assumes an organization with moderate complexity. Large enterprises with thousands of systems may need 18-36 months. Small organizations with simpler environments can complete migration in 3-6 months.

The key principle is that the timeline should be aggressive for the first step (hybrid key exchange) and pragmatic for the remaining steps. Every day without hybrid key exchange is a day of accumulating quantum risk. The remaining steps can proceed at a sustainable pace once the highest-priority threat is addressed.