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

Suppose Trent chooses the numbers

Calculate the session keys.

1. Show that in the Blom scheme, $K_{AB}\equiv a+b(r_A+r_B)+c{r}_A{r}_B(\text{mod}p)$.

2. Show that $K_{AB}=K_{BA}$.

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

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 $r_U=9\text{,}{r}_I=2$. We have received $a_U=18$, $b_U=29$, $a_I=24$, $b_I=23$ from Trent, the trusted authority. Calculate $a\text{,}b\text{,}$ and $c$.

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 ${\alpha }^x$ and ${\alpha }^y$ as before. She sends Bob $({\alpha }^x{)}^q(\text{mod}p)$ and sends Alice $({\alpha }^y{)}^q(\text{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.

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 $\alpha$. They privately choose random numbers $b\text{,}t\text{,}c\text{,}a$, respectively. Describe a protocol that allows them to compute $K\equiv {\alpha }^{btca}(\text{mod}p)$ securely (ignore intruder-in-the-middle attacks).

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 $K_N$ and XORs it with $K$. He sends $M_1=K_N\oplus K$ to Heidi. She XORs what she receives with her one-time pad key $K_H$ to get $M_2=M_1\oplus K_H$. Heidi sends $M_2$ to Nelson, who computes $M_3=M_2\oplus K_N$. Nelson sends $M_3$ to Heidi, who recovers $K$ as $M_3\oplus K_H$.

1. Show that $K=M_3\oplus K_H$.

2. Suppose Eve intercepts $M_1\text{,}{M}_2\text{,}{M}_3$. How can she recover $K$?