Diffie-Hellman 的非素數模數如何允許後門？
最近有人發現在 unix 工具中使用的 Diffie-Hellman 模數 (
socat) 不是素數。這導致一些人大喊“後門”。我不明白的是，這怎麼可能允許後門？
我猜這個問題可能是小型子群攻擊。但這可能與模數為素數時一樣嚴重。或者更好：一個非素數群可以有一個大素數子群，而一個素數群可以有小的素數子群。
想法？
似乎 Pohlig-Hellman 可能是一個答案：您可以計算平滑順序組中的離散對數。有人開始測試非素數模數的小因數，發現 3684787 = 271 x 13597 作為一個因數。似乎找不到任何其他“簡單”因素，那麼這是否意味著即使對手知道分解，Pohlig-Hellman 也不會工作？（他需要小因素，而不僅僅是已知因素。）
從那以後我寫了一篇論文來回答這個問題（當然在Poncho的大力幫助下）
我發現了很多實現後門的方法，有些是“ Nobody-But-Us”（NOBUS）後門，而有些則不是（我還在論文中為 NOBUS 提供了一些“安全性”）。
我們的想法是使用Pohlig-Hellman研究一種將後門注入 DH 的自然方式：
這裡的模數 $ p $ 是素數，所以我們可以自然地計算我們組中公鑰（元素）的數量： $ p-1 $ . 通過分解這個數字，您還可以獲得可能的子組。如果你有足夠的小子組 $ p_i $ 然後你可以使用中國剩餘定理將你找到的許多部分私鑰拼接成真正的私鑰。
這裡的問題是，如果你能做 Pohlig-Hellman，這意味著子群 $ p_i $ 足夠小，任何人都可以通過因式分解找到它們 $ p-1 $ .
下一個想法是隱藏這些小的子群，以便只有我們可以使用這種 Pohlig-Hellman 攻擊。
這裡主要 $ n $ 不再是一個素數了。我們改為使用RSA模數 $ n = p \times q $ . 自從 $ n $ 不再是素數，要計算新 DH 組中可能的公鑰數量，我們需要計算 $ (p-1)(q-1) $ （共素數的元素數 $ n $ ）。這有點棘手，只有我們知道 $ p $ 和 $ q $ 應該能夠計算出來。這樣，在 RSA 的假設下，我們知道沒有人能夠分解元素的數量 ( $ (p-1)(q-1) $ ) 找出有哪些子組。現在我們的小子群被我們很好地隱藏了，只有我們才能執行 Pohlig-Hellman。
當然還有更多。閱讀論文:)
這怎麼可能允許後門？
好吧，如果你對複合進行 DH 取模，如果攻擊者能夠解決 DH 問題（或 DLog 問題），對構成複合的每個素數取模，他們就可以恢復共享密鑰。
知道分解的人可以使用幾種方法比預期更容易地解決 DLog 問題。
每個素數都可以設置為承認一個小的子群攻擊（即，每個素數 $ p, q $ 有 $ p-1, q-1 $ 光滑的; 然而，這也使得因素更容易（如塞繆爾所說）。另一方面，可以有一個 $ p $ 和 $ q $ “部分平滑”；說，兩者 $ p-1 $ 和 $ q-1 $ 將包括大約 64 位的因子。這將給出一個 DLog $ O(2^{32}) $ 時間（煩人，但非常可行）；而 $ p-1 $ 因式分解方法可能需要 $ O(2^{64}) $ 時間（這可能沒有人會費心去嘗試）。
這種方法的一種變體（如果可以選擇 $ g $ 以及）是選擇 $ p-1 = 2p_1p_2 $ ， 在哪裡 $ p_1 $ 是（比方說）32 位素數，並且 $ p_2 $ 是 479 位素數，並選擇 $ g $ 所以（模 $ p $ ) 生成順序子組 $ p_1 $ . 而且，當然，你對 $ q $ . 您實際看到的 DLog 問題需要 $ O(2^{16}) $ 工作，和 $ pq $ 很難考慮（除非有人猜到 $ p_1 $ , 併計算 $ gcm(pq, g^{p_1}-1) $ ; 後門安裝程序會希望沒有人會想到嘗試這樣做）。
另一種方法是讓複合是（比方說）4 256 位素數的因子，它不需要承認小的子群。在這種情況下，知道因式分解的人可以通過解決以 256 位素數為模的 4 個問題來解決 DLog 問題；比小團體攻擊更努力；但是它仍然是實用的（並且複合材料仍然難以考慮）。
第三種方法是選擇素數 $ p $ 和 $ q $ 對SNFS友好；也就是說，這兩種形式 $ r^e + s $ ， 為了 $ r, s $ 小的。如果 $ p $ 和 $ q $ 使用不同的值 $ r $ ，這不會立即顯現出來。
所以，是的，複合模數可能是一個後門。