The Theory of Cryptography

This chapter is from the book 

10.3 Public-Key Cryptography

Public-key cryptography emerged in the mid-1970s with the work published by Whitfield Diffie and Martin Hellman.² The concept is simple and elegant yet has had a huge impact on the science of cryptography and its application. Public-key cryptography is based on the notion that encryption keys are related pairs, private and public. The private key remains concealed by the key owner; the public key is freely disseminated to various partners. Data encrypted using the public key can be decrypted only by using the associated private key and vice versa. Because the key used to encrypt plaintext is different from the key used to decrypt the corresponding ciphertext, public-key cryptography is also known as asymmetric cryptography.

The premise behind public-key cryptography is that it should be computationally infeasible to obtain the private key by simply knowing the public key. Toward achieving this premise, modern public-key cryptography derives from sophisticated mathematical foundations based on the one-way functions existing in the abstractions of number theory.

A one-way function is an invertible function that is easy to compute but computationally difficult to invert. A one-way trapdoor function is a one-way function that can be easily inverted only if one knows a secret piece of information, known as the trapdoor. Encryption is the easy one-way trapdoor function; its inverse, decryption, is the difficult direction. Only with knowledge of the trapdoor—the private key—is decryption as easy as encryption. Two of these currently known one-way functions, factoring large numbers and computing discrete logarithms, form the basis of modern public-key cryptography. Factoring large numbers is a one-way trapdoor function, whereas computing discrete logarithms is a one-way function with no trapdoors.

10.3.1 Algorithms and Techniques

This section examines the most common cryptographic algorithms that are based on the use of a public- and private-key pair.

10.3.1.1 RSA

The most famous of the well-known trapdoor one-way functions is based on the ease of multiplying two large prime numbers; the reverse process, factoring a very large number, is far more complex. This consideration is at the basis of Rivest-Shamir-Adleman (RSA), certainly the most widely used public-key encryption algorithm.

Basic RSA Concepts

A prime number, by definition, is an integer that has no positive divisors other than 1 and itself. A nonprime integer is called composite. Two integers a ≥ 1 and b ≥ 2 are said to be relatively prime if their greatest common divisor GCD(a, b) is 1. The number of elements in the set

• {a ∊ Z : 1 ≤ a < b, GCD(a, b) = 1}

where Z is the set of all integers, is often denoted by f(b). The function f is called the Euler phi-function.

Every integer b ≥ 2 can be factored as a product of powers of primes in a unique way. For example, 60 = 2² × 3 × 5. Factoring large numbers—numbers that expressed in binary format take 1,024 bits or more—is known to be computationally infeasible with current computing technology. Consequently, the one-way trapdoor problem is to make a very large number a public knowledge and secretly maintain its prime factors. With this in mind, we can now summarize the widely adopted RSA public-key algorithm.

How the RSA Algorithm Works

In simple terms, the RSA algorithm centers on three integer numbers: the public exponent, e; the private exponent, d; and the modulus, n. The modulus is obtained as the product of two distinct, randomly picked, very large primes, p and q. A well-known result from number theory implies that f(n) = (p − 1)(q − 1). The two numbers e and d are characterized by the fact that they are greater than 1 and smaller than f(n). In addition, e must be relatively prime with f(n), and it must also be de = 1 (mod f(n)), which means that d and e are the multiplicative inverse of the other modulo f(n). The pair (e, n) is the RSA public key, whereas the pair (d, n) is the RSA private key.

A block of plaintext P whose numerical equivalent is less than the modulus is converted into a ciphertext block by the formula P^e (mod n). Conversely, a ciphertext block C is converted back to its corresponding plaintext representation by the formula C^d (mod n). These two formulas are the inverse of the other. Therefore, whatever is encrypted with the public key can be decrypted only with the corresponding private key; conversely, whatever is encrypted with the private key can be decrypted only with the corresponding public key.

