3
$\begingroup$

I know that the additive finite group $(Zp,+)$ of prime order $p$ when I perform the Diffie-Hellman key exchange (DHKE) protocol is insecure. I didn't however find many sources online explain why it is insecure. Neither could I find information about what possible attacks can be performed in that case.

Can anybody explain why it is insecure and what possible attacks would be possible if I would use addition instead of multiplication?

Additionally, how can I make both Alice and Bob have the same key when performing the DHKE using $(Zp, +)$?

$\endgroup$
  • $\begingroup$ See Wikipedia’s Euclidean algorithm $\endgroup$ – user991 Oct 30 '16 at 5:27
3
$\begingroup$

Why can't we use $(Z_p,+)$?

In the DH key Exchange Alice and Bob agree on a common generator g which allow to share a common key. In fact in $(Z_p,+)$ every non zero element is a generator.

If a common generator g is preallably chosen, when Alice chose a secret a, transmitting A=g.a, the secret a will be immediatly disclosed by any one in the public channel by simply Computing $a=\frac{A}{g}$ and key exchange will be violated which isn't the case in $(Z_p,*)$, as the inversion by the discret logarithm, is considered hard.

$\endgroup$
  • $\begingroup$ interesting, good information to know, thanks. So in Z*p I could calculate A by using this formula A= g^Alice, pr mod p but what about when I use Zp+ $\endgroup$ – han Oct 30 '16 at 14:13
  • $\begingroup$ @han, In $(Z_p,+)$ every non zero element is a generator then g.a mean adding a g-times whith itself: $a+a+...+g = g.a$. which is different from $a*a...*a=g^a$ in $(Z_p,*)$. Look at the principal definitions inside a group. $\endgroup$ – Robert NACIRI Oct 30 '16 at 14:32
  • $\begingroup$ The fact that the discrete logarithm in $(Z_P, +)$ is easy, has nothing to do with the fact that every element is a generator. The discrete logarithm problem is easy in $(Z_P, +)$ because one can use the extended Euclidean algorithm to calculate it. $\endgroup$ – user27950 Oct 30 '16 at 15:07
  • $\begingroup$ Yes, I got all that information. But I want to know if I use Zp+ in DH can I get the same shared key. So I am trying to calculate manually to see by myself. That's why I am asking about the formula, is it different than Z*p $\endgroup$ – han Oct 30 '16 at 15:25
  • 1
    $\begingroup$ The arithmetic of the elliptic curve group is rather complicated. Please note, the fact that you use the addition symbol $ +$ on elliptic curve arithmetic does in no sense mean that it has something to do with the usual addition in integers or modular integers. It would probably be less confusing to use a completely different symbol instead. But in mathematics the same operator symbols are often used for very different structures. If you know C++ or C# then think about it as a kind of operator overloading. $\endgroup$ – user27950 Oct 30 '16 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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