5.4 PUBLIC KEY CRYPTOGRAPHY

Team-Fly

The idea of using one-way functions, which can only be inverted if a certain secret (a so-called "trapdoor") is known, has led to the invention of public key cryptography or asymmetric cryptography [21]. Today, public key cryptography is a battlefield for mathematicians and theoretical computer scientists. We are not going to delve into the mathematical foundations of public key cryptography. Instead, we address public key cryptography from a more practical point of view. From this point of view, a public key cryptosystem is simply a cryptosystem in which a user has a pair of mathematically related keys:

A public key that can be published without doing any harm to the system's overall security;
A private key that is assumed to never leave the possession of its owner.

For both the public and the private keys, it is computationally infeasible for an outsider to derive one from the other. The use of a public key cryptosystem is overviewed in Figure 5.3. A and B each has a public key pair (k_A, k_A⁻¹) and (k_B, k_B⁻¹). The private keys k_A⁻¹ and k_B⁻¹ are kept secret, whereas the public keys k_A and k_B are publicly available in certified form (e.g., digitally signed by a certification authority as further addressed later).

click to expand
Figure 5.3: A public key cryptosystem

If A wants to protect the confidentiality of a plaintext message P, she uses the public key of B, which is k_B, encrypts P with this key, and sends the resulting ciphertext C = E_{k_B} (P) to B (the term E_{k_B} (P) is abbreviated with E_B (P) in Figure 5.3). On the other side, B uses his private key k_B⁻¹ to successfully decrypt P = D_{k⁻¹_B}(C) = D_{k⁻¹_B}(E_{k_B}(P)). Note that the terms D_{k⁻¹_B} (C) and D_{k⁻¹_B}(E_{k_B}(P)) are abbreviated with D_B(C) and D_B(E_B(P)) in Figure 5.3.

A public key cryptosystem can not only be used to protect the confidentiality of a message, but also to protect its authenticity and integrity. If A wanted to protect the authenticity and integrity of a message M, she would compute a digital signature S for M. Digital signatures provide an electronic analog of handwritten signatures for electronic documents, and—similar to handwritten signatures—digital signatures must not be forgeable, recipients must be able to verify them, and the signers must not be able to repudiate them later. However, a major difference between a handwritten signature and a digital signature is that the digital signature cannot be constant, but must be a function of the entire document on which it appears. If this were not the case, a digital signature, because of its electronic nature, could be copied and attached to arbitrary documents.

Arbitrated digital signature schemes are based on secret key cryptography. In such a scheme, a TTP validates the signature and forwards it on the signer's behalf. True digital signature schemes, however, should come along without TTPs taking an active role. They usually require the use of public key cryptography: Signed messages are sent directly from signers to recipients. In essence, a digital signature scheme consists of:

A key-generation algorithm that randomly selects a public key pair;
A signature algorithm that takes as input a message and a private key and that generates as output a digital signature for the message;
A signature verification algorithm that takes as input a digital signature and a public key and that generates as output a message and an information bit according to whether the signature is valid for the message.

A comprehensive overview and discussion of public key-based digital signature schemes are given in [22]. According to the OSI security architecture, a digital signature refers to data appended to, or a cryptographic transformation of, a data unit that allows a recipient of the data unit to prove the source and integrity of the data unit and protect against forgery (e.g., by the recipient). Consequently, there are two classes of digital signatures:

A digital signature giving message recovery refers to the situation in which a cryptographic transformation is applied to a data unit. In this case, the data is automatically recovered if the recipient verifies the signature.
In contrast, a digital signature with appendix refers to the situation in which some cryptographically protected data is appended to the data unit. In fact, the data represents a digital signature and can be decoupled from the data unit that it signs.

In the case of digital signatures with appendix, the bandwidth limitation of public key cryptography is unimportant because of the use of one-way hash functions as auxiliaries. Again referring to Figure 5.3, A can use her private key k⁻¹_A to compute a digital signature S = D_A(M) or S = D_A(h(M)) for message M. In the second case, h refers to a collision-resistant one-way hash function that is applied to M before generating the digital signature. Anyone who knows the public key of A can verify the digital signature by decrypting it with k_A and comparing the result with another hash value that is recomputed for the same message with the same one-way hash function.