To better understand how RSA works, let us consider an example involving small numbers. We randomly pick two prime numbers, p = 7 and q = 11. This implies that n = p∊×q = 77 and f(n) = (p − 1)(q − 1) = 60. A valid choice for the public exponent is e = 13. By solving the equation 13d = 1 (mod 60), we get d = 37. Therefore, the RSA public key in this case is the pair (13, 77), and the corresponding RSA private key is the pair (37, 77). Let us now consider the plaintext message P = 9. By encrypting it with the RSA public key, we obtain the ciphertext message C = 9¹³ (mod 77) = 58. To decrypt this message, we have to apply the RSA private key and compute 58³⁷ (mod 77) = 9, which yields the original plaintext P.

To encrypt or decrypt a message, the RSA algorithm uniquely represents a block of data in either a plaintext or ciphertext form as a very large number, which is then raised to a large power. Note here that the length of the block is appropriately sized so that the number representing the block is less than the modulus. Computing such exponentiations would be very time consuming were it not for an eloquent property that the operation of exponentiation in modular arithmetic exhibits. This property is known as the modular exponentiation by the repeated squaring method.

Note that the one-way trapdoor function discussed in this section requires deciding on whether a randomly picked very large integer is prime. Primality testing, however, is a much easier task than factorization. Several methods have been devised to determine the primality of an odd number p, the most trivial of which is to run through the odd numbers starting with 3 and determine whether any of such numbers divides p. The process should terminate when the square root of p, , is reached, because if p is not a prime, the smallest of its nontrivial factors must be less than or equal to . Owing to the time complexity that it requires, in practice this procedure is stopped much earlier before reaching and is used as a first step in a series of more complicated, but faster, primality test methods.

Security Considerations

Breaking the RSA algorithm is conjectured to be equivalent to factoring the product of two large prime numbers. The reason is that one has to extract the modulus n from the public-key value and proceed to factor it as the product of the two primes p and q. Knowing p and q, it would be easy to compute f(n) = (p − 1)(q − 1), and the private key (d, n) could then be obtained by solving the equation de = 1 (mod f(n)) for the unknown d. With the complexity of the fastest known factoring algorithm being in the order of |n|, where |n| is the total number of the binary bits in the modulus n, this roughly means that, for example, every additional 10 bits make the modulus ten times more difficult to factor. Given the state of factoring numbers, it is believed that keys with 2,048 bits are secure into the future. The fastest known factoring algorithm to date is the number field sieve.

10.3.1.2 Diffie-Hellman

The Diffie-Hellman (DH) key-agreement algorithm is an elegant procedure for use by two entities establishing a secret cryptographic key over a public network without the risk of exposing or physically exchanging it. Indeed, DH presents a critical solution to the secret-key distribution problem. The security of the algorithm relates to the one-way function found in the discrete logarithm problem.

Basic DH Concepts

Let q be a prime number. An integer α is called a primitive root, or base generator of q, if the numbers α (mod q), α² (mod q), ... , α^q-1 (mod q) are distinct and consist of the integers from 1 to q – 1 in some permutations. For any integer y and a primitive root α of the prime number q, one can find a unique integer exponent x such that y = α^x (mod q). The exponent x is referred to as the discrete logarithm of y for the base α modulo q. This is a one-way function. In fact, computing y from x using this function is easy; for q about 1,000 bits long, this would take only a few thousand multiplications. However, the inverse function, x = log_α y (mod q), which yields x from y, is computationally infeasible, as far as anyone knows; Diffie proved that with q still about 1,000 bits long and the best known algorithm, the discrete logarithm would take approximately 10³⁰ operations.

How the DH Algorithm Works

The mathematics encompassed in the DH key-agreement algorithm is fairly simple. Let q and α be as explained previously. These two numbers are publicly available. Suppose that Alice and Bob want to agree on a secret key. Alice generates as her private key a secret random number x_A such that 1 ≤ x_A < q and publishes the corresponding public key

Similarly, Bob generates as his private key a secret random number x_B such that 1 ≤ x_B < q and publishes the corresponding public key

The secret key for Alice and Bob is

Alice can obtain this key by getting y_B from a public directory and then computing

