Diffie-Hellman 密鑰交換，為什麼很難破解？

我有點困惑為什麼很難打破 Diffie-Hellman

讓我們舉個例子

愛麗絲有G, a, and n

鮑勃有G, b and n

Eve（第三方）成功攔截G，n， $ G^a, G^b $

ALICE 生成密鑰G^(ab) mod n

BOB 生成相同的密鑰G^ba mod n

我不明白的是為什麼 Eve 不能通過知道來獲得a or b。G^a and G^b？

對我來說，他可以使用二分法：

Eve 將隨機抽取一個數字r_a。

   if G^r_a$ < G^a /* already known */
       increase(r_a); /* by power ietration for example, +1 +100, +1000, +10000 */
   else 
       decrease(r_a);
   adjust(r_a);

您概述的直接方法不起作用，因為 $ G^a $ 不是單調的 $ a $ ; 我們可以有 $ G^{r_a} < G^a $ 雖然 $ r_a > a $ . 發生這種情況是因為我們正在模數工作 $ n $ ，而不是對實數或整數進行取冪。

例如，如果我們有 $ n=101 $ 和 $ G=2 $ （對於一個玩具範例），那麼我們有：

$$ G^8 = 54 > G^{10} = 14 $$

雖然 $ 8 < 10 $

事實上，一個實用的方法來做機率

$$ 1 $$評價是否 $ a < b $ 給定 $ G^a \bmod n, G^b \bmod n $ （對於值 $ n $ 我們實際上在密碼學中使用）會引起極大的興趣（並且基本上會破壞所有基於模冪的加密）

---

$$ 1 $$通過機率評估，我的意思是該方法不必在所有情況下都給我們正確的答案；如果它是正確的且機率略大於 0.5 就足夠了

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