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.

I want to implement a basic version of Diffie-Hellman key agreement for groups.

So, my key is $K=g^{abc} \mod p$. Following this, the parameters I would need to transfer would be $K_a = g^{bc}$ etc. The group may become large (up to 100 member), so I don't want to calculate every parameter anew and reuse $K$. Is there an efficient way to do this? I tried multiplying $K$ with $(g^a)^{-1}$ but that did not create a valid parameter since the resulting key was not correct.

Another idea I didn't have implemented yet is to calculate the key as $K=g^t$ with $t=abc \mod p$. I think, that in this case I could compute the inverse $a^{-1}$of $a$ in $Z_p^*$ and get my parameters as e.g. $K_a=K^{a^{-1}}\mod p$. Do you think this would work? Are there possible security issues in this approach?

share|improve this question
    
"up to 100 member" $\:$ Wow, that's huge! $\:$ \end{sarcasm} $\;\;\;$ –  Ricky Demer Nov 18 '13 at 11:09
1  
You'd need to compute $K^{(a^{-1})}$. Only those who hold the private key $a$ can do this. Multiplying with $(g^a)^{-1} = g^{-a}$ would subtract $a$ from the exponent, not divide the exponent by $a$. –  CodesInChaos Nov 18 '13 at 11:13
1  
@RickyDemer Thanks for valuable content. –  LostAvatar Nov 18 '13 at 11:15
    
@CodesInChaos Sorry, error in the equation. $K^{a^{-1}}$ –  LostAvatar Nov 18 '13 at 11:16
    
@RickyDemer It's large enough to make group DH annoying since you need one round of communication for every member in the group. –  CodesInChaos Nov 18 '13 at 11:19
show 2 more comments

1 Answer 1

up vote 3 down vote accepted

You'd need to compute $K^{(a^{-1})}$. Only those who hold the private key $a$ can do this. Multiplying with $(g^a)^{-1} = g^{-a}$ would subtract $a$ from the exponent, not divide the exponent by $a$.

So your optimization isn't possible in practice. Take a look at the alternatives at Can one generalize the Diffie-Hellman key exchange to three or more parties?. Thomas Pornin describes a two-round shared key algorithm based on DH and links to an single-round scheme that uses advanced crypto.

share|improve this answer
    
To emphasize what CodesinChaos has said: given an Oracle that, given $g$ and $g^a$, computes $g^{-a}$, then you can solve the computational DH problem. Hence, if your (LostAvatar's) protocol could be done, it would also show that the shared secrets it generated was insecure. –  poncho Nov 18 '13 at 17:38
    
@poncho Could you describe how to use that oracle to break CDH? –  CodesInChaos Nov 18 '13 at 17:55
    
Refer to jmiller.uaa.alaska.edu/csce465-fall2013/papers/bao2003.pdf; the summary is: use the Oracle to compute $g^{a^2}$, $g^{b^2}$ and $g^{(a+b)^2}$ (using the Oracle to square is straight-forward). Obtain $g^{2ab} = g^{(a+b)^2} / (g^{a^2}g^{b^2})$, compute a modular square root, and $g^{ab}$ pops out. –  poncho Nov 18 '13 at 19:15
    
@poncho I guess in your first comment you meant: "given an Oracle that, given $g$ and $g^a$, computes $g^{a^{-1}}$"?, then you can solve the CDHP. –  DrLecter Nov 18 '13 at 21:57
    
@DrLecter: oops, you are correct. Call me fumble-fingered... –  poncho Nov 18 '13 at 22:11
add comment

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.