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

 2022-11-06 04:11

英语原文共 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

原文和译文剩余内容已隐藏,您需要先支付 30元 才能查看原文和译文全部内容!立即支付

以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。