The use of public key cryptography simplifies the problem of key management considerably. Note that in Figure 5.3, instead of providing A and B with a unique session key that is protected in terms of confidentiality, integrity, and authenticity, the trusted third party, which is now called a certification authority (CA), has to provide A and B with the public key of the communicating peer. This key is public in nature and must not be protected in terms of confidentiality. Nevertheless, the use of public key cryptography requires an authentication framework that binds public keys to user identities. As further addressed in Chapter 19, a public key certificate is a certified proof of such binding vouched for by a TTP acting as a CA [23]. According to Webster's Dictionary, the term certificate refers to a document stating the truth. In the digital world we live in today, the term is mostly used to refer to a collection of information to which a digital signature has been affixed by some authority who is recognized and trusted by some community of certificate users. According to this definition, there exist various types of certificates that potentially serve many purposes. In either case, a certificate is a form of credentials. Examples of credentials used in daily life are drivers' licenses, Social Security cards, or birth certificates. Each of these credentials has some information on it identifying its owner and some authorization stating that someone else has confirmed the information. A public key (or digital) certificate consists of three things:

A public key;
Certificate information that refers to the certificate owner's identity, such as his or her name);
One or more digital signatures.

The aim of the digital signature(s) on the certificate is to state that the certificate information has been attested to by some other person or entity.

A digital certificate can be one of a number of different formats, including, for example, PGP and X.509. PGP and X.509 certificates are identified in different ways. More specifically, PGP certificates are identified by user identifiers (IDs) that typically comprise a person's name followed by a bracketed e-mail address, whereas X.509 certificates are identified by X.500 distinguished names (DNs) or other naming schemes. Another major difference between the two certificate formats is that PGP allows many identities and signatures per certificate, whereas X.509 permits only one identity and one signature per certificate.

As their name suggests, X.509 certificates conform to the ITU-T recommendation X.509. In fact, X.509 specifies both a certificate format and a certificate distribution scheme [24]. It was first published in 1988 as part of the X.500 directory recommendations. The X.509 version 1 (X.509v1) format was extended in 1993 to incorporate two new fields to support directory access control, resulting in the X.509 version 2 (X.509v2) format. In addition, and as a result of attempting to deploy certificates within the global Internet, X.509v2 was revised to allow for additional extension fields. The resulting X.509 version 3 (X.509v3) specification was officially released in June 1996. Meanwhile, the ITU-T recommendation X.509 has been approved by the ISO/IEC Joint Technical Committee 1 (JTC1) [25]. The format of an X.509v3 certificate has originally been specified in a notation called Abstract Syntax Notation One (ASN.1). One can apply encoding rules to a certificate specified in ASN.1 format to produce a series of bits and bytes suitable for transmission in computer networks.

A trust model refers to the set of rules a system or application uses to decide whether a certificate is valid. There are (at least) three different trust models:

In the direct trust model, a user trusts a key that is valid because he or she knows where it came from (e.g., the user gets the key directly from another user).
In the hierarchical trust model, there are a number of "root" certificates from which trust extends. More specifically, in this model, certificates may certify public keys, or they may certify certificates that certify still other certificates down some chain.
The cumulative trust model encompasses both the direct and hierarchical trust models but also adds the notion that trust is in the eye of the beholder and the idea that more information is better. In this model, a certificate might be trusted directly, trusted in some chain going back to a directly trusted root certificate, or trusted by some group of introducers.

Obviously, direct trust is the simplest trust model, and many systems that use cryptography depend on it. For example, in Web browsers root CA keys are directly trusted because they are shipped together with the software packages.

Contrary to that, the trust model often used in the context of ITU-T X.509 certificates is hierarchical [24, 25].^[4] In this case, the simplest model one may think of is a certification hierarchy representing a tree with a single root CA. However, more general structures and graphs (including mutually certifying CAs, cross-certificates, and multiple root CAs) are also possible. In X.509 parlance, the term public key infrastructure (PKI) refers to an infrastructure that can be used to issue, validate, and revoke public keys and public key certificates. As such, a PKI comprises a set of agreed-upon standards, CAs, structures among multiple CAs, methods to discover and validate certification paths, operational and management protocols, interoperable tools, and supporting legislation. A PKI structure among multiple CAs generally provides one or more certification paths between a subscriber and a certificate-using application. A certification path (or certification chain) refers to a sequence of one or more connected nodes between the subscriber and a root CA. The root CA, in turn, is a CA that the certificate-using application trusts and has securely imported and stored its public key certificate.

In the following sections, we overview some public key cryptosystems that are in widespread use today. The notion of a PKI will be further addressed in Chapter 19.

5.4.1 RSA

The most widely used public key cryptosystem is RSA, invented by Ronald L. Rivest, Adi Shamir, and Len M. Adleman at MIT in 1977 [26]. The RSA cryptosystem gets its security from the difficulty and intractability of the integer factorization problem. What this means is that it is fairly simple to multiply two large prime numbers, but difficult to compute the prime factors of a large number. One of the nice properties of RSA is that the same algorithm can be used for both message encryption and decryption, as well as digital signature generation and verification. This is not the case for most other public key cryptosystems.

