# Diffie-Hellman insecure on addition modulo $n$

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?

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

## 2 Answers

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.

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