# 15.9 Exercises

1. In a network of three users, A, B, and C, we would like to use the Blom scheme to establish session keys between pairs of users. Let  and let



Suppose Trent chooses the numbers



Calculate the session keys.

1. Show that in the Blom scheme, .

2. Show that .

3. Another way to view the Blom scheme is by using a polynomial in two variables. Define the polynomial . Express the key  in terms of .

2. You (U) and I (I) are evil users on a network that uses the Blom scheme for key establishment with . We have decided to get together to figure out the other session keys on the network. In particular, suppose  and . We have received , , ,  from Trent, the trusted authority. Calculate  and .

3. Here is another version of the intruder-in-the-middle attack on the Diffie-Hellman key exchange in Section 10.1. It has the “advantage” that Eve does not have to intercept and retransmit all the messages between Bob and Alice. Suppose Eve discovers that , where  is an integer and  is small. Eve intercepts  and  as before. She sends Bob  and sends Alice .

1. Show that Alice and Bob each calculate the same key .

2. Show that there are only  possible values for , so Eve may find  by exhaustive search.

4. Bob, Ted, Carol, and Alice want to agree on a common key (cryptographic key, that is). They publicly choose a large prime  and a primitive root . They privately choose random numbers , respectively. Describe a protocol that allows them to compute  securely (ignore intruder-in-the-middle attacks).

5. Suppose naive Nelson tries to implement an analog of the three-pass protocol of Section 3.6 to send a key  to Heidi. He chooses a one-time pad key  and XORs it with . He sends  to Heidi. She XORs what she receives with her one-time pad key  to get . Heidi sends  to Nelson, who computes . Nelson sends  to Heidi, who recovers  as .

1. Show that .

2. Suppose Eve intercepts . How can she recover ?