Diffie-Hellman
除以222或 DH oracle 的主根
認為 $ g $ 是乘法群模素數的生成器 $ p=2q+1 $ 在哪裡 $ q $ 是素數。
假設我們知道 $ g^{2t}\bmod p $ 和 $ g^{2}\bmod p $ 並假設我們可以訪問 Diffie-Hellman 預言機。
我們能找到嗎 $ g^t\bmod p $ 在多項式時間內？
請注意，如果我們可以做到這一點，我們可以在生成器順序為偶數時通過訪問 DH 預言機來破壞離散日誌。
我們能找到嗎 $ g^t \bmod p $ 在多項式時間內？
我們可以找到 $ g^t $ 或者 $ -g^{t} = g^{t + (p-1)/2} $ ; 顯然，我們無法根據我們獲得的資訊判斷哪一個是正確的。
因為 $ p \equiv 3 \pmod 4 $ （因為 $ (p-1)/2 $ 假定為素數，並取 $ p=5 $ 表外 - 可以作為特殊情況處理），然後
$$ 1 $$我們可以用簡單的計算來計算模平方根 $ \sqrt{x} = \pm x^{(p+1)/4} $ . 所以，我們有 $ g^t \in{ -(g^{2t})^{(p+1)/4},+(g^{2t})^{(p+1)/4}} $ , 在 polytime 中很容易實現。
$$ 1 $$： 如果 $ p \equiv 1 \bmod 4 $ ，那麼計算模平方根仍然是實用的，它有點複雜。