RSA公钥密码算法的攻击与防范

1、精选文档RSA算法的攻击与防范摘要：作为对典型的公钥密码算法，RSA算法在信息平安领域得到了广泛的应用，但是其平安性却始终是学者们谈论的话题。本文首先介绍RSA公钥加密算法的工作原理，对RSA算法的缺陷以及对其所可能患病的攻击进行分析，最终争辩了针对RSA算法攻击的防范措施。关键词： 公钥密码算法 RSA算法 缺陷 攻击 防范Abstract:As the typical public-key algorithms,RSA algorithms has been widely applied in the field of information security,but its securi

2、ty has been among the scholars.This paper first introduces the theory of the RSA public-key encryption algorithm,and then,analysis the defects of the possible attacking,finally,discusses the attacking preventive measures for RSA algorithms.Keywords:Public-key algorithms;RSA algorithms;Defects;Attack

3、ing;Prevention一、引言计算机和互联网络的飞速进展使世界范围内信息的传递变得越来越便利，同时，也带来了保障信息平安的新问题。而密码学理论和技术的争辩与应用，为保证信道中信息的平安传输奠定了基础。现代密码体制主要分为私钥密码体制和公钥密码体制，其中私钥体制又称单钥体制或对称密码体制，其加密密钥和解密密钥相同，密钥严格保密；公钥体制又称双钥体制或非对称密码体制，其所用的加、解密钥不同，加密密钥公开，解密密钥不公开，适用于开放的使用环境。1976年Diffie和Hellman发表了密码学的新方向一文，首次提出了公开密钥的密码学，即公钥密码学，打破了长期使用单密钥体制的束缚。目前比较流行的

4、公钥密码算法主要有两种：一类是基于大素数因子分解问题的，其中最典型的代表就是RSA公钥密码算法； 1977年R.L.River，A.Shamir和L.Adleman3人共同提出了RSA算法，并很快成为了一种典型的公钥体制密码算法。另一类是基于离散对数问题的，如ELGamal公钥密码算法和椭圆曲线公钥密码算法等。二、RSA算法简介RSA公钥加密算法是1978年由美国麻省理工学院（MIT）的Rivest、Shamirh和Adleman共同提出的，它是目前最有影响力的公钥加密算法。RSA算法基于一个格外简洁的数学难题：将两个大素数相乘格外简洁，但想要对其乘积进行因式分解却格外困难，用很简洁的形式实现

5、了格外牢靠的密码算法。RSA的平安性依靠于大数的因子分解，而大整数因子分解问题是数学上的有名难题，至今没有有效的方法予以解决，因此能够确保RSA算法的平安性。RSA算法是目前最优秀的公钥方案之一，除加密功能外，公钥系统还用于身份验证（Authentication）或数字签名（Digital Signature），因此它为公用网络上信息的加密和鉴别供应了一种基本的方法。大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。它通常是先生成一对RSAl密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文档发送给个人，个人就能够

