最優非對稱加密填充

在密碼學中，最優非對稱加密填充（英語：Optimal Asymmetric Encryption Padding，縮寫：OAEP）是一種經常與RSA加密一起使用的填充方案。OAEP由Mihir Bellare和Phillip Rogaway發明^[1]，隨後在PKCS#1 v2和RFC 2437中得到標準化。

OAEP算法是費斯妥密碼的一種形式，它使用一對隨機預言G和H在進行非對稱加密之前處理明文。OAEP與任何安全的陷門單向置換${\displaystyle f}$ 結合使用在隨機預言模型中被證明是一種在選擇明文攻擊（IND-CPA）下語義安全的組合方案。當使用某些陷門置換（如RSA）實現時，OAEP也被證明可以抵抗選擇密文攻擊。OAEP可用於構建全有或全無轉換（all-or-nothing transform）。

OAEP滿足以下兩個目標：

1. 添加隨機性元素，這可用於將確定性加密方案（如傳統 RSA）轉變為概率加密方案。
2. 通過確保無法反轉陷門單向置換${\displaystyle f}$，從而無法恢復明文的任何部分，來防止密文的部分解密（或造成其他信息泄漏）。

當OAEP與任何陷門置換一起使用時，OAEP的原始版本（Bellare/Rogaway, 1994）在隨機預言機模型中顯示了一種「明文知曉性」的形式（他們聲稱這意味着對選擇密文攻擊是安全的）。然而隨後的結果與這一點相牴觸，表明OAEP僅是IND-CCA1安全的。但是與RSA-OAEP的情況一樣，當將OAEP與使用標準加密指數的RSA置換一起使用時，在隨機預言模型中證明了原始方案是IND-CCA2安全的。^[2]Victor Shoup 提供了一種改進的方案（稱為OAEP+），該方案可與任何陷門單向置換配合使用，以解決此問題。^[3]近期的研究表明，在標準模型中（即當哈希函數未建模為隨機預言時），無法在假定RSA問題的難度下證明RSA-OAEP具有IND-CCA2安全性。^[4][5]

算法

OAEP 是一種費斯妥密碼

在圖中，

• n 是 RSA 模數的位數。
• k₀ 和 k₁是協議中的固定整數。
• m 是n -k₀ -k₁位長的明文消息
• G 和 H 是隨機預言，如加密散列函數。
• ⊕ 是異或運算。

編碼過程包括如下步驟：

1. 用 k₁ 位長的 0 將消息填充至 n - k₀ 位的長度。
2. 隨機生成 k₀ 位長的串 r
3. 用 G 將k₀ 位長的 r 擴展至 n - k₀ 位長。
4. X = m00...0 ⊕ G(r)
5. H 將 n - k₀ 位長的 X 縮短至 k₀ 位長。
6. Y = r ⊕ H(X)
7. 輸出為 X || Y，在圖中 X 為最左邊的塊，Y 位最右邊的塊。

隨後可以使用 RSA 加密編碼的消息，使用 OAEP 可以避免 RSA 的確定性。

解碼過程包括如下步驟：

1. 恢復隨機串 r 為 Y⊕H(X)
2. 恢復消息 m00...0 為 X ⊕ G(r)

安全性

「全有或全無」的安全性基於以下事實：要恢復 m，必須完整地恢復 X 和 Y。從 Y 中恢復 r 需要 X，而從 X 中恢復 m 需要 r。由於加密哈希的任何更改的位都完全改變了結果，因此整個 X和整個 Y 必須都被完全恢復。

實現

在 PKCS#1 標準中，隨機預言 G 和 H 是相同的。但 PKCS#1 標準進一步要求隨機預言應是具有合適散列函數的 MGF1。^[6]

參見

• 密鑰封裝

參考文獻

1. M. Bellare, P. Rogaway. Optimal Asymmetric Encryption -- How to encrypt with RSA. Extended abstract in Advances in Cryptology - Eurocrypt '94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed, Springer-Verlag, 1995. full version (pdf) （頁面存檔備份，存於互聯網檔案館）
2. Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern. RSA-- OAEP is secure under the RSA assumption. In J. Kilian, ed., Advances in Cryptology -- CRYPTO 2001, vol. 2139 of Lecture Notes in Computer Science, SpringerVerlag, 2001. full version (pdf) （頁面存檔備份，存於互聯網檔案館）
3. Victor Shoup. OAEP Reconsidered. IBM Zurich Research Lab, Saumerstr. 4, 8803 Ruschlikon, Switzerland. September 18, 2001. full version (pdf) （頁面存檔備份，存於互聯網檔案館）
4. P. Paillier and J. Villar, Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption, Advances in Cryptology -- Asiacrypt 2006.
5. D. Brown, What Hashes Make RSA-OAEP Secure? （頁面存檔備份，存於互聯網檔案館）, IACR ePrint 2006/233.
6. Brown, Daniel R. L. What Hashes Make RSA-OAEP Secure? (PDF). IACR Cryptology ePrint Archive. 2006 [2019-04-03]. （原始內容存檔 (PDF)於2016-07-22） （英語）.