PKIaaS and Crypto-Agility Strategy: Preparing for Algorithm Changes

Every organization that uses PKI will eventually need to change the algorithms its PKI uses. Not because they chose the wrong algorithms initially, but because algorithm security does not remain constant over time. RSA-2048 was a secure choice in 2005 and an appropriate choice in 2015. NIST IR 8547 now establishes that RSA and ECC will be deprecated for new uses approximately 2030 and disallowed approximately 2035. NIST finalized three post-quantum cryptography standards in August 2024: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA). The migration from classical to post-quantum algorithms is not a future event to plan for; it is an active program that organizations should be executing now.

The critical question for organizations running PKI is not whether to migrate but how fast and at what cost. Organizations with self-managed, on-premises PKI face an infrastructure change to migrate algorithms: CA software updates, HSM firmware updates, new certificate templates, renewed change management cycles, and in some cases entirely new CA hierarchies for the new algorithm. Organizations using a crypto-agile PKI as a Service face a profile configuration change. The difference in effort, timeline, and risk between these two approaches is the core case for PKIaaS as a PQC migration accelerator.

Quick Answer: How Does PKIaaS Enable Crypto-Agility?

PKIaaS enables crypto-agility because the algorithm set used in certificate issuance is controlled by the certificate profile configuration, not by the CA hardware or software installation. When the platform team updates a certificate profile to specify ML-DSA (FIPS 204) instead of ECDSA P-256, all future certificate requests using that profile receive ML-DSA-signed certificates. The CA infrastructure (HSMs, CA software, key management) is the PKIaaS provider’s responsibility; when a new algorithm is supported by the platform, the customer configures its use through the management interface. Algorithm migration is a profile update, not an infrastructure project.

Key Takeaways

• NIST IR 8547 establishes that RSA and ECC will be deprecated for new uses approximately 2030 and disallowed approximately 2035. NIST finalized FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA) in August 2024. Organizations deploying PKI infrastructure today that will still be operational in 2030 should be designing PQC migration into that infrastructure now, not as a future retrofit.
• Crypto-agility in PKI means the ability to change the algorithm used in certificate profiles without replacing the CA infrastructure. PKIaaS delivers crypto-agility because the provider manages the CA software and HSM firmware currency; the customer manages the certificate profile configuration. When the provider adds ML-DSA support, the customer enables it in their certificate profiles. No HSM procurement, no CA software upgrade, no change management window for infrastructure.
• Cryptographic inventory is the prerequisite for algorithm migration planning. An organization that does not know which systems use which algorithms cannot prioritize the PQC migration, cannot identify which certificate types must be migrated before the 2030 deprecation window, and cannot measure migration progress. Cryptographic discovery and inventory must be the first step in any crypto-agility program, before profile updates begin.
• Hybrid and composite certificates are the migration bridge for environments that cannot update all relying parties simultaneously. A composite certificate combining ECDSA and ML-DSA in a single certificate works in both legacy systems (which verify using ECDSA) and updated systems (which verify using ML-DSA). PKIaaS deployments that support composite issuance enable migration to begin before the full relying party estate has been updated.
• Certificate profile centralization is what makes PKIaaS the right migration vehicle. In a self-managed PKI with multiple issuing CAs, each operating CA software configured independently, algorithm migration requires updating each CA individually. In PKIaaS, all issuing CAs are governed by the same management plane and the same certificate profiles. A profile update propagates to all CAs using that profile simultaneously. The migration operation scales with the profile set, not with the number of CAs.

Why the Algorithm Migration Window Is Not Optional

The post-quantum migration is not a threat on the horizon; it is a deadline with a specific date. NIST IR 8547 establishes a two-phase transition: deprecation of RSA and ECC for new uses approximately 2030, and disallowance of existing RSA and ECC uses approximately 2035. Federal systems governed by NIST guidance, and the many regulated and commercial systems that align to NIST standards, must complete their PQC migration within this window.

