2
$\begingroup$

I saw that non-negative integers with the addition operation cannot be the Diffie Hellman group. I'm having trouble understanding why it cannot be the DHKE group. To be DHKE group, there are five properties to be held,

  1. The operator is closed
  2. associativity
  3. identity element exists
  4. inverse element exists
  5. commutativity

I tried with the group of {0,1,2,3,4,5,6} and p=7, and all the above properties were held. I couldn't find any appropriate example to show the above properties are not held. What other examples can show that the non-negative integers with addition operator is not one of Diffie Hellman key groups?

$\endgroup$
6
  • 3
    $\begingroup$ Non-negative integers are not a group because the additive inverses are negative integers. $\endgroup$ – conchild Oct 3 '20 at 23:27
  • $\begingroup$ How come the additive inverses become negative integers? Since we don't even have subtraction operation? Could you give me an example of that? Or maybe I'm not understanding the inverse property correctly. Could you describe about the inverse property a bit more? $\endgroup$ – user19283043 Oct 3 '20 at 23:34
  • 1
    $\begingroup$ Applying an operation to an element and its inverse yields the appropriate identity. The additive identity is 0. A+inverse(A)=0. There's no set element (non-negative integer) that can be the result of inverse(A) and satisfy that equation, so the set of non-negative integers doesn't form a Group. $\endgroup$ – SAI Peregrinus Oct 4 '20 at 1:54
  • 1
    $\begingroup$ Side note: Groups aren't specific to DHKE, they're a concept from abstract algebra. DHKE happens to use groups, but they're not specifically "Diffie-Hellman" groups. $\endgroup$ – SAI Peregrinus Oct 4 '20 at 1:55
  • 1
    $\begingroup$ Groups don't have multiplication and addition. If you have two binary operations, both closed, associative, with (possibly separate) identity elements, inverses, and commutative you've got a field instead of a group. Different structure, not particularly relevant for DH (though fields show up a lot in cryptography). $\endgroup$ – SAI Peregrinus Oct 4 '20 at 2:55
3
$\begingroup$

To be DHKE group, there are five properties to be held,

This is true; however, to be a secure DHKE group, there has to be an additional property:

  • The "discrete log problem" needs to be hard; that is, given a public value $xG$ (where $G$ is the public group identifier, $x$ is your private value, and $xG$ is the generator acted upon itself $x$ times), it is hard to recover $x$.

In the addition case, we have $xG = \underbrace{G + G + … + G}_{x \text{ times}} = x \times G$., where $\times$ is integer multiplication.

If we know $x \times G$ and we know $G$, then it is easy to recover $x$ by doing a simple division (modular division if we're doing the addition modulo $p$, which isn't much harder), and hence the Diffie-Hellman would be trivially insecure.

Actually, just having a secure discrete log problem is not sufficient; the "Diffie-Hellman" problem also needs to be hard, that is, given $G$, $xG$ and $yG$, it should be hard to recover $xyG$ (this is known as the computational Diffie Hellman problem), or given $G$, $xG$, $yG$, $zG$, it should be hard to determine whether $xy = z$ (this is known as the decisional Diffie Hellman problem). Either of these problems may be easier than the "discrete log problem" for any group; however, for addition, none of these problems are hard.

$\endgroup$

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.