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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
up vote 13 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
2  
Back to my highschool math textbooks it is then. Thank you! – lxgr Mar 5 '14 at 21:55

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

share|improve this answer

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.