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?
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.
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$ 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
q is the order of group (which is generally prime) is usually kept small preferably 2.