3
$\begingroup$

I started to read about Diffie-Hellman exchange and I encountered a problem which I don't know how to solve.

Given $g=3$, $p=131$, $g^x\bmod p=112$, $g^y\bmod p=74$, compute $g^{xy}\bmod p$

  1. $113$
  2. $110$
  3. $112$
  4. $111$

How could I compute $g^{xy} \bmod p$? Or at least verify which one is correct. Any idea?

$\endgroup$

migrated from security.stackexchange.com Jul 5 '18 at 14:13

This question came from our site for information security professionals.

4
$\begingroup$

Actually, given $p,g,g^x\bmod p,g^y\bmod p$ deciding whether a given number is actually $g^{xy}\bmod p$ is also known as the Decisional Diffie-Hellman Problem (DDH), which sits at the basis of the (formal) security for the ElGamal cryptosystem and is assumed to be hard for properly chosen values of $p,g$ and $x,y$ in general.

For your particular scenario the best solution is to "just" solve the discrete logarithm problem, ie computing $x$ or $y$ and then computing $g^{xy}\bmod p$ to see which number falls out (113).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.