公钥加密系统

定义

公钥加密机制的应用：会话建立、密钥交换等。

对抗窃听的安全性

当讨论对称密码的窃听攻击时，我们区分了两种情况，①密钥只使用一次，②密钥使用多次。

对于公钥加密，如果系统的一次性密钥是安全的，那么它对多次密钥也是安全的。我们不必赋予攻击者请求加密他选择的明文的能力，因为他可以自己创建这些加密。公钥私钥对天生就是用来加密多个信息的。

对抗主动攻击的安全性

看一个电子邮件的例子，Bob 想发送邮件给他的朋友 Caroline ，Caroline 正好在 Gmail 上有账号，过程如下：这份加密的邮件发送给 Gmail 服务器，Gmail 服务器解密邮件查看接收方，如果接收方是 Caroline ，它会把这份邮件转发给 Caroline ，如果接收方是攻击者，它会把邮件转发给攻击者。

假设 Bob 加密了邮件，使用的系统允许攻击者篡改密文，且不会被检测到。想象这份邮件是使用计数器模式加密的，当攻击者截获了这个邮件，他可以改变接收方，使得接收方变成 attacker ，对于计数器模式这是非常容易做到的，攻击者知道邮件是发往 Caroline 的，他只对邮件内容感兴趣，所以他可以修改接收方，这样当服务器接收到邮件时，他会解密，看到接收方是攻击者，就把邮件转发给了攻击者。这是一个经典的主动攻击的例子，注意，攻击者只能解密接收方是攻击者的邮件。

我们的目标是设计安全的公钥系统，即使攻击者可以篡改密文，还可以解密特定的密文。攻击者的目标是获得明文内容。

选择密文安全

事实上，这是公钥加密的标准安全性观念。

我们有一个加密机制 (G,E,D) ，我们定义在明文空间和密文空间 (M,C) 上，定义两个实验，实验0 和实验1 ，b 表示挑战者是实现实验0 或是实验1 。

挑战者开始时生成一对公钥和私钥，然后把公钥给攻击者，现在攻击者可以请求解密很多密文，攻击者提交密文 $c_1$ ，获得了密文 $c_1$ 的解密 $m_1$ ，攻击者可以一次次这么做，然后说游戏结束。现在，他提交两个等长度的明文 $m_0$ 和 $m_1$ ，他会收到挑战密文 c ，也就是 $m_0$ 或 $m_1$ 的加密，现在攻击者可以继续提交这些密文询问，他可以继续请求解密，那么他提交了一个密文并获得了该密文的解密。

注意，如果攻击者可以提交他选择的任意密文，那么他可以破解这个挑战，他只需提交挑战密文 c 作为解密请求，然后他被告知他在挑战阶段获得的是 $m_0$ 还是 $m_1$ 的加密结果，因为我们有这么一个限制，攻击者可以提交任何他选择的密文，除了挑战密文，那么攻击者可以询问他选择的任何密文的解密，除了挑战密文。即使攻击者有所有这些的解密，他依然不能分辨出他得到的是 $m_0$ 还是 $m_1$ 的加密。

通常，攻击者无法判断密文来自 $m_0$ 还是 $m_1$ ，我们说这个选择密文 CCA 安全的。

选择密文安全的攻击方法

假设使用的加密系统满足给定信息的加密，攻击者可以改变接收方，那么我们可以这样赢得游戏。

①攻击者得到了公钥，发出两个等长度的明文，第一个明文内容是 0 ，第二个明文内容是 1 ，两个明文都给 Alice ，Alice 回复后，攻击者会得到挑战密文 c 。

②攻击者修改接收方，返回给 Alice 一个密文 c’ ，c’ 是 ”给 Charlie 的明文，挑战密文的内容 b“ 的加密结果，现在因为明文不同，我们知道密文也不同，c’ 一定和挑战密文 c 不一样，根据 CCA 游戏的定义，挑战者必须解密任何不同于挑战密文的密文，挑战者解密后给攻击者解密结果 m’ ，他给了攻击者 b ，攻击者可以输出挑战结果 b ，他以优势 1 赢得了游戏。

公钥加密的构建

