1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – poncho Feb 10 '15 at 11:13
  • $\begingroup$ 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. $\endgroup$ – mike russel Feb 10 '15 at 13:58
  • $\begingroup$ 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$ $\endgroup$ – poncho Feb 11 '15 at 4:50
  • $\begingroup$ $23/123\diamond 23/123$ is $46/123 - 1$ ? $\endgroup$ – mike russel Feb 11 '15 at 5:49
  • $\begingroup$ Never mind I got it. $23/123$ multiplied $358$ times mod $123 = 116/123$ Although i don't understand why it's mod 123 $\endgroup$ – mike russel Feb 11 '15 at 6:00
1
$\begingroup$

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.

Edit: you're right about 2).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mike russel Feb 10 '15 at 13:42
  • $\begingroup$ There was no question about security or Eve. This is a purely "try to figure out how DH works in toy examples" homework. And it shows quite easily in 1) why the dlog problem is required to be hard, if the DH problem should be hard to solve. $\endgroup$ – tylo Feb 11 '15 at 15:12
  • $\begingroup$ wWhat I meant is that even if you can't solve dlog in an additive group (which is super easy), you could break the scheme. For the first one, Eve can still find the shared secret but not as easily because she needs to compute a dlog... I'm not sure about whether this makes sense or not. $\endgroup$ – Florian Bourse Feb 11 '15 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.