Bob computes the same secret key in a similar way.

One problem in the algorithm that we have just described consists of finding a primitive root α of a given prime number q. The definition of primitive root does not help from a computational point of view, because it requires computing q – 1 powers in the worst case for every attempt to find a primitive root. However, a known algebraic theorem proves that an integer α is a primitive root of 9 if αⁱ ≠ 1 for any integer i ∊ {1, ..., q – }such that i is a divisor of q – 1. Therefore, the problem is reduced to factoring q – 1 and testing that αⁱ ≠ 1, where this time i varies only in the set of the divisors of q – 1. Unfortunately, as we discussed in Section 10.3.1.1 on page 360, factoring a large number is computationally infeasible too. In fact, this is exactly the one-way trapdoor function on which the security of the RSA algorithm relies. However, a solution to this problem for the DH algorithm consists of generating q – 1 before generating q itself. In other words, it is possible to generate q – 1 as the product of known primes—in which case, the factorization of q – 1 is known in advance—and subsequently test q for primality. As discussed in Section 10.3.1.1 on page 360, primality testing is a much easier task than factorization. An advantage of this algorithm is that its security does not depend on the secrecy of q and α. Once a pair of integers (q, α) has been found that satisfies the requirements described previously, the same pair can be published—in cryptography books, for example—and reused by algorithm implementors.

Security Considerations

With the algorithm described, Alice and Bob do not have to physically exchange keys over unsecure networks, because they can compute the same secret key independently of each other. An attacker would have to compute K_AB from the only public information available, y_A and y_B. No way to do this is known other than computing the discrete logarithm of y_A and y_B to find x_A and x_B, an operation that, as we said, is conjectured to be computationally infeasible even with the fastest known algorithm.

In order for Bob and Alice to be able to compute the same secret key independently of each other, they have to know each other's public keys. A general security problem that arises at this point is how to ascertain that the public key of an entity belongs to that entity. The DH algorithm does not offer a direct solution to this problem. However, we will see how to solve this problem in Section 10.3.4 on page 372.

10.3.1.3 Elliptic Curve

Recently, elliptic curves over finite fields have been proposed as another source of one-way trapdoor functions for use with existing public-key cryptographic systems.

Basic Elliptic-Curve Concepts

An elliptic curve in the plane x, y is the union of the singleton {O} with the set of the points (x, y) of the plane satisfying an equation of the form

• y² + axy + by = x³ + cx² + dx + e

where a, b, c, d, and e are real numbers, and x and y take on values in the real numbers. The element O is called point at infinity. For our purpose, it is sufficient to consider equations of the form

• y² = x³ ax + b

Figure 10.16 shows the elliptic curve with equation y² = x³ − x.

Figure 10.16. An Elliptic Curve

A form of addition can be defined over the set of points of an elliptic curve by imposing that if any three points on an elliptic curve lie on a straight line, their sum is O. The operation of addition for an elliptic curve, indicated with the symbol +, is constructed on the following rules.

1. The point at infinity, O, is the additive identity. This means that O = –O, and for any point P on the elliptic curve, P + O = O + P = P.

2. A vertical line meets the elliptic curve at two points with the same coordinates, say P₁ = (x, y) and P₂ = (x, −y). The vertical line also meets the curve at its infinity point, O. This implies that P₁ + P₂ + O = O, and P₁ = −P₂. Therefore, the negative of a point is a point with the same x coordinate but negative y coordinate. This construction is illustrated in Figure 10.17.

   Figure 10.17. The Addition Operation on an Elliptic Curve

3. If Q and R are two points with different x coordinates, draw a straight line between them and find the third point of intersection P₁. It is easily seen that P₁ exists and is unique, unless the line is tangent to the curve at either Q or R, in which case we take P₁ = Q or P₁ = R, respectively. Because P₁, Q, and R lie on the same straight line, it must be Q + R + P₁ = O, which implies Q + R = –P₁. This construction is illustrated in Figure 10.17.

