《信息安全大作业.doc》由会员分享，可在线阅读，更多相关《信息安全大作业.doc（5页珍藏版）》请在金锄头文库上搜索。
1、 RSA的算法研究及其安全性分析 姓名：刘波 学号：01105120摘要： 随着信息技术的发展，特别是电子商务的发展，网络信息的安全传输逐渐成为人们最为关心和头痛的事情。密码安全研究与设计是当前密码学领域的热点问题。通过对RSA的安全性进行了分析，提出构造安全素数。RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名：Ron Rivest, Adi Shamir 和Leonard Adleman 。虽然自1978年提出以来，RSA的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今（2006年）未被完全攻破。随
2、着越来越多的商业应用和标准化工作，RSA已经成为最具代表性的公钥加密技术。关键字： RSA算法, 数字签名, 公开密钥, 加密 RSA s algorithm research and its security analysis Liubo 01105120an abstract ： as the information technology the development of， in particular the electronic business development，the network of information the safety of transmission is
3、gradually become press most people care and headache what.the safety of research and design is the current to learn the field hot problem. by about RSA security on analysis,the proposed a structure of the security prime number.RSA firms the key Encrypt algorithm is neither can also be used for the f
4、irst data Encrypt the number of a signature algorithm.it is easy to understand and operate, it is also very popular.algorithm name in the inventor surname named after the first letter of the Ron Rivest, Adi Shamir and Leonard Adleman .although from 1978 to put forward by come,SA security has failed
5、to get the theory that, but it experience of the attack.as more and more commercial applications and normative work,RSA has become the most of great of male the key Encrypt technology.Keyword: RSA algorithm ,the number of a signature ,public dense key ,Encrypt 随着网络技术的飞速发展,信息安全性已成为亟待解决的问题.公钥密码体制中,解密和
6、加密密钥不同,解密和加密可分离,通信双方无须事先交换密钥就可建立起保密通信,较好地解决了传统密码体制在网络通信中出现的问题.另外,随着电子商务的发展,网络上资金的电子交换日益频繁,如何防止信息的伪造和欺骗也成为非常重要的问题.数字签名可以起到身份认证,核准数据完整性的作用.目前关于数字签名的研究主要集中基于公钥密码体制的数字签名. 公钥密码体制的特点是:为每个用户产生一对密钥(PK和SK);PK公开,SK保密;从PK推出SK是很困难的;A,B双方通信时,A通过任何途径取得B的公钥,用B的公钥加密信息.加密后的信息可通过任何不安全信道发送.B收到密文信息后,用自己私钥解密恢复出明文. 公钥密码体
7、制已成为确保信息的安全性的关键技术.RSA公钥密码体制到目前为止还是一种认可为安全的体制.本文详述了RSA算法和用RSA算法实现数字签名的理论,以及它们在实际应用中的实现.RSA的算法介绍：RSA系统由以下几部分组成：(1) 随机选取的在素数P和Q，还有N ，其中N=P*Q ，P和Q保密，N公开。 (2) 任取 (n)=（ P-1）*(Q-1)，其中 (n)表示比n小的素数的个数，任取2=e= (n),且(e, (n)=1,e为加密密钥，公开。(3) (计算d,使e*d=1(mod (n),称d为e对模 (n)的逆，其中d为解密秘钥，保密。在RSA系统中，设m为明文，且明文块的数值大小小于n,
8、c为密文，则其加密和解密算法如下：加密算法 C=E(m)=me(mod n)加密算法 m=D(c)=cd(mod n)在RSA系统中(e,n)构成加密秘钥，即公钥，(d,n) 构成解密秘钥，即私钥。RSA思想的证明： RSA是基于数论中的Euler定理和其它同余性质的，在证明RSA系统思想正确性之前，先给出Euler定理和同余式相乘的性质： Euler定理：设（a,n）=1,即a 和 n互素，则有a(n) = 1 (mod n )同余式相乘性质: 设有a=b (mod n),c=d (mod n) 则有a*c=b*d ( mod n)证明RSA系统思想正确性主要是看能否从密文c和解密秘钥d恢复
9、明文m,即由c和d,计算出m=D(c)=Cd (mod n)。下面就证明是否能从密文c和解密密钥d恢复明文m, 为 e*d=1 (mod (n) e*d=k* (n)+1,其中K为任意整数。由解密公式D(c) = Cd(mod n) 有：D(c)=Cd(mod n)=Me*d=Mk*(n)+1= Mk*(n)*M又由Euler定理有Mk*(n) =(M(n)k = 1( mod n)同样由同余式相乘性质有D(c)=Cd(mod n)=Me*d=Mk*(n)+1 = Mk*(n)*M = M (mod n)由于明文块数值小于n,则有D(c)=Cd(mod n)=Me*d=M k*(n)+1 =
10、Mk*(n)*M =M (mod n) = M故RSA中，能利用e和c恢复明文m,则RSA的系统思想证明是正确的。但众所周知RSA是基于整数因子分解的密码体制，它利用的是：求两个大素数的乘积是很容易计算的，但分解密两个大素数的乘积，求出它们的素数因子却是非常困难的，这样一个数学难题，它属于NP-完全类。因此RSA的安全性完全信赖于因子分解的困难性，只要N=P*Q被因子分解，则RSA便被击破，这样在RSA系统中怎样选取大的素数P，Q才是关键所在。RSA中素数的选取： 在RSA中，因N=P*Q， 若P，Q被知道，即能将N因子分解，则由 (n)=（P-1）*(Q-1)可以算出。由于e是公开密钥，且解
11、密秘钥D关于E满足D*E=1 (mod (n)则D也不难求得，这样RSA系统便被完全攻破。 RSA中的素数都是上面位的十进制数，怎样才能选择好的P和Q，怎样才能生成这样的数，并且判断它是否为素数，这是一个RSA系统关键的问题。针对素数P和Q的选择，1978年Rivest等人在正式发表的RSA公开密钥的论文中，就建议对素数P和Q的选择应当满足：(1) P、Q要足够在，在长度上应相差几位，且二者之差与P、Q位数相近；(2) P-1与Q-1的最大公约数GCD(P-1,Q-1)就尽量小；(3) P-1与Q-1均应至少含有一个大的素数因子。并把满足这些条件的素数称为安全素数。RSA的安全性分析：在公布R
12、SA算法之后，在使用RSA密码体制和分析RSA算法发现了一系列的算法本身脆弱性及其存在的问题。（1）RSA公钥密码体制在加密或解密变化中涉及大量的数值计算，其加密和解密的运算时间比较长，这比数据加密标准DES的计算量开销大，在一定程度上限制了它的应用范围，以致实际使用RSA密码体制无法用软件产品，必须用超大规模集成电路的硬件产品。（2）虽然提高N=P*Q的位数会大大提高RSA密码体制的安全性，但其计算量呈指数增长，以致使其实现的难度增大，实用性降低。（3）RSA公钥密码体制的算法完整性（指密钥控制加密或解密变换的唯一性）和安全性（指密码算法除密钥本身外，不应该存在其它可破译密码体制的可能性）沿
13、有等进一步完善。（4）RSA算法面临着数学方法的进步和计算机技术飞跃发展带来的破译密码能力日趋强的严重挑战。因子分解问题有了长跑的发展，1995年人类成功地分解了128位十进制数RSA密码算法，破译512位长的RSA指日可待。 尽管如此，自1978年RSA算法公布以来，公开密钥密码已从理论研究进入实际应用研究阶段。RSA公开密钥密码算法在信息交换过程中使用比较广泛，安全性比较高。以当前的计算机水平，如选择1024位长的密钥就认为是无法攻破的。RSA算法的安全性分析： RSA算法的时间复杂性取决于它所设计的几个基本运算的时间复杂性. 密钥生成过程时间主要是生成随机素数的时间及计算公钥和私钥的模乘
14、法的时间.生成随机素数的时间在于完成对随机大数的Fermat测试的时间,Fermat测试的时间复杂度为O(log2n)3),n所测试的整数.模乘法的计算方法采取先计算两个数的乘积,再取模n,时间复杂性为O(log2n)2). RSA加密解密计算的时间主要是模幂运算的时间,即形式为xc mod n的函数的运算时间.模幂算法采取平方乘算法,设l是c的长度,则计算xc mod n至多需要2l次模乘法,因为llog2n+1,所以模幂运算能在时间O(log2n)3)内完成.因此,RSA的加密和解密均可在多项式时间内完成.RSA算法数字签名的实现： RSA数字签名算法,包括签名算法和验证签名算法.首先用M
15、D5算法对信息作散列计算.签名的过程需用户的私钥,验证过程需用户的公钥.A用签名算法将字符串形式的消息处理成签名;B用验证签名算法验证签名是否是A对消息的签名,确认是A发送的消息;消息没有被攥改过;A一定发送过消息.签名算法 签名算法包括三步:（1）消息摘要计算,RSA加密（2)消息摘要计算，消息在签名前首先通过MD5计算,生成128位的消息摘要 (3)digest对摘要作RSA计算。用加密算法,采用签名者的私钥加密消息摘要,得到加密后的字符串。加密算法中使用的加密块为01类型。验证签名算法 验证签名算法包括两步:(1)RSA解密得签名者的消息摘要,验证者对原消息计算摘要,比较两个消息摘要.(2)验证签名的过程输入为消息,签名者的公钥,签名;输出为验证的结果,即是否是正确的签名. RSA解密. 签名实际是加密的字符串.用3.5所述的解密算法,采用签名者的公钥对这个加密的字符串解密.解密的结果应为128位的消息摘要.在解密过程中,若出现得到的加密块的类型不是01,则解密失败.签名不正确. 消息摘要计算和比较. 验证者对消息用MD5算法重新计算,得到验证者自己的消息摘要.验证者比较解密得到的消息摘要和自己的消息摘要,如果两者相同,则验证成功,可以确认消息的完整性及签名确实为签名者的;否则,验证失败.
