# Diffie-Hellman Application

Alice and Bob want to perform a Diffie-Hellman key exchange using the group $G$, a primitive root $g$, Alice’s secret key $k_A$ and Bob’s secret key $k_B$. In each case below compute the element of $G$ that Alice sends to Bob, the element that Bob sends to Alice, and the secret key that Alice and Bob will share.

1. $G=\mathbb Z/163\mathbb Z$(as an additive group), $g = 2$, $k_A = 128$, $k_B = 65$.
2. $G=\mathbb F_{163}^*$, $g = 2$, $k_A = 128$, $k_B = 65$
3. $G = [0, 1) ∩ \mathbb Q$ with group operation $$a\Diamond b = [a + b] = a + b − \left \lceil{a+b}\right \rceil$$ $g = 23/123$, $k_A = 358$ and $k_B = −44$.
4. $G = GL_2(\mathbb F_{17})$, $g= \left[\begin{array}{ c c } 2 & 3 \\ 4 & 5 \end{array} \right]$, $k_A = 13$, $k_B = 5$.

For $1)$ I did the following, Alice sends Bob $A = (128)2 \bmod p$ and then Bob sends Alice $B = (65)2 \bmod p$. Their secret key is $(128+65)2 \bmod p$.

For $2)$ I did this: Alice sends Bob $A = 2^{128}$ $mod p$ and Bob sends Alice $B = 2^{65} \bmod p$ Therefore, their secret key is $B = 2^{(65)(128)} \bmod p$.

For $3)$ Alice sends Bob $128\Diamond 23/123$ and Bob sends Alice $65\Diamond 23/123$ so their secret key is $(128\Diamond 65)\Diamond 23/123$. However I don't know whether this is right or not.

I don't know how to do the fourth one.

Any help is appreciated. Thank you.

• You don't have (3) correct; Alice sends Bob $116/123$, Bob sends Alice $95/123$, and their secret key is $62/123$. How did I get that? Well, consider the group operation, and if $a=p/q$, what is $a\Diamond a\Diamond ... \Diamond a$ Feb 10 '15 at 11:13
• The ceiling function makes any fraction in it as the highest integer. So Alice sends Bob $358+23/123 - \left \lceil{358+23/123}\right \rceil=358+23/123 - 359$ which is not the same as you provided. Feb 10 '15 at 13:58
• No, Alice does not send $358\diamond 23/123$ (for one, $358$ is not a member of the group $G$); instead, she sends $23/123\ \diamond\ 23/123\ \diamond\ 23/123\ \diamond ... \diamond\ 23/123$ Feb 11 '15 at 4:50
• $23/123\diamond 23/123$ is $46/123 - 1$ ? Feb 11 '15 at 5:49
• Never mind I got it. $23/123$ multiplied $358$ times mod $123 = 116/123$ Although i don't understand why it's mod 123 Feb 11 '15 at 6:00

Eve shouldn't be able to find the shared secret easily from the messages Alice and Bob send.

In the questions 1 and 2, you said that the shared secret is the sum/the product of the two messages, but anyone can compute them. Therefore, you are wrong. The shared secret should be:
1) $B=(128)(65)2 = (65)(128)2\mod p$,
2) $B=(2^{(65)})^{(128)}=(2^{(128)})^{(65)}\mod p$.

Once you understood these two examples, I am sure you will be able to solve the 2 other questions easily by thinking a bit more about it.

• But for the second one, $2^{(65)^{(128)}} = 2^{(65)(128)}$. What confuses me about 3 is the primitive root $g$. I can't think of a way to express it other than what i came up with. Feb 10 '15 at 13:42