4. To double a point Q, draw the tangent line in Q and find the other point of intersection S. Then Q + Q = 2Q = –S. This construction is illustrated in Figure 10.17.

Figure 10.17 shows how to perform the addition operation on the elliptic curve y² = x³ – x. It can be shown that if 4a³ + 27b² ≠ 0, the operation of addition constructed on rules 1–4 has the following properties.

• It is well defined. Given any two points P and Q on an elliptic curve, their sum P + Q is still a point on the same elliptic curve.

• It is associative. Given any three points P, Q, and R on an elliptic curve, (P + Q) + R = P + (Q + R).

• It is commutative. Given any two points P and Q on an elliptic curve, P + Q = Q + P.

• It possesses a unity element. Rule 1 establishes that the unity element for the operation of addtion is the point at infinity, O.

• Every point on the elliptic curve has an inverse. Given any point P on an elliptic curve, rules 1 and 2 show how to construct its inverse, –P.

These properties can be summarized by saying that the set of the points of an elliptic curve, coupled with the operation of addition that we have just defined, is an abelian group. Multiplication of a point P on an elliptic curve by a positive integer k is defined as the sum of k copies of P. Thus 2P = P + P, 3P = P + P + P, and so on.

An elliptic curve can be defined on a finite field as well. Let p > 3 be a prime number. The elliptic curve y² = x³ + ax + b over Z_p is the set of solutions (x, y) ∊ Z_p × Z_p to the congruence y² = x³ + ax + b (mod p), where a, b ∊ Z_p are constants such that 4a³ + 27b² ≠ Α (mod p), together with a special point O, called the point at infinity. Addition of two points on an elliptic curve and multiplication of a point for an integer are defined in a way that is similar to elliptic curves over real numbers.

Note that the equation of an elliptic curve over the finite field Z_p is defined as for real numbers. The only difference is that an elliptic curve Z_p is not continuous. Rather, the points that belong in the curve are only the pairs of non-negative integers in the quadrant from (0, 0) to (p, p) that satisfy the equation modulo p.

Given an integer k < p and the equation Q = kP, where P and Q are two points on an elliptic curve E over the finite field Z_p, the one-way function here consists of the easy operation of computing Q given k and P. The inverse problem of finding k given P and Q is similar to the discrete logarithm problem and is, in practice, intractable.

The Elliptic-Curve Algorithm

One straightforward application of the one-way function to DH is for two entities Alice and Bob to publicly agree on a point P on an elliptic curve E over a finite field Z_p, where p is a very large prime number (P ≈ 2¹⁸⁰). The criterion in selecting P is that the smallest integer value of n for which np = O be a very large prime number . The point P is known as the generator point. The elliptic curve and the generator point are parameters of the cryptosystem known to all the participants.

To generate the key, the initiating entity, Alice, picks a random large integer a < n, computes aP over E, and sends it to the entity Bob. The integer a is Alice's private key, whereas the point aP is her public key. Bob performs a similar computation with a random large number b and sends entity Alice the result of bP. The integer b is Bob's private key, whereas the point bP is his public key. Both entities then compute the secret key K = abP, which is still a point over E.

Security Considerations

Given an elliptic curve E on a finite field Z_p, where p is a very large prime number, the security of elliptic-curve cryptography depends on how difficult it is to determine the integer k given a point P on the curve and its multiple kP. The fastest known technique for taking the elliptic-curve logarithm is known as the Pollard rho method. With this algorithm, a considerably smaller key size can be used for elliptic-curve cryptography compared to RSA. Furthermore, it has been shown that for equal key size, the computational effort required for elliptic-curve cryptography and RSA is comparable. Therefore, there is a computational advantage to using elliptic-curve cryptography with a shorter key length than a comparably secure RSA.

10.3.2 Public-Key Security Attributes

This section examines the security implications of using public-key cryptography. Generally speaking, the strength of each algorithm is directly related to the type of the one-way function being used and the length of the cryptographic keys. Inverting the one-way functions we have discussed, namely, factoring a very large number and computing the discrete logarithm, is known to be practically infeasible within the computing means and the theoretic knowledge available today.

