改善具有小私有指数的RSA的维纳攻击外文翻译资料

英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

---

改善具有小私有指数的RSA的维纳攻击

吴恩武，陈建明，2,3岳春森，4和洪敏敏5

摘要

RSA系统是基于整数分解问题（IFP）的硬度。 给定RSA模量，难以确定主要因素是否有效。对RSA最著名的短指数攻击之一是维纳攻击。 1997年，Verheul和van Tilborg利用详尽的搜索来延伸维纳攻击的边界。他们的结果表明，扩展维纳边界r比特时，穷举搜索的成本是2r 8比特。 在本文中，我们首先将穷举搜索的成本从2r 8位降低到2r 2位。然后，我们提出一种名为EPF的方法。使用EPF，当我们扩展维纳的边界位时，穷举搜索的成本进一步减少到2r-6位。这意味着我们的结果比Verheul和van Tilborg的结果快了214倍。 此外，安全边界扩展7位。

1.介绍

在过去30年里，RSA [1]已经成为全球最受欢迎的公钥密码系统之一。它已被广泛应用于多种应用[2-4]。 RSA的安全性通常基于整数因式分解问题（IFP）的硬度，这仍然是一个经过充分研究的问题[5,6]。当前的RSA标准表明RSA模数应至少为1024位长。使用最著名的因式分解算法，预期的1024比特模数分解的工作量是280，目前被认为是不可行的。然而，虽然使用大的RSA模数达到高安全性水平，但是加密和解密过程涉及强指数模乘法，这使得RSA效率低下。因此，为加快RSA加密（或签名验证）和RSA解密（或签名签名）[7-12]，已经研究了许多方法。

此外，因为签名的复杂性取决于比特长度d，自签署以来减少签名时间最流行的方法是应用一个小的私有指数d。为了达到这个目标，选择e和d的顺序进行交换。首先在RSA密钥生成算法中进行选择d，然后计算满足的相应的公共指数e。这些RSA变体称为RSA-小D。然而，RSA-小D的变体具有安全缺陷[13-18]。 事实上，具有的RSA的实例可以通过维纳攻击有效地破坏[16]。除此之外，Boneh和Durfee的网格攻击[19]表明，RSA-小D的应该被认为是不安全的系统。

1997年，Verheul和van Tilborg [20]进行了详尽的搜索，进一步延伸了维纳攻击的边界。假设, 他们的结果表明，需要穷尽搜索2r 8位来扩展维纳的边界位。假设在目前的计算能力方面，64位的穷举搜索是可行的; 求解方程“2r 8=64”得出r=28，这意味着维纳攻击的边界应该提高到。

在本文中，我们试图降低Verheul和van Tilborg结果中详尽搜索的成本。 我们希望在延伸维纳的边界时，提出一种降低穷举搜索成本的方法。这种方法包括两个步骤。

步骤1.我们研究一种搜索尽可能多的MSB（最重要位）的方法，这相当于尽可能准确地估计p q。在此步骤中，为了扩展维纳的边界位，穷举搜索需要2r 2位。 这意味着我们的结果比Verheul和van Tilborg的更好，他们需要详细搜索2r 8位。

步骤2.我们开发了一种称为“估计主因子（EPF）”的方法来估计p q，然后我们得到两个整数和，它们分别是p和q的估计值。通过使用EPF，可以确定p q的前8个MSB。 这个结果比传统的估计更准确，通过2估计p q。 应用EPF可进一步降低详尽搜索的成本。 更具体地说，为了扩展维纳的边界位，穷举搜索需要2r-6位。 与Verheul和van Tilborg的结果相比，这需要详细搜索2r 8位，安全边界扩展了7位。

1.1.我们的贡献

本文的贡献总结如下：

（1）当我们扩展维纳的边界位时，我们首先将从2r 8（Verheul和van Tilborg的结果）穷尽搜索的成本降低到2r 2比特。这意味着在步骤1中穷举搜索速度快26倍。此外，安全边界扩展3位。

（2）我们提出一种新的方法，称为EPF，用于估算主要因素N。使用EPF，穷尽搜索2 r 2位（贡献（1）中提到）的成本进一步减少到2r-6位。 与Verheul和van Tilborg的结果相比，详尽的搜索速度是214倍。此外,安全边界扩展7位。

1.2组织

