Two recent surveys on key distribution and key agreement are Rueppel and Van Oorschot [RV94] and van Tilburg [VT93].

Exercises

8.1  Suppose the Blom Scheme with k = 1 is implemented for a set of four users, U, V, W and X. Suppose that p = 7873, r_U = 2365, r_V 6648, r_W = 1837 and r_X = 2186. The secret g polynomials are as follows:

(a)  Compute the key for each pair of users, verifying that each pair of users obtains a common key (that is, K_U,V = K_V,U, etc.).

(b)  Show how W and X together can compute K_U,V.

8.2  Suppose the Blom Scheme with k = 2 is implemented for a set of five users, U, V, W, X and Y. Suppose that p = 97, r_U = 14, r_V = 38, r_W = 92, r_X = 69 and r_Y = 70. The secret g polynomials are as follows:

(a)  Show how U and V each will compute the key K_U,V = K_V,U.

(b)  Show how W, X and Y together can compute K_U,V.

8.3  Suppose that U and V carry out the Diffie-Hellman Key Exchange with p = 27001 and α = 101. Suppose that U chooses a_U = 21768 and V chooses a_V 9898. Show the computations performed by both U and V, and determine the key that they will compute.

8.4  Suppose that U and V carry out the MTI Protocol where p = 30113 and α = 52. Suppose that U has a_U = 8642 and chooses r_U = 28654, and V has a_V = 24673 and chooses r_V = 12385. Show the computations performed by both U and V, and determine the key that they will compute.

8.5  If a passive adversary tries to compute the key K constructed by U and V by using the MTI protocol, then he is faced with an instance of what we might term the MTI problem, which we present in Figure 8.10. Prove that any algorithm that can be used to solve the MTI problem can be used to solve the Diffie-Hellman problem, and vice versa.

8.6  Consider the Girault Scheme where p = 167, q = 179, and hence n = 29893. Suppose α = 2 and e = 11101.

(a)  Compute d.

(b)  Given that ID(U) = 10021 and a_U = 9843, compute b_U and p_U. Given that ID(V) = 10022 and a_V = 7692, compute b_V and p_V.

(c)  Show how b_U can be computed from p_U and ID(U) using the public exponent e. Similarly, show how b_V can be computed from p_V and ID(V).

Figure 8.10  The MTI problem

(d)  Suppose that U chooses r_U = 15556 and V chooses r_V = 6420. Compute s_U and s_V, and show how U and V each compute their common key.