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.

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
1  
Because the discrete logarithm problem in $(\mathbb{Z}_n,+)$ is easy. You may look at this answer. –  DrLecter Dec 17 '13 at 21:05
add comment

2 Answers 2

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
add comment

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