陷门函数 TDF

陷门函数是一个函数，从集合 X 映射到集合 Y ，它定义为三个算法：一个通用的算法 G ，函数 F ，函数 F 的逆。

通用算法 G 运行时，会生成一对密钥，一个公钥和一个私钥。公钥定义了一个从集合 X 映射到集合 Y 的特定函数，私钥定义了这个函数的逆，从集合 Y 映射到集合 X 。

这里的想法是，你可以使用公钥 pk 计算这个函数再任意点的值，你可以使用私钥 sk 来计算函数的逆。逆是什么意思？如果我们看这个密钥生成算法 G 生成的公钥、私钥对，如果计算函数在点 x 的值，然后计算所得点的逆，应该获得原点 x 。

安全的陷门函数 TDFs

如果这个函数 F(pk,·) 是所谓的单向函数，我们说这个三元组 (G,F,$F^{-1}$) 是安全的。

单向函数的想法是，这个函数可以在任一点计算，但如果没有私钥 sk 的话，求它的逆是困难的。通常使用如下游戏定义：

挑战者生成一个公钥和私钥，生成一个随机 x ，挑战者把公钥发给攻击者，挑战者会计算函数在点 x 的值，然后把所得结果 y 也发给攻击者。攻击者看到一个公钥，定义了这个函数是什么，然后攻击者看到这个函数在一个随机点 x 处的像，他的目标是求这个函数在点 y 的逆，他输出某个 x’ 。

如果攻击者求出在点 y 的逆的概率是可忽略的，这个陷门函数是安全的。

使用 TDFs 构建公钥加密系统

构建公钥加密系统如下需要三个原件：

我们有①陷门函数 (G,F,$F^{-1}$) ，我们需要的另一个工具是一个②对称加密机制，我们假设这个加密机制对主动攻击是安全的，特别地，我需要提供认证加密。

注意！对称加密系统取 K 中的密钥，陷门函数取 X 中的元素为输入。这是两个不同的集合，所以我们需要③哈希函数从 X 映射到 K ，换句话说，它把集合 X 中的元素映射成密钥用于对称加密系统。

公钥加密系统的密钥生成与陷门函数的密钥生成是完全一样的。

公钥加密系统工作过程

加密工作流程：

①加密算法取一个公钥和明文为输入，它会生成一个集合 X 里的随机元素 x ；

②然后它会对随机元素 x 应用这个陷门函数，获得 y ，y 是 x 在陷门函数下的像；

③然后它会通过取 x 的哈希值，生成一个对称密钥，这是对称加密系统的对称密钥；

④最终它使用刚刚生成的密钥加密明文 m ，然后输出刚刚计算得到的值 y 与 m 在对称密码下的加密结果 c 。

注意：陷门函数只用于随机值 x ，而信息本身是用对称密钥系统由 x 推出的密钥加密的。

解密工作流程：

①解密算法取私钥和密文作为输入，密文本身包含两个部分，值 y 和 c ，首先应用陷门函数的逆变换，逆向陷门函数作用于值 y 返回 x ；

②对 x 取哈希值得到与加密时得到的一样的密钥 k ；

③应用对称解密算法解密密文 c ，获得最初明文 m 。

安全性定理

①如果开始的陷门函数是安全的，换句话说，这是个单向函数；②如果攻击者没有私钥的话，对称加密系统提供了认证加密；③哈希函数是一个随机神谕，即是个从集合 X 映射到密钥空间 K 的随机函数。在这三个条件下，系统是选择密文安全的，即 $CCA^{ro}$ 安全，ro 表示这个安全性是建立在所谓的随机神谕模型上的。

如果陷门函数是安全的，那么对称加密系统是安全的，能抵抗篡改，提供了认证加密。

错误使用 TDF 构建的公钥加密系统

为什么不要用陷门函数来加密？

我们首先能想到的是直接对明文 m 使用陷门函数，我们使用陷门函数加密明文 m ，然后使用陷门函数的逆函数解密密文 c ，以还原明文 m 。

