1

I'm given 2 prime numbers, g and n, as well 2 public keys, ga mod n and gb mod n, as part of a leaked Diffie hellman key exchange. I need to derive the shared key gab 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?

Improve this question
2
  • 1
    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
    Commented Feb 14, 2021 at 8:14
  • 1
    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
    Commented Mar 25, 2021 at 5:44

2 Answers 2

Reset to default
1

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 gx 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?

Improve this answer
0

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.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .