Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

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

Assume that the group $G$ is the set $\mathbb{Z}_{n} = \{0,\ldots, n-1\}$ for a 1024 bit integer and $+$ is addition modulo $n$. Then why would Diffie-Hellman key exchange in this group be insecure?

share|improve this question
Because the discrete logarithm problem in $(\mathbb{Z}_n,+)$ is easy. You may look at this answer. – DrLecter Dec 17 '13 at 21:05

With addition and $\mathbb{Z}_n$, each party chooses a secret $x$ and sends $xg \pmod n$ over the wire, for an agreed upon generator $g$. Division by $g$ modulo $n$ is easily computable, and reveals $x$.

In other words, a prerequisite for DH to be secure is that the equivalent to discrete logarithm is hard in the chosen group. With $\mathbb{Z}_n$ and addition, discrete logarithm becomes totally easy.

share|improve this answer

This is due to the Extended Euclidean algorithm, which allows us to compute inverses modulo any number. If the modulus is prime, things are even more easier to explain.

For prime $p$, we know that $g^{p-1} \equiv 1 \pmod{p}$.

Therefore, $y = g^{p-2} \equiv 1/g \pmod {p}$.

Therefore, $(xg).y \equiv x \pmod{p}$, revealing the secret key.

If modulus is not prime and factors are unknown, then $y$ can be computed using the extended Euclidean algorithm, which has complexity $O(\log{n})$ for modulus $n$.

share|improve this answer

Your Answer


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.