事实上，解密是加密的逆过程，这是完全不安全的。最简单的方法证明它不安全，在于这是一个确定的加密，在这里没有随机性被使用到，当我们加密一个明文 m ，由于算法是确定的，它不可能是语义安全的。当我们将这个陷门函数具象化，使用特定的实现，例如 RSA 陷门函数，那么这种机制会有很多可能的攻击。

陷门置换 RSA 的构建

数论回顾

详见《Number Theory》

RSA 陷门置换

SSL 和 TLS 都使用了 RSA ，用于证书和密钥交换；有很多安全的电子邮件系统和安全的文件系统，使用了 RSA 加密电子邮件和文件系统里的文件。

RSA 是一个陷门置换，本身不是一个加密系统，只是一个函数。

密钥生成算法函数 f 和逆函数 $f^{-1}$

密钥生成算法工作流程：

①我们生成两个质数 p 和 q ，每个大约是 1000 位，约 300 十进制位，然后 RSA 模就是这两个质数的乘积。

②接下来我们选取两个指数 e 和 d ，满足 e·d = 1 (mod φ(N)) ，这意味着 e 和 d 首先必须与 φ(N) 互质，其次，他们必须互为模 φ(N) 的逆。

③输出公钥为 (N,e) ，私钥为 (N,d) 。这个指数 e 有时被称为加密指数，指数 d 有时被叫做解密指数。

RSA 函数本身的定义是很简单的，为求简便，把它定义成从 Z_N^ 到 Z_N^ 的函数，这个函数有输入 x ，我们只需取 x ，计算 $Z_N$ 中 $x^e$ 。

解密时，我们只需给定输入 y ，计算 $y^d$ 模 N 就行了。假设 y 本身正好是 RSA 函数在某个值 x 处的值，这时，$y^d$ 就是 $RSA(x)^d$ ，而 x 本身 $x^e$ mod N ，因此，$y^d$ 就是 $x^{ed}$ mod N ，由于 e·d = 1 (mod φ(N)) ，这意味着存在某个整数 k 满足 ed = kφ(N)+1 ，根据欧拉定理，$x^{φ(N)}$ = 1 ，得出最后结果 x ，这意味着 d 次方就是 RSA 的逆。

为什么这个函数是安全的？即，为什么在没有私钥的条件下这个函数是单向的？

RSA 假设告诉我们给定公钥，RSA 函数是一个单向置换，因此，它是一个陷门置换，因为它有陷门，陷门指的是私钥里的 d ，这个陷门使得所有知道陷门的人，可以很容易的求逆。

形式化地，我们说对所有有效的算法 A ，如果我生成两个随机的质数 p 和 q ，把它们乘起来，获得模 N ，然后随机选择一个 $Z_N^$ 中的 y ，指数 e 由公钥指定，可以得到 RSA 在点 y 的逆的概率 $y^{1/e}$ ，这个概率是可忽略的，这个假设叫做 *RSA 假设。

公钥加密系统

将 RSA 陷门置换带入 ISO 标准机制，这个机制是基于一个必须提供认证加密的对称加密系统的，还是基于一个哈希函数的，从 RSA 的角度看，这个哈希函数把 $Z_N$ 里的元素映射到对称密钥系统的密钥，加密机制的工作方式如下：

算法 G 运行 RSA 的密钥生成算法，产生一个公钥和一个私钥，这个公钥包含了加密指数，私钥包含了解密指数。

加密过程如下：

①随机选择一个 $Z_N$ 中的元素 x ；

②对 x 应用 RSA 函数；通过对 x 取哈希先推导出一个对称密钥 k ，在实际中，这个哈希函数 H 使用 SHA-256 实现；

③输出 y 和使用密钥 k 加密后的信息。

解密过程：首先使用密钥来求密文开头的逆，即 y 的 RSA 逆，这回给我们值 x ，我们对 x 应用哈希函数得到密钥 k ，运行解密算法得到明文。

对教科书 RSA 的攻击例子

如果试图使用教科书 RSA ，换句话说，如果试图直接使用 RSA 来加密一个明文，会受到攻击。

设想我们有一个网页服务器，这个服务器有 RSA 私钥 (N,d) ，网页浏览器试图与网页服务器建立起一个安全的 SSL 会话，那么 SSL 的工作方式是：