本文的其余部分安排如下。 第2节介绍了本文的初步。 第3节描述了我们的方法的第1步。 在第4节中，我们提出EPF估计RSA模数的主要因素。 接下来，我们在第5节中提出了我们应用EPF的方法的第2步。最后,我们在第6节介绍我们的结论和未来的工作。

2.初步

在本节中，我们介绍本文的初步内容，其中包括RSA及其变体,以及维纳攻击。

2.1. RSA及其变体

RSA密码系统[1]由RSA密钥生成，加密和解密三部分组成，如下所述。

2.1.1. RSA密钥生成，加密和解密

RSA密钥生成输出RSA密钥：（N，e，d）。 首先，随机选择两个大素数，并计算，其中N称为RSA模数。其次，e称为公众指数，是随机选择的整数，满足，其中是欧拉函数。然后，令私有指数d进行乘法逆模（即，）。（e，N）是公钥，（d，N）是私钥。

从关键关系得出，存在唯一令人满意的正整数k满足:

(1)

我们称（1）为RSA密钥方程。 计算,加密明文消息。结果称为M的密文。为了执行RSA解密，密文是通过将其提高到d次N的幂模来解密。 从拉格朗日定理可以看出：(2)

通常，由于高效加密（或签名验证）的原因，e通常选择尽可能小的数。 建议选择的最小值是而不是，因为这两个消息之间的已知仿射关系存在[21]。 我们将带有小公众指数e的RSA系统称为“RSA-small-e”。另一方面，当私有指数d远小于Phi;（N）时，解密（或签名签名）的成本可以显着降低， 为了简单地减少解密（或签名签名）时间，可以在RSA密钥生成中首先选择一个小的私有指数d。 这种变体称为“RSA-small-d”，如下所示。

2.1.2.RSA-Small-d

通过观察RSA密钥方程（1）得出它相对于公共和私有指数是对称的，生成具有小私有指数的RSA的实例是容易的。 我们只是遵循原始RSA的相同的关键代数，从而交换公共和私人指数的选择顺序。

RSA-Small-d的缺点之一是其加密效率低下。由于RSA-Small-d中的公众指数总是计算为模Phi;（N）的倒数，所以预计与Phi;（N）几乎有大致相同的概率。 总而言之，虽然RSA-Small-d节省了解密（或签名）成本，但是它的加密成本仍然很大。

2.2。 维也纳攻击 。

对RSA而言，最着名的短期攻击之一就是维纳攻击。 Boneh和Durfee [22]在1990年表明，当时，RSA-Small-d应该被认为是不安全的。他通过持续分数的技术实现了攻击。 在下面的段落中，我们简要介绍继续的分数和维纳攻击。 细节可参考[16]。

定义1（持续的分数）。对于任何正整数alpha;，定义alpha;=，= [i]， =1 /（ - ）。i= 0,1,2，...可以扩展为以下形式：

(3)

1. 的形式称为连续分数表达式。为了简单起见，我们写（3）为alpha;=（）。 此外，表达式作为连续扩展收敛的分数，这意味着:

(4)

如果是有理数，则计算其连续分数表达式的过程见（3）将在某些指标k中停止。 也就是说，。 如果ɑ是不合理的，那么这个过程将会不断的进行。

定理2重新定义表示（4）的分数形式;

也就是令/ =，其中和是正整数。可以通过定义= 0， 1， = 1和 =0 ，和，，（ige;0）i。估计出和。

按照定理2中的符号，我们有推论3。

推论3.对于任何的ige;1有，

(5)

此外，如果ɑ是无理数，则limt→infin;/ =

定理4.如果一个实数和一个减少的分数a/b满足:

(6)

那么a / b等于继续收敛之一的alpha;的分数表达。

2.2.1. 维纳攻击

维纳攻击[16]是在dlt;，p和q有相同位长度时，基于使用连续分数来找到私人的近似值RSA-Small-d的多项式时间的指数。请注意，RSA-的关键性方程式可以重写为

(7)

其类似于（6）的左侧的形式。 为了应用定理4，我们将（7）的e/（N）替换为每个人都知道的e/N，并将e/N和k/d之间的差设置为小于。 那么将（7）变为，

(8)

因此，根据定理4，可以通过计算e / N的连续分数表达式的收敛之一找到k / d。

维纳攻击的安全边界是从（8）的充分条件推导出来的。 由于pasymp;qasymp;和kasymp;d，所以（8）的左侧被简化为:

(9)

因此，（8）转化为

（10）

这给出了维纳攻击的安全边界（忽略了常数），即：

(11)

