RSA算法安全性分析及其参数的选择(2)

且最好先使用单向Hash函数对消息进行散列运算。ISO9796分组格式可用来防止这种攻击。 2.2 公共模数攻击

如果系统中每个人拥有相同的模数n，即使每个人采用不同的公/私钥对，系统安全仍然会收到巨大的威胁。设消息为m，两个加密密钥为分别为e1，e2，且满足gcd(e1，e2)=1，两个密文为c1=me1mod n，c2=me2mod n，由于，攻击者很容易由扩展欧几里德算法得到r，s，满足re1+se2=1，那么c1rc2smod n=mre1+mse2mod n=m。因此，在一组用户之间共享模数是不安全的。 2.3 低加密指数攻击

在RSA加密和数字签验证中，如果选取了较低的e值可以加快速度，但这是不安全的，Hastad证明如果采用不同的模数n，相同的公钥e，则对 e(e+1) /2 个线性相关的消息加密，系统安全会受到威胁.如果消息比较短，或者消息不相关，就不存在这个问题.如果消息相同，那么只要有个消息就可以攻击系统.一般来讲，选取16 位以上的素数速度比较快，而且可以阻止该攻击.对于较短的消息，使用独立随机值填充消息，可以阻止该攻击，这也能保证memod n ≠ me。2.4 低解密指数攻击

Machael Wiener 给出了另外一种攻击，可以成功地计算解密指数d，前提是满足如下条件: 3 d < n 1 / 4，并且 q < p < 2 q。 2.5 定时攻击

定时攻击主要针对RSA核心运算是非常耗时间的模乘，只要能

精确监视 RSA 的解密过程，获得解密时间，就可以估算出私有密钥d。模指数运算是通过一位一位来计算的，每次迭代执行一次模乘，并且如果当前位是1，则还需要进行一次模乘.对于有些密码，后一次模乘执行速度会极慢，攻击者就可以在观测数据解密时，根据执行时间判断当前位是1 还是0，不过这种方法只是理论上可以考虑，实际操作很困难。如果在加密前对数据做盲化处理，再进行加密，使得加密时间具有随机性，最后进行去盲，这样可以抵抗定时攻击，不过增加了数据处理步骤。 3 RSA参数的选择

RSA算法的安全性主要依赖于RSA参数的选择，因此需要对这个算法中的各个参数仔细选择。

(1)p，q选择强素数，否则不能防御某些特殊的因子分解方法。假设p，q不是强素数。可以假设p-1没有大的素因子，p-1=p1a1……pmam，其中pi为素数，ai是自然数(1?i?m)。可以设pi〈A(1?i?m)，A为一较小的整数，此时分解n就比较容易。我们可以设a?ai(1?i?m)，可以构造B= p1a……pma ，此时必有(p-1)│B。由费马定理知道，2B=1mod p，又因为有(p-1)│B。我们如下处理x B =y mod n，可以把x B看成是p的某整数倍加1。如果2 B =y mod n中，y=1，则把x换成3……，直到y≠1。那么，gcd(y-1，n)=p，因为y应该为p的某整数倍加1。 由此可以求出p与q。

(2)p与q之差要比较大，否则n≈(p+q)2/4-(p-q)2/4。也就是说n0.5

接近(p+q)/2，逐个找比n0.5略大的自然数N，到使(N2-n)是一个完全

平方数。可以设x2=N2-n，则n=N2-x2=(N+ x ) ( N- x ) ，则 p =N- x ，q =N+ x。

(3)p3/1与q3/1的最大公因子应很小，否则，RSA有可能在不需要因子分解时即可被攻破，p3/1与q3/1都应包含大的素因子。

(4)p，q应该足够大，使得在计算上分解n是不可能的。 (5)gcd((p-1)，(q-1))小。否则，可以采用迭代方法。对密文C=Memod n反复进行e次幂的运算。ce，cee，……，到出现c的et次幂mod n为c时为止。则c的et-1次幂mod n为M，当t不是很大时，这种攻击是有效的。由Eluer定理知et=1modΦ(n)，同样由Eluer定理，t的最小值有t=Φ(Φ(n) )=Φ( (p-1) (q-1) )，如果gcd( (p-1)，(q-1))小，Φ(Φ(n))就很大，t就会很大。

(6)e不可选择过小，加密速度快但可以采用低指数攻击。在C=Memod n中，如果e选择过小，可能没有模n的运算，可以通过直接开平方得到。一般选择使ei=1 modΦ(n)中的i尽可能大的e。

(7)密钥d的选取是最为关键的，应使d>N0.25且越大越好，这是因为当d的长度小于N的长度的0.25倍时，攻击者可能通过连分数方法在多项式时间内求出d，而当d>N0.25时，攻击者只能采用穷举攻击法，若d较小，则显然破译困

难远比大因子分解的难度小，系统被直接攻破的可能性较大。另外，d又不能太接近e，否则RSA密钥系统较容易被攻破，因为攻击者最喜欢从比较小的数和e附近进行攻击。

(8)用户不能使用相同的模n，否则任一用户的n被分解，可通过

其他用户的公钥求出其私钥。

(9)明文M的熵要尽可能大，使得在已知密文的情况下，要猜测明文的内容几乎是不可能的。

由以上所述，RSA的全部保密性依赖于N=p×q的分解的难度计算，是一个大因子分解问题，但是，目前并不能从理论上证明这一点。而从实践的角度说，N=p×q的分解可使系统完全被解密。再有，即使N未被分解，若参数选择不当，攻击者也完全可能在可以接受的时间内解密，主要原因是明文和密文以及N和e提供了另外一些破解信息。 因此，破译RSA不可能比大因子分解更困难。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库RSA算法安全性分析及其参数的选择(2)在线全文阅读。