The 2030 deprecation date is closer than it appears when viewed through the lens of PKI program timelines. A CA hierarchy with a 20-year root CA validity period, intermediate CAs with 10-year validity, and issuing CAs with 5-year validity was probably designed and deployed well before 2025. Migrating it before 2030 requires: completing the cryptographic inventory to know what is in use (6 to 12 months for most large organizations), planning the migration sequence across certificate types (3 to 6 months), piloting PQC certificate issuance and relying party compatibility testing (3 to 6 months), and staged rollout across the certificate estate (12 to 24 months for large deployments). These timelines add up to 24 to 48 months of active program execution, placing the start date for a comfortable migration at 2026 or at the latest 2027.

Organizations that have not started the inventory phase are already behind the timeline for a low-risk migration. The organizations at greatest risk are those with large certificate estates, many certificate types, diverse relying party systems (some of which will be slow to update for ML-DSA support), and legacy CA infrastructure that requires hardware-level changes to support new algorithms. PKIaaS eliminates the last of these risks; the other three require program execution regardless of the PKI infrastructure model.

There is also a data security risk dimension independent of the compliance deadline. The “harvest now, decrypt later” (HNDL) attack strategy, in which adversaries collect encrypted data today with the intention of decrypting it when a cryptographically-relevant quantum computer becomes available, means that data encrypted with RSA or ECC keys today may be decryptable by a sufficiently capable quantum adversary in the future. Organizations with long data confidentiality requirements (classified government data, financial records, health information with multi-decade retention requirements) should treat the PQC migration as an active risk management program, not a compliance checkbox for 2030.

Step 1: Cryptographic Inventory Before Profile Updates

Algorithm migration planning requires a complete picture of what algorithms are in use, where, and in what certificate types. Without this picture, the migration plan is incomplete: some certificate types will be missed, some relying parties will encounter unexpected incompatibility, and the migration will appear complete on paper while leaving RSA or ECC certificates in production systems.

A cryptographic inventory for PKI migration planning collects:

• Signature algorithm and key size per certificate: Which algorithms (RSA-2048, RSA-4096, ECDSA P-256, ECDSA P-384, DSA) are currently in use across the certificate estate, and at what key sizes. This identifies which certificates are below current minimums and which will require migration by the 2030 deprecation date.
• Certificate type per certificate: TLS server, TLS client, smart card logon, S/MIME, code signing, device identity, CA certificate. Each certificate type has different relying parties with different update timelines, different validity periods, and different enrollment mechanisms. Migration planning must be done per certificate type, not per algorithm only.
• Issuing CA per certificate: Which CA issued each certificate, and whether that CA’s signing algorithm is the bottleneck (a CA signing with RSA-2048 produces RSA-2048-signed certificates regardless of the subscriber key). CA algorithm migration must precede subscriber certificate migration in the hierarchy.
• Relying party systems per certificate type: Which systems verify certificates of each type, and whether those systems have confirmed ML-DSA support or are on a roadmap for update. Systems that will not support ML-DSA within the migration window may require continued classical certificate issuance through the composite certificate bridge.
• Non-certificate cryptographic assets: SSH keys, TLS session configurations, code signing keys, symmetric encryption keys, and hardware root-of-trust certificates that use classical algorithms. These are outside the direct scope of PKI certificate migration but are part of the organization’s full post-quantum migration scope.

Encryption Consulting’s CBOM Secure provides this cryptographic inventory through automated discovery across the organization’s network and infrastructure, producing a Cryptographic Bill of Materials (CBOM) that catalogs every cryptographic asset in the environment. The CBOM is the input to the migration prioritization phase: it shows which algorithms are in use, which certificate types have the highest volume of classical-algorithm certificates, and which systems have the longest estimated relying party update timelines.

Step 2: Establishing Algorithm Policy in Certificate Profiles