10.3.2.1 Confidentiality

The premise of the privacy service here is achieved by encrypting data, using the recipient's public key, and the fact that decryption can be done only by using the recipient's private key. For example, if Alice needs to send a confidential message to Bob, she can encrypt it with Bob's public key, knowing that only Bob will be able to decrypt the ciphertext with his private key (see Figure 10.18).

Figure 10.18. Public-Key Scenario

Thus, only the recipient with knowledge of the private key is able to decrypt the enciphered data. It is worth noting that a privacy service strongly depends on the assurance that a public key is valid and legitimately belongs to the recipient.

One confidentiality problem that needs to be addressed by public-key encryption is the fact that in some cases, the plaintext corresponding to a given ciphertext can be easily understood. As an example, we consider the scenario in which Alice is a stock client and Bob a stockbroker, as shown in Figure 10.19.

Figure 10.19. Scenario Requiring Message Randomization

Typically, Alice's messages are all likely to be of the type "Buy" or "Sell." Knowing this, an attacker could build a table mapping ciphertexts to plaintexts. This would break the confidentiality of the transmission. Even worse, the attacker could impersonate Alice and replace the ciphertext corresponding to "Buy" with the ciphertext corresponding to "Sell" and vice versa (see Figure 10.20).

Figure 10.20. Message Randomization

This problem can be solved by randomizing the message. Before encrypting the plaintext message "Buy" or "Sell," the message-randomizing algorithm on Alice's side inserts a meaningless sequence of bits, which is randomly generated. As the ciphertext depends on the entire plaintext message, the ciphertexts produced by Alice are no longer recognizable. In addition, message randomization reduces the risks of message-prediction-and-replay-attacks (see footnote 6 on page 150).

10.3.2.2 Data Integrity, Data-Origin Authentication, and Nonrepudiation

As we said in Section 10.3.2.1 on page 367, privacy is provided by encrypting data, using a publicly available key, typically the recipient's public key. However, an eavesdropper may intercept the data, substitute new data, and encrypt it using the same public key. Simply applying a public-key algorithm to achieve privacy does not guarantee data integrity; nor does it guarantee data-origin authentication. In practice, digital signatures are the preferred method of achieving data integrity and data-origin authenticity. Another service that is inherently offered through digital signatures is nonrepudiation.

10.3.3 Digital Signatures

The use of public-key cryptography combined with one-way hash functions enables the digital signing of documents. This process inherently enables data integrity and data-origin authentication and has the potential to withstand repudiation. In fact, using the private key of a public- and private-key pair to encrypt a data stream automatically binds the subject—a person or an entity—with the encrypted data.

The cost of encrypting an entire document in order to simply establish this binding can be prohibitive. Fortunately, digital signing of a document is a computationally affordable alternative, as it does not require encrypting the entire document.

If confidentiality is a requirement, the message originator, Alice, encrypts the message only once, with the public key of the receiver, Bob, thereby guaranteeing confidentiality, because the ciphertext can be decrypted only with the Bob's private key. However, data integrity, data-origin authentication, and nonrepudiation are not guaranteed, because anybody could have used Bob's public key to encrypt a different message, pretending that it was sent by Alice. To resolve this ambiguity, Alice attaches a digital signature to the encrypted message. The digital signature is obtained by applying a mathematical function to the plaintext message. This mathematical function depends on Alice's private key.

An eavesdropper who attempted to replace the transmitted data with new data could still encrypt the new data with Bob's public key but would not be able to use Alice's private key to generate Alice's digital signature. Once he receives the encrypted message and the digital signature, Bob decrypts the ciphertext with his own private key. Finally, he uses Alice's public key to verify Alice's digital signature. If the digital signature verifies, Bob knows that the original message has been sent by Alice and has not been compromised during transmission. Because Alice's private key has been used to compute the digital signature, this entire process guarantees data integrity, data-origin authentication, and nonrepudiation (see Figure 10.21).

Figure 10.21. Digital-Signature Scenario

