Cryptography is the science of protecting data. Cryptographic algorithms mathematically combine input plaintext data and an encryption key to generate encrypted data (ciphertext). With a good cryptographic algorithm, it is computationally not feasible to reverse the encryption process and derive the plaintext data, starting with only the ciphertext; some additional data, a decryption key, is needed to perform the transformation.

In traditional, secret (or symmetric) key cryptography, the encryption and decryption keys are identical and thus share sensitive data. Parties wishing to communicate with secret-key cryptography must securely exchange their encryption/decryption keys before they can exchange encrypted data.

In contrast, the fundamental property of public-key (PK) cryptography is that the encryption and decryption keys are different. Encryption with a public-key encryption key is a one-way function; plaintext turns into ciphertext, but the encryption key is irrelevant to the decryption process. A different decryption key (related, but not identical, to the encryption key) is needed to turn the ciphertext back into plaintext. Thus, for PK cryptography, every user has a pair of keys, consisting of a public key and a private key. By making the public key available, it is possible to enable others to send you encrypted data that can only be decrypted using your private key. Similarly, you can transform data using your private key in such a way that others can verify that it originated with you. This latter capability is the basis for digital signatures, discussed below.

Public-Key Functionality

The separation between public and private keys in PK cryptography has allowed the creation of a number of new technologies. The most important of these are digital signatures, distributed authentication, secret-key agreement via public key, and bulk data encryption without prior shared secrets.