①网页浏览器开始时发送这个客户端 hello 消息，我想和你建立一个安全会话；

②网页服务器回复一个服务端 hello 消息，其中包含了服务器的公钥；

③网页浏览器生成一个随机数，这个随机数叫做预备主密钥 k ，把结果以密文形式发送给网页服务器，服务器会解密获得 k 。

现在，双方都有了共享密钥，他们可以使用它来安全会话。

如果我们直接使用 RSA 函数加密 k 会发生什么错误？换句话说，如果 k 直接加密成 $k^e$ mod N 的话，为了论证方便，我们假设 k 是一个 64 位密钥，我们把 k 当作范围从 0 到 $2^{64}$ 的一个整数，现在我们做如下事情：

①首先，假设 k 正好能分解成几个差不多大小的数的乘积，我们可以把 k 写成 $k_1$ 乘 $k_2$ ，$k_1$ 和 $k_2$ 是整数，比如说，两个都小于 $2^{34}$ ，那么实际上，k 可以被写成这样，有 20% 的概率会发生。但现在如果我们把这个 k=$k_1$ × $k_2$ 带入到定义密文的函数 c=$k^e$ in $Z_N$ 中，把 k 替换成 $k_1$ × $k_2$ ，我们会得到方程 c / ${k1}^e$ = ${k2}^e$ in $Z_N$ ，在这个方程中有两个变量 $k_1$ 和 $k_2$ ，我们把它们放在方程的两边，攻击者知道 c 、e 、N ，现在可以进行中间相遇攻击了。

②我们构建一张表，里边存放左边 c / ${k1}^e$ 的所有可能值，有 $2^{34}$ 个，然后对右边 ${k2}^e$ 所有的可能值，我们检查这个值是都在我们构建的表里，如果在，我们就找到了一个碰撞，我们就有了这个方程的一个解。一旦我们找到了一个元素具有形式 ${k2}^e$ 在我们构建的表里面，我们就已经解决了这个方程，并找到了 $k_1$ 和 $k_2$ ，一旦找到了 $k_1$ 和 $k_2$ ，我们可以很容易的还原 k ，k=$k_1$ × $k_2$ ，我们就破解了这个加密系统。暴力的搜索，我们可以在 $2^{64}$ 的时间里破解它。

永远不要直接用 RSA 去加密。必须通过一个加密机制来使用它，比如 ISO 的标准。

公钥密码学一号标准 PKCS1

在应用 RSA 函数前，必须对明文做些处理。ISO 的标准，我们生成了一个随机 x ，用 RSA 加密 x ，然后从这个 x 推出一个对称加密密钥，不过这不是 RSA 在实际中的应用。

在实际中，系统生成一个对称加密密钥，然后让 RSA 去加密这个给定的对称加密密钥，而不是生成加密密钥。在实际中，RSA系统有一个输入的对称密钥需要加密，例如，可能是一个 AES 密钥，128 位，然后这个密钥被加密，首先我们取这 128 位，把它扩展成整个模的大小，例如这个模是 2048 位，然后应用 RSA 函数。这是怎样预处理的？如何论证得到的系统是安全的呢？这在实际中是广泛应用的，即 PKCS1 1.5 。

PKCS1 v1.5

PKCS1 模式 2 表示加密，模式 1 表示签名。

PKCS1 加密工作过程：

取明文，比如这里是 128 位 AES 密钥，把它放在你要产生的值的最低 128 位，接下来在它前面附上 16 个 1 ，即十六进制的 FF ，接下来把它附在这个随机密码本的后面，这个密码本中任何地方都不含 FF ，最后在结果的最高位放上数 02 ，意味着这个明文已经被 PKCS1 模式 2 编码了。这整个值就是 2048 位的字符串，作为 RSA 函数的输入，去计算它的 e 次方模 N ，得到的就是 PKCS1 的密文。

PKCS1 解密工作过程：

解密者要求 RSA 函数的逆，还原这个分组，他会看最高位，发现是 02 ，意味着这是 PKCS1 格式的，他会移除这些 02 ，移除所有的这些随机密码本，直到遇见 FF ，剩下的就是最初明文，然后用这个明文来解密密文的内容。

