0
$\begingroup$

I have to elements of multiplicative group of finite field with generator g - $$g^x,g^y $$ Can I get? $$g^{xy} $$

$\endgroup$
  • $\begingroup$ This is Diffie-Hellman problem. Now, what is your actual question? Research on Diffie-Hellman Problem? Or you are given some instance of it? $\endgroup$ – kelalaka Nov 11 at 15:07
  • $\begingroup$ @kelalaka, Task is next, I have next equation $$g^(x(y + a))$$. And this equation check on recipient, $$g^x,g^y$$ knows everyone (x and y - knows only me and recipient). "a" is index(from 0 to 20 eg) in database . Pipeline is next: I compute $$g^{(x(y + a))}$$ (a - is my index) on my part and send it to recipient. Recipient iterate over all indexes and solve equation, if some result are equals - user is registered. As I understand. There is no way to send msg by intruder without knowing x and y. $\endgroup$ – Alex Nov 11 at 15:37
  • $\begingroup$ Hmmmm, if everyone knows $g^x, g^y$, and you transmit $g^{x(y+a)}$, and someone overhears it, and guesses $a$, then he has a guess to $g^{xy}$, which he can use in a later login attempt. Do you have something that protects against this sort of thing? $\endgroup$ – poncho Nov 12 at 21:57
1
$\begingroup$

The problem 'given a group and the elements $g, g^x, g^y$, find $g^{xy}$' is known as the Diffie-Hellman problem (or, more precisely, the computational Diffie-Hellman problem).

As for how difficult it is, well, we typically work with groups where this is difficult (by design; we often need to assume that the DH problem is hard).

As for how it might be solved, well, in a finite field multiplicative group, the best way of solving it is to solve the discrete log problem; this is, given $g, g^x$, recover $x$ (and from there, you can compute $(g^y)^x = g^{xy}$. If you are in a group where recovering $x$ (or $y$) directly is infeasible, then solving the DH problem (to the best of our knowledge) is also infeasible.

$\endgroup$

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.