There are a number of well-known PK cryptographic algorithms. Some, such as Rivest-Shamir-Adleman (RSA) and Elliptic Curve Cryptography (ECC), are general-purpose; they can support all of the above operations. Others support only a subset of these capabilities. Some examples include the Digital Signature Algorithm (DSA, which is part of the U.S. government's Digital Signature Standard, FIPS 186), which is useful only for digital signatures, and Diffie-Hellman (D-H), which is used for secret key agreement.

The following sections briefly describe the principal uses of PK cryptography. These operations are described in terms of two users, Bob and Alice. It is assumed that Bob and Alice can exchange information but do not have any pre-arranged, shared secrets between them.

Digital Signatures

Perhaps the most exciting aspect of public-key cryptography is creating and validating digital signatures. This is based on a mathematical transform that combines the private key with the data to be signed in such a way that:

• Only someone possessing the private key could have created the digital signature.
• Anyone with access to the corresponding public key can verify the digital signature.
• Any modification of the signed data (even changing only a single bit in a large file) invalidates the digital signature.

Digital signatures are themselves just data, so they can be transported along with the signed data that they protect. For example, Bob can create a signed e-mail message to Alice and send the signature together with the message text, providing Alice the information that is required to verify the message origin. In addition, digital signatures provide a way to verify that data has not been tampered with (either accidentally or intentionally) while in transit from the source to the destination. Therefore, they can be exploited to provide a very secure data-integrity mechanism.

Authentication

PK cryptography provides robust distributed authentication services. Entity authentication guarantees that the sender of data is the entity that the receiver thinks it is. If Alice receives data from Bob, and then sends him a challenge encrypted with Bob's public key, Bob then decodes this challenge and sends it back to Alice, proving that he has access to the private key associated with the public key that Alice used to issue the challenge. Alice can also send a plaintext challenge to Bob. Bob then combines the challenge with other information, which is digitally signed. Alice then uses Bob's public key to verify the signature and prove that Bob has the associated private key. The challenge makes this message unique and prevents replay attacks by a hostile third party. In either case, this is known as a proof-of-possession protocol because the sender proves that he has access to a particular private key.

Secret Key Agreement via Public Key

Another feature of PK cryptography is that it permits two parties to agree on a shared secret, using public, and nonsecure, communication networks. Basically, Bob and Alice each generate a random number that forms half of the shared secret key. Bob then sends his half of the secret, encrypted, to Alice, using her public key. Alice sends her half, encrypted, to Bob with his public key. Each side can then decrypt the message received from the other party, extract the half of the shared secret that was generated by the other, and combine the two halves to create the shared secret. Once the protocol is completed, the shared secret can be used for securing other communications.

Bulk Data Encryption without Prior Shared Secrets

The fourth major technology enabled by PK cryptography is the ability to encrypt bulk data without the establishment of prior shared secrets. Existing PK algorithms are computationally intensive relative to secret-key algorithms. This makes them ill suited for encrypting large amounts of data. To get the advantages of PK cryptography along with efficient bulk encryption, PK and secret-key technologies are typically combined. This is accomplished by first selecting a secret-key encryption algorithm and generating a random session key to use for data encryption. If Bob is sending the message, he first encrypts this session key, using Alice's public key. The resulting ciphertext key is then sent to Alice along with the encrypted data. Alice can recover the session key, using her private key, and then use the session key to decrypt the data.

Protecting and Trusting Cryptographic Keys

In secret-key cryptography, Alice and Bob trust their shared-secret key because they mutually agreed on it or exchanged it in a secure manner, and each has agreed to keep it stored securely to prevent access by a malicious third party. In contrast, using PK cryptography, Alice need only protect her private key and Bob, his private key. The only information they need to share is their public keys. They need to be able to identify the other's public key with positively, but they need not keep it secret. This ability to trust the association of a public key with a known entity is critical to the use of PK cryptography.

Alice might trust Bob's public key because Bob handed it to Alice directly in a secure manner, but this presupposes that Alice and Bob have had some form of prior secure communication. More likely, Alice has obtained Bob's public key through a nonsecure mechanism (for example, from a public directory), so some other mechanism is needed to give Alice confidence that the public key that she holds claiming to be from Bob really is Bob's public key. One such mechanism is based on certificates issued by a certificate authority (CA).

Certificates

Certificates provide a mechanism for gaining confidence in the relationship between a public key and the entity that owns the corresponding private key. A certificate is a digitally signed statement dealing with a particular subject public key, and the certificate is signed by its issuer (holding another pair of private and public keys). Typically, certificates also contain other information related to the subject public key, such as identity information about the entity that has access to the corresponding private key. Thus, when issuing a certificate, the issuer is attesting to the validity of the binding between the subject public key and the subject identity information.

The most common form of certificates in use today is based on the ITU-T X.509 standard. This is a fundamental technology used in the Windows 2000 PKI. It is, however, not the only form of certificates. Pretty Good Privacy (PGP) secure e-mail, for example, relies on a form of certificates unique to PGP.

Certificate Authorities

A certificate authority (CA) is an entity or service that issues certificates. A CA acts as a guarantor of the binding between the subject public key and the subject identity information that is contained in the certificates it issues. Different CAs may choose to verify that binding through different means, so it is important to understand the authority's policies and procedures before choosing to trust that authority to vouch for public keys.

Trust and Validation

The fundamental question facing Alice when she receives a signed message is whether she should trust that the signature is valid and was made by whoever claimed to make it. Alice can confirm that the signature is mathematically valid; that is, she can verify the integrity of the signature, using a known public key. However, Alice must still determine whether the public key used to verify the signature does, in fact, belong to the entity claiming to have made the signature in the first place. If Alice does not implicitly trust the public key to be Bob's, she needs to acquire strong evidence that the key belongs to Bob.

If Alice can locate a certificate, which was issued by a CA that Alice implicitly trusts, for Bob's public key, Alice can trust that Bob's public key really belongs to Bob. That is, Alice is likely to trust that she really has Bob's public key if she finds a certificate that:

• Has a cryptographically valid signature from its issuer.
• Attests to a binding between the name Bob and Bob's public key.
• Was issued by an issuer that Alice trusts.

Assuming that Alice finds such a certificate for Bob's public key, she can verify its authenticity, using the public key of the issuing CA, Ira. However, Alice is now faced with the same dilemma. How does she know that the public key actually belongs to Ira? Alice now needs to find a certificate attesting to the identity of Ira and the binding between Ira and Ira's public key.

Ultimately, Alice ends up constructing a chain of certificates leading from Bob and Bob's public key through a series of CAs and terminating in a certificate issued to someone that Alice implicitly trusts. Such a certificate is called a trusted root certificate because it forms the root (top node) of a hierarchy of public keys/identity bindings that Alice accepts as authentic (see section on Certificate Hierarchies). When Alice chooses to explicitly trust a particular trusted root certificate, she is implicitly trusting all the certificates issued by that trusted root, as well as all certificates issued by any subordinate CA certified by the trusted root.

The set of trusted root certificates that Alice explicitly trusts is the only information that Alice must acquire in a secure manner. That set of certificates secures Alice's trust system and her belief in the public-key infrastructure.