针对 PKCS1 v1.5 的攻击

在没有安全性证明的情况下，实际上系统会被破解，这里有一个非常优雅的攻击，由 Bleichenbacher 在 1998 年提出。

当 PKCS1 被使用在 HTTPS 中时的攻击过程：

假设攻击者截获了一个特定密文 ciphertext ，这是 PKCS1 密文，它是用 PKCS1 编码的，然后结果作为 RSA 函数的输入，我们把这个密文叫做 RSA 函数的输出。

攻击者想解密密文，我们简化 SSL ，比如说攻击者可以直接发送密文给网页服务器，服务器将试图使用它的私钥去解密密文，在解密之后，首先它问：密文的解密结果是否是 PKCS1 编码的？即，它会问最高两位是 02 吗？如果是，才继续正常的解密，然后继续执行协议；如果这些最高位不是 02 ，就会声明一个错误，告诉攻击者他发送了一条无效的密文。这一点，让攻击者得以测试出给定密文的最高 16 位是否为 02 ，从某种意义上讲，这就给了攻击者一个神谕，使得他可以测试任意密文的逆是否以 02 开头。

实际上，这足以完全解密攻击者想解密的任何密文，一点点的信息泄露，因为 RSA 的特性，让攻击者完全解密一个给定密文。攻击者会这么做，他有一个想解密的密文，他把密文直接交给网页服务器询问它是否以 02 开头，接下来，攻击者选择一个随机值 r ，他要构建一个新密文 c’ ，也就是 $r^e$·c mod N ，这会造成什么？如果我们把 r 带入 RSA 函数，我们只是与 RSA 明文相乘，PKCS1 封装的明文 m ，用 r 去乘它，计算整项的 e 次方，r 是攻击者控制的值。然后攻击者会把 c’ 发送给网页服务器，服务器回答是肯定的，以 02 开头；或是否定的，不以 02 开头。

现在，把这个问题进行抽象，推广到更一般的情况，考虑如下情形：我知道 PKCS1(m) 这个数 x ，这个数是我想获得的 PKCS1 对 m 的编码，然后让你选择 r ，我会告诉你 r·x mod N 是否以 02 开头，实际上通过足够多的这样的问题，你就可以还原 x 的全部了。这意味着攻击者可以抓取一个给定的密文，在攻击的最后给出密文 c 的解密结果。

怎么能够只通过学习明文的最高位是否是 02 就能还原整个明文呢？

举个简单的例子，幼儿 Bleichenbacher ，只求表达这个攻击的基本想法。

设想攻击者可以发送密文 c ，网页服务器会用私钥解密，不过我们假设服务器不检查开头是否是 02 ，而是看最高位是否为 1 ，如果最高位是 1 ，网页服务器会说：是，如果最高位不是 1 ，网页服务器会返回：不。

为求进一步简化，我们假设 RSA 的模 N 是 2 的某次幂，即 N=$2^n$ ，当然，这不是一个有效的 RSA 模，RSA 模是一个两指数的乘积，但为求简便假定 N 是 2 的幂。

现在发现，通过给网页服务器发送密文 c ，攻击者只是学习明文 x 的最高位，服务器的行为完全泄露了最高位，现在攻击者可以把密文乘以 $2^e$ ，现在乘以 $2^e$ 就有去乘明文 x 的效果，就是把 x 乘以 2 ，因为我们是工作在 2 的 n 次方模下，乘以 2 意味着左移，当我们左移时，事实上我们学到了 2x 的最高位，也就等于学到了 x 的次高位。2x 的最高位，左移了 x ，并取模 N ，那么现在， 2x mod N 的最高位，也就是 x 的次高位，我们就学到了 x 的另一位内容。

现在重复这步，询问 c·$4^e$ ，这对应于 ${4x}^e$ ，询问 4x 会得到 4x mod N 的最高位，4 对应着左移两位，这意味着我们学到了 x 的第三高位，当我们一次次重复，对于不同的 c 的倍数，可以看出经过一些询问，就还原了 x 。

