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?

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

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}}$

| improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – paratrooper Apr 4 '18 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.