原文：Twenty Years of Attacks on the RSA Cryptosystem

作者：Dan Boneh@Stanford University([email protected])

译者：Jing Ling@360ESG A-Team([email protected])

1 介绍

由Ron Rivest，Adi Shamir和Len Adleman发明的RSA密码系统首次在1977年8月的"科学美国人"杂志上发表（译者注：本文于1999年2月在美国数学学会的Notices杂志首次发布）。密码系统最常用于提供隐私保护和确保数字数据的真实性。目前，RSA部署在许多商业系统中。Web服务器和浏览器使用它来保护Web流量，它可以用于保障电子邮件的隐私和真实性，还可以用于保护远程登录会话，同时它也是电子信用卡支付系统的核心。简而言之，RSA常用于需要考虑数字数据安全性的应用中。

自最初发布以来，RSA系统已被许多研究人员分析认为是易受攻击的。尽管二十年的研究出了许多引人入胜的攻击，但其中没有一个攻击是毁灭性的。这些攻击主要说明了不当使用RSA的危险，可见安全地实施RSA确实也是一项非常重要的任务。我们的目标是使用基础数学的知识分析其中的一些攻击，在整个分析过程中，我们遵循标准命名约定，使用Alice和Bob表示希望彼此通信的两个正常通信方，使用Marvin来表示希望窃听或篡改Alice和Bob之间通信的恶意攻击者。

我们首先介绍一下RSA加密的简化版本。令$N = pq$是比特位长度相同($n/2$位)的两个大素数的乘积。常见$N$的长度大小是$n$=1024位（即：309个十进制数字），质因子$p,q$=512位。令$e,d$为满足$ed = 1\ \text{mod}\ \varphi(N)$的两个整数，其中$\varphi\left( N \right) = (p - 1)(q - 1)$是乘法群$\mathbb{Z}_{N}^{*}$的阶数。我们称$N$为RSA模数，$e$为加密指数，$d$为解密指数。$\left\langle N,e \right\rangle$为公钥。顾名思义，公钥是公开的，并用于加密消息。$\left\langle N,d \right\rangle​$称为密钥或私钥，一般情况下只有加密消息的接收者知道，私钥能够解密密文。

消息$M$是一个整数且满足$M \in \mathbb{Z}_{N}^{*}$，要加密$M$，计算$C = M^{e}\ \text{mod}\ N$，要解密密文合法接受者计算$M = C^{d}\ \text{mod}\ N$。（译者注：下面是译者添加的$M = C^{d}\ \text{mod}\ N$的证明）

欧拉定理：若$a,n$为正整数，且$a,n$互素（即$\gcd\left( a,n \right) = 1$），则$a^{\varphi(n)} = 1\ \ \text{mod}\ n$。

已知$\ 1 = \ ed\ \ \text{mod}\ \varphi(n)$，$m < n$，$c = m^{e}\ \text{mod}\ n$，$\gcd\left( m,n \right) = 1$，求证$m = c^{d}\ \text{mod}\ n$。

证明：

等式左边为$m$

等式右边为$c^{d}\ \text{mod}\ n$

$$\because c = m^{e}\ \text{mod}\ n$$

$$\therefore c^{d}\ \text{mod}n = {(m^{e}\ \text{mod}\ n)}^{d}\ \ \text{mod}\ n = m^{ed}\ \ \text{mod}\ n$$

$$\because 1 = \ ed\ \ \text{mod}\text{\ φ}\left( n \right)$$

$$\therefore ed = k\varphi\left( n \right) + 1$$

$$\therefore c^{d}\ \text{mod}\ n = m^{ed}\ \ \text{mod}\ n = m^{\text{kφ}\left( n \right) + 1}\ \ \text{mod}\ n = m{(m^{\varphi(n)})}^{k}\ \ \text{mod}\ n$$

$$\because\gcd\left( m,n \right) = 1$$

$$\therefore m^{\varphi(n)} = 1\ \ \text{mod}\ n$$

$$\therefore c^{d}\ \text{mod}\ n = m{(m^{\varphi(n)})}^{k}\ \ \text{mod}\ n = m{(1\ \ \text{mod}\ n)}^{k}\ \ \text{mod}\ n = m{(1)}^{k}\ \ \text{mod}\ n = m\ \ \text{mod}\ n$$

$$\because m < n$$

$$\therefore m\ \text{mod}\ n = m$$

$$\therefore c^{d}\ \text{mod}\ n = m\ \ \text{mod}\ n = m$$

等式右边等于等式左边，证毕。

定义一个RSA函数$x \longmapsto x^{e}\text{modN}$，如果$d$已知，很容易使用等式$m = c^{d}\ \text{mod}\ n$求出$x$，我们称$d$为求解函数的陷门。在本次课题研究在没有陷门$d$的情况下求解RSA函数，更准确的说，给一个三元组$\left\langle N,e,C \right\rangle$，我们知道在不知道$N$的因子想计算$C$模$N$的$e$根是非常困难的。因为$\mathbb{Z}_{N}^{*}$是有限集，因此可以枚举$\mathbb{Z}_{N}^{*}$的所有元素直到找到$M$。遗憾的是，这将导致算法具有$N$阶的运行时间，即其输入大小的指数，其为$\mathrm{\log}_{2}N$的阶数。我们对运行时间更低的算法感兴趣，即$n^{c}$的阶数（其中$n = \mathrm{\log}_{2}N$）或者$c$是一些小的常数（比如说小于5）。实践表明这些算法通常在所讨论的输入情况表现良好，在整篇论文中，我们将此类算法称为高效算法。

此次课题我们主要研究RSA函数而不是RSA密码系统。笼统地说，随机输入上求解RSA函数的应该是非常困难的，也就是意味着给定$\left\langle N,e,C \right\rangle$攻击者无法计算出明文$M$。这还不够，密码系统必须抵御更微妙的攻击。如果给出$\left\langle N,e,C \right\rangle$，想从$M$中计算出任何信息应该是非常难的，这被称为语义安全。我们不讨论这些微妙的攻击，但是必须指出的是如上所述的RSA在语义上是不安全的：给定$\left\langle N,e,C \right\rangle$，可以容易地推导出关于明文$M$的一些信息（例如，可以容易地从$C$推导出$N$上的$M$的雅可比符号）。通过向加密过程添加随机处理流程，可以保障RSA在语义上的安全性。

RSA函数$x \longmapsto x^{e}\text{modN}$是一个单向陷门函数，正向它可以很容易地计算，但是（据我们所知）除非在特殊情况下，否则在没有陷门$d$的情况下不能有效地反向求解的。单向陷门函数可用于数字签名，数字签名可以保障电子文件的真实性和不可否认性。例如，它们用于签署数字支票或电子采购订单。为了使用RSA对消息$M \in \mathbb{Z}_{N}^{*}$进行签名，Alice使用其私钥$\left\langle N,d \right\rangle$签名$M$并获得签名$S = M^{d}\ \text{mod}\ N$。给定$\left\langle M,S \right\rangle$之后任何人都可以验证$M$上的Alice签名通过$M = S^{e}\ \text{mod}\ N$。因为只有Alice可以生成$S$，人们可能会认为攻击者无法伪造Alice的签名。然而事情并非如此简单，为了保障签名的安全还需要一些额外的措施。数字签名是RSA的重要应用，此次课题我们也会研究一些针对RSA数字签名的攻击。

