用戶:AnthonyDonlon/archives/最優非對稱加密填充

密碼學中最優非對稱加密填充(英語:Optimal Asymmetric Encryption Padding,縮寫:OAEP)是一種經常與RSA加密一起使用的填充方案。OAEP 由 Mihir BellarePhillip Rogaway 發明[1],隨後在 PKCS#1 v2RFC 2437中得到標準化。

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

OAEP 滿足以下兩個目標:

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

當 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 模數的位數。
  • k0k1是協議中的固定整數。
  • mn -k0 -k 1位長的明文消息
  • GH隨機預言,如加密散列函數
  • ⊕ 是異或運算。

編碼過程包括如下步驟:

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

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

解碼過程包括如下步驟:

  1. 恢復隨機串 rYH(X)
  2. 恢復消息 m00...0 為 XG(r)

安全性

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

實現

在 PKCS#1 標準中,隨機預言 GH 是相同的。但 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] (英語).