Transitioning to and from crypto-agile hybrid public key infrastructures

A computer system comprising:

• one or more processors;
• and
• memory storing instructions that are operable when executed by the one or more processors to perform operations comprising:
• accessing a primary root certificate of a root certificate authority of a PKI system, the primary root certificate comprising a first public key based on a first cryptosystem and a first signature generated with a private key that corresponds to the first public key;
• generating a secondary crypto-agile root certificate of the root certificate authority, the secondary crypto-agile root certificate comprising:
• the first public key of the root certificate authority;
• a second public key of the root certificate authority based on a second cryptosystem;
• a second signature of the root certificate authority generated with a second private key that corresponds to the second public key;
• and
• a third signature of the root certificate authority generated with the first private key;
• and
• propagating the secondary crypto-agile root certificate to at least one subordinate entity in the PKI system, wherein propagating the secondary crypto-agile root certificate causes the secondary crypto-agile root certificate to be inserted in a certificate chain between the primary root certificate and a certificate of an intermediate certificate authority.

A non-transitory computer-readable medium comprising instructions that, when executed by data processing apparatus of a computer system, perform operations comprising:

• accessing a primary root certificate of a root certificate authority of a PKI system, the primary root certificate comprising a first public key based on a first cryptosystem and a first signature generated with a private key that corresponds to the first public key;
• generating a secondary crypto-agile root certificate of the root certificate authority, the secondary crypto-agile root certificate comprising:
• the first public key of the root certificate authority;
• a second public key of the root certificate authority based on a second cryptosystem;
• a second signature of the root certificate authority generated with a second private key that corresponds to the second public key;
• and
• a third signature of the root certificate authority generated with the first private key;
• and
• propagating the secondary crypto-agile root certificate to at least one subordinate entity in the PKI system, wherein propagating the secondary crypto-agile root certificate causes the secondary crypto-agile root certificate to be inserted in a certificate chain between the primary root certificate and a certificate of an intermediate certificate authority.