User: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] (英语).