OAEP Reconsidered
OAEP Reconsidered
复制标题
DOI：
10.1007/3-540-44647-8_15
复制
发表时间：
2001-08
期刊：
影响因子：
--
通讯作者：
V. Shoup
中科院分区：
文献类型：
--
作者：
V. Shoup
OAEP加密方案由Bellare和Rogaway在Eurocrypt '94上介绍。它将任何陷门置换方案转换为公钥加密方案。OAEP被广泛认为可以抵抗自适应选择密文攻击。这一观点的主要证明是在随机预言模型中假定陷门置换方案是单向的，证明了它的安全性，本文证明了这一证明是无效的。首先，它观察到在OAEP安全性证明中似乎存在一个重要的差距。第二，它证明了这个差距是无法填补的，因为OAEP不可能有标准的“黑匣子”安全性降低。这是通过证明存在一个预言机来实现的，相对于该预言机，一般的OAEP方案是不安全的。本文还提出了一个新方案OAEP+，沿着随机预言机模型中的完整安全性证明。OAEP+本质上与OAEP一样高效，甚至具有更严格的安全性降低。应该强调的是，这些结果并不意味着OAEP的特定实例化（如RSA-OAEP）是不安全的。它们只是破坏了其安全性的最初理由。事实上，RSA-OAEP在随机预言模型中是安全的，这基本上是偶然的，而不是设计的;然而，这一事实依赖于RSA函数的特殊代数性质，而不是一般OAEP方案的安全性。
The OAEP encryption scheme was introduced by Bellare and Rogaway at Eurocrypt ’94. It converts any trapdoor permutation scheme into a public-key encryption scheme. OAEP is widely believed to provide resistance against adaptive chosen ciphertext attack. The main justification for this belief is a supposed proof of security in the random oracle model, assuming the underlying trapdoor permutation scheme is one way.This paper shows conclusively that this justification is invalid. First, it observes that there appears to be a non-trivial gap in the OAEP security proof. Second, it proves that this gap cannot be filled, in the sense that there can be no standard “black box” security reduction for OAEP. This is done by proving that there exists an oracle relative to which the general OAEP scheme is insecure.The paper also presents a new scheme OAEP+, along with a complete proof of security in the random oracle model. OAEP+ is essentially just as efficient as OAEP, and even has a tighter security reduction.It should be stressed that these results do not imply that a particular instantiation of OAEP, such as RSA-OAEP, is insecure. They simply undermine the original justification for its security. In fact, it turns out— essentially by accident, rather than by design—that RSA-OAEP is secure in the random oracle model; however, this fact relies on special algebraic properties of the RSA function, and not on the security of the general OAEP scheme.