How do you perform the Burmester-Desmedt key exchange Protocol, in Diffie-Hellman extension protocol?

I've been searching high and low, but couldn't locate an example on how to prove if all the party is getting the same session key.

Here is the explanation that I got from the net:

enter image description here

I don't really get all the formula, especially this calculation:

$k_i = (k_i + 1 / k_i - 1)^{x_i} \mod p$


$k_i = g ^{x_1} \mod p$

assuming $x_1 = 4, g = 2$ ( 2 is a generator from $Z_{11}^*$ ) and $p = 11$

$k_1 = 2^4 \mod 11$

$k_1 = 5$


$k_1 = (k_1 + 1 / k_1 - 1) ^ x_1 \mod p$

$= (5+1 / 5-1) ^ 4 \mod 11$

$= (6 / 4) ^ 4 \mod 11$

= ...

How should I proceed from here on?


And after the k1 is found, how can i prove that other parties (n = 3) are getting the same session key (K) ?


All this work is done modulo the prime $p$ (which is 11 in your toy example); in this field, addition, subtraction and multiplication is done in the usual way (except you do a modulo $p$ at the end); however division is defined differently.

We define $x = 6/4\ (\bmod 11)$ to be that value such that $x \times 4 = 6\ (\bmod 11)$.

Now, we see that $7 \times 4 = 28$ and $28 = 6\ (\bmod 11)$, hence $6/4 = 7$. And, yes, if $p$ is prime, and if what you're dividing by is not zero, then it turns out that such division is uniquely defined; there will always be precisely one number between 0 and $p-1$ that meets this criteria.

How do we find such values $x$. Well, when $p$ is small, you can just test the various possibilities (like I did in this case). However, if $p$ is large, you can efficiently find such values using the Extended Euclidean Algorithm

  • $\begingroup$ I'd use \pmod {11} instead of \bmod in this context. $\pmod{11}$ $\endgroup$ – CodesInChaos Feb 22 '14 at 15:38
  • $\begingroup$ Thanks poncho. After i got the k1, how should i calculate the shared session Key by using the formula (K) aboves ? Thanks $\endgroup$ – Charlie Kee Feb 22 '14 at 16:30
  • $\begingroup$ Well, you take your $k_i$ value, and every else's $K_j$ values, raise them to the appropriate powers (modulo $p$, and then multiply them together (again, modulo $p$). The formula in the paper is pretty straight-forward. $\endgroup$ – poncho Feb 22 '14 at 17:37

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.