1
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.