RSA算法论文.docx

《RSA算法论文.docx》由会员分享，可在线阅读，更多相关《RSA算法论文.docx（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 RSA算法摘要: 随着信息技术的发展，特别是电子商务的发展，网络信息的安全传输逐渐成为人们最为关心与头痛的事情。密码安全研究与设计是当前密码学领域的热点问题。通过对RSA的安全性进行了分析，提出构造安全素数。RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解与操作，也十分流行。算法的名字以发明者的姓氏首字母命名：Ron Rivest, Adi Shamir 与Leonard Adleman。虽然自1978年提出以来，RSA的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今（2006年）未被完全攻破。随着越来越多的商业应用与标准化工作，RSA已经成为最具代表性

2、的公钥加密技术。关键字: RSA算法, 数字签名, 公开密钥, 加密引言： 随着网络技术的飞速发展,信息安全性已成为亟待解决的问题.公钥密码体制中,解密与加密密钥不同,解密与加密可分离,通信双方无须事先交换密钥就可建立起保密通信,较好地解决了传统密码体制在网络通信中出现的问题.另外,随着电子商务的发展,网络上资金的电子交换日益频繁,如何防止信息的伪造与欺骗也成为非常重要的问题.数字签名可以起到身份认证,核准数据完整性的作用.目前关于数字签名的研究主要集中基于公钥密码体制的数字签名. 公钥密码体制的特点是:为每个用户产生一对密钥(PK与SK);PK公开,SK保密;从PK推出SK是很困难的;A,B

3、双方通信时,A通过任何途径取得B的公钥,用B的公钥加密信息.加密后的信息可通过任何不安全信道发送.B收到密文信息后,用自己私钥解密恢复出明文. 公钥密码体制已成为确保信息的安全性的关键技术.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为加密密钥，公开。(

4、3) (计算d,使e*d=1(mod (n),称d为e对模 (n)的逆，其中d为解密秘钥，保密。在RSA系统中，设m为明文，且明文块的数值大小小于n,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 )同余式相乘性质:

5、 设有a=b (mod n),c=d (mod n) 则有a*c=b*d ( mod n)证明RSA系统思想正确性主要是看能否从密文c与解密秘钥d恢复明文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=M

6、k*(n)+1 = Mk*(n)*M = M (mod n)由于明文块数值小于n,则有D(c)=Cd(mod n)=Me*d=M k*(n)+1 = Mk*(n)*M =M (mod n) = M故RSA中，能利用e与c恢复明文m,则RSA的系统思想证明是正确的。但众所周知RSA是基于整数因子分解的密码体制，它利用的是：求两个大素数的乘积是很容易计算的，但分解密两个大素数的乘积，求出它们的素数因子却是非常困难的，这样一个数学难题，它属于NP-完全类。因此RSA的安全性完全信赖于因子分解的困难性，只要N=P*Q被因子分解，则RSA便被击破，这样在RSA系统中怎样选取大的素数P，Q才是关键所在。R

7、SA中素数的选取： 在RSA中，因N=P*Q， 若P，Q被知道，即能将N因子分解，则由 (n)=（P-1）*(Q-1)可以算出。由于e是公开密钥，且解密秘钥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的最大公约数

8、GCD(P-1,Q-1)就尽量小；(3) P-1与Q-1均应至少含有一个大的素数因子。并把满足这些条件的素数称为安全素数。RSA安全性分析：在公布RSA算法之后，在使用RSA密码体制与分析RSA算法发现了一系列的算法本身脆弱性及其存在的问题。（1）RSA公钥密码体制在加密或解密变化中涉及大量的数值计算，其加密与解密的运算时间比较长，这比数据加密标准DES的计算量开销大，在一定程度上限制了它的应用范围，以致实际使用RSA密码体制无法用软件产品，必须用超大规模集成电路的硬件产品。（2）虽然提高N=P*Q的位数会大大提高RSA密码体制的安全性，但其计算量呈指数增长，以致使其实现的难度增大，实用性降低

9、。（3）RSA公钥密码体制的算法完整性（指密钥控制加密或解密变换的唯一性）与安全性（指密码算法除密钥本身外，不应该存在其它可破译密码体制的可能性）沿有等进一步完善。（4）RSA算法面临着数学方法的进步与计算机技术飞跃发展带来的破译密码能力日趋强的严重挑战。因子分解问题有了长跑的发展，1995年人类成功地分解了128位十进制数RSA密码算法，破译512位长的RSA指日可待。 尽管如此，自1978年RSA算法公布以来，公开密钥密码已从理论研究进入实际应用研究阶段。RSA公开密钥密码算法在信息交换过程中使用比较广泛，安全性比较高。以当前的计算机水平，如选择1024位长的密钥就认为是无法攻破的。RSA

10、算法的时间复杂性： RSA算法的时间复杂性取决于它所设计的几个基本运算的时间复杂性. 密钥生成过程时间主要是生成随机素数的时间及计算公钥与私钥的模乘法的时间.生成随机素数的时间在于完成对随机大数的Fermat测试的时间,Fermat测试的时间复杂度为O(log2n)3),n所测试的整数.模乘法的计算方法采取先计算两个数的乘积,再取模n,时间复杂性为O(log2n)2). RSA加密解密计算的时间主要是模幂运算的时间,即形式为xc mod n的函数的运算时间.模幂算法采取平方乘算法,设l是c的长度,则计算xc mod n至多需要2l次模乘法,因为llog2n+1,所以模幂运算能在时间O(log2

11、n)3)内完成.因此,RSA的加密与解密均可在多项式时间内完成.RSA数字签名算法的实现： RSA数字签名算法,包括签名算法与验证签名算法.首先用MD5算法对信息作散列计算.签名的过程需用户的私钥,验证过程需用户的公钥.A用签名算法将字符串形式的消息处理成签名;B用验证签名算法验证签名是否是A对消息的签名,确认是A发送的消息;消息没有被攥改过;A一定发送过消息.签名算法 签名算法包括三步:（1）消息摘要计算,RSA加密（2)消息摘要计算，消息在签名前首先通过MD5计算,生成128位的消息摘要 (3)digest对摘要作RSA计算。用加密算法,采用签名者的私钥加密消息摘要,得到加密后的字符串。加

