使用彩虹表攻擊在沒有填充的情況下破壞 RSA
我們使用沒有 OAEP 的 RSA，輸入域相對較小。
假設我們將 John 和 Bob 連接在一條線上，並且我們正在竊聽他們。Bob 首先將他的公鑰 (e,n) 發送給 John，然後 John 將他的消息 m 加密並在加密後的線路上發送。當我們竊聽線路時，我們會得到他的加密消息，例如 3211 4431 9938 …（我使用低模僅作為範例）
我作為攻擊者可以製作一個從 0 到 n 的每個數字的加密彩虹表，然後使用我創建的表解密 John 的消息。
- 我對麼？
- 當我們使用任何填充技術時，我們通過在消息中插入隨機位來防止這種攻擊（對嗎？），但是如果解密器（Bob）不知道這些隨機位，他如何“刪除”這些隨機位。
- 是的，問題中的攻擊適用於範例的低模數。術語“字典”比“彩虹表”更合適（用於製作預先計算的雜湊表的緊湊表）。
但是，實際的攻擊無法以這種方式進行。在 RSA 實踐中，不可能建構足夠大的字典，因為建構需要花費太多時間（與模數成正比 $ n $ ，現在通常至少為 2048 位）。但是，如果 Alice 直接用教科書 RSA 加密了一條已知屬於一個小集合（例如班級卷上的名字）的消息 $ m\mapsto c:=m^e\bmod n $ ，那麼就可以解密 $ c $ 通過加密每個可能的消息並測試匹配的 $ c $ . 順序搜尋 $ m $ 在課堂上roll會做：對應的字典 $ c $ 僅在有多個消息時才有用（並且 RSA 實際上並沒有通過將消息分成小塊來使用，如問題所示）。 2. 隨機加密填充解決了這個問題，通過可逆地翻轉消息 $ m $ 變成一個足夠隨機的消息代表 $ \widetilde m\in[0,n) $ . 然後教科書 RSA 可以安全地應用於 $ \widetilde m $ ，根據 RSA 假設：對於正確的公鑰 $ (n,e) $ 並且隨機 $ x\in[0,n) $ , 很難找到 $ x $ 從 $ x^e\bmod n $ .
如果解密器（Bob）不知道這些隨機位，他如何“刪除”它們？
大局是愛麗絲和鮑勃之間有一個約定，關於哪些位 $ \widetilde m $ 是由 Alice 添加的填充（其中一些是隨機的），應該由 Bob 刪除。該簡化描述非常接近RSAES-PKCS1-v1_5中已棄用的填充技術。現代RSAES-OAEP有額外的步驟，所以除了（最多）8 位 $ \widetilde m $ 即使在 $ m $ 不是（這是在應用隨機填充後通過可逆對稱密碼變換獲得的，它分散了隨機性），但這個想法仍然存在。