多素數 RSA；對於 2048 位模數，我可以使用多少個素數？

在標準 RSA 中，模數n=p1p2 $ n=p_1 p_2 $ 是兩個素數的乘積p1,p2 $ p_1,p_2 $ 大小相同。假設我們將模數構造為多個素數的乘積p1,…,pķ $ p_1,\dots,p_k $ ， IE，n=p1p2⋯pķ $ n=p_1 p_2 \cdots p_k $ ，其中所有素數的大小大致相同。我想知道對於典型的模數大小，這在多大程度上降低了 RSA 的安全性。

讓我更具體一點。我希望安全性與使用 2048 位模數的標準 RSA 獲得的安全性相當。我可以用嗎ķ=3 $ k=3 $ （三個素數）沒有顯著的安全損失？ ķ=4 $ k=4 $ ? 最大的素數是多少ķ $ k $ 我可以使用，而不會顯著喪失安全性？假設每個素數是2048/ķ $ 2048/k $ 位長，所以所有的質因數都是等長的。

相關：另請參閱誰首先發表了對 RSA 中兩個以上素因子的興趣？，它詢問了這項技術的發明者。我在問一些稍微不同的東西；在這個問題上，我不是在問它的發明者；我問的是具體的安全級別。

如果我們考慮一個 RSA 模數ñ $ N $ 的n $ n $ 位 (n=2048 $ n=2048 $ 在問題中）的產品ķ $ k $ 約的素數n/ķ $ n/k $ 位，可以有多高ķ $ k $ 不失去安全感？這是一個在 Multiprime-RSA 被命名之前就已經研究過的問題，沒有明確的答案，除了：我們不能在不安全的方面犯錯ķ=2 $ k=2 $ .

我們為什麼要ķ>2 $ k>2 $ ?

• 對於在具有固定字長的軟體或硬體中實現的經典乘法算法（涵蓋了我所知道的所有硬體和許多軟體實現），使用此處描述的標準方法，RSA 私鑰函式可能會節省高達 1 倍的工作量關於ķ2/4 $ k^2/4 $ 相比ķ=2 $ k=2 $ ，並且在實踐中實現了很多加速；加上它允許簡單有效的並行化ķ $ k $ 核心。
• 當有硬體來執行強制最大模寬度的模乘時，增加ķ $ k $ 是增加的唯一途徑n $ n $ （因此可以防止因式分解）同時使用此硬體資源。
• 保存因子記錄的算法 [ GNFS和以前的[(MP)QS ]](http://en.wikipedia.org/wiki/Quadratic_sieve#Multiple_polynomials)ķ=2 $ k=2 $ 執行時間依賴於n $ n $ 沒有影響ķ $ k $ ; 因此，使用這些算法的因式分解攻擊的安全性在以下情況下保持不變ķ $ k $ 不斷增長n $ n $ .
• 給定一個公鑰及其證書，並（無旁通）訪問實現 RSA 私鑰功能的黑匣子X↦Xd反對ñ $ x\mapsto x^d\bmod N $ , 最有名的判斷方法ķ=2 $ k=2 $ 涉及保理ñ $ N $ ; 因此我們可以增加ķ $ k $ 無需擔心與僅與公鑰有關的設備的互操作性。

為什麼我們要立即堅持ķ=2 $ k=2 $ ?

• 自從美國標準FIPS 186-4包含 RSA 以來，這是強制要求的，並且通過參考以符合部分或全部FIPS 140；由法國官方RGS 推薦；並且幾乎每個安全機構都對這個參考網站列出的密鑰大小提出建議，上次我檢查過；然後是一些。
• 在無數的情況下ķ=2 $ k=2 $ 是唯一與周圍環境兼容的東西。智能卡領域的眾多範例中的一個：Java Card 3 Classic API。
• 雖然PKCS#1標準化了 Multi-Prime RSA 甚至是私鑰交換格式，但有些設備（包括一些聲稱與PKCS#11兼容）不支持它。如果您想將私鑰移動到其他設備，或者甚至以面向未來的格式備份機上生成的密鑰，請當心！
• 一些模冪運算硬體或軟體需要素數p $ p $ 確切的位大小是某物的倍數（通常是 2 的冪，例如 64）；這是另一個互操作性障礙（在n=2048 $ n=2048 $ ,ķ=3 $ k=3 $ ，作為 64 的倍數將強制一個素數為 640 位，而不是 683 位）。注意：可以通過在模冪運算期間將模數減少適當的素數倍數，然後進行最終減少來解決此問題。
• 至少在美國和歐洲（ US 5,848,159、US 7,231,040、EP0950302 ）已有專利（現已過期），它們對使用 Multiprime-RSA 是否會帶來法律風險產生恐懼、不確定性和懷疑。

思考時還需要考慮哪些其他事項ķ>2? $ k>2? $

1. 到目前為止，主要的一個：使用ECM進行分解攻擊的努力（以任何衡量標準）增加（比多項式更快）n/ķ $ n/k $ ，因此隨著ķ $ k $ 為常數n $ n $ . 而對手（我們必須假設，知道ķ $ k $ ) 有分解方法的選擇，如果有優勢會選擇 ECM。我所知道的所有關於決定的文獻（如下所列）ķ $ k $ 因此旨在盡可能高地選擇它，以使 ECM 的預期工作量（或執行時間、成本..）不低於 GNFS 的預期工作量，有時還會預測這些預期的未來工作量；這ķ $ k $ 當然，交叉的四捨五入。
2. ECM 很容易分佈在許多幾乎不需要相互通信的商品電腦上，而據我們所知，GNFS 中的矩陣步驟需要一個具有大量記憶體的高度連接的超級電腦（或者可能花費更多的二進制數量級）篩分步驟中的計算能力主導目前參數化的計算工作）。這在某種程度上使 GNFS 和 ECM 之間的比較無效，即考慮計算工作、工作量或執行時間，而不是一些嘗試的**成本衡量[相對較小的相關問題：據報導ECM可以利用 GPU；但這可能不是什麼爭論，因為GNFS 將來可以通過在內部使用 ECM 從 GPU 中受益]。
3. 自電腦問世以來，甚至在本世紀，當談到已發布的分解算法的未來執行時間（成本要低得多）時，我們還沒有一個精確的水晶球（這只會因為它們的相對成本而變得更糟，或者如果我們考慮未發表的改進或算法）。無論我們在 ECM 和 GNFS 之間進行什麼比較，我們對未來安全性的要求越高，我們應該在這些不確定性的基礎上採取更多的餘量，並將平衡轉向更低的ķ $ k $ （四捨五入前）。
4. AFAIK，認證實驗室沒有檢查過 Multiprime-RSA 的實施是否存在側通道攻擊。這不僅僅是一個認證問題：擔心較小的素數或最後的 CRT 步驟（獲得任何速度優勢所必需的）會使實現更容易受到側通道洩漏的影響，這並非沒有道理。至少在不受信任的環境中執行的 HSM 和智能卡中，這是一個潛在的問題。
5. 使用 ECM 時，在分數之後會發現因式分解的機率ε $ \epsilon $ 預期的工作大約是ε $ \epsilon $ （為了2−20≤ε≤0.3 $ 2^{-20}\le\epsilon\le0.3 $ 和常見的 ECM 參數）。這與 GNFS 和 QS 形成鮮明對比，在預期工作的最後百分之幾之前，我們根本無法進行分解。如果我們想要剩餘風險ε $ \epsilon $ 如果對手在某項工作上取得成功，我們應該至少以 GNFS 的工作為目標，至少1/ε $ 1/\epsilon $ 適用於 ECM 的時間；將分頻器移向較低ķ $ k $ （四捨五入前）。在安全方面，對於已知攻擊的可接受殘餘風險沒有達成共識，我已經看到了這樣的ε $ \epsilon $ 完全忽略，或從 5%（對於整個系統）設置為2−40 $ 2^{-40} $ （對於對稱密碼學，誠然沒有強烈的動機來調整它）。
6. 當我們想要生成米 $ m $ 密鑰，並且對手會滿足於分解任何一個（在機器對機器應用程序中密鑰用於身份驗證或簽名時經常出現這種情況），我們應該注意另外兩種分解算法：Pollard 的p-1和威廉姆斯的 p+1。問題是：使用大小的素數n/ķ $ n/k $ 隨機選擇，這些算法（尤其是第一個）在比率的角度上大大超過了 ECM賠率執行 $ \text{odds to factor}\over\text{runtime} $ 對於小賠率 $ \text{odds to factor} $ . 因此，對手將通過嘗試 Pollard 的 p-1，然後是 Williams 的 p+1，在米 $ m $ 模數可用，在使用 ECM 之前；並且可以在預期工作的一小部分上受益米 $ m $ . 為了證實這一點：GMP-ECM從業者使用該策略，在 p-1 方面取得了顯著成功，在p+1 方面取得了較小的成功。我們可以生成素數，而不是評估這種風險p $ p $ 以這樣的方式p−1 $ p-1 $ 和p+1 $ p+1 $ 有一個已知的高素因數，這使得這些算法無用（如果不是簡單的話，這也是有效可行的，例如，如FIPS 186-4附錄 B.3 中所解釋的，這對於ķ=2 $ k=2 $ 強制要求 512 位的素數，但不是 1024 位）。
7. 還應考慮到 ECM 預計需要近ķ $ k $ 分解 Multiprime-RSA 的工作量少了幾倍ñ $ N $ 比隨機的ñ $ N $ 具有可比尺寸且尺寸素因子較低的n/ķ $ n/k $ .

參考

限於本世紀，我只知道 4 篇參考文獻可以找到平衡ķ $ k $ :

• Arjen K. Lenstra：難以置信的安全性：使用公鑰系統匹配 AES 安全性，Asiacrypt 2001（備用連結）。
• Dan Boneh，Hovav Shacham：RSA 的快速變體，在CryptoBytes，Vol.中有刪節版本。2002年第5期第1期。
• M. Jason Hinek：On the Security of Multi-prime RSA，滑鐵盧大學應用密碼研究中心 (CACR) 的技術報告，2006 年（備用連結）。
• Jean-Sébastien Coron、Aline Gouget、Pascal Paillier、Karine Villegas：SPAKE：用於非接觸式應用的單方公鑰認證密鑰交換協議（2010 年金融密碼學研討會，付費牆免費摘錄）

最近的回答！

後面的參考資料簡要地觸及了幾乎相同的問題p $ p $ 在不平衡的 RSA中（1. 舍入不同以獲得ķ $ k $ , 4. 可能與最終 CRT 步驟不同，7. 不適用）。作者的結論是n=2048 $ n=2048 $ ,p=560 $ p=560 $ 提供良好的平衡；它會由此而來ķ=3 $ k=3 $ 很好，但是ķ=4 $ k=4 $ 不是。這是基於對 ECM 和 GNFS 的分析（據我所知，僅考慮 1）參考：

• Paul Zimmermann、Bruce Dodson：ECM 的 20 年，在第 7 屆算法數論研討會論文集上，2006 年（備用付費連結）。
• Thorsten Kleinjung、Kazumaro Aoki、Jens Franke、Arjen Lenstra、Emmanuel Thomé、Joppe Bos、Pierrick Gaudry、Alexander Kruppa、Peter Montgomery、Dag Arne Osvik、Herman te Riele、Andrey Timofeev、Paul Zimmermann：768 位 RSA 模數的分解，在Crypto 2010 的程序中。

關於 ECM 的最新數據點：2013 年末，Ryan Propper報告使用 GMP-ECM 6.4.3 + GMP 5.1.0 從 787 位複合材料中找到 274 位因子(7337+1)/8/101020140256422276570987002251440602782290400709 $ (7^{337}+1)/8/101020140256422276570987002251440602782290400709 $ 兩個未知素數的乘積，在使用小於 6GB RAM 的商品 CPU 上。他進一步報告說，這是對斯坦福大學集群的 10 天努力，在 5000 條曲線之後發現了分解。通過推斷日誌，我得到 16 小時/曲線的執行時間和預期的221 $ 2^{21} $ 曲線（約212 $ 2^{12} $ core.years），如果這接近正確的話，平均已經使用了 300 多個核心，並且在 1/400 處發現分解的機率如此之快；“這是相當幸運的發現”是輕描淡寫的。ECM 記錄中的第二大記錄也是相當幸運的；如果考慮到上面的 5.，這是可以預料的！

引用自：https://crypto.stackexchange.com/questions/15823