4
$\begingroup$

Why is Diffie-Hellman defined on a cyclic group? Doesn't it work for any commutative operation which the inverse is hard to find?

Say Alice and Bob agree in a public prime $c$ and both choose a secret prime $a$ respectively $b$

Alice sends $ac$ to Bob and Bob $bc$ to Alice.

Alice then multiplies $a$ with bobs message $bc$ yielding $abc$ Bob then multiplies $b$ with Aice's message $ac$ yield $bac$

which are the same due to commutativity and associativity. Hence they now share a common secret $abc$.

It is hard for Eve to factorize $ac$ and $bc$ into its original primes $a,b,c$ and Eve hasn't got enough information to construct $abc$ so why isn't this a valid Diffie-Hellman key-exchange?

$\endgroup$
6
  • 1
    $\begingroup$ Eve divides $ac$ by $c$. $\endgroup$
    – yyyyyyy
    Commented May 7, 2015 at 8:48
  • $\begingroup$ Or multiplies like this: $(ac)\cdot(bc)/(c)$ to get the shared "secret" $\endgroup$
    – tylo
    Commented May 7, 2015 at 8:49
  • 1
    $\begingroup$ @yyyyyyy: "the inverse is hard to find"; that implies that the "division problem", that is, given $b$ and $a$, find $c$ such that $a \times c = b$, is hard. $\endgroup$
    – poncho
    Commented May 7, 2015 at 11:28
  • $\begingroup$ Related questions: Diffie-Hellman on infinite groups and How does the wider cryptographic community view non-abelian group based cryptography? $\endgroup$ Commented May 7, 2015 at 12:23
  • $\begingroup$ @poncho From the notation up there and the lack of definition of the group, you could assume that to be $\mathbb{Z}$ or a subgroup of that and consider the factorization problem as hard - which is only true if you don't publish one of factors previously. And in that case division is easy. Regarding the question: If you go with the standard DH notation ($g^a,g^b,g^{ab}$) and base the chosen elements on a single generating element $g$, you operate on a cyclic group if it is finite. If there are multiple generating elements, you either have a problem with soundness or end up with standard DH. $\endgroup$
    – tylo
    Commented May 7, 2015 at 12:46

3 Answers 3

3
$\begingroup$

Diffie-Hellman operates in a cyclic group by definition: the elements $g, g^a, g^b, g^{ab}$ are in the cyclic group generated by $g$. Technically, a monoid is sufficient, but since cryptography mostly operates in finite structures, you get a group anyway.

In your example, you operate in the cyclic group $c\mathbf{Z}$, and as you were told in the comments, Diffie-Hellman is not secure in this group because an attacker knows $c$ and $ac$, and can thus obtain $a$, and from $a$ and $bc$ can obtain the secret $abc$.

$\endgroup$
3
$\begingroup$

Why is diffie-hellman defined on a cyclic group[0]? Doesn't it work for any commutative operation which the inverse is hard to find?

No, you need associativity as well; once you have that, your idea would work fine, once we find a semigroup (that's what we call sets with an operator that is associative) with the appropriate properties.

That's the sticky point - what is an appropriate semigroup? Do you have any suggestions?

$\endgroup$
1
  • $\begingroup$ One could work with a commutative magma action instead of a semigroup. $\;$ $\endgroup$
    – user991
    Commented May 7, 2015 at 13:56
-1
$\begingroup$

Carefully selected (more in next para) cyclic groups $\{g^0,g^1,g^a,..., g^b, ...\}$ are used because in these groups finding the discrete logarithm of a group element is computationally hard, i.e. determining $a$ from $g^a$ is hard. This enables Alice and Bob to share public keys ($g^a$ and $g^b$) and come up with a shared secret $g^{ab}$, while Eve who sees the public key cannot compute the secret key. For Eve not to determine $g^{ab}$ from $g^a$ and $g^b$, requires three conditions to be satisfied:

  1. Computing $a$ from $g^a$ is hard (the discrete logarithm problem), and
  2. Computing $g^{ab}$, given $g^a$ and $g^b$ is hard (the computational Diffie-Hellman problem), and
  3. $g^{ab}$ being totally random element in group $\Bbb G$ given $g^a$ and $g^b$, i.e. given $g^a$ and $g^a$, Eve's guess of $g^{ab}$ is at-best uniform random probability (the decisional Diffie-Hellman problem)

The carefully selected cyclic group is typically a prime-order subroup of $\Bbb Z_p^*$. Let $p=rq +1$, with $p$ and $q$ large primes (eg. $p$ 3072 and $q$ 256 bits). Then subgroup of $\Bbb Z_p^*$ of order $q$ is selected. In such a subgroup all three conditions above are conjectured to be met. (Ref: Section 8.3.3 and Chapter 9 of "Introduction to Modern Cryptography" by J. Katz and Y.Lindell).

The hard problem of factorizing two large prime numbers from their product cannot be used here, because the assumption for Diffie-Hellman is that Alice, Bob and Eve have the same information to start off with. So if Alice and Bob agree in public to the prime $c$ and share $ac$ and $bc$ with each other, Eve can easily factor $ac$ or $bc$, since Eve also knows $c$. The hard factoring problem works in RSA, because neither Eve nor Alice know the prime factors of $n$. So Alice can encrypt using public key and only Bob can decrypt, because only Bob knows the prime factors.

$\endgroup$
2
  • $\begingroup$ The structure being a cyclic group does not make the Dlog problem hard. There are many cyclic groups where that problem is easy. Also Dlog being hard is not known to be sufficient for the security of DH. $\endgroup$
    – Maeher
    Commented May 6 at 14:52
  • $\begingroup$ @Maeher, thank you for your comments. I updated the answer adding the additional conditions. Also added information about the cyclic group that are typically used. $\endgroup$
    – Irfan
    Commented May 12 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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