Bleichenbacher 需要一百万次的原因在于，他不是测试一位，而是测试最高两位是否为 02 。

抵抗 PKCS1 v1.5 的攻击

看 RFC ，提出的方案如下：

如果在你应用 RSA 解密之后，你会获得一个明文，它并不是 PKCS1 编码的，换句话说，它不是以 02 开头的，你可以选取某个随机字符串 r ，只假定明文是一个随机字符串 r ，只当什么也没发生，稍后协议会失败。具体地说，如果 PKCS1 编码不正确，你会说预备主密钥是这个随机字符串，或只是随机接收的，我们继续协议，当然建立会话会失败，因为客户端和服务端最终达成的交换密钥不一致，这会导致会话终止。

我们实际上不告诉攻击者明文是否以 02 开头，我们只是假定明文是某个随机值，对于许多网页来说，这只是一点点的代码改动，是容易布置的。

PKCS1 是否应该都被改变，使得我们得以证明选择密文安全？这让我们以一种不同的方法来进行使用 RSA 的加密，即所谓的优化非对称加密补齐 OAEP 。

PKCS1 v2.0 OAEP

OAEP 是更好的使用 RSA 加密的方法，由 Bellare 和 Rogaway 于 1994 年提出，OAEP 工作流程如下：

取你想加密的明文信息 msg ，例如 128 位的 AES 密钥，然后首先在明文后面附上一小段密码本，在前面附上 01 ，然后再根据标准来加一组 0 ，假设这里有 128 位 0 。然后也可以选择一个随机值 rand ，使得这整个字符串与你的 RSA 模一样大，比如说 2047 位。

在你应用 RSA 函数之前，首先取你选的随机数，把它交给哈希函数 H ，这个哈希函数产生一个值，这个值与你编码的左边一样大，你把输出求异或，把得到的结果交给另一个哈希函数 G ，你用一个随机值去异或，最后会得到两个值，把它们联结起来得到 2047 位长的字符串，这也就是你应用 RSA 函数的字符串，结果就是 RSA 加密。

现在有一个 2001 年证明的理论，由 Fujisaki ，Okamoto ，Pointcheval 和 Stern 提出，证明了事实上如果你只假设 RSA 函数是一个安全的陷门函数，事实上这个模式使用 RSA 加密是选择密文安全的话，我们还必须假设函数 H 和 G 是某种理想的哈希函数才行，我们假设 H 和 G 是随机函数，从它们的定义域映射到它们的值域，这些叫做随机神谕。在实际中，当实现 OAEP 时，对于 H 和 G ，人们就使用 SHA-256 。这个定理依赖于 RSA 的性质，事实上如果你使用一个普通的陷门置换，这个定理不成立，其它的置换未必具备 RSA 的代数性质。

为什么这叫做优化非对称加密补齐呢？

原因在于，如果你看密文，会注意到，其密文是尽可能短的，密文与 RSA 输出一样长，没有附在密文后面的值。例如 ISO 标准中，即使你必须加密一个非常短的明文，你必须使用 RSA 加密 x ，然后在 x 后面附上使用对称加密系统加密的短消息，即使你必须加密 128 位 AES 密钥，根据 ISO 标准，你会获得一个 RSA 输出加上一段对称密码。而在 OAEP 中，你只获得了一个 RSA 输出，没有其他东西。从某种意义上这是优化的，密文长度是优化的。

如果我们拥有一个普通的陷门置换，如何正确的使用 OAEP 呢？

实际上，对 OAEP 有一个小修改，可以使得结果更为一般，这是 Shoup 于 2001 年给出的结果。证明了如果给我一个普通陷门置换 f ，实际上如果不用 OAEP 里的固定补齐，而是使用这个哈希函数 W ，它是你要加密的明文 m 和随机性 r 的哈希函数，然后在解密时，检测这个哈希函数的值是否正确，那么当你解密时，检查 W(m,r) 是否与明文中这个位置的内容一致，这种改进后的 OAEP 叫做 OAEP+ ，事实上，它是 CCA 安全的，对任意陷门置换都是选择密文安全的，不必依赖于 RSA 的特定性质。

