RSA 的安全強度與模數大小的關係
NIST SP 800-57 §5.6.1 p.62–64 指定了 RSA 模數大小之間的對應關係 $ n $ 和預期的安全強度 $ s $ 位：
Strength RSA modulus size 80 1024 112 2048 128 3072 192 7680 256 15360這大約可以計算 $ s \approx 4 n^{0.43} $ （但我不知道我的推斷是否意味著什麼；在 DES 上索引到 112 的強度，而在 AES 上索引 128 及以上的強度，即強度是用指定的密鑰大小強制使用相應對稱算法的難度） .
這些數字的依據是什麼？它們是否來自最著名的因式分解方法的預期復雜性？或者他們是從特定因式分解工作中的計算量推斷出來的，例如RSA-768（這“需要超過 $ 10^{20} $ 操作”）？
（我要求提供比給定密鑰大小的破解 RSA 的難度更精確的資訊。今天認為多大的 RSA 密鑰是安全的？有很好的 RSA 分解歷史，但沒有回答我的問題 - 那是什麼？強度估計基於？）
這些似乎是基於General Number Field Sieve的複雜性，它是最快（如果不是最快）的經典因式分解算法之一。我在 Mathematica 中證實了這一點。
這是 GNFS 的複雜性（來源）：
$$ \exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right) $$ 在哪裡 $ n $ 是一個要考慮的數字。評估上述表達式 $ 2^b $ 是分解 a 所需時間的粗略近似值 $ b $ 位整數。這是一個表格，顯示了評估的位長 $ 2^{1024},2^{2048},\dots $ :
Strength RSA modulus size Complexity bit-length 80 1024 86.76611925028119 112 2048 116.8838132958159 128 3072 138.7362808527251 192 7680 203.01873594417665 256 15360 269.38477262128384我使用以下 Mathematica 程式碼生成了這些數字：
({#, N@Log2@gnfsComplexity[2^#]} &) /@ {1024, 2048, 3072, 7680, 15360}其中
gnfsComplexity定義為：gnfsComplexity[n_] := Exp[(64/9 * Log[n])^(1/3) * (Log[Log[n]])^(2/3)]這不是我寫過的最漂亮的東西，但它看起來很準確。（對於那些不熟悉 Mathematica 的人，第二個程式碼片段定義了一個函式，它是上述 GNFS 複雜性的音譯 $ n $ . 第一個程式碼片段評估了這種複雜性 $ n=2^{1024}, 2^{2048} $ 等，取對數以 2 為底，並將其轉換為數值近似值——十進制數——而不是像分數這樣的精確結果。）
至於 RSA 的較大密鑰大小背後的原因，解釋並不難。如果您查看問題中的文件，您會注意到分組密碼的“安全位”與該分組密碼的密鑰大小（以位為單位）幾乎完全相關（極少數例外）。這是因為我們對安全分組密碼的最佳攻擊本質上是暴力搜尋密鑰，平均需要 $ 2^{n-1} $ 時間在哪裡 $ n $ 是密鑰的位長。
然而，對於 RSA，我們最好的攻擊方式不是對密鑰進行暴力搜尋；相反，我們“簡單地”分解（公共）模數，因此該方案的安全性圍繞分解的效率。GNFS具有次指數但仍然是超多項式的時間複雜度，並且可以使用該時間複雜度來粗略地近似該方案提供的安全性。我相信這就是 NIST 在這裡所做的。