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$
In DHKE, Alice and Bob chooses random $x$ and $y$, $1 \leq x,y &lt; 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 &lt; \varphi(P)$ and $xy &gt; \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 &lt; n$$