如果 RSA 僅用於加密隨機的對稱密鑰，那麼教科書 RSA 有什麼問題？
據我所知，IND-CPA 用於防止頻率分析。但是，如果 RSA 僅用於加密對稱密鑰，那麼僅使用教科書 RSA 有什麼問題，因為隨機密鑰不太可能重複？
這是一個常見的錯誤，所以我想給出一個深入的答案。基本上，您提出的是依靠 RSA 的單向功能作為單向功能，而不是依靠其 CPA 或 CCA 安全性作為加密方案。使用 RSA 作為單向函式的優點是不需要填充等。
現在，首先要注意的是 RSA 假設表明，當給定環中的隨機元素時，RSA 很難反轉。所以，如果你選擇一個隨機值 $ x $ 之間 $ 0 $ 和 $ N-1 $ 然後計算 $ x^e \bmod N $ ，那麼根據 RSA 假設將很難找到 $ x $ . 然而，這並不意味著很難找到一些 $ x $ （並且知道一些密鑰是災難性的），這也不意味著在 $ x $ 之間不是隨機元素 $ 0 $ 和 $ N-1 $ . 例如，如果 $ x $ 是隨機的 128 位字元串（轉換為大數）？
好消息是，我們確實對此有（部分）答案。首先，考慮以下情況 $ e=3 $ . 在這種（很常見的）情況下，如果 $ N $ 是 2048 位長然後對於任何字元串 $ x $ 長度最多為 682 位，很容易反轉並找到 $ x $ 給予時 $ y=x^e \bmod N $ . 這是因為當 $ e=3 $ , 的長度 $ x^e $ 是長度的 3 倍 $ x $ . 如果長度為 $ x $ 小於 682 位，則長度為 $ x^e $ 小於 2048，所以 $ x^e \bmod N $ 等於 $ x^e $ 在整數上（這是因為沒有發生過模歸約）。請注意，在整數上找到立方根很容易（只需對可能性進行“二進制搜尋”）。我強調，由此得出的結論是不要使用更大的 $ e $ ; 結論是不要做普通的RSA。
然而，由於人們通常對此還不信服，因此還有另一種攻擊適用於任何 $ e $ ，包括較大的值。在這種攻擊中，當輸入 $ x $ 長度為 128 位，可以找到 $ x $ 大約 $ 2^{64} $ 時間，給定 $ x^e \bmod N $ . 通常，可以在時間上反轉 RSA，即輸入字元串長度的平方根。所以，這並不安全。現在，您可能想說：好的，所以我將使用 256 位密鑰！但是，請注意，您將擁有 128 位安全性，而不是 256 位安全性。更重要的是，這種需要平方根時間的攻擊表明這是一個非常糟糕的主意。所以，不要這樣做！（攻擊參考：Dan Boneh 等人的這篇論文中出現了對普通 RSA 的基本攻擊。（為什麼教科書 ElGamal 和 RSA 不安全），並且可以使用本文中的技術消除該論文中的空間要求： Oorschot 和 Wiener（具有密碼分析應用程序的並行碰撞搜尋。）
這導致了另一種可能性，即選擇隨機 $ x $ 之間 $ 0 $ 和 $ N-1 $ 併計算 $ x^e \bmod N $ . 然後，使用雜湊函式 $ H $ , 導出一個密鑰 $ k=H(x) $ 用於對稱加密。在隨機預言機模型中（與 $ H $ 作為隨機預言機）這實際上是安全的，如果對稱方案是 CCA 安全的，甚至是 CCA 安全的（這實際上是 CCA 安全的 KEM/DEM 方案；有關此內容的更多資訊，請參見下一段）。但是，如果沒有隨機預言機，我們不知道如何證明這一點是安全的。
一般來說，我們知道為了得到一個 CPA 安全的混合加密方案，我們需要非對稱和對稱方案都是 CPA 安全的；對於 CCA 安全性也是如此。但是，還有更有效的工作方式，即 KEM/DEM 範式。這比混合加密更輕鬆，因為非對稱部分為對稱加密定義了一個隨機密鑰，但不一定要由加密器來確定密鑰是什麼。如果您不熟悉它，我會讓您查找 KEM/DEM 範式。