Because classical cryptosystems use shared keys, it is not possible to bind an identity to a key.

Public key cryptosystems use two keys, one of which is to be available to all. The association between the cryptographic key and the principal is critical, because it determines the public key used to encipher messages for secrecy. If the binding is erroneous, someone other than the intended recipient could read the message.

For purposes of this discussion, we assume that the principal is identified by a name of some acceptable sort and has been authenticated to the entity that generates the cryptographic keys. The question is how some (possibly different) principal can bind the public key to the representation of identity.

An obvious idea is for the originator to sign the public key with her private key, but this merely pushes the problem to another level, because the recipient would only know that whoever generated the public key also signed it. No identity is present.

Creating a message containing a representation of identity, the corresponding public key, and a timestamp, and having a trusted authority sign it.

CAlice = { eAlice || Alice || T } dCathy

This type of structure is called a certificate.

A certificate is a token that binds an identity to a cryptographic key.

When Bob wants to communicate with Alice, he obtain's Alice's certificate CAlice. Assuming that he knows Cathy's public key, he can decipher the certificate. He first checks the timestamp T to see when the certificate was issued. (From this, he can determine if the certificate is too old to be trusted; see below.) He looks at the subject entity (Alice, to whom the certificate was issued). The public key in the certificate belongs to that subject, so Bob now has Alice's public key. He knows that Cathy signed the certificate and therefore that Cathy is vouching to some degree that the public key belongs to Alice. If he trusts Cathy to make such a determination, he accepts the public key as valid and belonging to Alice.

One immediate problem is that Bob must know Cathy's public key to validate the certificate. Two approaches deal with this problem. The first, by Merkle, eliminates Cathy's signature; the second structures certificates into signature chains.

Certificate Signature Chains

The usual form of certification is for the issuer to encipher a hash of the identity of the subject (to whom the certificate is issued), the public key, and information such as time of issue or expiration using the issuer's private key. To validate the certificate, a user uses the issuer's public key to decipher the hash and check the data in the certificate. The user trying to validate the certificate must obtain the issuer's public key. If the issuer has a certificate, the user can get that key from the issuer's certificate. This pushes the problem to another level: how can the issuer's certificate be validated?

Two approaches to this problem are to construct a tree-like hierarchy, with the public key of the root known out of band, or to allow an arbitrary arrangement of certifiers and rely on each individual's knowledge of the certifiers. First, we examine X.509, which describes certificates and certification in general. We then look at the PGP certification structure.

Certification Signature Chains

X.509the Directory Authentication Framework is the basis for many other protocols. It defines certificate formats and certification validation in a generic context. Soon after its original issue in 1988, I'Anson and Mitchell found problems with both the protocols and the certificate structure. These problems were corrected in the 1993 version, referred to as X.509v3.

The X.509v3 certificate has the following components.

To validate the certificate, the user obtains the issuer's public key for the particular signature algorithm (field 3) and deciphers the signature (field 11). She then uses the information in the signature field (field 11) to recompute the hash value from the other fields. If it matches the deciphered signature, the signature is valid if the issuer's public key is correct. The user then checks the period of validity (field 5) to ensure that the certificate is current.

A certification authority (CA) is an entity that issues certificates.

If all certificates have a common issuer, then the issuer's public key can be distributed out of band. However, this is infeasible. For example, it is highly unlikely that France and the United States could agree on a single issuer for their organizations' and citizens' certificates. This suggests multiple issuers, which complicates the process of validation.

Suppose Alice has a certificate from her local CA, Cathy. She wants to communicate with Bob, whose local CA is Dan. The problem is for Alice and Bob to validate each other's certificates.

Assume that X<<Y>> represents the certificate that X generated for the subject Y (X is the CA that issued the certificate). Bob's certificate is Dan<<Bob>>. If Cathy has issued a certificate to Dan, Dan has a certificate Cathy<<Dan>>; similarly, if Dan has issued a certificate to Cathy, Cathy has a certificate Dan<<Cathy>>. In this case, Dan and Cathy are said to be cross-certified.

Two CAs are cross-certified if each has issued a certificate for the other.

Because Alice has Cathy's (trusted) public key, she can obtain Cathy<<Dan>> and form the signature chain

Cathy<<Dan>> Dan<<Bob>>

Because Alice can validate Dan's certificate, she can use the public key in that certificate to validate Bob's certificate. Similarly, Bob can acquire Dan<<Cathy>> and validate Alice's certificate.

Dan<<Cathy>> Cathy<<Alice>>

Signature chains can be of arbitrary length. The only requirement is that each certificate can be validated by the one before it in the chain. (X.509 suggests organizing CAs into a hierarchy to minimize the lengths of certificate signature chains, but this is not a requirement.)

Certificates can be revoked, or canceled. A list of such certificates enables a user to detect, and reject, invalidated certificates.

PGP Certificate Signature Chains

PGP is an encipherment program widely used to provide privacy for electronic mail throughout the Internet, and to sign files digitally. It uses a certificate-based key management infrastructure for users' public keys. Its certificates and key management structure differ from X.509's in several ways. Here, we describe OpenPGP's structure; but much of this discussion also applies to other versions of PGP.

An OpenPGP certificate is composed of packets. A packet is a record with a tag describing its purpose. A certificate contains a public key packet followed by zero or more signature packets. An OpenPGP public key packet has the following structure.

The information in an OpenPGP signature packet is different for the two versions. Version 3 contains the following.

A Version 4 signature packet is considerably more complex, but as a Version 3 signature packet does, it binds a signature to an identifier and data. The interested reader is referred to the OpenPGP specifications.

PGP certificates differ from X.509 certificates in several important ways. Unlike X.509, a single key may have multiple signatures. (All Version 4 PGP keys are signed by the owner; this is called self-signing.) Also unlike X.509, a notion of "trust" is embedded in each signature, and the signatures for a single key may have different levels of trust. The users of the certificates can determine the level of trust for each signature and act accordingly.

In the example above, Alice followed two signature chains:

Henry<<Henry>> Henry<<Giselle>> Giselle<<Bob>>

and

Jack<<Ellen>> Ellen<<Bob>>

(where the unchecked signatures have been dropped). The trust levels affected how Alice checked the certificate.

A subtle distinction arises here between X.509 and PGP certificates. X.509 certificates include an element of trust, but the trust is not indicated in the certificate. PGP certificates indicate the level of trust, but the same level of trust may have different meanings to different signers.

Summary

The deployment and management of public keys is complex because of the different requirements of various protocols. Most protocols use some form of the X.509v3 certificates, although the extensions vary. The infrastructure that manages public keys and certification authorities is called a public key infrastructure. Several such infrastructures are in place, such as the PGP Certificate Servers and the commercial certificate issuers for World Wide Web browsers.