RSA密钥对可以这样生成，选取两个随机$\frac{n}{2}$位素数并将它们相乘以获得$N$来生成。然后，对于给定的加密指数$e < \varphi(N)$，使用扩展欧几里德算法计算$d = e^{- 1}\mathrm{\ \text{mod}}\ \varphi(N)$。由于素数集是足够密集的，因此可以通过重复选择随机$\frac{n}{2}$位整数并使用概率素性测试对每个素数进行素性测试来快速生成随机$\frac{n}{2}$位素数。

1.1 大数分解

给了RSA公钥$\left\langle N,e \right\rangle$，首先想到的攻击就是分解模数$N$，给了$N$的因子攻击者可以计算得到$\varphi(N)$，从而也可以计算得到解密指数$d = e^{- 1}\ \text{mod}\ \varphi(N)$，我们称这种分解模数的方法为针对RSA的暴力攻击。虽然分解算法已经稳步改进，但是在正确使用RSA情况下，当前的技术水平仍远未对RSA的安全性构成威胁。大整数分解是计算数学之美，不过本文研究主题并不是大整数分解。为完整起见，我们顺便提一下，目前普通数字域筛法是效率最高的分解方法。分解$n$位整数需要时间为$\exp\left( ((c + o(1))n^{\frac{1}{3}}\mathrm{\log}^{\frac{2}{3}}n) \right)$其中$c < 2$，对RSA进行攻击的方法花费时间超过这个范围就那么吸引人了，比如暴力搜索$M$方法，还有一些RSA发布不久后的旧方法。

我们的目的是研究在不直接分解RSA模数$N$情况下解密消息的攻击方法，值得注意的是，一些RSA模数的稀疏集，$N = pq$可以很容易地被分解，举个例子，如果$p - 1$是乘积的质因子且小于$B$，那么在小于$B^{3}$时间内分解$N$。

如上所述，如果存在有效的因式分解算法，则RSA是不安全的，反之亦然。这是一个由来已久的公开问题：必须要有一个$N​$的因子才能有效地计算$e^{th}​$模$N​$的根数？破解RSA和因式分解一样难吗？我们在下面提出了具体的开放性问题。

开放性问题 1

给定$N$和$e$满足$\gcd\left( e,\varphi\left( N \right) \right) = 1$，定义$f_{e,N}$函数：$\mathbb{Z}_{N}^{*} \rightarrow \mathbb{Z}_{N}^{*}$，$f_{e,N}\left( x \right) = x^{\frac{1}{e}}\mathrm{\ \text{mod}}\ \ N$。是否有多项式时间算法$A$来计算给定$N$的因子以及对于某个$e$求得$f_{e,N}\left( x \right)$的一个谕言？

$f\left( x \right)$的谕言用于评估在单位时间内任何输入$x$的函数，最近Boneh和Venkatesan提供的证据表明，在$e$比较小的情况下，上述问题的答案可能是否定的。换句话说，在$e$比较小的情况下，可能不存在从分解到破解RSA的多项式时间缩减。他们通过实验表明在某个模型中对小$e$的问题的肯定答案会产生一个有效的因式分解算法。我们注意到，对开放问题1的肯定回答会引起对RSA的"选择密文攻击"。因此，否定的回答可能才是大家喜闻乐见的。

接下来，我们证明公开私钥$d$和分解$N$是等价的。由此可见，对于知道$d$的任何一方来说，隐藏$N$的因式分解是没有意义的。

事实1

$\left\langle N,e \right\rangle$为RSA的公钥，给定私钥$d$可以有效地分解模数$N = pq$。相反地，给定$N$的因式分解，可以有效地算出私钥$d$。

证明

$N$的因式分解得到$\varphi\left( N \right)$，因为$e$已知的，那么可以算出$d$，反之亦然。我们现在证明给定$d$可以分解$N$。给定$d$，计算$k = de - 1$。根据$d$和$e$的定义我们知道$k$是$\varphi\left( N \right)$的倍数。由于$\varphi\left( N \right)$是偶数，$k = 2^{t}r$其中$r$为奇数且$t \geq 1$。对于每个$g \in Z_{N}^{*}$都有$g^{k} = 1$，因此$g^{k/2}$是单位模$N$的平方根。根据中国剩余定理，1有四个平方根模$N = pq$。其中两个平方根是$\pm 1$，另外两个是$\pm x$，其中$x$满足$x = 1\mathrm{\ \text{mod}}\ p$和$x = - 1\mathrm{\ \text{mod}}\ q$。用这最后两个平方根中的任意一个，通过计算$\mathrm{\gcd}(x - 1,N)$来揭示$N$的因式分解。一个直截了当的论证表明，如果从$Z_{N}^{*}$中随机选择$g$，那么序列中的一个元素$g^{k/2}$，$g^{k/4}$,...，$g^{k/2^{t}}\ \text{mod}\ N$是统一平方根的概率至少为1/2，从而揭示了$N$的分解，序列中的所有元素可以在时间$O(n^{3})$内有效地计算，其中$n = \log_2N$。

2 基本攻击

我们首先描述一些老的基本攻击，这些攻击说明了RSA的公然滥用情况。虽然存在许多这样的攻击，但我们仅举两个例子。

2.1 共模

为了避免为每个用户生成不同的模数$N = pq$，人们可能希望一劳永逸地固定使用一个$N$，所有用户都使用相同的$N$。可信的中央机构可以向用户$i$提供唯一的一对$e_{i}$，$d_{i}$，用户$i$从其中生成公钥$\left\langle N,e \right\rangle$和私钥$\left\langle N_{i},e_{i} \right\rangle$。

乍一看，这似乎行得通：为Alice准备的密文$C = M^{e_{a}}\mathrm{\ \text{mod}}\ \ N$无法由Bob解密，因为Bob不知道$d_{a}$。但是，这是不正确的，由此产生的系统是不安全的。事实上，Bob可以使用他自己的指数$e_{b}$，$d_{b}$来分解$N$。一旦$N$被分解，Bob就可以从她的公钥$e_{a}$中计算出Alice的私钥$d_{a}$。Simmons的这一观察结果表明，RSA模不应被一个以上的实体使用。

2.2 盲化

