使用公鑰密碼術加密長消息的成本是多少？
讓 m 是任意大小的消息，可能非常大。是否有必要在公鑰加密方案中使用更大的參數才能讓接收者解密該消息？
我的猜測是，在 RSA 的情況下，消息的大小不能超過模數的大小。我認為這適用於任何公鑰加密方案。
如果是這樣，我們在談論什麼樣的算法複雜性：它在輸入大小（消息）中是線性的，還是更糟？
$$ I assume it’s worse $$ 編輯：我不想使用對稱密鑰加密。
編輯 2：您可以假設我們擁有一個安全通道，我們將通過該通道發送加密消息。
真正的問題不是加密甚至是解密具有巨大價值的加密方案，而是密鑰的生成：
對於 RSA、ElGamal、Paillier 等，您需要一個或多個大素數，它們構成計算的模數。在實踐中，您可以使用Miller-Rabin 素數檢驗找到大素數。它的執行時間為 $ O(t \log^3 n) $ ，並且對於大數，它可以改進為 $ O(t \log^2 n) $ 如果使用基於 FFT 的乘法。 $ t $ 記下測試執行的次數，您的錯誤率為 $ 1/4^k $ ，其中測試表示一個複數的素數。雖然具有乘法優化的執行時具有較小的指數，但 Big-O 表示法確實隱藏了常數因子，而且我不知道收支平衡在哪裡，但我們假設目前的加密庫已經使用了優化。
作為this SO answer中的參考，生成一個 $ 2048 $ 位 RSA 密鑰（生成兩個 $ 1024 $ 位素數和少量的計算時間來找到 $ e $ 互質於 $ \phi(n) $ 併計算 $ d $ ) 左右 $ 1 $ 秒。所以 $ \approx 0.5s $ 為一個 $ 1024 $ 位素數。
如果我們想將大小增加一個因子 $ a $ , 那麼 Miller-Rabin 檢驗需要 $ a^2 $ 時間更長。但是，我們還需要測試 $ a $ 平均數倍的數字才能找到一個實際的素數。範例：隨機 $ 1000 $ 比特數以機率大致為素數 $ 1/ln(2^{1000}) = (\log 2)/ 1000 $ 我們平均需要 $ 1000/(\ln 2) $ 測試找到一個素數，一個隨機 $ 2000 $ 比特數是有機率的素數 $ (\log 2)/2000 $ , 平均而言我們需要測試 $ 2000/(\ln 2) $ 數字來找到一個素數。這意味著，我們希望在 $ a $ 數倍數才能找到素數。
例如，對於一個素數 $ 1 M $ 例如位和估計 $ 0.5 $ 秒 $ 1024 $ 位素數，我們有一個因數 $ ~976.5 $ 在大小上，所以 Miller-Rabin 本身的執行時間是 $ 0.5 \cdot 976.5^2 $ , 我們需要測試 $ 976.5 $ 盡可能多的值，從而導致總體執行時間為 $ \approx 465 M $ 秒，大約是 $ 14.76 $ 年。
如果你想使用 RSA，你需要其中兩個素數，所以 30 年後你有一個 RSA 模數 $ 2,000,000 $ 位，它允許您加密 $ 0.25 $ MByte 數據在一塊。當然使用大型計算中心會加快速度，但真正的問題是大小，因為我猜你沒有 $ 0.25 $ 當您寫“可能非常大”時，請記住 MB 數據。
編輯：加密和解密的規模隨著大小的增加而減少。對於 RSA，您仍然可以在加密中使用一個小指數，這不必比目前的大很多。這意味著平方和乘法的步數大致相同，只是每個乘法和模運算需要更多時間。解密然後涉及一些長度的模數，但總的來說它在最壞的情況下仍然是二次的，並且比素數生成少得多。