还有一个结果叫做简单非对称加密补齐 SAEP+ ，就是说如果要依赖 RSA 的性质，那么在特殊情况下，当 RSA 的公钥指数等于 3 时，实际上你不需要第二阶段的加密工作，这里这个简单的补齐机制使用了函数 W 就足以保证选择密文安全了。

它们是 OAEP 的变种，但并没有被实际使用。

如何解密 SAEP 密文 ct ？这里你有密文 ct ，如图那种方法是正确的密文解密？

第一个。有了密文，我们首先需要应用 RSA 逆函数作用于密文，我们会得到 RSA 明文，正好就是 x 和 r ，接下来我们需要使用函数 h 计算 r 的哈希值，然后把结果与 x 异或，这会给我们 m 和 (m,r) ，最后我们需要确保补齐 W(m,r) 是正确的，我们检查 w 是否等于 W(m,r) ，如果是，我们输出 m ；如果不是，我们输出 ⊥ ，表示密文无效。

解密中的补齐检查在我们看过的所有的机制中都是很重要的，例如 OAEP+ 和 SAEP+ 就是这样解密的，检查补齐是否正确是很重要的。类似地在 OAEP 中，在解密时这个检查也很重要，如果补齐不是 01000 ，就输出 ⊥说密文是无效的。

事实上实现 OAEP 可能是很困难的。假设你写了一个 OAEP 解密程序，首先取密文为输入，对密文应用 RSA 逆函数，比如说你希望得到 n 位值输出，2047 位，在 2048 位 RSA 模的情形下，如果你获得了某个比 $2^{2047}$ 大的数，你就拒绝，我们说错误=1 ，然后离开，接下来我们检查补齐是否是正确的，如果补齐不正确，我们还是拒绝和离开。这个实现的问题是，对于计时攻击来说是脆弱的。通过泄露时间信息，攻击者可以解出是什么导致了错误，是 RSA 解密后数太大的错误，还是因为补齐太大的错误，如果攻击者通过计时可以区分这两种错误，那么与 Bleichenbacher 类似，实际上是可能完全解密任何你选择的密文的，一丁点的信息泄露都可以让攻击者完全解密任何他想要的密文。这展示了，即使你正确的实现了 OAEP 的数学部分，你也可能会搞砸，使自己暴露于计时攻击中。

不要自己去实现密码学，特别是 RSA 、OAEP 。

RSA 陷门置换的安全性

RSA真的是一个单向函数吗？

如果一个攻击者想求 RSA 函数的逆，攻击者有公钥 (N,e) ，现在他有 $x^e$ ，他的目标是还原 x 。那么，有了 $x^e$ mod N ，还原 x 的难度有多大？也就是，计算合数模的 e 次方根有多难？如果这个问题实际上很难，那么 RSA 事实上就是一个单向函数；如果很简单，那么 RSA 就会被破解了。

这个问题目前最好的算法，需要我们首先分解模 N ，一旦我们分解了模，就容易计算模 p 的 e 次方根，容易计算模 q 的 e 次方根，然后有了这些 e 次方根，实际上容易把它们组合起来，使用中国剩余定理，即可以还原模 N 的 e 次方根，我们一旦能够分解模，计算模 N 的 e 次方根就会很容易，但是分解模，就目前来看是一个非常困难的问题。

但一个自然的问题是，为了计算模 N 的 e 次方根，真的一定要分解模吗？

就目前我们所知道最好的计算模 N 的 e 次方根的算法，是需要将 N 因子分解的，但是也许就有一条捷径可以让我们计算模 N 的 e 次方根而不用分解模。为了证明这是不可能的，我们必须证明一个规约，就是说我们必须证明，如果我给大家一个有效算法可以计算模 N 的 e 次方根，这个算法也可以被改造成一个计算因子分解的算法，这会证明任何人都不能以比分解模更快的速度计算模 N 的 e 次方根，如果我们有这么一个结果，就会证明破解 RSA 实际上与分解大合数一样难。