With the fundamental premise that the private key remains in the confines of its owner, verifying a digital signature using the associated public key certainly leaves no possibility for the originator to deny involvement. Denial, however, can always take place on the basis that a private key has been compromised. A strong nonrepudiation service never exposes the private keys it manages, even to the owner. Tamper-proof hardware modules for private keys become necessary for a legally binding nonrepudiation service.

If a confidentiality service is not needed, Alice can transmit the signed document to Bob in its cleartext form. The signature is provided to Bob for data-integrity verification, data-origin authentication, and nonrepudiation purposes.

The most well-known digital signature algorithms are RSA and Digital Signature Algorithm (DSA). These algorithms are discussed in the next two subsections.

10.3.3.1 RSA Signature

The RSA digital-signature algorithm proceeds along two main steps, as shown in Figure 10.22.

1. Using one of the common hashing algorithms, such as MD5 or SHA-1, a document is first digested into a much smaller representation: its hash value.

2. The hash value of the document, rather than the entire document itself, is then encrypted with the private key of the originator.

Figure 10.22. The Process of Computing a Message's RSA Digital Signature

If confidentiality is needed, the document itself must be encrypted, as explained in Section 10.3.2.2 on page 369.

10.3.3.2 DSA Signature

Other types of digital signatures rely on algorithms designed solely for signing but not encrypting. In other words, the digital signature is still obtained by encrypting the hash value of a document with the originator's private key, but the public and private key pair here can be used only for digital signing, not for encrypting arbitrary-size messages.

An example of this class of algorithms is the standard DSA, which computes a signature over an arbitrary-size input, using SHA-1 as a message digest, five public parameters, and a private key. DSA signatures have better performance characteristics than RSA does.

10.3.4 Digital Certificates

As we mention in Section 10.3.5 on page 375, authenticating the identity of a sending entity and protecting data to allow only authenticated and authorized receivers to view that data is an extremely important security requirement, especially for the exchange of security-sensitive data or when the nature of the transaction requires data-origin authentication and nonrepudiation. Encrypting a message with the receiver's public key guarantees confidentiality, whereas digitally signing a message by encrypting its hash value with the originator's public key guarantees data-origin authentication and nonrepudiation.

These scenarios are very attractive, but for them to work, it is necessary to have a means to bind a public- and private-key pair to its owner. To understand why, let us consider the following scenario. Alice wants to send Bob a confidential message in a secure manner over a public network. To do so, she needs to encrypt the message with Bob's public key. For sure, only Bob will be able to read the message once it is transmitted, because the message's ciphertext can be decrypted only with Bob's private key. However, how can Alice be sure that Bob is really Bob? Owning a public- and private-key pair does not give any assurance about the real identity of a person. Similarly, Bob may receive a signed message from Alice, and he can verify the digital signature's authenticity by decrypting it with Alice's public key, but how can he be sure that the entity that signed the message declaring to be Alice is really Alice?

A solution to this problem is to use digital certificates, which can be used to exchange public keys and to verify an entity's identity. An entity's digital certificate is a binary file that contains the entity's public key and Distinguished Name (DN), which uniquely identifies that entity, along with other pieces of information, such as the start and expiration dates of the certificate and the certificate's serial number (see Figure 10.23).

Figure 10.23. Information Contained in a Digital Certificate

The international standard for public-key certificates is called X.509 (see Appendix B on page 553). This standard has evolved over time, and the latest version is V3. The most significant enhancement in X.509 V3 is the ability to add other, arbitrary data in addition to the basic name, address, and organization identity fields of the DN. This is useful when constructing certificates for specific purposes. For example, a certificate could include a bank account number or credit card information.

Digital certificates are released by trusted third-party registry organizations called Certificate Authorities. These CAs are public organizations that are trusted by both the sender and the receiver participating in a secure communication. An entity, Alice, can receive her own certificate by generating a public- and private-key pair and by transmitting the public key along with a certificate request and proof of ownership of the public key to a CA. For serious applications, Alice can obtain a certificate only by applying in person and showing evidence of her identity. If Alice's request for a certificate is accepted, the CA wraps Alice's public key in a certificate and signs it with its own private key.

