3
$\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
    May 7, 2015 at 8:48
  • $\begingroup$ Or multiplies like this: $(ac)\cdot(bc)/(c)$ to get the shared "secret" $\endgroup$
    – tylo
    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
    May 7, 2015 at 11:28
  • $\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
    May 7, 2015 at 12:46

2 Answers 2

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$
2
$\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
    May 7, 2015 at 13:56

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.