Cracking diffie-hellman public key to obtain shared key

Question

I'm given 2 prime numbers, g and n, as well 2 public keys, g^a mod n and g^b mod n, as part of a leaked Diffie hellman key exchange. I need to derive the shared key g^ab mod n using the given information. I understand that I have to find a and b which are the private keys first but have no idea how to solve it since it states online that it is a discrete log problem that is very hard to solve. What are the steps I should take?

The very point of DH is that the public available information (i.e. sniffing on the wire) are **not sufficient** to derive the secret in **realistic time frame**. Thus what you are trying to do is **practically impossible** as long as strong enough keys are used. — Steffen Ullrich, Feb 14 '21 at 08:14
Why is the CTF tag included? Is this a toy problem? If so, maybe we can help. But if it is a real-life problem, you are probably out of luck. — hft, Mar 25 '21 at 05:44

forest · Answer 1 · 2021-02-22T01:22:46.893

A "hard problem" in cryptography does not simply mean that the problem is difficult to understand or complicated to implement, but that there is no known way to efficiently solve the problem in all cases. The discrete logarithm problem, which is the difficulty of finding x given g^x mod p, is a hard problem. The Number Field Sieve is the asymptotically fastest known method to compute discrete logarithms. If x is large and random, p is a non-smooth prime number, and g is an appropriate generator (like 2 or 5), then even this fast algorithm will not be able to find x before the sun burns out.

See also Can you give me a summary of cryptographic hardness assumptions?

score 0 · Answer 2 · edited Apr 04 '21 at 10:23

While it has not been proven that you absolutely need to solve DL problem to solve the CDH problem, which means cracking Diffie Hellman given two public keys, it does seem to be the case.

The solvability of the problem depends on a few factors like the order of $g$ , length of $n$ as well as the largest factor of $n-1$ . If $n-1$ is too smooth, i.e. has a lot of small factors, then it is easily solved. $n$ needs to be very big, i.e. minimum recommended 2048 bits, otherwise the whole group and all key pairs used in this group can be broken. And generally $(n-1)/q$ where q is the order of group (which is generally prime) is usually kept small preferably 2.

Cracking diffie-hellman public key to obtain shared key

2 Answers2