4
$\begingroup$

I know that the security of Diffie Hellman Key Exchange depends upon the discrete logarithm problem, but is it possible to extract the private keys if we know more? Say that in addition to modulus ($q$), primitive root ($g$) and public keys of Alice and Bob ($g^a$ and $g^b$ respectively), if we knew the calculated key ($g^{ab}$) as well, will it be possible to extract individual keys of Alice and Bob ($a$ and $b$) without using a brute force method? I know it sounds silly and serves no practical purpose at all, but the question was bugging me.

Thanks,

Edit: Added $g$ and other variables for clarity.

|improve this question
$\endgroup$
  • $\begingroup$ What do you mean by the individual keys of Alice and Bob? They both share the same key after executing the protocol. $\endgroup$ – Christian Matt Mar 13 '17 at 21:53
  • 1
    $\begingroup$ I think he means their private exponents. The question is still unclear though, what do you mean by calculated key? $g^{ab}$ where $a$ and $b$ are the private keys and $g$ is the generator (primitive root)? $\endgroup$ – puzzlepalace Mar 13 '17 at 21:55
  • $\begingroup$ exactly that, sorry for being not clear $\endgroup$ – theycallmefm Mar 13 '17 at 22:05
  • $\begingroup$ Heh, it would be something if one party could calculate the private key of the other party by just establishing the shared secret :) Do you know that there are DH/ECDH certificates out there? I'll wait for a nice algorithmic explanation from one of the math wizards out there though. $\endgroup$ – Maarten Bodewes♦ Mar 13 '17 at 22:08
  • $\begingroup$ i know, i just try to find an answer to the simple version for no practical purposes whatsoever $\endgroup$ – theycallmefm Mar 13 '17 at 22:10
5
$\begingroup$

This is as hard as computing the discrete logarithm: Assume you have an algorithm $\mathcal{A}$ that given $g^a$, $g^b$ and $g^{ab}$ efficiently computes $a$ and $b$ for uniform $a$ and $b$. You can use this algorithm to compute discrete logarithms as follows: Given $h = g^a$, choose a uniform $b$, compute $g^b$ and $h^b = g^{ab}$. Now give $g^a$, $g^b$ and $g^{ab}$ to $\mathcal{A}$ to obtain $a$, the discrete logarithm of $h$.

|improve this answer
$\endgroup$
  • $\begingroup$ so basically there is no better approach than brute-forcing random keys since they are equivalent in computational hardness? $\endgroup$ – theycallmefm Mar 13 '17 at 22:14
  • 2
    $\begingroup$ There might be better ways to compute discrete logarithms than brute force, depending on the group. $\endgroup$ – Christian Matt Mar 13 '17 at 22:15
  • $\begingroup$ See, e.g., en.wikipedia.org/wiki/Discrete_logarithm#Algorithms $\endgroup$ – Christian Matt Mar 13 '17 at 22:53
0
$\begingroup$

If i got you well you want to now if there is any way Bob(or any intruder) can calculate Alice's private key. The answer is 'NO', in fact that's the strength of the DH algorithm and that's the reason it is used for exchanging keys. A common key is established without either side knowing the other's private key.

|improve this answer
$\endgroup$
  • $\begingroup$ Hi Melo and welcome. Can you indicate in which part this answer differs from the given one? Possibly I'm overlooking something, but as it stands I don't see any specific improvement over the accepted answer. $\endgroup$ – Maarten Bodewes♦ Apr 18 '17 at 20:29
  • $\begingroup$ Hello Maarten Dodewes, in fact I'm not that familiar with how this forum works, my answer isn't really different from the other one, it was just a clarification. But thanks for helping me learn in a polite way. Point noted!!. $\endgroup$ – Melo Apr 19 '17 at 14:45

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.