Algorithm policy in PKIaaS is expressed through certificate profiles. Each profile specifies the permitted key algorithms and minimum key sizes for certificates issued under that profile. In a crypto-agile PKIaaS deployment, the algorithm policy is centralized in the certificate profile set and enforced by the CA at issuance time: a request for a certificate using an algorithm not permitted by the profile is rejected before any certificate is signed.

Establishing algorithm policy for the PQC migration involves three profile-level decisions:

• Minimum key size enforcement for existing algorithms: Before migrating to PQC algorithms, confirm that all active certificate profiles enforce current minimum key sizes for classical algorithms — RSA-2048 minimum (RSA-3072 or RSA-4096 preferred for new issuance), ECDSA P-256 minimum (P-384 preferred). Profiles that permit RSA-1024 or other sub-minimum key sizes should be updated immediately, regardless of where the organization is in the PQC migration timeline. Under-sized keys are a present-day risk, not a future one;
• Classical-only profiles for certificate types whose relying parties have not yet confirmed ML-DSA support: Some certificate types (browser-facing TLS, legacy network device authentication) will depend on relying parties that may not immediately support ML-DSA verification. During the transition period, certificate profiles for these types maintain classical algorithm requirements (ECDSA P-256 or RSA-2048) while the relying party ecosystem catches up;
• Composite/hybrid profiles for certificate types in active PQC migration: For certificate types where relying parties are being updated to support ML-DSA but not all relying parties are updated simultaneously, composite certificate profiles specify both ECDSA and ML-DSA components in a single certificate. The profile defines the algorithm combination, the key parameters for each component, and whether the classical or PQC signature takes precedence for relying parties that support both. Once the relying party estate for a certificate type is fully updated, the composite profile transitions to a pure ML-DSA profile;
• ML-DSA-only profiles for certificate types with fully updated relying party estates: Certificate types where all relying parties have been confirmed to support ML-DSA verification move to pure ML-DSA profiles. This is the migration endpoint for each certificate type: the composite phase is a bridge, not a permanent state.

Step 3: CA Key Algorithm Migration

The CA signing key algorithm is the first migration target, not the last. Every certificate issued by a CA inherits the CA’s signature algorithm in its issuer chain: a CA signing with RSA-2048 signs all subscriber certificates with RSA-2048, regardless of the subscriber key algorithm. Migrating to ML-DSA subscriber certificates under an RSA-signed issuing CA produces a hybrid chain that is not fully post-quantum (the chain of trust from root to subscriber still includes an RSA-signed CA certificate).

Full PQC migration of the PKI hierarchy requires migrating the CA keys from root to leaf in the hierarchy. The process:

• Generate new ML-DSA root CA keys (with a new root CA key ceremony).
• Generate new ML-DSA intermediate and issuing CA keys, signed by the ML-DSA root CA.
• Distribute the new ML-DSA root CA certificate to all trust stores (operating system, browser, application, device) alongside the existing classical root CA certificate, maintaining both during the transition period.
• Begin issuing subscriber certificates from the new ML-DSA issuing CA hierarchy for certificate types whose relying parties have confirmed ML-DSA root CA trust.
• Continue issuing from the classical CA hierarchy for certificate types whose relying parties have not yet updated trust stores to include the ML-DSA root.
• Retire the classical CA hierarchy after all relying party trust stores have been updated and all classical-hierarchy certificates have expired or been replaced.

In a PKIaaS deployment, generating new CA keys for ML-DSA, subordinating them under the new PQC root, and configuring issuing CAs to use the PQC hierarchy is a management console and API operation. The PKIaaS provider manages the HSM key generation and the CA hierarchy configuration. In a self-managed on-premises PKI, each of these steps requires hardware interaction with the HSM, CA software configuration changes, and physical ceremony coordination. The PKIaaS advantage in CA key migration is the same as in profile updates: configuration replaces hardware interaction.

Hybrid and Composite Certificates: The Migration Bridge

Composite certificates encode both a classical signature (ECDSA P-256 or P-384) and a post-quantum signature (ML-DSA) in a single X.509 certificate. The composite structure is defined in IETF draft standards for composite public key and signature algorithms (ongoing work in the IETF LAMPS working group as of 2026).

