# Breaking a modified version of Diffie Hellmann Protocol

I'm modifying the Diffie Hellman protocol as follows: We are given a large prime number $p$ and exponent $x$ such that $0 \lt x \lt p-1$ and $\mathrm{gcd}(x, p-1) = 1$. Also we pick $g$ such as $1 \lt g \lt p-1$.

We are also given $y = (g^x) \bmod{p}$. Essentially, we know about the prime $p$, the exponent $x$ and the result $y$. But $g$ is kept secret.

This is similar to Diffie Hellman protocol except that exponent $x$ is made public while $g$ is kept secret. So I'm trying to find if there's an efficient way to determine the secret $g$ or is this also a discrete logarithm problem?

• Yes, it's easy to recover $g$. If you assure me that this is not homework, I'll tell you how... Apr 3, 2018 at 17:10
• No this isn't related to any homework Apr 4, 2018 at 0:20

## 1 Answer

Yes, there's an easy way to recover $g$:

$$g = y^{x^{-1} \bmod p-1} \bmod p$$

This works because the multiplicative group $\mathbb{Z}_p^*$ has order $p-1$, and hence $g = g^{x \cdot x^{-1}} = (g^x)^{x^{-1}} = y^{x^{-1}}$

• I see. Why didn't I see that before. This clarifies my doubt. So in this case it means that the problem is simple and is not a discrete logarithm problem (unlike the original diffie hellman). I'm accepting your answer. Apr 4, 2018 at 3:25