Why is it hard to compute $$(g^x\bmod p, g^y\bmod p) \longmapsto g^{xy}\bmod p $$ when can we quickly compute $$x \longmapsto g^x\bmod p$$ ?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Does this answer your question? What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman? and Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y? $\endgroup$– kelalakaCommented Dec 9, 2021 at 16:51
-
$\begingroup$ The present question is not really a dupe of this question, but the later's accepted answer covers the present question to a large degree. Short answer: because we do not know an efficient method. Fact: one method would be to find $x$ and use $g^{xy}\bmod p\ =\ (g^y\bmod p)^x\bmod p$, but we do not know an efficient method to compute $x$ from $g^x\bmod p$. $\endgroup$– fgrieu ♦Commented Dec 9, 2021 at 17:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
I believe you are asking a question about DH exchanging key protocol.
In DH, A creates a random private key of x and then will send the 𝑔𝑥mod𝑝 to B.
so nobody knows the X, although everyone can see the 𝑔𝑥mod𝑝 they cannot get the x from it, because of DLP (Discrete Logarithm Problem).
-
1$\begingroup$ This does not answer the question. $\endgroup$– MaeherCommented Dec 9, 2021 at 19:47
-
$\begingroup$ A bit more going into depth would have helped here, you could have explained that you'd need $x$ to calculate $(g^x\bmod p, g^y\bmod p) \longmapsto g^{xy}\bmod p$ I suppose. As it stands, just saying that DH is considered secure because of DLP doesn't really touch the question at hand. That said, a bit more direction could have helped instead of just downvotes and negative comments. $\endgroup$– Maarten Bodewes ♦Commented Dec 10, 2021 at 22:53