# 15.9 Exercises

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

$${r}_{A}=11\phantom{\rule{1em}{0ex}}{r}_{B}=3\phantom{\rule{1em}{0ex}}{r}_{C}=2.$$Suppose Trent chooses the numbers

$$a=8\phantom{\rule{1em}{0ex}}b=3\phantom{\rule{1em}{0ex}}c=1.$$Calculate the session keys.

Show that in the Blom scheme, ${K}_{AB}\equiv a+b({r}_{A}+{r}_{B})+c{r}_{A}{r}_{B}\text{}(\text{mod}\text{}p)$.

Show that ${K}_{AB}={K}_{BA}$.

Another way to view the Blom scheme is by using a polynomial in two variables. Define the polynomial $f(x\text{,}\text{}y)=a+b(x+y)+cxy\text{}(\text{mod}\text{}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{,}\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{,}\text{}\phantom{\rule{thinmathspace}{0ex}}b\text{,}\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{}(\text{mod}\text{}p)$ and sends Alice $({\alpha}^{y}{)}^{q}\text{}(\text{mod}\text{}p)$.

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

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{,}\text{}t\text{,}\text{}c\text{,}\text{}a$, respectively. Describe a protocol that allows them to compute $K\equiv {\alpha}^{btca}\text{}(\text{mod}\text{}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}$.

Show that $K={M}_{3}\oplus {K}_{H}$.

Suppose Eve intercepts ${M}_{1}\text{,}\text{}{M}_{2}\text{,}\text{}{M}_{3}$. How can she recover $K$?