非对称加密算法的研究与设计论文终稿

华北科技学院毕业论文

(5)对每一个密钥k=(n，p，q，d，e)，定义加密变换为Y=Ek(x)=xemodn，解密变换为Dk(x)=Ydmod n，这里X，Y∈Zn。这里我们要用到模取幂运算。

事实上，memodn可以直接计算，没有必要先算m^e，那样肯定不行，计算量将很大。memodn叫做模取幂运算，根据简单的数论知识，可以设计一个分治算法。具体如下：

设是整数b的二进制表示（即b的二进制有k+1位，b[k]是最高位），下列过程随着c的值从0到b成倍增加，最终计算出acmodn。

Modular-Exponentiation(a, b, n) 1. c ← 0 2. d ← 1

3. 设 是b的二进制表示 4. for i←k downto 0 5. do c ← 2c

6. d ← (d*d) mod n 7. if b[i] = 1

8. then c ← c + 1

9. d ← (d*a) mod n 10. return d

首先说明一下，上述伪代码中用缩紧表示语句之间的层次关系，例如第5~9行都是for循环体内的语句，第8~9行都是then里面的语句。这是我比较喜欢的一种表示方法。上述伪代码依次计算出的每个幂或者是前一个幂的两倍，或者比前一个幂大1。过程依次从右到左逐个读入b的二进制表示已控制执行哪一种操作。循环中的每次迭代都用到了下面的两个恒等式中的一个：

a2cmodn?(acmodn)2。 a2c?1modn?a(acmodn)2。

用哪一个恒等式取决于b[i]=0还是1。由于平方在每次迭代中起着关键作用，所以这种方法叫做“反复平方法”。在读入b[i]位并进行相应处理后，c的值与b的二进制表示的前缀的值相同。事实上，算法中并不真正需要变量c，只是为了

第37页共62页

非对称密码学加密算法的研究与设计――RSA算法的程序设计

说明算法才设置了变量c：当c成倍增加时，算法保持条件d?acmodn不变，直至c=b。

(6)将{e，n}作为公开密钥，{d，n}作为私有密钥。

3.4 RSA的安全性分析

3.4.1针对RSA的攻击

还没有发现针对RSA的破坏性攻击。已经预言了几种基于弱明文、弱参数选择或不当执行的攻击。图就是这些潜在攻击的分类。 因数分解 选择密文 加密指数 针对RSA的潜在攻击 解密指数 明文 模 执行 针对RSA潜在攻击的分类

3.4.2因数分解攻击

RSA的安全性基于这么一种想法，那就是模要足够大以至于在适当的时间内把它分解是不可能的。收信者选择p和q，并且计算出n=p?q。虽然n是公开的，但p和q是保密的。如果攻击者能分解n并获得p和q，她就可以计算出f(n)=(p??????q????。然后，因为e是公开的，攻击者还可以计算出d?e?1mod?(n)。私密指数d是攻击者可以用来对任何加密信息进行解密的暗门。

有许多种因数分解算法，但是没有一种可以分解带有多项式时间复杂度的大整数。为了安全，目前的RSA要求n必须大于300个十进制数位，这就是说模必须最小是1024比特【5】。即使运用现在最大最快的计算机，分解这么大的整数所要花费的时间也是不可想象的。这就表明只要还没有发现更有效的因数分解算法，RSA就是安全的。

第38页共62页

华北科技学院毕业论文

3.4.3选择密文攻击

针对RSA的潜在攻击都基于RSA的乘法特性，我们假定发信者创建了密文：

c?memodn并且把c发送给收信者。我们也假定收信者要对攻击者的任意密文解密，

而不是只解密c。攻击者拦截c并运用下列步骤求出m：

(1) 攻击者选择Zn*中的一个随机整数x。 (2) 攻击者计算出y?c?xemodn。

(3) 为了解密攻击者把y发送给收信者并得到z?ydmodn；这个步骤就是选择密文攻击的一个例子。

(4) 攻击者能够很容易地得到m，因为

z?ydmodn?(c?xe)dmodn?(cd?xed)modn?(cd?x)modn?(m?x)modn z?(m?x)modn?m?z?x?1modn

攻击者运用扩展的欧几里得算法求x的乘法逆，并最终求得m。 3.4.4对加密指数的攻击

为了缩短加密时间，使用小的加密指数e是非常诱人的。普通的e值是e=3。不过有几种针对低加密指数的潜在攻击，在这里我们只作简单的讨论。这些攻击一般不会造成系统的崩溃，不过还是得进行预防。为了阻止这些类型的攻击，我们推荐使用e=216+1=65537(或者一个接近这个值的素数)。

主低加密指数攻击称为Coppersmith定理攻击。该项定理表明在一个e阶的mod n多项式f(x)中，如果有一个根小于n1/e，就可以运用一个复杂度log n的算法求出这些根

【5】

。这个定理可以应用于c?f(m)?memodn的RSA密码系统。如果e=3并且在明文当

中只有三分之二的比特是已知的，这种算法可以求出明文中所有的比特。

如果一个实体使用相同的低加密指数给一个接收者的群发送相同的信息，就会发动广播攻击。例如，假设有如下的情节：发信者要使用相同的公共指数e=3和模n1、n2和n3给三个接收者发送相同的信息。

33modn2 c3?m3modn3 c1?m13modn1 c2?m2 第39页共62页

非对称密码学加密算法的研究与设计――RSA算法的程序设计

对这些等式运用中国剩余定理，攻击者就可以求出形式c?m3modn1n2n3的等式。这就表明m3??n1n2n3。也表明c=m3是在规则算法中(不是模算法)。攻击者可以求出c?m1/3的值。

相关信息攻击是由Franklin Reiter提出来的，下面我们就简单描述一下这种攻击。发信者用e=3加密两个明文m1和m2，然后再把c1和c2发送给收信者。如果通过一个线性函数把m1和m2联系起来，那么攻击者就可以在一个可行的计算时间内恢复m1和m2。

短填充攻击是由Coppersmith提出来的，下面我们就简单描述一下这种攻击。发信者有一条信息m要发送给收信者。她先用r1对信息填充，加密的结果是得到了c1，并把c1发送给收信者。攻击者拦截c1并把它丢掉。收信者通知发信者他还没有收到信息，所以发信者就再次使用r2对信息填充，加密后发送给收信者。攻击者又拦截了这一信息。攻击者现在有c1和c2，并且她知道c1和c2都是属于相同明文的密文。Coppersmith证明如果r1和r2都是短的，攻击者也许就能恢复原信息m【5】。 3.4.5对解密指数的攻击

可以对解密指数发动攻击的两种攻击方式就是：暴露解密指数攻击和低解密指数攻击。我们简单讨论一下这两种攻击。

如果攻击者可以求出解密指数d，她就可以对当前加密的信息进行解密。不过，到这里攻击并还没有停止。如果攻击者知道d的值，她就可以运用概率算法(这里不讨论)来对n进行因数分解，并求出p和q值。因此，如果收信者只改变了泄露解密指数但保持模n相同，因为攻击者有n的因数分解，所以她就可以对未来的信息进行解密。这就是说，如果收信者发现解密指数已经泄露，他就要有新的p和q的值还要计算出n，并创建所有新的公钥和私钥。因此在RSA中，如果d已经泄露，那么p、q、n、e和d就必须要重新生成。

低解密指数攻击，收信者也许会想到，运用一个小的私钥d就会加快解密的过程。Wiener表示如果d?n1/4，一种基于连分数(一个数论当中的问题)的特殊攻击类型就可以危害RSA的安全【5】。要发生这样的事情，必须要有q

第40页共62页