Mathematically spoken, the RSA public key cryptosystem requires two distinct large primes (p and q). Denote n = pq and φ(n) = (p−1)(q−1), where φ refers to the Euler function. Each user chooses a large number d > 1 such that (d, φ(n)) = 1 and computes the number e (1 < e < φ(n)) that satisfies the congruence ed ≍ 1 (mod φ(n)). The numbers n and e constitute the public key, whereas the remaining items p, q, φ(n), and d form the private information. More commonly, d is referred to as the private key. Against this background, message encryption and decryption work as follows:

To encrypt, one raises the plaintext block P to the power of e and reduces modulo n: C = P^e (modφ(n));
To decrypt, one raises the ciphertext block C to the power of d and reduces modulo n: P = C^d (modφ(n)).

Digital signature generation and verification uses the same algorithms with different keys (the private key is used to digitally sign a message, whereas the public key is used to verify the signature).

The RSA public key cryptosystem was protected by U.S. Patent No. 4,405,829 "Cryptographic Communications System and Method," issued and granted to MIT on September 20, 1983. The patent expired on September 20, 2000.

5.4.2 Diffie-Hellman

In 1977, Whitfield Diffie and Martin Hellman proposed a key agreement protocol that allows participants to agree on a key over an insecure public channel [21]. The protocol gets its security from the difficulty and intractability of the discrete logarithm problem in a finite cyclic group, such as the multiplicative group of a finite field. What this basically means is that, in general, the inverse operation of the exponentiation function is the logarithm function. There are efficient algorithms for computing logarithms in many groups; however, one does not know a polynomial-time algorithm for computing discrete logarithms in cyclic groups. For example, for a very large prime number p and two smaller numbers y and a, it is computationally intractable to find an x that satisfies the equation y = a^x mod p.

Mathematically speaking, the Diffie-Hellman key agreement protocol requires a finite cyclic group G of order | G | and generator a. To agree on a session key, A and B then secretly choose elements x_A and x_B in G. These elements represent A and B's private keys. A and B compute their public keys y_A = a^xA and y_B = a^xB, and exchange these public keys over an unsecured public channel. Finally, A and B compute K_AB = y^xA_B = a^xBxA and K_BA = y^xB_A = a^xAxB. Note that K_AB = K_BA, so this value can actually be used as a session key to secure communications between A and B.

The Diffie-Hellman key agreement protocol was protected by U.S. Patent No. 4,200,770, "Cryptographic Apparatus and Method," issued and granted to Stanford University on April 29, 1980. The patent expired in 1997.

5.4.3 ElGamal

In the early 1980s, Taher ElGamal adapted the Diffie-Hellman key agreement protocol and came up with a public key cryptosystem that can be used for data encryption and digital signatures [27, 28]. Contrary to RSA, however, the ElGamal algorithms for data encryption and decryption are different from the the ElGamal algorithms for digital signature generation and verification. This is no serious drawback but is not advantageous from an implementor's point of view.

Unlike many other public key cryptosystems, the ElGamal public key cryptosystem is not covered by any patents.

5.4.4 DSS

In the early 1990s, the U.S. NIST published the Digital Signature Standard (DSS) as a viable alternative to RSA signature schemes. The DSS refers to an optimized modification of the ElGamal cryptosystem that can be used only for digital signature generation and verification [29].

5.4.5 ECC

More recently, the use of elliptic curve cryptography (ECC) has attracted a lot of interest. ECC-based public key cryptosystems obtain their security from the difficulty and intractability of the elliptic curve discrete logarithm problem (that uses groups of points on elliptic curves). As illustrated in Table 5.2, a number of different types of cryptography have been defined over elliptic curves. The resulting ECC-based public key cryptosystems seem to be advantageous with regard to their security properties (meaning that smaller keys are required for a similar level of security). As such, they are particularly useful in situations where small keys are required (e.g., mobile and wireless applications).

Table 5.2: ECC-Based Public Key Cryptosystems
Acronym	Text

ECDH	Elliptic curve Diffie-Hellman key agreement
ECDSA	Elliptic curve digital signature algorithm
ECES	Elliptic curve encryption scheme
ECMQV	Elliptic curve MQV key agreement
ECNRA	Elliptic curve Nyberg-Rueppel signature scheme with appendix

Unlike RSA, the general category of ECC is not patented. Individual companies, however, have filed patents for specific efficiency or security algorithms that are related to ECC. Most important, the Certicom Corporation^[5] holds several patents in this field.

^[4]Note that X.509 does not embody a hierarchic trust model. The existence of cross-certificates, as well as forward and reverse certificates, makes the X.509 model a mesh, analogous in some ways to PGP's web of trust. The X.509 model is often erroneously characterized as a hierarchic trust model because it is usually mapped to the directory information tree (DIT), which is hierarchic, more like name schemes.

^[5]http://www.certicom.com

Team-Fly