Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$

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

share|improve this question

migrated from security.stackexchange.com Feb 22 at 15:06

This question came from our site for Information security professionals.

1 Answer 1

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

share|improve this answer
    
I'd use \pmod {11} instead of \bmod in this context. $\pmod{11}$ –  CodesInChaos Feb 22 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 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 at 17:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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