假设我给你一个算法，可以计算模 N 的立方根，对任意 $Z_N$ 中的 x ，这个算法会计算出 x 的模 N 立方根，你能证明，使用这样一个算法能分解模 N 吗？即使整个证明我们还不知道，我们知道的是，e = 2 时，如果我给你一个计算模 N 平方根的算法，那么事实上这就蕴含着分解模的算法，那么，计算平方根事实上与分解模一样困难。如果回想 RSA 的定义要求 ed = 1 mod Φ(N) ，这意味着，e 与模 Φ(N) 必须是互质的，第一个方程是说，e 是 Φ(N) 可逆的，但是，如果 e 是 Φ(N) 可逆的，这必将意味着 e 必须与 Φ(N) 互质，而 Φ(N)=(p-1)(q-1) ，由于 p 和 q 都是大质数，p-1 和 q-1 总是偶数，因此 gcd(2,Φ(N))=2 ，因为 Φ(N) 是偶数，因此，公钥指数 2 与 Φ(N) 不互质。这意味着，即使我们有了一个从计算平方根到因子分解的规约，e=2 也不能被拿来当作 RSA 指数，真正合法的最小 RSA 指数等于 3 ，但是等于 3 ，问题就是计算立方根，与因子分解一样难。

我们目前只知道 RSA 是一个单向函数，事实上，破解 RSA，计算 e 次方根，都要求因子分解模。

现在有很多研究工作，试图提高 RSA （加密或解密）的性能。

一个试图提高 RSA 性能的错误例子

设想如果我想加速 RSA 解密，解密是通过计算密文的 d 次方，而指数算法的运行时间与 d 的长度大小成线性关系，与 log(d) 呈线性。试想，如果要加速 RSA 解密，为什么不使用一个小 d 呢？比如说，使用一个解密指数，大约是 $2^{128}$ ，这已经够大了，穷举 d 实际上是不可能的，但正常情况下，解密指数 d 约与模一般大，比如说 2000 位，通过使用仅为 128 位的 d ，从 2000 位降到 100 位，可以提高 RSA 解密速度 20 倍，实际上这是一个非常糟糕的点子。

看下面的思路，Michael Winener 有一个攻击，证明了事实上，一旦私钥指数 d 小于模的 1/4 次方，RSA 是不安全的。如果模大约是 2048 位，这意味着如果 d 小于 $2^{512}$，那么 RSA 是完全不安全的，而且这是最坏的一种不安全。即，给定一个公钥 e ，你可以很快还原出私钥 d 。有传言说，这个攻击可以针对最多 512 位，那么为什么我们不让这个模，比如说 530 位，那么这个攻击就不能用了，但是我们依然可以让 RSA 解密加速 4 倍，因为我们把指数从 2000 位降到 530 位，实际上，这是不安全的。Wiener 的攻击有一个扩展，证实了如果 d 小于 $N^{0.292}$，那么 RSA 也是不安全的。事实上，这个猜想是说，这对最多 $N^{0.5}$ 来说是正确的，这是一个开放的问题。

为了准确，当说 RSA 是不安全时，意思是，有了公钥 (N,e) ，你的目标是还原私钥 d 。

这里的教训是，任何人都不应该在 d 上强加任何结构以期提高 RSA 性能。

Wiener’s attack

它涉及的只是操作一些不等式。在 Wiener 的攻击里，我们有模和 RSA 指数：(N,e)，目的是还原私钥指数 d 。我们只知道 d 是小于 N 的四次方根的，事实上我将假设 d 小于 N 的四次方根再除以 3 ，这个 3 不重要，但这里主要起作用的项是，d 小于 N 的四次方根。

首先，因为 e 和 d 是 RSA 的公钥和私钥指数，我们知道 ed = 1 mod Φ(N)，这是什么意思？这意味着，存在某个整数 k ，满足 ed = k·Φ(N)+1 ，事实上，ed = k·Φ(N)+1 这个等式是这个攻击的关键所在，首先我们将两边同时除以 d·Φ(N) ，得到 e/Φ(N) - k/d = 1/(d·Φ(N)) ，加上绝对值，不会改变等性，|e/Φ(N) - k/d| = 1/(d·Φ(N))，现在 Φ(N) 几乎等于 N ，