Alice can now convey her public key information to other entities by transmitting her certificate. A receiving entity, Bob, can verify the certificate's authenticity by verifying the CA's digital signature. This can be done without even contacting the CA, because CAs' public keys are available in all the most common client and server applications, such as Web browsers, Web servers, and other programs that require security. If the signature is verified, Bob is assured that the certificate really belongs to Alice. From this moment on, when he receives a message digitally signed by Alice, he knows that it is really Alice who signed it and transmitted it—data-origin authentication—and Alice will not be able to deny that the message originated from her—nonrepudiation. Similarly, by accessing Bob's certificate from a CA and by encrypting a message with Bob's public key, Alice is assured that only Bob, and no other person, will be able to decrypt the message—confidentiality.

As Figure 10.23 shows, certificates contain start and end dates. The validity of a certificate should not be too long, to minimize the risks associating with having inadvertently exposed the associated private key and to make sure that the current key strength still makes it computationally infeasible to compute the private key from the public key. If the private key associated with the public key in a certificate gets inadvertently exposed, a certificate's owner should make an immediate request for suspending the certificate's validity. In this case, the CA will add an entry for that certificate in its certificate revocation list. A CRL also enumerates those certificates that have been revoked because their owners failed to comply with specific requirements. A CRL should always include data explaining why a certificate was suspended or revoked.

In the scenario that we have described in this section, there is only one CA that the sender and the receiver participating in a secure communication use to verify each other's public key's authenticity. In real-life situations, there are chains of CAs, whereby each successive CA verifies and vouches for the public key of the next identity in the chain. In this case, a public-key certificate embodies a chain of trust. Consider the situation shown in Figure 10.24.

Figure 10.24. Certificate Hierarchy

A system has received a request containing a chain of certificates, each of which is signed by the next higher CA in the chain. The system has also a collection of root certificates from trusted CAs. The system can then match the top of the chain in the request with one of these root certificates, say, Ham's. If the chain of signatures is intact, the receiver can infer that Nimrod is trustworthy and has inherited the trustworthiness from Ham. Note that one of the implications of a certificate chain is that the certificate at the top of the chain is self-signed.

10.3.5 Key Distribution

In public-key cryptography, an entity's private key never has to be exposed, whereas the corresponding public key is made publicly available. This makes it possible to obtain confidentiality, nonrepudiation, data-origin authentication, and data integrity without having to distribute the secret key. The main problem of public-key cryptography is that it is computationally expensive. Conversely, secret-key cryptography, described in Section 10.2 on page 346, offers better performance and scales well for Kerberos and distributed computing environment (DCE) security, even though its limitation lies in the fact that it becomes necessary to share the secret key across unsecure networks.

Combining public-key and secret-key cryptography yields the performance advantages of secret-key cryptography and the security enhancements of public-key cryptography, as shown in Figure 10.25. One algorithm that combines public-key and secret-key cryptography is DH (see Section 10.3.1.2 on page 362), which allows two parties to independently compute the same secret key. To do this, each entity uses its own private key and the other entity's public key. With Diffie-Helmann, the shared secret key is mathematically computed by the two parties, and there is no need to physically exchange it over the network.

Figure 10.25. Combining Public-Key and Secret-Key Cryptography

Another way to use public-key cryptography for secure secret-key establishment over a public network is, essentially, to consider the secret key as the data that needs to be distributed with a privacy requirement. Thus, the secret key is encrypted using the public key of the target entity. The receiving entity uses its private key to decrypt the enciphered secret key and hence has established a common secret key with the sending entity. This is, for example, the approach used by the SSL and TLS protocols (see Section 13.1 on page 449). Other protocols that combine secret- and public-key cryptography are IPSec and S/MIME (see Section 12.2 on page 439).

Note that authenticating the identity of the sending entity is a strong security requirement. A breach in such a key-establishment mechanism risks exposing the entire cryptographic channel that follows key establishment.