BOX 5.6
Public Key Cryptography

Public key cryptosystems were first described in the open literature by Whitfield Diffie and Martin Hellman at Stanford University in 1976.¹ In public key systems, each user has two keys. One is kept private while the other, as the name implies, is usually made public. These keys are mathematically related in such a way that knowledge of the public key does not allow one to determine the corresponding private key. (The reverse may or may not be true, depending on the public key algorithm in question.) This property of public key cryptosystems means that data encrypted with one user’s public key can be decrypted using his or her corresponding private key, without sharing the private key with others. Conversely, data that are transformed with a user’s private key (digital signing) can be verified with the corresponding public key, again without the need to divulge the key used to generate the signature. This latter relationship is most relevant to user-authentication systems based on public key technology. The use of public key systems significantly transforms the problem of key distribution: Distribution of public keys requires authentication and integrity of the public keys (we have to know whose public keys we are using) but not confidentiality (because the public keys need not be kept secret).

There are two basic ways in which public key systems are used:²

• Encryption. Public key systems are used to provide confidentiality by having the recipient of a confidential message first provide its public key to the sender. This transaction does not have to be held in secret because the key distribution, the public key, does not have to be kept confidential. The sender then encrypts the communication in the recipient’s public key and sends it to the recipient. Only the recipient can decrypt the message using his or her private key.

• Digital signature. Public key systems such as the RSA system³ and the Digital Signature Standard⁴ can provide what is often referred as a “digital signature.” Digitally signed data are not encrypted by the process. Instead, they are protected against unauthorized modification, and the identity of the signer of the data can be determined (data origin authentication) if, for example, a PKI has been established (or if the verifier trusts, through some other means, that the public key of the signer is as described). A message or document is digitally signed by transforming the data⁵ using the signer’s private key.

Digital Certificates

Most uses of public key systems require that one know that a given public key belongs to a particular person or organization. One obvious way to obtain the public key securely is to obtain it directly from the sender in a secure out-of-band channel (for example, by way of a personal interaction). This approach, while viable in some circumstances, in general does not scale very well.

However, the very nature of a digital signature lends itself to a solution to this problem. Specifically, if a recipient knows one public key, the issuer of that public key can “vouch” for the association between a different public key and its owner by issuing a digital document of that assertion. With some additional structure, this system becomes the basis for digital certificates, and therefore a PKI. The entity that signs (issues) a certificate usually is referred to as a certificate authority (CA). Note that CAs collect data from many users as part of the certificate issuance (registration) process and assign a single identifier to each user. This practice encourages a user to collapse multiple identities into a single identity for presumed ease of use in interactions with a diverse set of organizations, heightening the risk of linkage.

Because a certificate represents a binding between an identifier (presumably associated with the owner) and a key, it inherently contains some notion of identity. Just how strong this notion is, and the form of identity bound into a certificate, depends on the policies of the CA and on the intended use of the certificate. In some forms, a certificate can contain a name, an e-mail address, or an account number. In others, there may be no meaningful identification, just the public key itself. The basic notion behind the use of a certificate is to establish a certification path between a known public key and the certificate being verified.

---

¹See W. Diffie and M. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory IT-22(6)(1976):644-654.

²A third type of public key cryptosystem, public key agreement algorithms, is not discussed here, since these systems usually are employed for confidentiality but not for authentication.

³RSA was developed by Ron Rivest, Adi Shamir, and Leonard Adelman at MIT. See “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM 21,2 (February 1978): 120-126.

⁴See Federal Information Processing Standards Publication 186 on the Digital Signature Standard, available online at <http://www.itl.nist.gov/fipspubs/fip186.htm>.

⁵In practice, the data to be signed are first compressed in a one-way fashion, using a hash algorithm, and the resulting hash value is digitally signed. This variant on the basic scheme is employed because public key signature operations are relatively slow and signing a large amount of data would be very burdensome.