Logjam：為 TLS 開發人員和系統管理員解釋“複合訂單子組”？
我已經閱讀了最近的僵局論文Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice。
在該
Recommendations部分的第 11 頁，他們指出：避免固定素數組從中期來看，採用協商的 Diffie-Hellman 組可以幫助減輕由 NFS 風格的預計算對非常常見的固定組造成的一些損害。目前的 IETF 草案
$$ 18 $$建議對 TLS 進行協商的組擴展。但是，我們注意到可以創建陷門素數$$ 43 $$在計算上難以檢測。至少，應檢查素數是否為安全素數，或者組應使用可驗證的生成過程，例如 FIPS 186 中提出的過程$$ 37 $$，並且應該修復在 TLS 會話中生成素數的過程，以阻止陷門的風險。
雖然這在數學上比這節要輕鬆，但
Attacks on Composite-Order Subgroups我仍然不知道這在實現、算法和庫方面意味著什麼。在該頁面的下方，他們還指出
這種情況的一個重要教訓是，密碼學家和實際系統的創建者需要更好地溝通。
因此，作為一名從事涉及 TLS 內部實現的項目的軟體人員，我希望數學家/密碼學家向我們解釋沒有群論背景的人（如果可能）什麼是“選擇安全素數”，並選擇發電機 $ g $ 它“生成一個具有至少一個足夠大的子組順序的組”（第 6 頁，
Attacks on Composite-Order Subgroups），以及這對我編寫的程式碼、我實現的算法和我呼叫的庫意味著什麼。外行的解釋，或指向用於生成 DHE 參數的群論相關算法的指針會很棒。
安全素數是素數 $ p $ 為此 $ (p-1)/2 $ 也是素數。元素的順序 $ g $ 該組的 $ \mathbf{Z}^*_p $ （整數模 $ p $ , 不包括 0) 是最小整數 $ n $ 這樣 $ g^n\equiv 1\pmod{p} $ ; 這始終是一個因素 $ p-1 $ . 生成的組的子組的順序 $ g $ 是順序的因素 $ g $ ; 對安全來說重要的是，至少一個順序的主要因素 $ g $ 很大（對於安全素數，如果 $ g $ 不是 1 或 2 那麼它的質因數為 $ (p-1)/2 $ ，很大）。如果你選擇一個不是安全素數的素數，你需要確保 $ g $ 是至少一個大素數的倍數；嘗試確保它不是許多小素數的倍數和/或選擇一個大指數也很重要。
您可以在RFC 3526中找到良好的安全素數。你也可以自己生成；嘗試很多大奇數並檢查兩者是否 $ p $ 和 $ (p-1)/2 $ 是素數。然後你選擇 $ g $ 這樣 $ g^2\not\equiv 1\pmod{p} $ ，你很好（因為這意味著 $ g $ 是的倍數 $ (p-1)/2 $ ）。有了一個安全的素數，最糟糕的情況是你的指數的最後一點洩漏，這對於相當大的指數來說沒什麼大不了的（所以你甚至不需要選擇太大的指數來保證安全）。
以下是關於為什麼這很重要的更詳細的背景。我試圖以一種你可以在沒有先前背景的情況下理解的方式來解釋它背後的數學，但我不確定我做得如何。
群論
Diffie-Hellman 密鑰交換是在 group 中完成的，它是一組元素和一個具有許多不錯屬性的操作。在 Diffie-Hellman 中，這個群是模素數的整數 $ p $ , 不包括的任何倍數 $ p $ （所以，之間的數字 $ 1 $ 和 $ p-1 $ 是組的元素），運算是乘法。一個組有一組與之關聯的元素；如果這些元素的子集是同一操作下的組，則稱為子組。 Diffie-Hellman 更具體地發生在生成器生成的子組中 $ g $ , 表示包含的最小子群 $ g $ . 該子組由可以寫成的所有內容組成 $ g\times g\times\cdots\times g $ （或者 $ g^n $ ）。該子群的階（也稱為 $ g $ ) 是子群中的元素個數，等於最小的 $ n $ 在哪裡 $ g^n\equiv 1 \pmod{p} $ （一旦你達到 1，你就開始重複自己）。這個子群的階總是主群階的一個因子（對於 Diffie-Hellman 來說總是 $ p-1 $ ); 這適用於所有組和子組。
最後，一個數論事實：如果 $ g $ 是 $ r $ ， 然後 $ g^x\equiv g^y\pmod{p} $ 當且僅當 $ x\equiv y\pmod{r} $ . 這意味著暴力破解 $ e\equiv g^x $ 只需要嘗試所有值 $ x $ 介於 0 和 $ r-1 $ .
複合訂單
複合順序子組聽起來像：子組的順序由 $ g $ 不是素數。在這種情況下，如果您有 $ e=g^x\pmod{p} $ 並試圖找到 $ x $ ，您可以將問題分解為解決較小子組上的離散對數問題。 例如，假設 $ g $ 是 220。那麼 $ e^{44}\equiv (g^x)^{44}\equiv (g^{44})^x\pmod{p} $ . 的順序 $ g^{44} $ 是 $ 220/44=5 $ （因為 $ (g^{44})^5=g^{220}\equiv 1 $ ）。所以，任何 $ y $ 為此 $ (g^{44})^y\equiv e^{44} $ 是一致的 $ x $ 模 5。我們可以解決這個 5 階子組上的離散對數問題，以找到 $ x $ 模 5。同樣，我們可以找到 $ x $ mod 11 通過求解一個 11 階子組的離散對數。因為順序 $ g $ 是的倍數 $ 2^2 $ ，我們需要從本質上解決兩個 2階離散對數問題：第一個得到 $ x $ mod 2，然後使用它我們解決另一個得到 $ x $ 模式 4。
一旦你有了價值 $ x $ 模數的所有素因數的所有冪 $ g $ ，中國剩餘定理說你有足夠的資訊來唯一確定 $ x $ 對這些素數的冪的乘積取模（即取模的階數 $ g $ ）。這樣做實際上非常快（順便說一句，這也是對具有多個收件人的教科書 RSA 進行攻擊的基礎，您可以在其中得到 $ m^e $ 模很多不同的值，可以計算出真實的 $ m^e $ ）。因此，您不必在 220 元素組上求解離散對數，而是在 11 元素組、兩個 2 元素組和一個 5 元素組上求解。
此外，作為 $ g $ 是組順序的一個因子，將組的順序分解（即 $ p-1 $ ) 讓您攻擊該組中的任何生成器。這意味著攻擊者可以提前做一些工作，讓他們攻擊任何使用給定值的 Diffie-Hellman $ p $ .
減輕
解決這個問題的方法是確保順序的主要因素之一 $ g $ 很大；你的力量本質上是由數量級的最大素數的大小給出的力量 $ g $ ，所以你想最大化它。最簡單的方法是選擇一個安全的素數—— $ (p-1)/2 $ 也是素數。使用安全素數，任何元素的順序（記住，必須除 $ p-1 $ ) 是 1、2、 $ (p-1)/2 $ ， 或者 $ p-1 $ . 很容易檢查你的發電機沒有訂單 $ 1 $ 或者 $ 2 $ ，如果不是，那麼它的順序有一個很大的素數（ $ (p-1)/2 $ ). 如果事情不是安全的素數，你仍然可以有安全的選擇 $ g $ 如果你有一個大的主要因素 $ g $ . 然而，所有的小因素的順序 $ g $ 洩露有關您的指數的一些資訊；如果您有很多小因素並選擇了一個較小的指數（這通常很好），您最終可能會洩露很多關於您的指數的資訊。安全素數意味著最多只有一個小因子的數量級 $ g $ ，因此您不必嘗試許多可能的值就不會洩漏太多資訊 $ g $ 得到一個沒有很多小因素或有很大因素的人。