6、用私钥解密接受。三、RSA的算法描述（一）RSA算法密钥的产生1.选两个大的素数p，q(保密)；2.计算n=p*q(公开)，欧拉函数（n）=（p-1）*（q-1）；3.随机选取e作为公钥(加密密钥)，满足gcd(e,（n）)=1(公开)；4.计算私钥d(解密密钥)，满足edl(mod(（n）)，即ed-1(mod(（n）)；5.销毁p，q及（n）；6.得到所需的公开密钥和保密密钥。公开密钥：EK=e，n； 保密密钥：DK=d，n；（二）RSA算法加密和解密变换首先将明文分块并数字化，每个数字化的明文的长度不大于2n，然后对每个明文块m（0mn）一次进行加解密变换：1.加密变换：使用公钥e和明文

7、m，获得密文cme（modn）2.解密变换：使用私钥d和密文c，获得明文mcd（modn）四、RSA算法的缺陷RSA密码算法作为公钥密码体制的代表被广泛地应用于现代信息平安的各个领域，它的平安性的理论基础是大素数的因子分解问题，此问题至今没有很好的算法，但是它本身却存在着一些缺陷，综合来说，RSA算法的不足或者缺陷主要包括：（一）RSA算法所要求的n，p，q都要求为很大的整数或素数，实现时接受的是重复平方求模和相乘后求模的迭代方法来实现，此方法在进行数据加密时耗费时间过长。（二）RSA算法中所用的p，q假如太接近的话，密码分析者可以通过计算 ，然后在 四周搜寻p，q来分解n。（三）对于一个明文

8、消息m（0mn),假如将其加密成m自身，称m为RSA的不动点，也成m为未隐匿的消息。对RSA算法来讲其不动点的个数为（1+gcd(e-1)，(p+1)*(1+gcd(e-1)，(q-1)。由于e-1，p-1，q-1都是偶数，所以RSA不动点的个数至少为9个。（四）同态性。由RSA算法知对于一切x1，x2Zn，有Ek（x1，x2）Ek(x1)Ek(modn)是RSA算法的一个缺陷，由于攻击者知道C1,C2的明文，就可以知道C1C2(modn)对应明文m1m2（modn）。基于以上的缺陷，攻击者想来对RSA算法进行攻击的一系列攻击方法，其中最常用的攻击方法有因子分解攻击、选择密文攻击、同模攻击、小

9、指数/指数攻击、迭代循环攻击、定时攻击等。五、常见的RSA攻击方法（一）因子分解攻击易知，若n=pq被因子分解，则可以得到p(n)=(p-1)*(q-1)的值，从而利用edl(mod(（n）)解出d。较早消灭的因子分解攻击方法是试除法，即通过尝试小于n的全部素数，来找到因子。这种方法理论上是有效的，但对于大数n，由于要花费更多时间使其变得不行能完成。由于因子分解的时间简单性并未降到多项式时间，所以仍是一个计算上的难题。但是随着计算速度的提高，分解的速度会越来越快，2002年人们成功分解了RSA-158。（二）选择密文攻击选择密文攻击是通过骗取把握私钥者的签名实现攻击。假设攻击者截获了密文y，想

10、得到明文x，可以接受如下方法：选择一个随机数r，r<n，然后使用收件人的公钥加密r，假设得到的中间结果为t，明显t=re(modn)；然后着将中间结果t与截获的密文相乘，假设得到O，O=t*Y(modn)，想方法骗取收件人用私钥d对O进行签名，假设签名后的结果为u，u=O(modn)，得到u后，攻击者计算值f=r-1(modn)，结合u就可以计算出明文X。（三）共模攻击共模攻击是由于在RSA体制的实现过程中，不同用户使用相同的模n、不同的指数值e和d所引起的。由于消灭这种状况可能导致下列三个主要问题，所以会使得系统变得不再平安。1.若相同的明文分送给两个不同的使用者，且此二使用者的公开密

11、钥为互素，则此系统并担忧全。2.拥有一对的加/解密密钥就能因子分解n。3.拥有一对加/解密密钥，能在不必分解n的状况下，求出另一对加解密密钥。（四）小指数攻击从计算速度角度考虑，公钥指数e越小加密速度越快。可是，当明文也很小时就会消灭问题。比如我们取e=3，明文x小于N 的三次方，密文y=xe(modN)=x3(modN)=x3，这样直接对密文y开三次方就会得到明文x。（五）定时攻击定时攻击主要针对RSA核心运算是格外耗时间的模乘，只要能精确监视RSA的解密过程，获得解密时间，就可以估算出私有密钥d。模指数运算是通过一位一位来计算的，每次迭代执行一次模乘，并且假如当前位是l，则还需要进行一次模

12、乘对于有些密码，后一次模乘执行速度会极慢，攻击者就可以在观测数据解密时，依据执行时间推断当前位是1还是0。六、RSA算法的防范针对RSA算法的固有缺陷和对RSA算法的常见攻击方法，我们可以实行以下几种措施对其进行防范：（一）为了保证平安性，在选取p、q时使用较大的素数，因式分解理论的争辩现状表明：使用RSA密钥至少需要1024比特，才能有效的保证攻击者无法在短时间破解得到因子。（二）通过设计新的素数生成方案，保证为每一用户生成不同的大素数，从而消退用户共模，避开系统患病共模攻击。（三）公钥e不行选得过小，使攻击者很难通过开方得到密文。（四）通过常数取幂时间，随即延时，在加密前对数据做盲化处理盲

13、化等方法对定时攻击进行防范。七、结束语RSA算法是第一个能同时用于加密和数字签名的算法，也是被争辩得最为广泛的公钥算法，从1978年提出到现在的三十多年里经受了各种攻击的考验，被认为是目前最优秀的公钥方案之一。但是，假RSA的平安性还需要不断的争辩和改进，这就使得我们在应用时既要留意使用平安和环境平安，发挥RSA自身的优势，同时也要重视多种密码体制并用，不断争辩和发觉新的密码体制，来满足人们的通信平安保密需求。参考文献：1卢开澄.计算机密码学（第2版）M.北京:清华高校出版社,19982洪帆,崔国华,付小青.信息平安概论M.武汉:华中科技高校出版社,20053赵胜,孙永道.RSA公开密钥加密算法解析J.硅谷,2008(11):5657.4Carisle Adams,Steve Lloyd.公开密钥基础设施概念?标准和设施M.北京:人民邮电出版社,20015陈彦学.信息平安理论实务M.北京:中国铁道出版社,20016(美)Bruc