Cryptography: Theory and Practice:Key Distribution and Key Agreement

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

8.4.3 Key Agreement Using Self-certifying Keys

In this section, we describe a method of key agreement, due to Girault, that does not require certificates. The value of a public key and the identity of its owner implicitly authenticate each other.

The Girault Scheme combines features of RSA and discrete logarithms. Suppose n = pq, where p = 2p₁ + 1, q = 2q₁ + 1, and p, q, p₁, and q1 are all large primes. The multiplicative group isomorphic to . The maximum order of any element in is therefore the least common multiple of p - 1 and q - 1, or 2p₁q₁. Let α be an element of order 2p₁q₁. Then the cyclic subgroup of generated by α is a suitable setting for the Discrete Logarithm problem.

In the Girault Scheme, the factorization of n is known only to the TA. The values n and α are public, but p, q, p₁, and q₁ are all secret. The TA chooses a public RSA encryption exponent, which we will denote by e. The corresponding decryption exponent, d, is secret (recall that d = e^–1 mod ø (n)).

Each user U has an ID string ID(U), as in previous schemes. A user U obtains a self-certifying public key, p_U, from the TA as indicated in Figure 8.8. Observe that U needs the help of the TA to produce p_U. Note also that

can be computed from p_U and ID(U) using publicly available information.

The Girault Key Agreement Protocol is presented in Figure 8.9. The information transmitted during the protocol is depicted as follows:

Figure 8.8 Obtaining a self-certifying public key from the TA

At the end of the protocol, U and V each have computed the key

Here is an example of key exchange using the Girault Scheme.

Example 8.4

Suppose p = 839 and q = 863. Then n = 724057 and ø(n) = 722356. The element α = 5 has order 2p₁q₁ = ø(n)/2. Suppose the TA chooses d = 125777 as the RSA decryption exponent; then e = 84453.

Suppose U has ID(U) = 500021 and a_U = 111899. Then b_U = 488889 and p_U = 650704. Suppose also that V has ID(V) = 500022 and a_V = 123456. Then b_V = 111692 and p_V = 683556.

Now, U and V want to exchange a key. Suppose U chooses r_U = 56381, which means that s_U = 171007. Further, suppose V chooses r_V = 356935, which means that s_V = 320688.

Then both U and V will compute the same key K = 42869.

Let’s consider how the self-certifying keys guard against one specific type of attack. Since the values b_U, p_U, and ID(U) are not signed by the TA, there is no way for anyone else to verify their authenticity directly. Suppose this information is forged by W (i.e., it is not produced in cooperation with the TA), who wants to masquerade as U. If W starts with ID(U) and a fake value , then there is no way for her to compute the exponent corresponding if the Discrete Log problem is intractible. Without computation cannot be performed by W (who is pretending to be U).

Figure 8.9 Girault Key Agreement Protocol

The situation is similar if W acts as an intruder-in-the-middle. W will be able to prevent U and V from computing a common key, but W is unable to duplicate the computations of either U or V. Thus the scheme provides implicit key authentication, as did the MTI protocol.

An attentive reader might wonder why U is required to supply the value a_U to the TA. Indeed, the TA can compute p_U directly from b_U, without knowing a_U. Actually, the important thing here is that the TA should be convinced that U knows the value of a_U before the TA computes p_U for U.

We illustrate this point by showing how the scheme can be attacked if the TA indiscriminately issues public keys p_U to users without first checking that they possess the value a_U corresponding to their b_U. Suppose W chooses a fake value and computes the corresponding value

Here is how he can determine the corresponding public key

W will compute

and then given and ID(W) to the TA. Suppose the TA issues the public key

to W. Using the fact that

it is immediate that

Now, at some later time, suppose U and V execute the protocol, and W substitutes information as follows:

Now V will compute the key

whereas U will compute the key

W can compute K′ as

Thus W and V share a key, but V thinks he is sharing a key with U. So W will be able to decrypt messages sent by V to U.

8.5 Notes and References

Blom presented his key predistribution scheme in [BL85]. Generalizations can be found in Blundo et al. [BDSHKVY93] and Beimel and Chor [BC94].

Diffie and Hellman presented their key exchange algorithm in [DH76]. The idea of key exchange was discovered independently by Merkle [ME78]. The material on authenticated key exchange is taken from Diffie, van Oorschot, and Wiener [DVW92].

Version V of Kerberos is described in [KN93]. For a recent descriptive article on Kerberos, see Schiller [SC94].

The protocols of Matsumoto, Takashima, and Imai can be found in [MTI86]. Self-certifying key distribution was introduced by Girault [GIR91]. The scheme he presented was actually a key predistribution scheme; the modification to a key agreement scheme is based on [RV94].

Table of Contents