设$\left\langle N,d \right\rangle$是Bob的私钥，而$\left\langle N,e \right\rangle$是他相应的公钥。假设攻击者Marvin想要Bob在消息$M \in Z_{N}^{*}$上签名。当然Bob不是傻瓜，他拒绝签署$M$。但是Marvin可以尝试以下方法：他随机选择一个$r \in Z_{N}^{*}$并设$M^{'} = r^{e}\text{M}\ \text{mod}\ N$。然后他让Bob在随机消息$M^{'}$上签名。Bob可能愿意在看上去没什么问题的$M$上签名$S^{'}$，但是回想一下$S^{'} = {(M^{'})}^{d}\mathrm{\ \text{mod}}\ \ N$，Marvin现在简单地计算$S = S^{'}/r\mathrm{\ \text{mod}}\ \ N$就得到Bob在初始$M$上的签名$S$。

$$S^{e} = \frac{\left( S^{'} \right)^{e}}{r^{e}} = \frac{\left( M^{'} \right)^{ed}}{r^{e}} \equiv \frac{M^{'}}{r^{e}} = M(\mathrm{\ \text{mod}}\ \ N)$$

这种称为盲化的技术使Marvin能够在他选择的消息上获得有效的签名，方法是让Bob在随机的"盲化"消息上签名。Bob不知道他实际在签名的是什么消息。由于大多数签名方案在签名之前对消息$M$应用"单向散列"算法，因此此种攻击倒不是一个严重的问题。尽管我们将盲化描述为一种攻击，但它实际上是实现匿名数字现金所需的一个有用属性(可以用来购买商品的现金，但不会透露购买者的身份)。

3 低私钥指数

为了减少加密时间（或签名生成时间），人们可能希望使用小值$d$而不是随机$d$。由于模幂运算需要花费线性时间为$\log_2d$，所以小$d$可以使性能提高至少10倍(对于1024位模数而言)。不幸的是，由M.Wiener发现的一种巧妙的攻击表明，一个小的$d$会导致密码系统完全被攻破。

定理2（M. Wiener）

令$N = \text{pq}$且$q < p < 2q$，$d < \frac{1}{3}N^{\frac{1}{4}}$，给定$\left\langle N,e \right\rangle$且满足$ed = 1\ \text{mod}\ \varphi(N)$，攻击者可以有效计算出$d$。

证明

证明基于使用连分数的逼近，由于$ed = 1\ \text{mod}\ \varphi(N)$，那么存在一个$k$满足$ed - k\varphi(N) = 1$。所以，

$$\left| \frac{e}{\varphi(N)} - \frac{k}{d} \right| = \frac{1}{d\varphi(N)}$$

因此，$\frac{k}{d}$是$\frac{e}{\varphi(N)}$的逼近，尽管Marvin不知道$\varphi(N)$，但是他可能会使用$N$去近似$\varphi(N)$。因为$\varphi\left( N \right) = N - p - q + 1$（译者注：$\varphi\left( N \right) = \left( p - 1 \right)\left( q - 1 \right) = pq - p - q + 1 = N - p - q + 1$），$p + q - 1 < 3\sqrt{N}$（译者注：因为$q^{2} < pq = N$，所以$q < \sqrt{N}$，所以$N - \varphi\left( N \right) = p + q - 1 < 2q + q - 1 < 3q < 3\sqrt{N}$），我们有$\left| N - \varphi\left( N \right) \right| < 3\sqrt{N}$。

使用$N$替换$\varphi(N)$，我们得到：

$$\left| \frac{e}{N} - \frac{k}{d} \right| = \left| \frac{ed - kN}{\text{Nd}} \right| = \left| \frac{ed - k\varphi\left( N \right) - kN + k\varphi\left( N \right)}{\text{Nd}} \right|\text{}$$

$$= \left| \frac{1 - k\left( N - k\varphi\left( N \right) \right)}{\text{Nd}} \right| \leq \left| \frac{3k\sqrt{N}}{\text{Nd}} \right| = \frac{3k}{d\sqrt{N}}$$

现在，$\text{kφ}\left( N \right) = ed - 1 < ed$，因为$e < \varphi\left( N \right)$，我们知道$k < d < \frac{1}{3}N^{\frac{1}{4}}$（译者注：可以得到$3k < 3d < N^{\frac{1}{4}}$和$dN^{\frac{1}{4}} > 3d^{2}$）。因此我们得到：

$$\left| \frac{e}{N} - \frac{k}{d} \right| \leq \frac{1}{dN^{\frac{1}{4}}} < \frac{1}{2d^{2}}(译者注：有的资料写成\frac{1}{3d^{2}})$$

这是一个经典的逼近关系，分数$\frac{k}{d}$且$d < \varphi(N)$在$\log_2N$约束内非常逼近$\frac{e}{N}$。实际上，所有类似$\frac{k}{d}$这样的分数都是$\frac{e}{N}$的连分数展开的收敛。因此我们首要做的便是计算$\frac{e}{N}$的连分数的$\log N$收敛，其中一个连分数就等于$\frac{k}{d}$。因为$ed - k\varphi\left( N \right) = 1$，我们有$\gcd\left( k,d \right) = 1$，因此$\frac{k}{d}$是一个最简分数。这是可以算出密钥$d$的线性时间算法。

由于通常$N$都是1024位，因此$d$必须至少256位长才能避免这种攻击。这对于诸如"智能卡"之类的低功耗设备来说是不幸的，因为小$d$就能节省大量能耗。 然而，并不是毫无办法。Wiener提出了许多能够实现快速解密并且不易受其攻击影响的技术：

使用大$\mathbf{e}$ ：假设不是减小$e$模$\varphi\left( N \right)$，而是使用$\left\langle N,e^{'} \right\rangle$作为公钥，其中对于某些大$t$有$e^{'} = e + t \cdot \varphi\left( N \right)$。

显然，$e^{'}$可以代替$e$用于消息加密，当使用大的$e$值时，上述证明中的$k$不再小。一个简单的计算表明，如果$e^{'} > N^{1.5}$，那么无论$d$多小，都无法实施上述攻击。然而，大的$e$值将导致加密时间的增加。

使用CRT：

另一种方法是使用中国剩余定理（CRT）。假设选择$d$使得$d_{p} = d\mathrm{\ \text{mod}}\ (p - 1)$和$d_{q} = d\mathrm{\ \text{mod}}\ (q - 1)$都很小，比如都是128位。则可以进行如下密文$C$的快速解密：首先计算$M_{p} = C^{d_{p}}\mathrm{\ \text{mod}}\ p$和$M_{q} = C^{d_{q}}\mathrm{\ \text{mod}}\ q$。

然后使用CRT计算满足$M = M_{p}\mathrm{\ \text{mod}}\ p$和$M = M_{q}\mathrm{\ \text{mod}}\ q$的唯一值$M \in \mathbb{Z}_{N}$.

得到的$M$满足等式$M = C_{d}\mathrm{\ \text{mod}}\ \ N$。关键点在于虽然$d_{p}$和$d_{q}$很小，但是$\text{d}\mathrm{\ \text{mod}}\ \varphi(N)$的值可以很大，大约在$\varphi(N)$的数量级上。因此，定理2的攻击不再适用。我们注意到，如果给定了$\left\langle N,e \right\rangle$，则存在一种攻击能够使攻击者能够在时间$O\left( min(\sqrt{d_{p}},\sqrt{d_{q}}) \right)$内对$N$进行因子分解。因此，$d_{p}$和$d_{q}$不能太小。

我们不知道这些方法中是否都安全。我们所知道的是，Wiener攻击对它们无效。最近由Boneh和Durfee改进的定理2证明了只要$d < N^{0.292}$，攻击者就可以从$\left\langle N,e \right\rangle$中有效地算出$d$。这些结果表明Wiener的界限并不固定。正确的界限可能是$d < N^{0.5}$。截至撰写本文时，还是一个尚未解决的问题。

开放性问题2

令$N = pq$，$d < N^{0.5}$，如果Marvin知道$\left\langle N,e \right\rangle$和$ed = 1\mathrm{\ \text{mod}}\ \varphi(N)$及$e < \varphi(N)$关系，他能有效算出$d$吗？

4 低公钥指数

为了减少加密或签名验证时间，通常会使用一个小的公钥指数$e$。$e$的最小可能值为3，但为防止某些攻击，建议使用$e = 2^{16} + 1 = 65537$。当使用值$2^{16} + 1$时，签名验证需要17次乘法，而使用随机的$e \leq \varphi(N)$时则需要大约1000次乘法。与上一节的攻击不同，当使用一个小$e$时，针对的攻击不只是攻破而已。

4.1 Coppersmith定理

针对RSA低公钥指数最有力的攻击基于Copper-smith的一个定理，Coppersmith定理有很多应用，这里我们只讨论其中的一些应用，证明使用LLL格基约化算法如下。

定理3（Coppersmith） 令$N$为一个整数，$f\mathbb{\in Z}\left\lbrack x \right\rbrack$是$d$次的一元多项式，设$X = N^{\frac{1}{d} - \epsilon}$其中$\epsilon \geq 0$，在给定$\left\langle N,f \right\rangle$之后Marvin能够有效找到所有满足$f\left( x_{0} \right) = 0\ \text{mod}\ N$的整数$\left| x_{0} \right| < X$，运行时间由在$O(w)$维数且$w = \mathrm{\min}(\frac{1}{\epsilon},\log_2N)$的格上运行LLL算法所需的时间决定。

该定理为有效地求$f$模$N$的所有小于$X = N^{\frac{1}{d}}$的根提供了一种算法，当$X$越小，算法的运行时间越短。这个定理的强大之处在于它能够找到多项式的小根。当模数为素数时，就目前而言，找不到比使用Coppersmith定理更好的求根算法了，没有理由不使用Coppersmith定理。

我们概述了Coppersmith定理证明背后的主要思想，我们采用由Howgrave-Graham提出的简化方法，给定一个多项式$f\left( x \right) = \sum_{}^{}{a_{i}x^{i}\mathbb{\in Z}\left\lbrack x \right\rbrack}$，定义$\left\| h \right\|^{2} = \sum_{i}^{}{\left| a_{i} \right|^{2}}$，证明依赖于下面的观察。

引理4

令$h\left( x \right)\mathbb{\in Z}\left\lbrack x \right\rbrack$为$d$次多项式，$X$为正整数，假设$\left\| h(xX) \right\| < \frac{N}{\sqrt{d}}$，如果$\left| x_{0} \right| < X$满足$h\left( x_{0} \right) = 0\ \text{mod}\ N$，那么$h\left( x_{0} \right) = 0$成立。

证明 从Schwarz不等式观察到：

$$\left| {h(x}_{0}) \right| = \left| \sum_{}^{}{a_{i}x_{0}^{i}} \right| = \left| \sum_{}^{}{a_{i}X^{i}}\left( \frac{x_{0}}{X} \right)^{i} \right| \leq \sum_{}^{}\left| a_{i}X^{i}\left( \frac{x_{0}}{X} \right)^{i} \right|$$

$$\leq \sum_{}^{}{\left| a_{i}X^{i} \right| \leq}\sqrt{d}\left\| h\left( \text{xX} \right) \right\| < N$$

因为$h\left( x_{0} \right) = 0\ \text{mod}\ N$,我们得出结论$h\left( x_{0} \right) = 0$。

引理指出，如果$h$是一个低范数多项式，则$\text{h}\mathrm{\ \text{mod}}\ \ N$的所有小根也是$h$在整数上的根。引理表明，要找到$f\left( x \right)\mathrm{\ \text{mod}}\ \ N$的一个小根$x_{0}$，我们需要寻找另一个与$f$模$N$有相同根的低范数多项式$h \in \mathbb{Z}\left\lbrack x \right\rbrack$，这样就能容易找到$h$在整数上的根$x_{0}$。为此，我们可以寻找一个多项式$g\mathbb{\in Z}\left\lbrack x \right\rbrack$，使得$h = gf$具有低范数，即范数小于$N$。这相当于寻找具有低范数多项式$f,xf,x^{2}f\ldots,x^{r}f$的整数线性组合。不过，大多数情况下，并不存在具有足够小的范数的非平凡线性组合。

Coppersmith找到了解决这个问题的窍门：如果$f\left( x_{0} \right) = 0\ \text{mod}\ N$成立，那么对于任意$k$则有$f\left( x_{0} \right)^{k} = 0\ \text{mod}\ N^{k}$。更一般地，定义以下多项式：

$$g_{u,v}\left( x \right) = N^{m - v}x^{u}f{(x)}^{v}$$

对于一些预定义的$m$，则$x_{0}$是$g_{u,v}\left( x \right)$模$N^{m}$的一个根，其中$u \geq 0$和$0 \leq v \leq m$。要使用引理4，我们必须找到多项式$g_{u,v}\left( x \right)$的一个整数线性组合$h\left( x \right)$，使得$h(xX)$的范数小于$N^{m}$ (回想一下$X$是满足$X \leq N^{1/d}$的$x_{0}$上界)。由于范数（是$N^{m}$而不是$N$）的松弛上界，我们可以证明，对于足够大的$m$，总是存在一个线性组合$h\left( x \right)$满足所要求的界。一旦$h\left( x \right)$被找到，引理4就意味着它有$x_{0}$作为整数的根,因此,可以很容易地找到$x_{0}$。

如何有效地找到$h\left( x \right)$还有待证明，要做到这一点，我们必须说明一些关于$\mathbb{Z}^{w}$格的基本事实。 设$u_{1},\ldots,u_{w} \in \mathbb{Z}^{w}$是线性独立的向量。由$\left\langle u_{1},\ldots,u_{w} \right\rangle$构成的(满秩)格$L$是$u_{1},\ldots,u_{w}$的所有整数线性组合的集合。$L$的行列式定义为$w \times w$方阵的行列式，它的行列式是向量$u_{1},\ldots,u_{w}$。

在我们的例子中，我们把多项式$g_{u,v}\left( \text{xX} \right)$看作向量，并研究了它们所构成的格$L$。设$v = 0,\ldots,m$，$u = 0,\ldots,d - 1$，则格的维数$w = d(m + 1)$。例如，当$f$是二次一元多项式且$m = 3$时，得到的格由以下矩阵的行构成：

$*$元对应于我们忽略其值的多项式的系数，所有空元为零。由于矩阵是三角形的，它的行列式是对角线上元素的乘积(如上所示)，我们的目标是在这个格中找到短向量。

Hermite的一个经典结论表明：任意维数为$w$的格$L$包含一个非零向量$v \in L$，它的$L_{2}$范数满足$\left\| v \right\| \leq \gamma_{w}{det(L)}^{\frac{1}{w}}$，其中$\gamma_{w}$是只依赖于$w$的常数。Hermite的界可以用来证明，对于足够大的$m$，我们的格包含需求小于$N^{m}$的范数向量。问题是我们能否有效地在$L$中构造长度小于Hermite界的短向量。LLL算法是一种有效的算法，恰好可以做到。

事实5（LLL）

设$L$是由$\left\langle u_{1},\ldots,u_{w} \right\rangle$所构成的格。当$\left\langle u_{1},\ldots,u_{w} \right\rangle$作为输入时，LLL算法输出一个向量$v \in L$满足：

$$\left\| v \right\| \leq 2^{\frac{w}{4}}{det(L)}^{\frac{1}{w}}$$

LLL算法的运行时间是输入长度的四分之一。

LLL算法（以其发明者L. Lovasz、A. Lenstra和H. Lenstra Jr的名字命名）在计算数论和密码学中有许多应用。它在1982年的发现为整数上多项式的因式分解提供了一种有效的算法，更广泛地说，为数环上的多项式的因式分解提供了一种有效的算法。LLL算法经常被用来攻击各种密码系统，例如，许多基于"背包问题"的密码系统都是使用LLL算法破解的。

利用LLL算法，我们可以完成Coppersmith定理的证明。为了保证LLL算法产生的向量满足引理4的界，我们需要满足：

$$2^{\frac{w}{4}}{det(L)}^{\frac{1}{w}} < \frac{N^{m}}{\sqrt{w}}$$

其中$w = d(m + 1)$是$L$的维数。常规计算表明，对于足够大的$m$，能满足约束条件。实际上，当$X = N^{\frac{1}{d} - \epsilon}$时，取$m = O(\frac{k}{d})$和$k = \mathrm{\min}(\frac{1}{\epsilon},\log N)$就足够了。因此，运行时间主要由在维数为$O(k)$的格上运行LLL算法所决定。

一个自然而然的问题，Coppersmith定理能否应用于二元和多元多项式。如果$f(x,y) \in \mathbb{Z}_{N}\left\lbrack x,y \right\rbrack$有根$\left( x_{0},y_{0} \right)$且有适当的界$\left| x_{0}y_{0} \right|$，Marvin能有效地找到$\left( x_{0},y_{0} \right)$吗？尽管相同的技术似乎适用于某些二元多项式，但目前还是一个有待证明的开放性问题。随着越来越多的结果依赖于Coppersmith定理的二元扩张，所以严密的算法将会非常有用。

开放性问题3

找出Coppersmith定理可以推广到二元多项式的一般条件。

4.2 Hastad广播攻击

作为Coppersmith定理第一个应用，我们对由Hastad提出的旧攻击进行了改进。假设Bob希望将加密消息$M$发送给多方$P_{1},P_{2},\ldots,P_{k}$。每一方都有自己的RSA密钥$\left\langle N_{i},e_{i} \right\rangle$。我们假定$M$比所有$N_{i}$都小。Bob为了发送$M$，天真地使用每个公共密钥对其进行加密，并将第$i^{\text{th}}$个密文发送给$P_{i}$。攻击者Marvin可以窃听Bob对外的连接，并收集传输的$k$个密文。

为了简单起见，假设所有公钥指数$e_{i}$为3。一个简单的论证表明，当$k \geq 3$时，Marvin可以计算出$M$。实际上，Marvin得到$C_{1},C_{2},C_{3}$，其中：

$$C_{1} = M^{3}\ \text{mod}\ N_{1},C_{2} = M^{3}\ \text{mod}\ N_{2},C_{3} = M^{3}\ \text{mod}\ N_{3}$$

对于所有的$i \neq j$，我们可以假设$\gcd\left( N_{i},N_{j} \right) = 1$，否则Marvin可以因式分解一些$N_{i}$。因此，将中国剩余定理(CRT)应用于$C_{1},C_{2},C_{3}$，给出的$C^{'} \in \mathbb{Z}_{N_{1}N_{2}N_{3}}$满足${C^{'} = M}^{3}\ \text{mod}\ N_{1}N_{2}N_{3}$。由于$M$小于所有的$N_{i}$，我们有$M^{3} < N_{1}N_{2}N_{3}$，那么${C^{'} = M}^{3}$在整数上成立，因此，Marvin可以通过计算$C^{'}$的实数立方根来得到$M$。更一般的情况是，如果所有的公钥指数都等于$e$，则只要$k \geq e$，Marvin就可以计算出$M$。不过这种攻击只有使用较小的$e$值时才是可行的。

Hastad提出了一种更强的攻击方法。为了抵御Hastad的攻击，考虑一下对上述攻击做一下天真防御。Bob可能在加密之前"填充"消息，而不是广播加密的$M$。例如，如果$M$是$m$位长的，Bob可以将$M_{i} = i2^{m} + M$发送给$P_{i}$。由于Marvin获得了不同消息的加密，他无法发起攻击。然而，Hastad证明了这种线性填充是不安全的，事实上，他证明了在加密之前对消息应用任何固定多项式都不能阻止攻击。

假设对于每个参与者$P_{1},P_{2},\ldots,P_{k}$，Bob有一个固定的公用多项式$f_{i} \in \mathbb{Z}_{N_{i}}\left\lbrack x \right\rbrack$。为了广播消息$M$，Bob将$f_{i}(M)$的加密发送给$P_{i}$。Marvin通过窃听知道了$C_{i} = f_{i}{(M)}^{e_{i}}\ \text{mod}\ N_{i}$，其中$i = 1,\ldots,k$。Hastad表明，如果有足够的参与方，Marvin可以从所有的密文中计算出明文$M$。下面的定理是Hastad原始结论的一个更强的版本。

定理6 (Hastad) 设$N_{1},\ldots,N_{k}$是成对的相对素数，集合$N_{\min} = {min}_{i}(N_{i})$。设$g_{i} \in \mathbb{Z}_{N_{i}}\left\lbrack x \right\rbrack$是$k$个$d$次多项式。假设存在唯一的$M < N_{\min}$满足：

$$g_{i}\left( M \right) = 0\ \text{mod}\ N_{i}(i = 1,\ldots,k)$$

假设$k > d$，给定$\left\langle N_{i},g_{i} \right\rangle_{i = 1}^{k}$，我们可以有效地找到的$M$。

证明 令$\overline{N} = N_{1}{\cdots N}_{2}$，我们假定所有的$g_{i}$都是一元的。(实际上，对于某些$i$，$g_{i}$的首项系数在$\mathbb{Z}_{N_{i}}^{*}$中是不可逆的，那么$N_{i}$的因式分解就会显现出来。通过将每个$g_{i}$乘以$x$的适当幂，假定它们都有$d$次。构造多项式：

$$g\left( x \right) = \sum_{i = 1}^{k}{T_{i}g_{i}(x)},\mathrm{}\mathrm{其中}\mathrm{}T_{i} = \begin{matrix} 1\mathrm{\ \text{mod}}\ \ N_{j}\mathrm{}\mathrm{若}i = j \\ 0\mathrm{\ \text{mod}}\ \ N_{j}\mathrm{}\mathrm{若}i = j \\ \end{matrix}$$

其中$T_{i}$是整数，被称为中国剩余系数。那么$g(x)$一定是一元的，因为它首项模了所有的$N_{i}$，且次数为$d$。此外，我们还知道$g(M) = 0\mathrm{\ \text{mod}}\ \overline{N}$。定理6现在便可由定理3推导而来，因为$M < N_{\min} < {\overline{N}}^{\frac{1}{k}} < {\overline{N}}^{\frac{1}{d}}$。

该定理表明，如果提供了足够多的方程，可以有效地求解以相对素数复合模的一元方程组。令$g_{i} = f_{i}^{e_{i}} - C_{i}$，我们可以知道，当参与方数至少为$d$时，Marvin可以从给定的密文中计算出$M$，其中$d$是$e_{i}deg(f_{i})$在所有$i = 1,\ldots,k$上的最大值。特别地，如果所有的$e_{i}$都等于$e$，并且Bob发送线性相关的消息，那么Marvin只要$k > e$就可以算出明文。

Hastad的原始定理比上述定理更弱。与$d$次多项式不同，Hastad定理需要$\frac{d(d + 1)}{2}$次多项式。Hastad定理的证明类似于上一节中提到的Coppersmith定理证明。由于Hastad定理没有在格中使用$g$的幂，从而得到了一个较弱的界。

总结这一节，我们注意到，要正确地防御上述广播攻击，必须使用随机填充方法，而不是使用固定填充方法。

4.3 Franklin-Reiter相关消息攻击

当Bob用相同的模数发送与Alice相关的加密消息时，Franklin和Reiter发现了一种聪明的攻击。$\left\langle N,e \right\rangle$是爱丽丝的公钥，假设$M_{1},M_{2} \in Z_{N}^{*}$是两个不同的消息，对于某些已知的多项式$f \in Z_{N}\left\lbrack x \right\rbrack$，$M_{1},M_{2}$满足$M_{1} = f\left( M_{2} \right)\mathrm{\ \text{mod}}\ - N$。为了将$M_{1}$和$M_{2}$发送给Alice，Bob可能会天真地对消息进行加密，并传输得到的密文$C_{1},C_{2}$。我们通过证明可以知道，在给定$C_{1},C_{2}$的情况下，Marvin可以很容易地计算出$M_{1},M_{2}$。虽然攻击对任意小$e$都有效，但为了简化证明，我们给出了$e = 3$的引理。

引理7(FR)

令$e = 3$，$\left\langle N,e \right\rangle$为RSA公钥。设$M_{1} \neq M_{2} \in Z_{N}^{*}$对于$b \neq 0$的线性多项式$f = ax + b \in Z_{N}\left\lbrack x \right\rbrack$满足$M_{1} = f\left( M_{2} \right)\ \text{mod}\ N$。然后，给定$\left\langle N,e,C_{1},C_{2},f \right\rangle$，Marvin可以在$\log N$的平方时间内计算出$M_{1},M_{2}$。

证明

为了保证这部分证明的一般性，我们使用任意$e$来表示它（而不是限制为$e = 3$）。由于$C_{1} = M_{1}^{e}\mathrm{\ \text{mod}}\ \ N$，我们知道$M_{2}$是多项式$g_{1}\left( x \right) = f\left( x \right)^{e} - C_{1} \in Z_{N}\left\lbrack x \right\rbrack$的根。同样，$M_{2}$也是$g_{2}\left( x \right) = x^{e} - C_{2} \in Z_{N}\left\lbrack x \right\rbrack$的根。线性因子$x - M_{2}$是两个多项式的除法。因此，Marvin可以使用欧几里德算法来计算$g_{1}$和$g_{2}$的最大公约数(Greatest Common Divisor, GCD)。如果GCD是线性的，则可以找到$M_{2}$。GCD可以在$e$和$\log N$的平方时间内算出。

我们证明了当$e = 3$时，GCD一定是线性的。多项式$x^{3} - C_{2}$因子将$p$和$q$都模成一个线性因子和一个不可约二次因子(因为$\mathrm{\gcd}(e,\varphi\left( N \right)) = 1$，所以$x^{3} - C_{2}$在$Z_{N}$中只有一个根)。因为$g_{2}$不能整除$g_{1}$，所以GCD一定是线性的。对于$e > 3$情况，GCD几乎总是线性的。然而，对于一些罕见的$M_{1},M_{2}$和$f$，有可能得到一个非线性的GCD，在这种情况下攻击会失败。

对于$e > 3$情况，攻击所需时间是$e$的平方时间。因此，只有在使用小的公钥指数$e$时才能应用这种攻击。对于大型电子计算机来说，计算GCD的工作令人望而却步。一个有趣的问题(尽管可能很难)，为任意的$e$设计这样的攻击，尤其是能否在$\log e$的多项式时间中找到上述$g_{1}$和$g_{2}$的GCD？

4.4 Coppersmith短填充攻击

Franklin-Reiter的攻击可能看起来有点人为。毕竟，为什么Bob要给Alice发送相关消息的加密呢？Coppersmith加强了攻击，并证明了一个关于填充攻击的重要的结论。

随机填充算法可以通过将一些随机位附加到其中一个端来填充明文$M$，但是以下攻击指出了这种简单填充的危险。假设Bob向Alice发送了正确填充的$M$加密。攻击者Marvin拦截密文并阻止其到达目的地。Bob注意到Alice没有回复他的消息，并决定将$M$重新发送给Alice。他随机填充$M$并传输生成的密文。Marvin现在有两个密文，对应于使用两种不同随机填充对同一消息的两次加密。以下定理表明，虽然他不知道使用的填充算法，但Marvin仍能够算出明文。

定理8

设$\left\langle N,e \right\rangle$为RSA公钥，其中$N$的长度为是$n$位。令集合$m = \left\lbrack n/e^{2} \right\rbrack$。设$M \in Z_{N}^{*}$是长度最长为$n - m$位的消息。定义$M_{1} = 2^{m}M + r_{1}$和$M_{2} = 2^{m}M + r_{2}$，其中$r_{1}$和$r_{2}$是分别为$0 \leq r_{1},r_{2} \geq 2^{m}$的整数。如果Marvin知道了$\left\langle N,e \right\rangle$和$M_{1},M_{2}$的加密$C_{1},C_{2}$(但不知道$r_{1}$或$r_{2}$)，则他可以有效地计算出M。

证明

定义$g_{1}\left( x,y \right) = x^{e} - C_{1}$和$g_{2}\left( x,y \right) = x^{e} - C_{2}$，我们知道当$y = r_{2} - r_{1}$时，这些多项式有相同的根$M_{1}$。换句话说，$\Delta = r_{2} - r_{1}$是结式$h(y) = \text{res}_{x}(g_{1},g_{2}) \in \mathbb{Z}_{N}\left\lbrack y \right\rbrack$的根。$h$的次数最多是$e^{2}$。此外有$\left| \Delta \right| < 2^{m} < N^{\frac{1}{e^{2}}}$，因此$\Delta$是$h$模$N$的一个小根，而Marvin可以利用Coppersmith定理（定理3）有效地求出这个根。一旦$\Delta$已知，便可以使用上一节的Franklin-Reiter攻击算出$M_{2}$，从而得到$M$。

当$e = 3$时，只要填充长度小于消息长度的$\frac{1}{9^{th}}$，就可以进行攻击。这是一个重要的结论。注意，对于建议值$e= 65537$，对于标准的模数大小来说，这种攻击是无用的。

4.5 部分密钥泄露攻击

设$\left\langle N,d \right\rangle$为RSA私钥，假设Marvin通过某种方式知道了$d$的一部分，比如说四分之一。他能得到$d$剩下的部分吗？当相应的公钥指数很小时，答案是肯定的，令人惊讶吧。最近，Boneh，Durfee和Frankel证明了只要$e < \sqrt{N}$，就有可能从它的一小部分位算出$d$的所有部分。可见结论说明了保护整个RSA私钥的重要性。

定理9 (BDF)

设$\left\langle N,d \right\rangle$为RSA私钥，其中$N$长度为$n$位.。给定$d$的$\left\lceil \frac{d}{4} \right\rceil$最小有效位，Marvin可以在$\text{e}\log_2e$的线性时间算出$d$。

证明依赖于另一个完美精妙的Coppersmith定理。

定理10 (Coppersmith)

设$N = PQ$是一个$n$位RSA模。然后，给定$p$的$n/4$最小有效位或$p$的$n/4$最有效位，可以有效地将$N$分解。

定理9很容易从定理10推理出来，事实上，根据$e$和$d$的定义，存在一个整数$k$，使得：

$$ed - k(N - p - q + 1) = 1$$

由于$d < \sqrt{N}$，我们必有$0 < k \leq e$。对方程模$2^{\frac{n}{4}}$进行约化，设$q = \frac{N}{p}$，得到：

$$\left( ed \right)p - kp\left( N - p + 1 \right) + kN = p(\mathrm{\ \text{mod}}\ 2^{\frac{n}{4}})$$

由于Marvin知道了$d$的$n/4$最小有效位，他知道$ed\ \text{mod}\text{}2^{\frac{n}{4}}$的值，因此，他得到了一个关于$k$和$p$的方程。对于$k$的每一个$e$的可能值，Marvin求解$p$的二次方程，并能得到了$p\ \text{mod}\text{}2^{\frac{n}{4}}$的一些候选值。对于这些候选值，他运用定理10尝试去分解$N$。可以证明$p\ \text{mod}\text{}2^{\frac{n}{4}}$的候选值的总数最多为$\text{e}\log_2e$，因此，在最多$\text{e}\log_2e$次尝试之后，$N$将被分解。

定理9被称为部分密钥泄露攻击，对于更大的$e$值，只要$e < \sqrt{N}$，也存在类似的攻击，不过，要实现此种攻击的技术有点复杂。有趣的是，基于离散日志的密码系统，如ELGamal公钥系统，似乎不容易受到部分密钥泄漏攻击的影响。事实上，如果给出$g^{x}\mathrm{\ \text{mod}}\ p$和$x$的常数部分，则没有已知的多项式时间算法来计算$x$的其余部分。

为了总结这一节，我们将证明当加密指数$e$很小时，RSA系统会泄漏相应私钥$d$一半的最高有效位。要了解这一点，再考虑一个方程$ed - k(N - p - q + 1) = 1$，其中$k$是$0 < k \leq e$的整数。给定$k$，Marvin可以很容易地计算出：

$$\widehat{d} = \left\lfloor (kN + 1)/e \right\rfloor$$

之后：

$$\left| \widehat{d} - d \right| \leq \frac{k\left( p + q \right)}{e} \leq \frac{3k\sqrt{N}}{e} < 3\sqrt{N}$$

因此，$\widehat{d}$是$d$的很好的近似值。该界表明，对于大多数$d$，$\widehat{d}$中一半的最高有效位与$d$相同。由于$k$只有$e$个可能的值，因此Marvin可以构造一个大小$e$的小集合，使得集合中的一个元素等于$d$的一半最高有效位的。$e = 3$的情况特别有趣，在这种情况下，可以知道$k = 2$，系统完全泄漏了$d$的一半最高有效位。

5 执行攻击

我们将注意力转向另一类完全不同的攻击。这些攻击不是攻击RSA函数的底层结构，而是专注于RSA的实现。

5.1 时序攻击

想一下存储RSA私钥的智能卡，由于卡是防篡改的，攻击者Marvin可能无法审阅其内容并使其泄露出密钥。然而，Kocher的一个巧妙攻击表明，通过精确测量智能卡执行RSA解密（或签名）所需的时间，可以快速发现私有解密指数$d$。

我们将解释如何使用"重复平方算法"对一个简单的RSA实现进行攻击。设$d = d_{n}d_{n - 1}\ldots d_{0}$是$d$的二进制表示（即$d = \sum_{i = 0}^{n}{2^{i}d_{i}},其中d_{i} \in \left\{ 0,1 \right\}$）。基于$C = \prod_{i = 0}^{n}M^{2^{i}d_{i}}\mathrm{\ \text{mod}}\ \ N$的观察基础，我们可以知道用重复平方算法来计算$C = M^{d}\mathrm{\ \text{mod}}\ \ N$最多使用$2n$次模乘，算法是如下工作的：

令$z$等于$M$，$C$等于1，对于$i = 0,\ldots,n$，执行以下步骤：

（1）如果$d_{i} = 1$，令$C$等于$C \bullet z\mathrm{\ \text{mod}}\ \ N$，

（2）令$z$等于$z^{2}\mathrm{\ \text{mod}}\ \ N$。

最后，$C$有值为$M^{d}\mathrm{\ \text{mod}}\ \ N$。

当$i = 0,\ldots,n$时，变量$z$遍历$M^{2^{i}}\ \text{mod}\ N$值的集合，变量$C$在集合中"收集"适当幂以获得$M^{d}\mathrm{\ \text{mod}}\ \ N$。

为了发起攻击，Marvin要求智能卡在大量随机消息$M_{1},\ldots,M_{k} \in \mathbb{Z}_{N}^{*}$上生成签名，并测量每个签名生成所需的时间$T_{i}$。

攻击从最低有效位开始一次一个地算出$d$的比特位。我们知道$d$是奇数，因此$d_{0} = 1$。考虑第二次迭代。最初$z = M^{2}\mathrm{\ \text{mod}}\ \ N$且$C = M$。如果$d_{1} = 1$，则智能卡会计算乘积$C \bullet z = M \bullet M_{i}^{2}\mathrm{\ \text{mod}}\ \ N$，否则，它是不会计算的。设$t_{i}$是智能卡计算$M_{i} \bullet M_{i}^{2}\mathrm{\ \text{mod}}\ \ N$所花费的时间。由于计算$M_{i} \bullet M_{i}^{2}\mathrm{\ \text{mod}}\ \ N$的时间取决于$M_{i}$的值，因此$t_{i}$彼此不同（简单模约化算法需要不同的时间，取决于所减少的值）。一旦Marvin获得智能卡的物理规格，之后他便会测量得到$t_{i}$（在发起攻击之前）。

Kocher观察到当$d_{1} = 1$时，两个集合$\left\{ t_{i} \right\}$和$\left\{ T_{i} \right\}$是相关的。例如，如果，对于某些$i$，$t_{i}$比预期的要大得多，那么$T_{i}$也可能大于预期。另一方面，如果$d_{1} = 0$，则两个集合$\left\{ t_{i} \right\}$和$\left\{ T_{i} \right\}$表现为独立的随机变量。通过测量相关性，Marvin可以确定$d_{1}$是0还是1。继续使用这个方法，他可以很快得到$d_{2}$，$d_{3}$。注意，当使用低公钥指数$e$时，上一节的部分密钥泄露攻击表明，使用Kocher的时序攻击，只需要知道$d$的四分之一的位就行。

有两种方法可以抵御攻击。最简单的是添加适当的延迟，以使模幂运算总是要花费一定的时间。第二种方法是由Rivest提出的基于盲化的方法。在解密M之前，智能卡选择一个随机的$r \in \mathbb{Z}_{N}^{*}$并计算$M^{'} = M \bullet r^{e}\mathrm{\ \text{mod}}\ \ N$，然后将$d$应用于$M^{'}$上并获得$C^{'} = \left( M^{'} \right)^{d}\mathrm{\ \text{mod}}\ \ N$，最后，令$C = \frac{C^{'}}{r}\text{modN}$。通过这种方法，将$d$应用于Marvin不知道的随机消息$M^{'}$上，这样的话，Marvin就不能发起攻击了。

Kocher最近在这些线路上发现了另一种叫做功率密码分析的攻击。 Kocher表明，通过在签名生成过程中精确测量智能卡的功耗，Marvin通常可以轻松发现密钥。事实证明，在多精度乘法期间，卡的功耗高于正常值。通过测量高消耗周期的长度，Marvin可以很容易地确定在给定的迭代中卡是执行一次还是两次乘法，从而暴露出$d$的比特位。

Kocher最近发现了另一种类似的攻击，称为能量分析攻击。Kocher指出通过精确测量智能卡在签名生成过程中的功耗，Marvin通常可以很容易地得到秘密密钥。结果表明，在多精度乘法过程中卡的功耗会高于正常值，通过测量高消耗周期的长度，Marvin可以很容易地确定在给定的迭代中卡是否执行一次或两次乘法，从而得到$d$的比特位。

5.2 随机故障

RSA的解密和签名的实现经常使用中国剩余定理来加速$M^{d}\mathrm{\ \text{mod}}\ \ N$的计算，签名者Bob为了替换模$N$的工作，先计算签名模$p$和$q$的结果，然后利用中国剩余定理将结果结合起来。更准确地说，Bob首先计算：

$$C_{p} = M^{d_{p}}\mathrm{\ \text{mod}}\ p和C_{q} = M^{d_{q}}\mathrm{\ \text{mod}}\ q$$

其中$d_{p} = d\mathrm{\ \text{mod}}\ (p - 1)$和$d_{q} = d\mathrm{\ \text{mod}}\ (q - 1)$。然后，他得到签名$C$通过令：

$$C = T_{1}C_{p} + T_{2}C_{q}\left( \mathrm{\ \text{mod}}\ \ N \right)$$

其中：

$$T_{1} = \left\{ \frac{1\mathrm{\ \text{mod}}\ p}{0\mathrm{\ \text{mod}}\ q} \right\} 和T_{2} = \left\{ \frac{1\mathrm{\ \text{mod}}\ p}{0\mathrm{\ \text{mod}}\ q} \right\}$$

与$d_{p}$和$d_{q}$两个指数相比，CRT最后一步的运行时间可以忽略不计。注意$p$和$q$是$N$的一半长，然后由于乘法的简单实现需要平方时间，所以模$p$的乘法速度是模$N$的4倍，而且，$d_{p}$是$d$的一半长，计算$M^{d_{p}}\mathrm{\ \text{mod}}\ p$的速度是计算$M^{d}\mathrm{\ \text{mod}}\ \ N$的8倍，因此，整个签名时间减少了四倍，许多实现都使用这种方法来提高性能。

Boneh，DeMillo和Lipton观察到使用CRT方法有内在的危险。假设在生成签名时，Bob的计算机上的一个小故障导致它在一条指令中错误计算。例如，在将寄存器中的值从一个位置复制到另一个位置时，其中一个比特位被翻转了。(故障可能是由环境电磁干扰引起的，也可能是由于罕见的硬件缺陷造成的，比如早期版本的奔腾芯片。)

Marvin得到了无效的签名给定之后可以很容易地对Bob的模数$N$进行分解。

正如A. K. Lenstra所说，我们发现了一个新的攻击。假设在Bob生成签名时发生单个错误，那么，$C_{p}$或$C_{q}$中将有一个被错误地计算。如果说$C_{p}$是正确的，那么${\widehat{C}}_{q}$就会不正确，得到的签名为$\widehat{C} = T_{1}C_{p} + T_{2}{\widehat{C}}_{q}$。一旦Marvin获取到了$\widehat{C}$，通过计算${\widehat{C}}^{e} \neq M\mathrm{\ \text{mod}}\ \ N$，他就知道这是一个错误的签名。然而注意到：

$${\widehat{C}}^{e} = M\mathrm{\ \text{mod}}\ p当{\widehat{C}}^{e} \neq M\mathrm{\ \text{mod}}\ q$$

因此，$\mathrm{\gcd}(N,{\widehat{C}}^{e} - M)$便是$N$的一个非平凡因子。

要使攻击奏效，Marvin必须对$M$有充分的了解。也就是说，我们假设Bob不使用任何随机填充方法，签名前的随机填充可以防御此种攻击，对于Bob来说，一个更简单的防御方法是在将生成的签名发送给全世界之前检查生成的签名。当使用CRT加速方法时，检查是特别重要的。随机故障攻击对许多密码系统都是有害的，许多系统，包括RSA的非CRT实现，都可以使用随机故障进行攻击。不过，这些结论更多的是理论性的。

5.3 Bleichenbacher对PKCS 1的攻击

设$N$是$n$位RSA模，$M$是$m$位消息，其中$m < n$。在应用RSA加密之前，一般会通过向其添加随机位，将消息$M$填充到$n$位。公钥加密标准1（Public Key Cryptography Standard 1, PKCS 1）的旧版标准就是使用的这种方法。填充后，消息如下所示：

---

02 随机位 00 M

---

生成的消息长度为$n$位，并直接使用RSA加密。包含"02"的初始块长度为16位，从上图可看出已在消息中添加了随机填充。

当运行在Bob的机器上应用程序(例如，Web浏览器)接收到消息时，会对其进行解密，检查初始块，并去掉随机填充。但是，一些应用程序会检查"02"初始块，如果不存在，就会返回一条错误消息，说明"无效的密文"。Bleichenbacher表示这个错误消息可能导致灾难性的后果：攻击者Marvin可以使用错误消息解密他所选择的密文。

假设Marvin截获了一个针对Bob的密文$C$，并希望对其进行解密。为了发动攻击，Marvin随机挑选了一个$r \in \mathbb{Z}_{N}^{*}$，计算$C^{'} = rC\mathrm{\ \text{mod}}\ \ N$，并将$C^{'}$发送到Bob的机器。运行在Bob的机器上的应用程序接收$C^{'}$并尝试解密它。它要么用错误消息进行响应，要么根本不响应(如果$C^{'}$的格式正确的话)。因此，Marvin知道$C^{'}$解密过程中16位最高有效位是否等于02。实际上，Marvin有这样的谕言，对于他选择的任何$r$，他都可以测试$\text{rC}\ \text{mod}\ N$解密的16位最高有效位是否等于02。Bleichenbacher证明了这样的谕言足以解密$C​$。

6 结论

对RSA系统进行了20年的研究以来，产生了一些有见地的攻击，但还没有发现破坏性的攻击。到目前为止发现的攻击主要说明了在实现RSA时需要避免的陷阱，目前看来，可以信任正确的RSA密码系统实施来提供数字世界中的安全性。我们将针对RSA的攻击分为四类：(1)利用系统公然误用的基本攻击；(2)低私钥指数攻击，此种攻击非常严重，绝不能使用低私钥指数；(3)低公钥指数攻击；(4)对RSA系统执行时的攻击。这些持续不断的攻击说明，我们对基本数学结构的研究还是不够的。另外，Desmedt和Odlyzko、Joye和Quisquater以及DeJonge和Chaum还提出了一些额外的攻击。在整篇论文中，我们观察到通过在加密或签名之前正确填充消息可以防御许多攻击。

致谢

我要感谢Susan Landau鼓励我撰写调查问卷，感谢Tony Knapp帮忙编辑手稿。我还要感谢在早些时候Mihir Bellare、Igor Shparlinski和R. Venkatesan对草案发表的评论。

---