破解 Diffie Hellmann 協議的修改版本

我正在修改 Diffie Hellman 協議如下：我們得到一個大素數 $ p $ 和指數 $ x $ 這樣 $ 0 \lt x \lt p-1 $ 和 $ \mathrm{gcd}(x, p-1) = 1 $ . 我們也選擇 $ g $ 如 $ 1 \lt g \lt p-1 $ .

我們也得到 $ y = (g^x) \bmod{p} $ . 本質上，我們知道素數 $ p $ , 指數 $ x $ 和結果 $ y $ . 但 $ g $ 是保密的。

這類似於 Diffie Hellman 協議，除了指數 $ x $ 被公開，而 $ g $ 是保密的。所以我試圖找出是否有一種有效的方法來確定秘密 $ g $ 或者這也是一個離散對數問題？

是的，有一個簡單的方法可以恢復 $ g $ :

$$ g = y^{x^{-1} \bmod p-1} \bmod p $$ 這是有效的，因為乘法組 $ \mathbb{Z}_p^* $ 有訂單 $ p-1 $ ， 因此 $ g = g^{x \cdot x^{-1}} = (g^x)^{x^{-1}} = y^{x^{-1}} $

引用自：https://crypto.stackexchange.com/questions/58063