15.9 Exercises – Introduction to Cryptography with Coding Theory, 3rd Edition

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 p=31 and let

    rA=11rB=3rC=2.

    Suppose Trent chooses the numbers

    a=8b=3c=1.

    Calculate the session keys.

    1. Show that in the Blom scheme, KABa+b(rA+rB)+crArB (mod p).

    2. Show that KAB=KBA.

    3. Another way to view the Blom scheme is by using a polynomial in two variables. Define the polynomial f(x, y)=a+b(x+y)+cxy (mod p). Express the key KAB in terms of f.

  2. You (U) and I (I) are evil users on a network that uses the Blom scheme for key establishment with k=1. We have decided to get together to figure out the other session keys on the network. In particular, suppose p=31 and rU=9, rI=2. We have received aU=18, bU=29, aI=24, bI=23 from Trent, the trusted authority. Calculate a, b,  and c.

  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 p=Mq+1, where q is an integer and M is small. Eve intercepts αx and αy as before. She sends Bob (αx)q (mod p) and sends Alice (αy)q (mod p).

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

    2. Show that there are only M possible values for K, so Eve may find K 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 p and a primitive root α. They privately choose random numbers b, t, c, a, respectively. Describe a protocol that allows them to compute Kαbtca (mod p) 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 K to Heidi. He chooses a one-time pad key KN and XORs it with K. He sends M1=KNK to Heidi. She XORs what she receives with her one-time pad key KH to get M2=M1KH. Heidi sends M2 to Nelson, who computes M3=M2KN. Nelson sends M3 to Heidi, who recovers K as M3KH.

    1. Show that K=M3KH.

    2. Suppose Eve intercepts M1, M2, M3. How can she recover K?