# Why does Diffie-Hellman need be a cyclic group?

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?

• Eve divides $ac$ by $c$. – yyyyyyy May 7 '15 at 8:48
• Or multiplies like this: $(ac)\cdot(bc)/(c)$ to get the shared "secret" – tylo May 7 '15 at 8:49
• @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. – poncho May 7 '15 at 11:28
• – CodesInChaos May 7 '15 at 12:23
• @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. – tylo May 7 '15 at 12:46

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$.
• One could work with a commutative magma action instead of a semigroup. $\;$ – user991 May 7 '15 at 13:56