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$
5
  • $\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, 2017 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, 2017 at 21:55
  • $\begingroup$ exactly that, sorry for being not clear $\endgroup$
    – theycallmefm
    Mar 13, 2017 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, 2017 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, 2017 at 22:10

2 Answers 2

Reset to default
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$
3
  • $\begingroup$ so basically there is no better approach than brute-forcing random keys since they are equivalent in computational hardness? $\endgroup$
    – theycallmefm
    Mar 13, 2017 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, 2017 at 22:15
  • $\begingroup$ See, e.g., en.wikipedia.org/wiki/Discrete_logarithm#Algorithms $\endgroup$
    – Christian Matt
    Mar 13, 2017 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$
2
  • $\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, 2017 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, 2017 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.