最优非对称加密填充

在密码学中，最优非对称加密填充（英语：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） （英语）.