12、密算法中使用的加密块为01类型。验证签名算法 验证签名算法包括两步:(1)RSA解密得签名者的消息摘要,验证者对原消息计算摘要,比较两个消息摘要.(2)验证签名的过程输入为消息,签名者的公钥,签名;输出为验证的结果,即是否是正确的签名. RSA解密. 签名实际是加密的字符串.用3.5所述的解密算法,采用签名者的公钥对这个加密的字符串解密.解密的结果应为128位的消息摘要.在解密过程中,若出现得到的加密块的类型不是01,则解密失败.签名不正确. 消息摘要计算与比较. 验证者对消息用MD5算法重新计算,得到验证者自己的消息摘要.验证者比较解密得到的消息摘要与自己的消息摘要,如果两者相同,则验证成功

13、,可以确认消息的完整性及签名确实为签名者的;否则,验证失败.RSA加密算法的缺点：(1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。(2)安全性, RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。(3)速度太慢,由于RSA 的分组长度太大，为保证安全性，n 至少也要 600 bitx以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。结束语： RSA算法是一种安全技术,但是RSA算法的安全性只是一种计算安全性,绝不是无条件的安全性,这是由它的理论基础决定的.因此,在实现RSA算法的过程中,每一步都应尽量从安全性考虑.总之，随着密码技术的进一步发展，以及计算机安全研究的技术人员的不断努力，我相信具有更高性能、更高效率的密码加密体制将会诞生。参考文献：1 胡道元，闵京华网络安全清华大学出版社 2005 年2 冯登国，裴定一密码学导引,科学出版社，1999 年3 卓光辉，祁明，周浩华数字签名技术的研究与进展,2000 年4 曹珍富公钥密码学,黑龙江教育出版社，1993年第 7 页