Diffie Hellman 不安全的主要漏洞
如果使用不安全的素數 p（即， $ p-1 $ 有很多小因素）。StackExchange 上的許多答案聲稱，對於任何因素 $ r $ 在哪裡 $ g^{\frac{p-1}{r}}\neq1 $ , 如果給定 $ g $ 和 $ g^x \bmod p $ , 可以確定 $ x \bmod r $ 在 $ O(\sqrt{r}) $ 時間（見這個和這個答案）。
兩個答案中的後一個甚至包括一個方法的大綱。然而，這需要 $ A^{\frac{p-1}{r}} $ 和 $ A $ 是要計算的公鑰。對於一個大 $ A $ 和 $ p $ （比如說 4096 位）和一個小的 $ r $ （8位或更少），對我來說這似乎在計算上是不可能的。因此，我想知道如何為這個問題編寫一個可以在有限時間和記憶體中執行的解決方案。
對於一個大 $ A $ 和 $ p $ （比如說 4096 位）和一個小的 $ r $ （8位或更少），對我來說這似乎在計算上是不可能的。
其實計算很簡單 $ A^{\frac{p-1}{r}} \bmod p $ ; 一種直接的方法是使用二進制求冪算法。
如果 $ \frac{p-1}{r} < 2^n $ ，那麼這將不會超過 $ 2n $ 模乘法（因此，在您的範例中，模乘法少於 8184 個）；可以做得更好一些，但這足以表明它是實用的。
注意：您使用相同的算法在 DH 中進行計算（計算 $ g^x \bmod p $ 對於大 $ x $ ） 可行的。
注意符號（這可能會讓您感到困惑）：有時，我們會省略 $ \bmod p $ ; 在那些時候，我們假設讀者會明白我們不是在工作 $ \mathbb{Z} $ ，而是在現場 $ \mathbb{Z}/p $ ，因此 $ \bmod p $ 操作是隱式的。這類似於在其他數學分支中，假設您知道我們是否在工作 $ \mathbb{Z} $ 或者 $ \mathbb{R} $ 或者 $ \mathbb{C} $ …