具有復合 p 的 DSA
DSA 的基本要求之一是選擇一些素數 $ p $ 一定的位長。安全性在於解決問題的難解性 $ y = g^x \pmod{p} $ 為了 $ x $ .
是否有任何*“簡單”*的方法來解決離散對數問題？ $ p $ 是複合的嗎？我想到了中國剩餘定理，但似乎無法弄清楚它是如何工作的。如果沒有明顯的方法來解決 $ p $ 複合那麼需要什麼 $ p $ 成為素數？
是否有任何“簡單”的方法來解決離散對數問題？ $ p $ 是複合的嗎？
如果你知道分解 $ p = rs $ ，則可以歸結為解決問題 $ y = g^x \pmod r $ 和 $ y = g^x \pmod s $ ，然後結合這兩種解決方案；因此，您將問題的難度降低到更難的程度 $ r, s $ 子問題。
如果你不知道分解 $ p $ ，那麼它至少和因式分解一樣困難 $ p $ （如果你可以解任意離散對數模 $ p $ ，那麼你可以考慮 $ p $ ).
這意味著產生的人 $ p $ 也許可以給自己一個後門（因為他比其他人更容易解決離散日誌）。
另一方面，這不是完整的故事。
您指定了 DSA；DSA 對其執行的組提出了更多要求。一方面，它實際上在一個素數大小的子組中執行，該子組比模數大小要小得多，並且必須在全域參數中列出（因為驗證者需要它）。而且，如果你想知道，子群是素數這一事實很重要，如果它是複合的，你可以分解它，並獨立地攻擊每個因素。
所以，假設我們有 $ p = rs $ （分解是秘密的），我們有一個生成器 $ g $ 和 $ g^q = 1 \pmod p $ （對於一些中等大小的素數 $ q $ ).
這立即意味著我們有 $ g^q = 1 \pmod r $ 和 $ g^q = 1 \pmod s $ ; 但是，如果我們有 $ g = 1 \pmod r $ , 然後一個簡單的計算 $ \operatorname{gcd}(g-1, p) $ 將揭示因式分解，因此為了安全，我們必須有 $ g \ne 1 \pmod r $ 和 $ g \ne 1 \pmod s $ .
這意味著 $ r - 1 = 0 \pmod q $ 和 $ s - 1 = 0\pmod q $ ，或者換句話說，我們有：
$$ p = (aq +1)(bq+1) $$ 在哪裡 $ q $ 是公開的，並且 $ a, b $ 是一些未知的整數。
如果我們通過大小 $ q $ （可能是 256 位），以及 $ r = aq+1 $ , $ s = bq+1 $ （可能每個 1024 位，因此 $ a, b $ 每個可能是 768 位），目前尚不清楚目前基於格的分解方法是否可行，但它比任何人都相信的更接近。