PKCS 1.5 如何解決 Textbook RSA 的不安全問題？
眾所周知，由於以下問題，Textbook RSA 使用起來不夠安全；
- 可猜測的明文問題
- 小的 $ e $ 問題
我想知道 PKCS 1.5 是如何解決這些問題的。
RSAES-PKCS1-v1_5PKCS#1 v1.5 描述了一種將教科書 RSA 轉變為（啟發式）小消息安全加密方案的方法（正式稱為考慮）。為一個 $ k $ -字節（ $ 8k-7 $ 至 $ 8k $ -bit) 公鑰的公共模數部分 $ (N,e) $ ，要加密的消息 $ M $ 是一個 $ \mathrm{mLen} $ -byte 字節串 $ \mathrm{mLen}\le k-11 $ . 資訊 $ M $ 變成了 $ \mathrm{EM}=\mathtt{0x00}\mathbin|\mathtt{0x02}\mathbin|\mathrm{PS}\mathbin|\mathtt{0x00}\mathbin|M $ ， 在哪裡 $ \mathrm{PS} $ 被繪製為 $ k-\mathrm{mLen}-3 $ -byte 由新近均勻隨機非零字節組成的字節串。然後（在字節串和整數之間的大端轉換左隱式）密文是 $ C\gets\mathrm{EM}^e\bmod N $ . 那是教科書的RSA加密 $ \mathrm{EM} $ .
而明文 $ M $ 可能仍然很容易猜測，驗證這種猜測變得更加困難。蠻力方法變成：盡一切可能 $ \mathrm{PS} $ 併計算相應的 $ C $ , 直到一個匹配。該策略需要 $ 255^{k-\mathrm{mLen}-3}/2 $ 平均嘗試（對於每個可能的 $ M $ ）。那是旁邊 $ 2^{63} $ 至少，並且增長了一個因素 $ 255 $ 對於我們刪除的每個字節的消息容量。這被認為可以解決可猜測的明文問題；但我們沒有正式的證據證明它確實如此。
謝謝 $ \mathtt{0x02} $ 在第二個字節 $ \mathrm{EM} $ , 它認為 $ \mathrm{EM}>2^{8k-15} $ . 由此可見，對於 $ e\ge3 $ , $ \mathrm{EM}^e\gg N^2 $ 對於所有實用的 $ k $ ，這對於解決一些小問題綽綽有餘 $ e $ 問題：
- 任何已知的擴展 $ e^\text{th} $ 根攻擊（在這個針對教科書 RSA 的攻擊中，其中 $ C\gets M^e\bmod N $ , 它用於 $ M<N^{1/e} $ ，我們可以反算 $ M $ 從 $ C $ 作為 $ M\gets\sqrt[e]C $ )
- Coppersmith 的 Short Pad Attack（將 Franklin-Reiter 相關消息攻擊擴展到隨機填充）。
RSAES-PKCS1-v1_5也幾乎挫敗了哈斯塔德的廣播攻擊。在這次針對教科書 RSA 的攻擊中，將相同的消息發送到至少 $ e $ 收件人允許解密。隨機的 $ \mathrm{PS} $ 使 $ \mathrm{EM} $ 對於相同的 $ M $ 可能不同。就算 $ e=3 $ , $ \mathrm{PS} $ 最小 8 字節，並且 $ 2^{36} $ 同一封郵件的收件人 $ M $ , 機率 $ e $ 填充資訊 $ \mathrm{EM} $ 如果我的數學計算正確的話，它們是相同的，低於百萬分之一。但是，許多
RSAES-PKCS1-v1_5實現在與小型設備一起使用時很容易受到攻擊 $ e $ ， 如 $ e=3 $ . 這是因為實現經常檢查前兩個字節 $ C^d\bmod N $ 是 $ \mathtt{0x00}\mathbin|\mathtt{0x02} $ , 和/或解析後面的內容以找到第一個 $ \mathtt{0x00} $ ，表示開始 $ M $ 並允許恢復 $ \mathrm{mLen} $ . 當此類檢查的結果以某種方式洩露故障發生的地方（通過詳細的錯誤程式碼、時間或其他側通道）提供給能夠送出密碼以進行解密的對手時，則適用Bleichenbacher 的填充預言攻擊。它將對解密實體的中等數量的查詢轉換為任意參數的 RSA 私鑰操作，允許解密一條消息，或者如果使用相同的密鑰進行加密和簽名，則計算一個簽名。不過，這不是致命的：
RSAES-PKCS1-v1_5填充可以在恆定時間內檢查，無論特定故障如何，都可以使用單個錯誤程式碼。另一種可能的策略是不檢查剩下的 10 個字節；或者什麼時候 $ \mathrm{mLen} $ 事先知道，不做填充檢查，簡單地提取 $ M $ 作為最右邊的 $ \mathrm{mLen} $ 字節 $ C^d\bmod N $ .