5
$\begingroup$

The computational Diffie-Hellman problem states that for a cyclic group $G$ of order $p$ and a generator $g$, it is hard to find the value $g^{xy}$ given only $g^x$ and $g^y$ (but easy if either $x$ or $y$ is known); the easiest way being to compute the discrete logarithm of either $g^x$ or $g^y$ and then calculating $(g^x)^y$ = $g^{xy}$.

This is probably just a big misunderstanding of group theory and/or modular operations on my part, but why is it not possible to just calculate the product $g^x \cdot g^y$ as a "regular" group operation (multiplication modulo $p$)? Is this also computationally difficult, or would the result be wrong?

$\endgroup$
16
$\begingroup$

$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x$ of them] $\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.03 in}y$ of them] $\ldots \cdot g\cdot g\cdot g)$
$= \;\;\; g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$ of them] $\ldots \cdot g\cdot g\cdot g \;\;\; = \;\;\; g^{\hspace{.02 in}x+y}$

$\endgroup$
  • 2
    $\begingroup$ Back to my highschool math textbooks it is then. Thank you! $\endgroup$ – lxgr Mar 5 '14 at 21:55
3
$\begingroup$

As a add on to the above answer, it would be insecure to use $g^{x+y}$ as key , because both $g^x$ and $g^y$ will be transmitted publicly and by simply eavesdropping one can easily find the required key i.e $g^{x+y}$.

$\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.