# Extracting Private Keys in Diffie Hellman

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.

• What do you mean by the individual keys of Alice and Bob? They both share the same key after executing the protocol. Mar 13, 2017 at 21:53
• 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)? Mar 13, 2017 at 21:55
• exactly that, sorry for being not clear Mar 13, 2017 at 22:05
• 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. Mar 13, 2017 at 22:08
• i know, i just try to find an answer to the simple version for no practical purposes whatsoever Mar 13, 2017 at 22:10

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