Lets say there are 2 parties X and Y. They have agreed on prime number P and generator g. X uses the secret key K. After the key exchange they calculated the common secret key g^4.
What are the 2 possible values for the secret key of Y?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
That the parties have agreed on a DH secret means the following: $$g^4=(g^K)^Y=g^{KY}\pmod P$$ Now we can just look at the exponents: $$4=KY\pmod{P-1}$$ Which may or may not have the unique solution for $Y$: $$Y=4\cdot K^{-1}\pmod{P-1}$$
That is if $\gcd(K,P-1)>1$ and we know that $K^{-1}$ must exist, then it will have multiple possible values. The precise values depend on $P$ and $K$.
