# Collisions in Diffie-Hellman private keys

Given a generator $$g$$, a large, safe prime $$P$$ and a result of the DH key exchange $$g^{xy} \mod P$$, how would I come up with two different $$x', y'$$ s.t. $$g^{x'y'} = g^{xy} \mod P$$

• $x$ and $y$ are random. if $x$ or $y$ are factorable then you can have. – kelalaka Dec 6 '18 at 9:40
• Totally trivial answer: $x' = xy$, $y'=1$ – poncho Dec 6 '18 at 15:07

## 1 Answer

In DHKE, Alice and Bob chooses random $$x$$ and $$y$$, $$1 \leq x,y < n$$, respectively.

For simplicity assume that $$x$$ is a product of two primes $$x = r \cdot s$$

Then set $$x' = r \neq x$$ and $$y' = s \cdot y \neq x$$ then $$g^{x'y'} = g^{rsy}=g^{xy}$$ will be another pair.

if $$x$$ and $$y$$ are primes then there are two cases $$xy < \varphi(P)$$ and $$xy > \varphi(P)$$ that will result in the same equation that need to be solved.

$$xy \equiv x' y' \mod \varphi{(P)}\;\;, 1 \leq x',y < n$$

• Is it possible if $x$ and $y$ are prime? – dc3cdd1fc7 Dec 6 '18 at 9:50
• there can be due to the modulus operation. You can use this to find a case. – kelalaka Dec 6 '18 at 10:06