rsa加密算法的安全性分析

《rsa加密算法的安全性分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、RSA加密算法的安全性分析*肖媛媛(潍坊学院,山东潍坊261061)摘要:描述了RSA算法,给出了RSA加解密的算法以及它的抗攻击能力分析表,总结了常见的攻击方式,最后分析了在实际应用中存在的一些弊端。关键词:RSA;公钥密码体制;安全性中图分类号:TP309文献标识码:A文章编号:1671-4288(2009)06-0050-03随着当前网络技术和电子商务的高速发展和普及,对网络数据安全的需求日益迫切,如何保证网络上的信息安全成为一个重要的研究课题,而数据加密是保护信息安全的一种重要方法。密码学

2、的鼻祖香农[1]提出了一些概念和基本理论,论证了只有一种密码算法在理论上是不可解的。目前,在各种公钥密码算法中,RSA公钥密码算法是用途比较完备、使用最为广泛的一种公钥密码体制。它表达方法简单,保密性强,没有密钥管理的麻烦;并且可用于数字签名、认证等服务,特别适合于现代保密通信的需要。但由于其算法是基于大数的模幂模乘运算,特别是目前为防止各种攻击,其模长在不断增加,算法运行的速度成为RSA密码算法的一个显著缺陷,特别是在软件环境下,加解密速度比较慢。1RSA算法原理1978年,RivestRL、S

3、hamirA和AdlemanL发表了著名的论文/AMethodforObtainingDigitalSignaturesandPublic-KeyCyrptosystems0,继MH背包公钥密码体制以后,提出了第一个有效的公钥密码体制,现被用他们的名字的首字PI命名,称为RSA公钥密码体制[2]。1.1RSA的密钥生成步骤¹找到2个大质数p,q;º做乘法n=p*q;»选择一个数e,满足e

4、;¾公匙就是(n,e),私匙是(n,d);¿销毁p和q;加密算法是这样的,把明文分成比n小的数据块用公开指数作乘方取模运算c=memodn(m是明文块(message),c是密文块(cipher))。解密过程正相反,把密文数据块用私密指数作乘方取模运算m=cdmodn攻击者有公匙,就是e和n,想获得私匙,换句话就是d,对n进行因数分解来获得p,q从而算出d是最好的攻击方法,直接穷举d或推断(p-1)(q-1)都要慢许多[3]。1.2几种因数分解的算法¹试探除法:最古老也是最笨拙的方法,穷举所有小于

5、sqrt(n)的质数,耗时以指数率增长。º二次筛法(QS)[4]:对10110以内的数是最快的算法。»MPQS:QS的改进版本,速度要快一些。¼分区筛法(NFS)[5]:目前对大于10110的数是最快的算法,曾被用来成功地分解过第9费马数。这些算法代表了人们对RSA攻击的探索历程,最好的算法具有超多项式率(亚指数率)的时间复杂度,NFS具有最接近于多项式率的表现。大数分解仍然是困难的,但随着数论的发展和计算能力的增强而变得容易了。1977年,RonR-ivest说过分解一个125位的数需要花费4@

6、1013a。在1994年RSA129被分解了,花费了5000MIPS#a的机时,是利用Internet上一些计算机的空闲)50)第9卷第6期潍坊学院学报Vol.9No.62009年11月JournalofWeifangUniversityNov.2009*收稿日期:2009-06-24作者简介:肖媛媛(1982-),女,山东淄博人,潍坊学院信息与控制工程学院助教。CPU周期一共花了8个月完成的。1995年,Blacknet密钥被分解,用了几十台工作站和1台MarPar,共用400MIPS#a,历时

7、3个月。随着时间的推移,可能被分解的密钥长度还会增加。表1是常用的几种RSA密钥长度(PGP精选出的)与其对应的NFS分解算法所耗费的时间。表1NFS因数分解时间表密钥长NFS分解算法耗费的时间/MIPS#a5123000076820000000010243000000000002048300000000000000000000RSA的安全性依赖于大数分解的难度,因此需要一些产生非常大的质数的方法。目前还没有一种迅捷的产生一个大质数的算法,因此实际采用的方法是产生一个大奇数,然后测试它的质数性。1

8、.3大素数的选取(确定密钥)为了测试一个数的质数性,最显而易见的方法是作试探除法:将n用2到sqrt(n)的每个整数来除。如果n是质数,所有这些数都不能整除它,如果n是质数的话,这个算法的耗时是指数方式增长的,这对需要测试的大数来说太不经济了。从这里也可以看出,试探除法不是一条可行的RSA攻击道路。实际可以采用的方法是对候选奇数做费马测试。费马测试并不能确定它是否质数,但通过费马测试以后的数不是质数的概率大大降低。下面是费马测试的细节:¹待测奇数n;º在质数集合中依次选取一个质数b