0
$\begingroup$

Is it possible to reverse Diffie-Hellman key exchange to get the private key of one of the parties, given a large prime number 'p' .

$\endgroup$

migrated from security.stackexchange.com Sep 12 '17 at 7:09

This question came from our site for information security professionals.

4
$\begingroup$

It is certainly possible given enough compute resources.

However, if you mean to ask whether it is computationally feasible for an eavesdropper to derive the private keys, then- no, it is not.

Refer to the secrecy chart on Wikipedia:

The private keys a and b are meant to be known only to Alice and Bob respectively.

In the real world, the Logjam attack is one example of how adversaries with nation state-level compute resources (such as the NSA) could theoretically break Diffie Hellman implementations, relying on the fact that a small set of primes were used across most common implementations.

$\endgroup$
2
$\begingroup$

Is it possible to reverse Diffie-Hellman key exchange to get the private key of one of the parties, given a large prime number $p$ .

As this is formulated: yes.

Using a large prime is not sufficient for a secure Diffie-Hellman key exchange.
For DH to be secure you want the Computational Diffie-Hellman Problem (CDH) to be hard which in turn implies that you want the Discrete Logarithm Problem (DLOG) to be hard as well. Solving the DLOG means recovering either partie's private key, solving the CDH means recovering the resulting shared secret.

Now we can construct large primes $p$ (like 2048-bit and longer) for which the DLOG is easy. For example if we chose an $n$-bit prime $p$ such that $p-1$ has only prime factors smaller than $B$ (namely $k$ many) we can compute discrete logarithms in time less than $\mathcal O(k(\log n+\sqrt B))$ using the Pohlig-Hellman algorithm.


However, the following statement holds:

It is computationally not feasible using classical computers to solve the CDH problem if the sampling of the private exponents has sufficient entropy and the field prime $p$ is a safe prime of sufficient size and the common generator $g$ has order $>2$.

Where sufficiently large means 2048-bit long or more for the prime and 128-bit or more entropy for each exponent.

And yes, good real-world implementations do look out for these things and are thus secure (from a theoretical point of view).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy