最優非對稱加密填充

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

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

OAEP滿足以下兩個目標：

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

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

算法

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。

參見

• 密鑰封裝