The migration value of composite certificates is that they eliminate the need to simultaneously update all relying parties before any PQC certificate can be deployed. A relying party that supports only classical ECDSA verification can still verify a composite certificate using the ECDSA component. A relying party that has been updated to support ML-DSA can verify the same certificate using the ML-DSA component. The certificate is verifiable in both environments.

Practical considerations for composite certificate deployment:

• Certificate size increases: Including both ECDSA and ML-DSA public keys and signatures in one certificate produces a significantly larger certificate than a classical-only certificate. ML-DSA (FIPS 204) with parameter set ML-DSA-65 produces a public key of 1,952 bytes and a signature of 3,309 bytes. Combined with an ECDSA P-256 public key (65 bytes) and signature (64-72 bytes), a composite certificate is substantially larger than a classical certificate. Applications that transmit certificates in bandwidth-constrained contexts (some TLS handshake configurations, some IoT device communication protocols) should evaluate composite certificate size impact before deployment;
• PKIaaS provider support confirmation required: Composite certificate issuance requires the PKIaaS CA software and HSM firmware to support generating both algorithm components in a single certificate signing operation. Confirm composite certificate support with the PKIaaS provider before designing a migration plan that depends on this capability. As of August 2026, composite certificate support varies by PKIaaS provider;
• Composite as a transitional state, not a permanent one: A composite certificate environment carries both classical and PQC algorithm maintenance overhead indefinitely if not managed as a transition. The migration plan for each certificate type should define the criteria for moving from composite to pure ML-DSA profiles — specifically, what percentage of relying parties must support ML-DSA before the composite phase ends for that certificate type.

Algorithm Policy as an Ongoing Governance Practice

Crypto-agility is not a project with a completion date; it is an ongoing governance practice. The PQC migration is the current implementation of that practice, but algorithm changes will continue beyond PQC: ML-DSA parameter set updates, new algorithm standardization, algorithm-specific vulnerabilities discovered post-standardization, and CA/B Forum requirements for browser-trusted certificates will all drive future algorithm policy changes.

PKIaaS governance for algorithm policy involves three permanent operational practices:

• Certificate profile review cadence: Certificate profiles should be reviewed at least annually against current NIST, ETSI, and CA/B Forum algorithm requirements. Any profile that permits algorithms or key sizes below current standards should be updated. The review should be documented, including the decision rationale for any profile that maintains sub-current-standard algorithms for backward-compatibility reasons (with a planned end date for the exception);
• Continuous cryptographic inventory: The CBOM maintained by the cryptographic inventory platform should be a continuously updated view, not a point-in-time assessment. New certificates are issued daily; algorithms in use change as new certificate types are deployed and old ones expire. The ongoing CBOM feeds the algorithm policy review with current data rather than stale assessment data;
• Algorithm deprecation trigger process: When NIST, ETSI, NSA, or the CA/B Forum announces a deprecation or disallowance for a specific algorithm or key size, the organization should have a defined process for: (1) assessing impact using the current CBOM (which systems use the deprecated algorithm and in what volume); (2) updating the affected certificate profiles to add the new algorithm or remove the deprecated one; (3) identifying the relying party update timeline for the transition; and (4) executing the migration according to the prioritized certificate type sequence. This trigger process should be documented and tested before a real deprecation announcement requires it.

CNSA 2.0 and National Security System Obligations

For organizations operating US national security systems or systems subject to NSA guidance, the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0) establishes the algorithm requirements for national security systems in the post-quantum era. CNSA 2.0 specifies ML-KEM and ML-DSA as the required algorithms for new systems and defines transition timelines for existing systems.

CNSA 2.0 timelines are generally more aggressive than NIST IR 8547 timelines for general-purpose systems. Defense contractors, intelligence community operators, and federal agencies operating classified or national security systems should confirm which timeline applies to their specific system classification and ensure that their PKIaaS deployment is on a migration path compatible with CNSA 2.0 requirements.

