最先進的 RSA 密鑰生成
我想知道是否有一種算法可以在目前的密碼分析技術中生成 RSA 密鑰。
除了關鍵長度之外，我知道在選擇素數方面存在一些弱點，可以幫助攻擊者分解模數 $ N $ .
據我所知，標準密鑰生成會生成正確長度的隨機數，並嘗試將其分解為小因子（例如 $ \leq 10000 $ )，然後進行一個或多個素性檢驗（如 Fermat 和 Miller-Rabin），直到置信水平足夠高。
但是風險呢？ $ p-1, q-1 $ 有小因素嗎？
人們一致認為使用隨機素數是安全的 $ p $ 和 $ q $ 生成 2048 位（或更寬）的 RSA 公共模數時，它有兩個素數 $ p $ 和 $ q $ 大約是密鑰大小的一半。這是由FIPS 186-4附錄 B.3 批准的；具體而言，B.3.1 項 A 中的措辭：
使用方法 1 和 2
$$ yielding provable (1) and probable (2) random primes $$, $ p $ 和 $ q $ 可以生成長度為 1024 或 1536 位的； $ p $ 和 $ q $ 不應使用這些方法生成長度為 512 位的。反而， $ p $ 和 $ q $ 應使用基於輔助素數的條件生成長度為 512 位的。
儘管 FIPS 186-4 要求（在本引文的第二部分） $ p-1 $ , $ q-1 $ , $ p+1 $ , $ q+1 $ 生成 1024 位密鑰時至少有一個已知的大素因數，其中兩個素因數 $ p $ 和 $ q $ 是 512 位的，許多人認為這是不必要的複雜性。
要求這樣做的理由 $ p-1 $ （和 $ q-1 $ ) 至少有一個重要因素是確保抵抗Pollard 的 p-1因式分解。這種預防措施在超過一定規模後變得毫無意義的標準理由是，我們擁有具有更好漸近執行時間的分解算法（包括GNFS和ECM ）；如果我們添加：對於任何固定的成功機率[幾乎同樣適用於要求 $ p+1 $ （和 $ q+1 $ ) 至少有一個大因數，這將是為了防止Williams 的 p+1因式分解；而當我們不需要防范波拉德的 p-1 時，我們也不需要防范威廉姆斯的 p+1，因此我忽略了後者]。
定量地確定我們何時可以免除針對 Pollard 的 p-1 的預防措施並非易事！
- 有一種觀點認為，如果參數使我們對 ECM 足夠安全，我們也可以對 Pollard 的 p-1 安全。這個論點是錯誤的（這並不排除它得出正確的結論），至少當我們考慮在對手滿足於分解任何一個的上下文中生成許多密鑰時 $ k $ 密鑰，而不是某個密鑰（例如，對手的目標是通過一些簽名檢查，並且她知道許多可以發出有效簽名的實體的公鑰證書，這在機器對機器應用程序中很常見）。反駁：從比率的角度來看， Pollard 的 p-1優於ECM $ \text{odds to factor}\over\text{computing effort} $ 因式分解隨機整數時計算工作量低（因此，在GMP-ECM中，Pollard 的 p-1 花費了大量時間，取得了巨大成功）；擴展（具有相當的優勢）以分解作為指定大小的隨機素數乘積的整數；這個比率是最重要的，只要一個數字 $ k $ 鍵數不會成為限制因素。
- 有一種觀點認為 GNFS 比 ECM 好得多，以至於它超越了 Pollard 的 p-1 在密碼學參數方面可能優於 ECM 的任何優勢。該論點適用於 RSA 模數（取決於先前的考慮） $ N $ 有兩個大小大致相等的質因數。但它不適用於何時 $ N $ 有一個因素 $ p $ 遠小於一半 $ N $ ，這是多素數 RSA 的情況（參見PKCS#1）和不平衡 RSA 中的RSAP 和 SPAKE/ALIKE，例如考慮 1248 位 $ N $ 帶有 352 位 $ p $ , 預計提供 80 位安全性$$ for some definition of that; these parameters are supposed to balance GNFS and ECM $$.