# Cracking diffie-hellman public key to obtain shared key

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?

• 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. Feb 14, 2021 at 8: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, 2021 at 5:44

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.