PKIaaS certificate profile updates for CNSA 2.0 compliance follow the same mechanism as for general NIST IR 8547 compliance: profile algorithm updates, CA key migration to ML-DSA signing keys, and composite certificate bridge where needed. The difference is the timeline and the specific algorithm parameter sets required by CNSA 2.0 (ML-DSA-87, ML-KEM-1024 for TOP SECRET systems).

Measuring Migration Progress

A crypto-agility program requires measurable progress metrics. For PQC certificate migration, the primary metrics are:

• Algorithm distribution across the active certificate estate: What percentage of currently active certificates use ECDSA P-256, ECDSA P-384, RSA-2048, RSA-4096, composite (ECDSA + ML-DSA), and pure ML-DSA? This metric, tracked monthly from the CLM inventory, shows migration velocity and identifies certificate types or issuing CAs where migration has stalled;
• Percentage of certificate types with ML-DSA-capable profiles: For each certificate type in the PKIaaS profile set, is the active profile ML-DSA-capable (pure ML-DSA or composite), or is it still classical-only? This metric tracks profile update progress independently of the actual certificate estate — a profile can be updated to support ML-DSA before the first ML-DSA certificate under that profile is issued;
• Relying party ML-DSA support coverage: For each certificate type, what percentage of the relying party population has been confirmed to support ML-DSA certificate verification? This metric drives the composite-to-pure-ML-DSA transition decision for each certificate type — the threshold for ending the composite phase should be defined in the migration plan and tracked against the relying party inventory;
• Classical algorithm certificate expiry profile: What is the maximum remaining validity period across all classical-algorithm certificates in the active estate? This metric ensures that all classical-algorithm certificates will have expired before the 2035 disallowance date, without requiring proactive revocation and replacement of every certificate before its natural expiry.

How Encryption Consulting Can Help

• CBOM Secure: Encryption Consulting’s CBOM Secure provides the cryptographic inventory that is the prerequisite for PQC migration planning: automated discovery of all cryptographic assets across the organization’s network and infrastructure, algorithm classification (RSA, ECDSA, AES, and their respective key sizes), CBOM generation in CycloneDX format, and continuous inventory updates that feed ongoing algorithm policy governance. Contact us at Encryption Consulting to start with a cryptographic inventory assessment.
• PKI as a Service: Encryption Consulting’s PKIaaS offering is the crypto-agile CA infrastructure that enables profile-level algorithm migration without infrastructure replacement: ML-DSA (FIPS 204) certificate profile support, composite/hybrid certificate issuance capability, centralized certificate profile management across the full issuing CA hierarchy, and the CA key migration services needed to create PQC root and issuing CA keys under the new algorithm hierarchy.
• PQC Advisory Services: Encryption Consulting’s PQC Advisory Services provide the structured migration roadmap from classical to post-quantum PKI: inventory assessment using CBOM Secure output, migration prioritization by certificate type and relying party update timeline, composite certificate profile design, CA key migration planning (ceremony design for new ML-DSA root CA keys), relying party compatibility testing, and staged rollout planning through the 2030 deprecation and 2035 disallowance dates.
• PQC Center of Excellence: Encryption Consulting’s PQC Center of Excellence provides the technical expertise and regulatory alignment for organizations navigating NIST IR 8547, CNSA 2.0, ETSI EN 319 series PQC guidance, and industry-specific post-quantum requirements. The Center provides research-backed assessments of algorithm migration risks, composite certificate interoperability testing, and executive-facing migration status reporting.
• CertSecure Manager: Encryption Consulting’s CertSecure Manager provides the CLM visibility layer for measuring migration progress: algorithm distribution metrics across the active certificate estate, certificate type-level migration status tracking, relying party compatibility monitoring, and classical algorithm expiry profile reporting. The CLM metrics feed the ongoing algorithm policy governance practice that crypto-agility requires.

Conclusion

