Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 10 down vote accepted

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

share|improve this answer
1  
Back to my highschool math textbooks it is then. Thank you! –  lxgr Mar 5 at 21:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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