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.

Given the finite cyclic, additive group (G, +), with |G| = n and generator = g, what are the computations and exchanged messages for Diffie-Hellman?

What I tried myself:

  • Alice chooses a private $a$ and sends $p(|G|)$ and $g$ (generator) to Bob.
  • Alice calculates $A = a\cdot g \mod p (|G|)$ and sends it to Bob.
  • Bob chooses a private $b$ and calculates $B = b \cdot g \mod p (|G|)$ and sends it back to Alice.
  • Alice calculates $a \cdot B \mod p (|G|)$ which is the shared key.
  • Alice calculates $b \cdot A \mod p (|G|)$ which is the shared key.

Is this way of thinking correct? Because I'm not sure because the group is additive.

share|improve this question
    
In the beginning you write that the oder of $G$ is $n$ and then you switch to $p$ (or to be precise a strange notation $\pmod{p~|G|}$ which does not make sense)? Furthermore, your write-up does not use the notation of additive groups (but multiplicative ones). –  DrLecter Dec 17 '13 at 14:39
    
How should I change it to use the the additive groups then? –  Matthias_164 Dec 17 '13 at 14:42
1  
Additive vs. multiplicative is only a difference in notation. Replace multiplication with addition and exponentiation with scalar multiplication. –  CodesInChaos Dec 17 '13 at 14:44
1  
But if you use addition modulo a prime, that's a bad idea, since the discrete logarithm problem in that group is easy. –  CodesInChaos Dec 17 '13 at 14:44
    
@Matthias_164: Is $G$ just an arbitrary group or the integers modulo $N$ (in which case it's probably simpler to rewrite in that notation) –  figlesquidge Dec 17 '13 at 14:46
show 2 more comments

1 Answer

up vote 3 down vote accepted

Given the additive group $(G, +)$ with $|G| = p$ and generator $P$, what are the computations and exchanged messages for Diffie-Hellman?

I use order $p$ and assuming $p$ to be prime and the generator as $P$ (as it is used in context of elliptic curve groups - since you need additive groups where the DLP and the CDHP are hard - which is not the case for $\mathbb{Z}_n$).

  • Alice chooses random $a\in \mathbb{Z}_p^*$ and sends $A=aP$ (this means $P+\ldots+P$, $a$ times).
  • Bob chooses $b\in \mathbb{Z}_p^*$ and sends $B=bP$.
  • Alice computes $K=aB=(ab)P$
  • Bob computes $K=bA=(ba)P=(ab)P$

Note that since I assume that we work on elliptic curve groups there is no reduction modulo the group order after the additive operation.

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.