The post-quantum migration is the most significant algorithm change in the history of PKI. The NIST IR 8547 deprecation and disallowance timeline is fixed. The FIPS 203, 204, and 205 standards are final. The migration program needs to be running now for organizations that want to reach the 2030 deprecation date in a position of readiness rather than scramble.

PKIaaS makes this migration program faster and lower-risk than the equivalent program on self-managed PKI infrastructure. The mechanism is crypto-agility: algorithm migration through profile configuration rather than infrastructure replacement. The certificate profile is the policy lever; updating the profile propagates the algorithm change to all future certificate issuance under that profile. The CA software and HSM firmware that support ML-DSA are the PKIaaS provider’s responsibility. The organization’s responsibility is the inventory, the prioritization, the profile updates, the relying party compatibility work, and the governance practices that make the migration measurable and sustainable.

Organizations that start the cryptographic inventory now have time to execute a methodical migration. Organizations that start in 2028 will be doing emergency migrations under deadline pressure with relying party compatibility as an unknown variable. The difference is planning, and planning starts with knowing what you have.

If your organization is beginning a PQC migration assessment or designing a crypto-agility program, reach out to Encryption Consulting.

This post is reviewed on a six-month cadence and when NIST, NSA, ETSI, or IETF publish updates to PQC standards, algorithm transition timelines, or composite certificate specifications that affect PKI migration planning.

Frequently Asked Questions

What is crypto-agility and why does it matter for PKI?

Crypto-agility is the ability to replace cryptographic algorithms without replacing the systems that use them. For PKI, it means the CA can issue certificates using ML-DSA instead of ECDSA by updating a certificate profile, not by replacing CA hardware or software. It matters because NIST IR 8547 establishes that RSA and ECC will be deprecated approximately 2030 and disallowed approximately 2035. PKIaaS delivers crypto-agility because algorithm selection is in the certificate profile, not in the CA infrastructure.

What NIST post-quantum cryptography standards apply to PKI certificates?

NIST finalized three PQC standards in August 2024. FIPS 204 (ML-DSA, based on CRYSTALS-Dilithium) is the primary post-quantum digital signature algorithm for PKI certificate signing. FIPS 205 (SLH-DSA, based on SPHINCS+) is an alternative post-quantum signature algorithm with hash-based security assumptions. FIPS 203 (ML-KEM, based on CRYSTALS-Kyber) applies to TLS key exchange rather than certificate signing. For PKI certificate migration, FIPS 204 ML-DSA is the primary migration target for CA signing keys and subscriber certificates.

What are hybrid or composite PQC certificates?

A composite certificate contains both a classical signature (ECDSA) and a post-quantum signature (ML-DSA) in a single X.509 certificate. Relying parties that support only ECDSA can verify the certificate using the classical component; relying parties updated to support ML-DSA can verify using the post-quantum component. This enables PQC migration to begin before all relying parties have been updated, eliminating the need to synchronize the entire relying party estate before any PQC certificates can be deployed.

What is the NIST IR 8547 deprecation timeline for RSA and ECC?

NIST IR 8547 establishes that RSA and ECC will be deprecated for new uses approximately 2030 (new systems and new certificates should use PQC algorithms after this date) and disallowed approximately 2035 (existing RSA and ECC uses must be migrated by this date). Given that enterprise PQC migration programs typically require 24 to 48 months to execute across all certificate types, organizations should be starting inventory and planning work now to meet the 2030 deprecation date without emergency-mode execution.

How does PKIaaS make algorithm migration faster than self-managed PKI?

In self-managed PKI, algorithm migration requires CA software updates, HSM firmware updates, new certificate templates, and change management cycles for each CA independently. In PKIaaS, the provider manages CA software and HSM firmware currency. When ML-DSA is supported by the platform, the customer updates certificate profiles through the management interface. All issuing CAs using that profile receive the update simultaneously. Algorithm migration is a profile configuration change, not a multi-CA infrastructure upgrade project.