“教科书”/“原始”/“未填充” RSA 有一个“哎呀，现实世界发生了”的问题。

考虑任何模数为 4096 位的 RSA 密钥。有人几乎不可能恢复使用该密钥加密的消息，对吧？让我们假设这个键的公共指数值 ( e) 为3。

如果 Alice 使用这个公钥加密给 Bob 的消息“No”，她会做类似的事情

• "No"=> ASCII("No")=> 0x4E 0x6F=> m=0x4E6F。
• c = POW(0x4E6F, 3) MOD n=> c = 0x75CCE07084F MOD n。
  • 我们知道这n是一个 4096 位数字（给定），因此它大于0x75CCE07084F，所以c=75CCE07084F。

马洛里现在看到了[506 0x00s] 07 5C CE 07 08 4F. “嗯，”她想，“那是一个可疑的零”。她calc.exe以编程模式（十六进制）启动输入75CCE07084F，并将其切换为十进制（8095174953039）。她将其复制/粘贴到科学模式并点击立方体根按钮 ( 20079)。她对整数解决方案嗤之以鼻，然后进行复制/粘贴模式切换以返回十六进制 ( 0x4E6F)。她进一步检查了一个 ASCII 图表并重建该消息可能是英文单词“No”。Mallory 现在已在不使用私钥的情况下恢复了此消息。

什么地方出了错？

消息和指数的组合导致不需要模运算。计算第 n 个根并不令人愉快，但这不是一个棘手的问题。

对于长度小于密钥大小三分之一的e=3任何内容，都不会涉及取模操作。m对于 4096 位密钥，这意味着所有m<= 170 字节都可以立即恢复，因为密钥不相关。

如何解决？

一种方法是增加公共指数的最小大小。但是，这并不能解决教科书 RSA 的次要问题：每次发送针对相同密钥加密的相同消息都是相同的。

另一种方法是让它m总是“几乎n”。似乎可以通过获取正常消息并将其反转来实现这一点，但是 a) 可能会超过n，并且 b)m在以大量 0x00s 结尾时会失败。（这仍然不能解决确定性问题）。

因此，提出的解决方案是始终“填充”一条消息，以确保设置了一些高位，并且任何求幂都使用模值。

输入 PKCS1 填充

PKCS#1（加密）填充看起来像

00 02 [a bunch of non-zero random bytes] 00 [the message]

非零随机字节的数量与使所有内容完全适合大小为(keysize + 7) / 8字节的缓冲区（除以 8，向上舍入）所需的数量一样多。规范说至少有 8 个。这意味着产生任何消息的相同加密值的机会是 1 in 2^64，这是非常好的唯一性。消息越短，重复的可能性就越小。

该消息的“大小”为 4096-6=4090 位。将其带到第三个会产生 4090*3 = 12270 位范围内的答案。这肯定会超过我们的 4096 位模数，因此保证会涉及到 mod。我们还解决了制作它的最初目标，这样您就不能轻易解密消息。

这次出了什么问题？

事实证明，错误的答案可以“成功解密”。任何消息 C 对任何具有赔率的 4096 位密钥 k 都是有效的

1/256 * 1/256 * (255/256)^8 * (1 - (255/256)^502)

（“第一个字节是零”，“第二个字节是 2”，“8 个字节内没有出现零”，“最终出现零”）

0.004 * 0.004 * 0.996^8 * (1 - 0.996^502)
0.004 * 0.004 * 0.969 * (1 - 0.140)
0.004 * 0.004 * 0.969 * 0.860
1.27e-5

因此，每 78,000 条消息中大约有 1 条是“有效的”，但却是错误的。这会使 Bob 感到困惑，并让他做出一些愚蠢的回应。如果夏娃（比马洛里有更多的空闲时间）愿意，她现在可以开始向鲍勃发送聪明的胡言乱语，并观察他何时说他很困惑，最终夏娃可以弄清楚原来的信息是什么。（Bleichenbacher 攻击（Crypto.SE））

输入 OAEP 填充

OAEP 填充要复杂得多（https://www.rfc-editor.org/rfc/rfc3447#section-7.1）。它的构造方式是

• 仍然始终设置一个非常高的位
• 仍然注入随机性，因此保留了非确定性
• 解密操作可以确定它是否得到了正确的答案（相对于“可能足够正确”的答案）

OAEP 依赖于“正确性”属性的哈希算法，因此只要使用了良好的哈希算法，就意味着没有棘手的次要答案。

好的，那么签名呢？

类似（但不同）的论点使我们从教科书 RSA 到 PKCS#1 签名填充。

PKCS#1 到 PSS 的转换有点难以解释。引用RFC 3447：

本文档规定了两种带附录的签名方案：RSASSA-PSS 和 RSASSA-PKCS1-v1_5。尽管没有针对 RSASSA-PKCS1-v1_5 的攻击已知，但为了提高鲁棒性，建议在新应用程序中最终采用 RSASSA-PSS。包含 RSASSA-PKCS1-v1_5 是为了与现有应用程序兼容，虽然仍然适用于新应用程序，但鼓励逐步过渡到 RSASSA-PSS。

PSS 将随机性添加到签名生成过程中，以及在验证期间删除/验证随机性的方法。

结论

原始的 RSA 操作完成了他们需要做的事情，将一个数字变成另一个数字，另一个数字可以变成第一个数字。重要的后缀“安全地”需要对函数的输入进行一些约束。填充算法提供了这些约束（当学习到新的约束时，就会发明新的填充算法）。