RSA 的核心运算是模幂运算：给定输入m，计算m ^e模n。尽管通常这是整数模n的单向排列，但它并不能满足通用非对称加密所需的所有特征：

• 如果e小且m小，则m ^e可能小于n，此时模幂不再是模的，并且可以有效地恢复。

• 该操作是确定性的，它允许对消息进行详尽搜索：攻击者加密可能的消息，直到找到与实际加密消息的匹配项。

• 模幂运算具有延展性：给定m ₁和m ₂的“加密” ，简单的乘法产生m ₁ m ₂的加密。这类似于同态加密，它可以是一个好的属性，也可以不是，取决于上下文。

由于这些原因，受RSA约束的整数m不能是单独加密的数据，而应该是确保m “不小”、包含一些随机字节并抑制延展性的变换的结果。

PKCS#1中的“v1.5”填充做得相当好，但有两个（已知的）警告：

• 如果攻击者可以提交恶意消息进行解密，解密引擎就可以变成一个填充预言机，并观察解密引擎是否找到了正确的填充结构。这是 Bleichenbacher 的攻击，它可能对 SSL 服务器起作用，需要大约一百万次中止的握手来恢复 SSL 对称密钥。SSL 服务器已被修补（如果解密未能找到填充，引擎仍然会继续使用随机 blob 而不是“预主密钥”），但这突出了 PKCS#1 v1.5 的潜在问题。

• 这种填充方案从未被“证明”过。安全证明是一件很好的事情。在我看来，这种填充有更好的地方，那就是它已经在现场部署并广泛使用了近 20 年；但是当有一些数学可以证实经验时，许多人更喜欢它。

OAEP旨在在这两点上做得更好。事实证明，对于填充预言机，事情并不是那么清楚；第一个证明被 Shoup 证明有些错误。Fujisaki、Okamoto、Pointcheval 和 Stern 在 RSA 的情况下“修复”了证明（OAEP 被设计为通用填充方案，但我们现在只有在与 RSA 一起使用时才有安全证明）。

总而言之，OAEP 试图改进以前的填充以抵抗选择密文攻击（不是选择明文攻击：因为公钥是公开的，任何人都可以随意加密任何东西），但是 v1.5 填充已经启发式地擅长它，高达一百万左右的解密，这对于许多目的来说已经足够了，并且可以为其他人打补丁（就像为 SSL 所做的那样）。如果正确实施，OAEP 会做得更好，这并不像通常认为的那么容易。

我想深入挖掘，所以最终阅读了 Daniel Bleichenbacher的基于 RSA 加密标准 PKCS #1 的针对协议的选择密文攻击。

存在主要弱点是因为 PKCS#1 填充使一些假设成为可能。然后可以利用这些假设来设计攻击。检查论文，这是一个聪明的攻击！攻击分为 4 个阶段，每个阶段逐步提取比前一个阶段更多的信息。它是高度迭代的，但在实用范围内（典型的 SSL 会话密钥为 1 天）。

• 阶段 1：你盲目地尝试一些在解密后简单地通过远程端的填充检查的密文
• 阶段 2-4：锁定上述结果并逐步缩小搜索空间。

由于两个原因，第 2-4 阶段的锁定/变窄是可能的：

1. 幂运算可以非常轻松地进行操作，尤其是在有限域中对整数进行逆运算。这是 RSA/模幂运算本身的属性 - 本身不是填充。例如，论文中的一句话：

   希望找到密文 c 的解密 m = c^d (mod n) 的攻击者可以选择一个随机整数 s 并要求解密看似无辜的消息 c' = (s^e)*c mod n . 从答案m' = (c')^d，很容易恢复原始消息，因为m = m's^−1 (mod n)。

2. 人们可以在选择的密文和远程端的解密结果之间映射直接的数学关系。这是同态，对输入的操作在输出上产生相同的操作。您不知道确切的结果，但可以推断出“我不知道值是多少，但现在是之前值的 2 倍”。实际值本身是通过绘制一个范围然后迭代地缩小范围来找到的。

OAEP 稍作改变，因为它在 RSA 解密（模幂运算）和填充检查之间添加了一些散列（不平衡 feistel 散列）。这基本上破坏了上面的第 2 点，并且攻击无法进行到第 2-4 阶段，因为来自第 1 阶段的知识不能被传递——来自 OAEP 之间的散列极大地扭曲了理解远程方在OAEP 解码时看到的内容的能力。唯一可能的方法是您可以确定性地反转散列函数以继续进行信息收集阶段。但这意味着哈希被破坏了。

所以 RSA 是可操纵的，这意味着攻击者可以以受控方式修改消息，即将它们乘以已知常数。因此，我们需要某种填充来防止这种情况发生：我们不想被攻击者询问“这是什么消息？” 并给他解密另一条消息所需的信息。（还有其他攻击：调查是http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf）

Ergo 填充是必需的。第一个填充方案首先放置一个常量字节，然后是随机的非零字节，然后是一个零字节，其余的数字就是消息。这看起来很好。

遗憾的是，这意味着攻击者可以了解 rM、M 任何消息、r 任何数字的第一个字节是否是给定的常数。事实证明，这足以证明关键因素，如 90 年代后期所示。www.bell-labs.com/user/bleichen/papers/pkcs.ps 是论文。

SSL v3.0 和其他几个部署的协议一样不安全，这使得这是一个相当严重的问题。