是否有任何標準的多質 RSA 密鑰生成？
FIPS 186-3 指定了一種生成 DSA 參數的方法。
是否有任何類似的（官方標准或廣泛接受的推薦）顯示如何為多素數 RSA 生成素數？
PKCS#1v2支持多素數 RSA（也稱為 RSA-MP）。該標準支持公鑰 $ (n,e) $ 其中模量 $ n $ 是的產品 $ u≥2 $ 不同的奇數素數： $ n=\prod_{i=1}^u{r_i} $ ， 和 $ 1<e<n $ 和 $ \gcd(r_i-1,e)=1 $ （暗示 $ e $ 奇怪的）。私人指數 $ d $ 是這樣的 $ 1<d<n $ ， 和 $ e⋅d≡1\pmod{\operatorname{lcm}_{i=1}^u(r_i-1)} $ . 無其他要求 $ (n,e,d) $ 由 PKCS#1v2 給出。RSA-MP 是 $ u>2 $ . 製作 $ u=2 $ , $ p=r_1 $ , $ q=r_2 $ ，然後您又回到了 PKCS#1v1 中的 RSA。
我不知道有關生成 RSA-MP 密鑰的標準。但是，對於有關位大小問題的建議 $ n $ 和因素的數量 $ u $ ，一篇值得推薦的論文是Unbelievable Security: Matching AES security using public key systems，作者：Arjen K. Lenstra。尤其參見綜合表 $ u:⌈\log_2\min(r_i)⌉ $ 對於給定的安全級別（以位為單位，2K3DES 95 位），在給定的年份（該參數考慮了作者對算法改進的評估，但不考慮摩爾定律），並根據兩個模型。
更正：即使在 2K3DES 級別（對於從 Y2010 開始的任何條目）也遵循該大小建議，添加大約 $ 32/u $ 每年位數來解釋摩爾定律（以前忘記了！），並且隨機選擇一個密鑰的素數，我認為在該表的 Y2030 限制之前，無需擔心*對該密鑰的因式分解攻擊。*請注意，我的背書假設對手對在極多的隨機密鑰中分解單個隨機密鑰沒有太大興趣。
我也喜歡簡短且圖形化的 Multi-prime RSA trade offs，儘管它僅限於 2048 位模數。
要考慮的主要事項 $ \log_2n $ , $ \log_2r_i $ ， 和 $ u $ ， 是：
- $ n $ 應該足夠大，以至於 GNFS 分解是不可怕的。對於正常 RSA 和 RSA-MP，考慮因素是相同的，因為多重性 $ u $ 因素或它們的大小 $ \log_2r_i $ , 不影響 GNFS 的預期執行時間；只要 $ \log_2n $ 很重要。
- 每個 $ r_i $ 應該足夠大 $ n $ 不受已知算法分解的影響，該算法主要受提取的因子大小（而不是因子的複合大小）的影響，特別是ECM（在這些算法中，ECM 最有可能分解一個特定的鍵）。在正常 RSA 中，習慣上選擇大小相等（或幾乎相等）的兩個素數：這使得 GNFS 極有可能在很大程度上包含所有其他已知的分解算法，包括 ECM。但是，這不適用於 RSA-MP。在找到一個的同時 $ r_i $ 本身並不能偽造簽名或破譯，它仍然必須被認為是一場致命的災難，因為 GNFS 可以解決複合的因式分解 $ n/r_i $ 以大大降低的成本。因此，習慣上根據 ECM 執行時間的估計來選擇因子的最小大小（考慮一個函式 $ \log_2r_i $ , 往往忽略了相對邊際的影響 $ \log_2n $ ).
- 那麼最好的選擇 $ u $ 是 $ {\log_2n}\over{\log_2r_i} $ , 在某個方向上四捨五入。
為此，我相信前面提到的Unbelievable Security。
關於選擇的細節應考慮到通常 $ ⌈\log_2n⌉ $ 是規定的，在這種情況下，我們可能會使用 $ \log_2r_i\approx ⌈\log_2n⌉/u $ ; 如果沒有，四捨五入通常很少或沒有性能成本 $ ⌈\log_2r_i⌉ $ 直到下一個字長的倍數，例如 32 位或 64 位，然後使用 $ log_2n\approx ⌈\log_2r_i⌉⋅u $ .
除了 PKCS#1v2 中的要求之外，RSA 密鑰對的密鑰生成標准通常會增加額外的要求。FIPS 186-3是一種被廣泛接受的標準，在 B.3.1 節中有以下要求；我正在盡力給出理由：
- 公共指數 $ e $ 應核實 $ 2^{16}<e<2^{256} $ . 下限在這裡是因為對基於 RSA 的不良方案的一些攻擊通常在以下情況下更容易 $ e $ 是小; 上限是公鑰操作的互操作性。
- 位大小為 $ n $ , $ nlen=⌈\log_2n⌉ $ , 應為 1024、2048 或 3072（注意：在 FIPS 186-3 的附錄 B.3.1 中，指的是 1024 位、2048 位和 3072 位素數；應理解為 $ n $ ，雖然那是複合的）。有限的選擇最大化了公鑰的關鍵互操作性；下限還強制執行基線安全性（根據NIST 特別出版物 800-131A，對於簽名生成，1024 位在 2010 年之前是可以接受的，從 2011 年到 2013 年不推薦使用，並且在 2013 年之後不允許使用）；一些人認為缺少 4096 位或更多位表明 ECDSA 是可行的方法。
- 主要因素 $ p $ , $ q $ 的 $ n $ 應在範圍內 $ [2^{(nlen-1)/2},2^{nlen/2}] $ ; 這主要是為了簡化跨實現的私鑰的互操作性。
- $ |p–q|>2^{nlen/2–100} $ ; 這是 ANSI X9.31 的遺產，在 AFAIK 中，它被引入作為一種簡單的方法來反駁修辭論點“但即使是 Pierre de Fermat 也知道一種可以擊敗 RSA 的分解算法”。
- 素數 $ p $ 和 $ q $ 應使用相同的算法隨機選擇（與 $ e $ 一個輸入），從幾個批准的算法中選擇，分為兩個主要類別（隨機素數和帶條件的隨機素數，根據素數是可能的素數還是可證明的素數進行細分）。這避免了糟糕的算法，防止優化 $ d $ , $ dP $ , $ dQ $ 提供有問題的安全性，並簡化實施的驗證，甚至允許已知答案測試。
- 這些批准的算法是這樣的 $ p $ 512位， $ p-1 $ （分別。 $ p+1 $ ) 應有一個質因數 $ p_1 $ （分別。 $ p_2 $ ) 超過 100 位；同樣的 $ q $ ; 如果使用類似的條件（這是可選的） $ p $ 1024 位（分別為 1536 位），應該超過 140 位（分別為 170 位）。這些要求旨在為Pollard提供保險 $ p-1 $ 和威廉的 $ p+1 $ 因式分解算法。
- 這些經過批准的算法帶有最大的素數 $ p_1 $ 和 $ p_2 $ 在 (6.) AFAIK 中討論過，這只是排除了選擇這些素數 $ p_1 $ 和 $ p_2 $ 大到素數的選擇 $ p $ 減少到這成為一個問題的地步。
如果我不得不提議改編 FIPS 186-3 來生成 RSA-MP 密鑰，它可能是：
- 不變（雖然我個人會選擇 $ e=2^{16}+1 $ ; 如果你問，我會放寬下限 $ e=3 $ ，在使用好的方案時不會影響安全；但這與 RSA-MP 無關）。
- $ nlen=⌈\log_2n⌉ $ 在 1024、2048 或 3072 中實現與基於 FIPS 的簽名驗證設備的完全互操作性；或改為 $ 1024≤nlen≤16384 $ 和 $ nlen≡0\pmod{64} $ 在與潛在的簽名驗證者達成協議的條件下，以獲得更大的靈活性和未來的開放性。建議 $ nlen $ 和 $ u $ 基於上面的令人難以置信的安全參考，雖然 $ u≤nlen/512 $ 無論。
- 適應 $ 2^{64⋅⌊(nlen/64+i−1)/u⌋-1/u}<r_i<2^{64⋅⌊(nlen/64+i−1)/u⌋} $ . 這確保 $ ⌈\log_2r_i⌉≡0\pmod{64} $ , $ ⌈\log_2\prod_{i=1}^u{r_i}⌉=nlen $ , 最多兩個不同的 $ ⌈\log_2r_i⌉ $ .
- 替換為任意兩個測試 $ r_i $ 至少在它們的 100 個高位中的一個上有所不同（更多是為了捕捉錯誤而不是擔心費馬因式分解）。
- 保留“帶條件的隨機素數”類別的算法，僅調整已批准算法的參數；見下文 (6.) 中的理由。
- 保留，並要求 $ ⌈\log_2p_1⌉ $ 和 $ ⌈\log_2p_2⌉ $ 超過 $ 60+5⋅⌈\log_2p⌉/64 $ . 這會線性縮放 FIPS 186-3 中的值 100 和 140，並刪除忽略該值的選項 $ ⌈\log_2p⌉>1024 $ 通過使用“隨機素數”類別中的算法。我的觀點是這個要求在 RSA-MP 的背景下是有意義的：一個理性的對手內容不應該開始在一個或幾個模數上使用 ECM；而是應該首先在所有模數上嘗試 Pollard 的 p-1，因為 ECM 策略對於給定的努力具有明顯較小的成功機會（論點：Pollard 的 p-1 通過使用最先進的因子分解有很大的好處諸如 gmp-ecm 之類的程序；另請參閱此相關答案）。
- 保留；這真的只是沒有改變批准的算法。
如果您認為 RSA 密鑰的安全性很容易分解（還有其他考慮因素），那麼您顯然應該使它們具有相同的大小。
你可以認為一個傳統的 N 位密鑰由兩個素數組成，但你也可以換一種方式看待它——你取兩個素數 $ M_1 $ 和 $ M_2 $ 位長並產生一個密鑰 $ M_1 + M_2 $ 位長。
很明顯，您希望素數的大小相當接近，並且讓它們具有相同的位長長度只是一個好習慣。如果它們是不平衡的，那麼計算這個數字會更容易。
我們可以將其擴展為您想要多素數 RSA，您也希望它們都具有大致相同的大小。以由兩個 1000 位素數和一個 48 位素數組成的 2048 位 RSA 密鑰為例。直接聲明此密鑰與 2000 位雙素數密鑰具有相同的強度是很簡單的，因為它很容易分解出 48 位素數。如果你告訴人們你已經這樣做了，他們會說你扔掉了 48 位。
如果您創建一個帶有不平衡質數的雙質 RSA 密鑰並告訴人們，他們會理所當然地被激怒。有人可能會爭辯說，多質 RSA 密鑰的主要原因是擁有一個安全性縮短的長密鑰。我相信這就是您通常看不到它們的原因。除了讓加密變得更弱之外，很難知道你正在解決什麼問題。