2.3.Verheul和van Tilborg的扩展

当私人指数d lt;时，维纳攻击效果非常好。但是，如果比特长度比

的比特长度稍大，那又如何呢？ 1997年，Verheul和van Tilborg [20]提出了一种通过对2r 8位执行穷尽搜索来解决这个问题的技术，其中r =。意味着d的比特长度比的比特长度长r比特。Verheul和van Tilborg观察到k/d在（8）中可以变为下面的式子：

（12）

其中/是连续分数的收敛e/N，Delta;= 1或2的表达式，并且U和V是两个具有上限的未知数的整数。如下：

(13)

既然是一个小整数，我们可以省略它的不确定性。（12）的未知部分约为2r 8位，这给出了Verheul和van Tilborg的延伸的结果：延伸维纳的位边界需要详尽的搜索约2r 8位。

假设64位的穷举搜索是可行的,在当前的计算能力方面。对于方程“2r 8=64”解得r=28,这表明维纳的边界可以延伸到28比特比比特长。因此在情况下的RSA-小D就被连续的分数攻击加上成本完全打破执行64位的穷举搜索。在第3节中，我们将会显示出，为了通过比特扩展维纳的边界，它只需要详细搜索2r 2位，而不是从Verheul和van Tilborg的扩展成本中得到的，需要详细搜索2r 8位。

1. 将搜索成本降低到2r 2位

我们的方法分为两个步骤，分别在第3节和第5节中进行描述。 在本节中，我们研究一种搜索尽可能多位p q的MSB（最高有效位）的方法，这相当于尽可能准确地估出p q。通过使用这种方法，当我们扩展维纳的边界r位时，我们可以将从2r 8位（Verheul和van Tilborg的扩展）的详尽搜索的成本降低到2r 2位。

用A来估计p q。在本文中，我们假设A lt;p q。 因此估计为（N 1) -A ，这意味着:

(14)

在维纳攻击中运用（14），即替换e/N（8）为e/（（N 1）minus;A），我们有:

(15)

请注意，如果A=p q，那么（15）对于任何的d可以化为：

（16）

简化（15）为：

（17）

综合上得出：

（18）

在（18）解出d,我们得到这个私有指数的上界：

(19)

根据上述不等式，我们知道p q和A之间的差异越小，d的上限越高。 因此，为了扩展RSA-Small-d的安全边界，我们尝试尽可能精确地估计p q-A为更小的数。方程（19）还表明，维纳边界进一步扩展的复杂性可以降低到估计p q的MSB的复杂度。关系如下所示：

重新整理（18）我们得出：

(20)

定义作为p q和A之间的差值，因此。在（20）中用来代替A，得出下面的算式：

（21）

在（21）中在两边同时间消除算式，可以得到下面的式子：

(22)

现在我们考虑每边的比特长度。假设d的比特长度为n/4 r比特，比维纳的边界长r比特长度。 由于RSA-Small-d的密钥生成，在高概率的情况下出现参数k和参数d的长度相同，即。除此之外，我们对p q的第一个MSB s进行详尽的搜索。 就这样p q和A之间的差可以减少到（n/2 1）位。也就是说，asymp;（n/2 1）- s。 因此，对于-2kd，导致了(22）左手边上的式子占据了主导地位，它大概有（（n/2 1)- s） 1 2times;（n/ 4 r)比特长。

1. 的充分条件是：

（23）

上面的计算表达式可以简化为：

2r 2lt;s(24)

方程（24）给出以下结论。 为了让维纳攻击的边界提高出r比特的长度，我们必须对p q的前2r 2MSB s进行详尽的搜索，其中。 这个结果比Verheul和van Tilborg在计算表达式在[20]中得到的结果更加好，Verheul和van Tilborg需要详细搜索2r 8位。因此，假设在目前的计算能力方面，64位的穷举搜索是可行的。

对于下面的方程计算出r:

2r 2=64(25)

得出结果r=31,这意味着RSA小-D是不安全的。这种情况是指当时。

4.估计主因子（EPF）

在这一节中，一个叫做估计总理的新颖方法因子（EPF），用于估计主要因素

RSA的模量，将会被提出来。

4.1EPE

不失一般性，我们假设qlt;plt;2q,N=pq。 将和表示为和的差距。

（26）

应用（26）去计算N=pq，则式子可以改变为：

N=pq=（27）<!--

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[138931]，资料为PDF文档或Word文档，PDF文档可免费转换为Word