破解 diffie-hellman
我想製作一個應用程序，展示對性能較弱的 diffie-hellman 的攻擊。我需要實現一種可以使用共享變數來計算密鑰的算法。在尋找資源時，我不斷遇到 logjam 攻擊。但是，我無法真正過濾掉所有 HTTP 協議資訊中的數字。
如果有人可以提供一些資源來為我指明正確的方向，或者提供如何從已知變數成功計算密鑰的公式。這將不勝感激！
編輯
我找到了這個資源，看起來很有希望。 http://index-of.es/Miscellanous/How%20To%20Backdoor%20Diffie-Hellman.pdf
第 6 頁說
要攻擊 Diffie-Hellman 密鑰交換，可以從對等方的公鑰 ya = g a (mod p) 中提取密鑰 a。然後可以使用另一個對等方的公鑰 yb = g b (mod p) 計算共享密鑰 g ab (mod p)。
解決這個問題的簡單方法是計算 g 的每個冪（同時跟踪指數），直到找到公鑰。這稱為試乘法，平均需要 q 2 次操作才能找到解決方案（q 是基數）。以預期 √q 步計算離散對數的算法更有效
我把它翻譯成
計算 g 的每個冪
g^1 mod(p), g^2 mod(p), g^3 mod(p)..g^n mod(p)這會起作用，但是它需要將指數從公式中分離出來才能起作用。這對我來說很難。
你將如何
a隔離p^a mod(p)
對 Diffie-Hellman 的一個有趣的密碼分析攻擊是小子群限制攻擊。如果不小心選擇了 DH 參數，則攻擊會起作用。以下是有關其工作原理的簡要說明。
DH 在乘法組中工作。假設我們正在工作 $ Z^*_p $ . 作為 $ p $ 是素數，這個群的階（ $ p-1 $ ) 是複合的，因此根據拉格朗日定理存在子群。攻擊者通過乾擾通信並對其進行修改，基本上將密鑰空間減少到具有更小訂單的這些子組之一。
讓我們的DH組成為 $ (Z_p^,) $ 和 $ \alpha $ 成為使用的原始根。通常 Alice 計算一個隨機數 $ s_a $ 並保密。愛麗絲發送 $ \alpha^{s_a} $ 給 Bob，但攻擊者 Eve 先收到它。Eve 通過搜尋因子來查找可能的子群 $ (p-1) $ 並找到一個小因素 $ q $ . 根據拉格朗日定理，她知道存在一個有序子群 $ q $ . 她計算 $ t=\frac{p-1}{q} $ 並發送鮑勃 $ (\alpha^{s_a})^t $ . Bob 還計算了他的秘密隨機值 $ s_b $ 併計算共享密鑰 $ (\alpha^{ts_a})^{s_b} $ . 然後 Bob 發送 Alice $ \alpha^{s_b} $ 但夏娃攔截。夏娃送愛麗絲 $ (\alpha^{s_b})^t $ Alice 還將共享秘密計算為 $ (\alpha^{ts_b})^{s_a} $ . 兩者都有共同的秘密，是的，但他們的共同秘密是有形式的 $ (\alpha^t)^x $ . 這種形式的數字由帶有生成器的子組生成 $ \alpha^t $ 已知是有序的 $ q $ . 作為 $ q $ 很小（由於我們假設 DH 參數選擇不當），Eve 可以簡單地通過蠻力計算 DH 離散對數問題，因為試驗要少得多。
如何保護？
挑選 $ p $ 這樣 $ p=2q+1 $ 在哪裡 $ q $ 也是一個素數（參見Sophie-Germain primes）。有了這個屬性，組順序將是 $ p-1=2q $ . 作為 $ q $ 是質數，只有因數 $ p-1 $ 是 2 和 $ q $ . 因此，在與 DH 設置共享密鑰時，請檢查您的組順序是否為 2。如果是這種情況，您就知道自己受到了攻擊。