# Burmester-Desmedt (BD) key agreement protocols

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:

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

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

Example:

$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$

therefore,

$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?

ADDITIONAL

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

-

## migrated from security.stackexchange.comFeb 22 '14 at 15:06

This question came from our site for information security professionals.

## 1 Answer

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

-
I'd use \pmod {11} instead of \bmod in this context. $\pmod{11}$ – CodesInChaos Feb 22 '14 at 15:38
Thanks poncho. After i got the k1, how should i calculate the shared session Key by using the formula (K) aboves ? Thanks – Charlie Kee Feb 22 '14 at 16:30
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. – poncho Feb 22 '14 at 17:37