RSA 密鑰長度是否存在實際上限？
假設有人想使用RSA加密來發送密鑰位以用於對稱加密系統，可以說是一種專用的密鑰交換系統。假設您認為目前使用的 RSA 密鑰長度在 10 年或 15 年內不會安全。
使用一百萬位的 RSA 密鑰長度會有哪些技術困難（硬體和/或軟體）？
假設您是從頭開始設計的，並且您對硬體-軟體設計選項一無所知。還假設您不在乎加密或解密資訊是否需要 24 小時左右。
具有長度密鑰的 RSA 的計算成本 $ n $ 位大致是 $ O(n^2) $ 用於公鑰操作（加密、簽名驗證），以及 $ O(n^3) $ 用於私鑰操作（解密、簽名生成）。因此，具有百萬位密鑰的 RSA 將比具有 1024 位密鑰的 RSA 慢大約 10 億倍（用於私鑰操作）；後者在普通 PC 上大約需要 1 毫秒，因此您需要使用百萬位密鑰進行兩週的計算。
記憶體空間不是硬性限制，因為 RSA 計算只需要保留一些密鑰大小的值；一百萬位整數是 128 kB；您可以在 RAM 中擁有數千個。但是，您將超過 1 級記憶體（在普通 PC 上為 32 或 64 kB），因此您可以預期會出現一些減速（使用蒙哥馬利的乘法，數據訪問是順序的，因此這種影響應該是有限的）。
當然，安全不僅僅是抵禦攻擊；這也是對能夠抵抗攻擊的信心。我對使用帶有一百萬位密鑰的 RSA 的系統的信心幾乎為零……因為這毫無意義。RSA 是安全的，因為大整數很難分解。具有最佳可用硬體的最知名算法在大約 1024 位時失敗；2048 位綽綽有餘。超越是對尚未發現的算法可能是什麼樣子進行瘋狂且完全未經證實的猜測，這是對關於未來神話般一瞥的傳說謠言的猜測。當有人跟我說有一個超大的 RSA 密鑰，比如一個 8192 位密鑰“只是為了安全”，我覺得他好像在談論購買SUV展示他的男子氣概（在您的情況下，您是在主張購買航空母艦）。
我看到了兩個主要的複雜點：
- 我們需要找到適當大小的素數。對於您的“百萬位”密鑰，素數 $ p $ 和 $ q $ 必須有大約 500000 位。我想這種大小的素數測試比我們通常的 2048 位素數要困難得多（儘管我沒有在快速搜尋中找到數字）。
此外，您需要更多的熵作為素數搜尋算法的輸入，否則可能會從隨機性方面受到攻擊。
- 對於每次解密，您需要一個帶模數的模冪運算 $ n $ 和指數 $ d $ ， 在哪裡 $ d $ 具有幾乎相同的位數 $ n $ .
簡單的平方和乘法算法採用 $ \log_2 n $ 平方和平均 $ \frac 12 \log_2 n $ 乘法（取決於有多少個 1 位）。每個平方/乘法本身使用一個 $ \log_2 n $ - 位數，即自行移動 $ \log_2 n $ 添加此類 $ \log_2 n $ - 位數（如果實現為雙加）。那將是 $ (\log_2 n)^3 $ 單位操作，這將是你的百萬位（ $ 2^{20} $ 位）數 $ (2^{20})^3 = 2^{60} $ 位操作（有一些小因素）。現在我們進入類似於暴力破解 DES 的區域（我不確定其中有多少可以並行化）。
有一些更快的求冪和乘法算法，但如果我理解正確的話，它們只會改變一個常數因子，而不是實際的複雜度。