RSA算法论文.docx

《RSA算法论文.docx》由会员分享，可在线阅读，更多相关《RSA算法论文.docx（6页珍藏版）》请在优知文库上搜索。

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

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

3、径取得B的公钥,用B的公钥加密信息.加密后的信息可通过任何担心全信道发送.B收到密文信息后,用Fl己私钥解密复原出明文.公钥密码体制已成为确保信息的平安性的关键技术.RSA公钥密码体制到目前为止还是一种认可为平安的体制.本文详述了RSA算法和用RSA算法实现数字签名的理论，以及它们在实际应用中的实现.RSA算法介绍：RSA系统由以下几部分组成：(1)随机选取的在素数P和Q,还有N,其中N=P*Q,P和Q保密,N公开。(2)任取(n)=(P-I)*(Q-1),其中(n)表示比n小的素数的个数，任取2=e=(n),且(e,(n)=l,e为加密密钥，公开。(3)(计算d,使e*d=l(mod(n),

4、称d为e对模(n)的逆，其中d为解密秘钥，保密。在RSA系统中，设m为明文，且明文块的数值大小小于n,c为密文，则其加密和解密算法如下：加密算法C=E(In)=11f(modn)加密算法m=D(c)=C1(modn)在RSA系统中(e,n)构成加密秘钥，即公钥，(d,n)构成解密秘钥，即私钥。RSA思想的证明：RSA是基于数论中的Euler定理和其它同余性质的，在证明RSA系统思想正确性之前，先给出Euler定理和同余式相乘的性质：Euler定理：设(a,n)=1,即a和n互素,则有ai=1(modn)同余式相乘性质：设有a=b(modn),c=d(modn)则有a*c=b*d(modn)证明

5、RSA系统思想正确性主要是看能否从密文c和解密秘例d复原明文m,即由c和d,计算出m=D(c)=Cd(modn)。下面就证明是否能从密文C和解密密钥d复原明文m,*.*为e*d=l(mod(n)e*d=k*(n)+l,其中K为随意整数。由解密公式D(C)=C(11odn)有：D(C)=CI(modn)=ME=*M又由EUler定理有MtIf=(M吗卜=Kmodn)同样由同余式相乘性质有D(c)=Cd(modn)=!Il=MmMl=Mw,*M=M(modn)由于明文块数值小于n,则有D(C)=C(modn)=N1=M-=Mkl*M=M(modn)=M故RSA中，能利用e和c复原明文m,则RSA的

6、系统思想证明是正确的。但众所周知RSA是基于整数因子分解的密码体制，它利用的是：求两个大素数的乘积是很简单计算的，但分解密两个大素数的乘积，求出它们的素数因子却是特别困难的，这样一个数学难题，它属于NP-完全类。因此RSA的平安性完全信任于因子分解的困难性，只要N=P*Q被因子分解，则RSA便被击破，这样在RSA系统中怎样选取大的素数P,Q才是关键所在。RSA中宗数的选取：在RSA中，因N=P*Q,若P,Q被知道，即能将N因子分解，则由(Q=(P-1)*(QT)可以算出。由于e是公开密钥，且解密秘钥D关于E满意)*E=1(mod(n)则D也不难求得，这样RSA系统便被完全攻破。RSA中的素数都

7、是上面位的十进制数，怎样才能选择好的P和Q,怎样才能生成这样的数，并且推断它是否为素数，这是一个RSA系统关键的问题。针对素数P和Q的选择，1978年Rivcst等人在正式发表的RSA公开密钥的论文中，就建议对素数P和Q的选择应当满意：(DP、Q要足够在,在长度上应相差儿位，且二者之差及P、Q位数相近；(2)PT及QT的最大公约数GCD（P-1,QT）就尽量小：（3）PT及Q-I均应至少含有一个大的素数因子。并把满意这些条件的素数称为平安素数。RSA平安性分析：在公布RSA算法之后，在运用RSA密码体制和分析RS算法发觉了一系列的克法本身脆弱性及其存在的问题。（I）RSA公钥密码体制在加密或解

8、密改变中涉及大量的数值计算，其加密和解密的运算时间比较长，这比数据加密标准DES的计算量开销大，在肯定程度上限制了它的应用范围，以致实际运用RS密码体制无法用软件产品，必需用超大规模集成电路的硬件产品。（2）虽然提高=P*Q的位数会大大提高RS密码体制的平安性，但其计算量呈指数增长，以致使其实现的难度增大，好用性降低。（3） RSA公钥密码体制的算法完整性（指密钥限制加密或解密变换的唯一性）和平安性（指密码算法除密钥本身外，不应当存在其它可破译密码体制的可能性）沿有等进一步完善。（4） RSA郛法面临着数学方法的进步和计算机技术S跃发展带来的破译密码实力口趋强的严峻挑战。因子分解问题有了长跑的

9、发展，1995年人类胜利地分解了128位十进制数RSA密码算法，破译512位长的RSA指日可待。尽管如此，H1978年RSA算法公他以来，公开密钥密码已从理论探讨进入实际应用探讨阶段。RSA公开密钥密码算法在信息交换过程中运用比较广泛，平安性比较高。以当前的计算机水平，如选择1024位长的密钥就认为是无法攻破的。RSA算法的时间困难性：RSA算法的时间困难性取决于它所设计的几个基本运算的时间困难性.密钥生成过程时间主要是生成随机素数的时间及计算公钥和私钥的模乘法的时间.生成随机素数的时间在于完成对随机大数的Fermat测试的时间,FCrmat测试的时间困难度为O(IOg2n)3),n所测试的整

10、数.模乘法的计算方法实行先计算两个数的乘积,再取模n,时间困难性为O(log2n)2).RSA加密解密计算的时间主要是模幕运算的时间，即形式为Xcmodn的函数的运算时间.模泰算法实行平方乘算法,设1是C的长度，则计算xcmodn至多须要21次模乘法，因为llog2n+l,所以模哥运算能在时间O(IOg2n)3)内完成.因此,RSA的加密和解密均可在多项式时间内完成.RSA数字签名算法的实现IRS数字签名算法,包括签名算法和验证签名算法.首先用MD5算法对信息作散列计尊.签名的过程需用户的私钥,验证过程需用户的公钥.A用签名算法将字符串形式的消息处理成签名；B用验证签名算法验证签名是否是A对消

11、息的签名，确认是A发送的消息;消息没有被摄改过;A肯定发送过消息.签名算法签名弊法包括三步：(D消息摘要计算,RSA加密(2)消息摘要计算,消息在签名前首先通过MD5计算,生成128位的消息摘要(3)digest对摘要作RSA计算。用加密算法,采纳签名者的私钥加密消息摘要,得到加密后的字符串。加密算法中运用的加密块为Ol类型。验证签名算法验证签名算法包括两步：(DRSA解密得签名者的消息摘要,验证者对原消息计算摘要，比较两个消息摘要.(2)验证签名的过程输入为消息，签名者的公钥,签名；输出为验证的结果，即是否是正确的签名.RSA解密.签名实际是加密的字符串.用3.5所述的解密算法,采纳签名者的

12、公钥对这个加密的字符串解密.解密的结果应为128位的消息摘要.在解密过程中，若出现得到的加密块的类型不是01,则解密失败.签名不正确.消息摘要计算和比较.验证者对消息用MD5算法重新计算,得到验证者自己的消息摘要.验证者比较解密得到的消息摘要和Fl己的消息摘要，假如两者相同，则验证胜利，可以确认消息的完整性及签名的确为签名者的；否则,验证失败.RSA加密算法的缺点：(D产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。(2)平安性，RSA的平安性依靠于大数的因子分解，但并没有从理论上证明破译RSA的难度及大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。(3)速度

13、太慢，由于RSA的分组长度太大，为保证平安性，n至少也要60ObitX以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。结束语：RSA算法是一种平安技术,但是RSA算法的平安性只是一种计算平安性,绝不是无条件的平安性,这是由它的理论基础确定的.因此,在实现RSA算法的过程中，每一步都应尽量从平安性考虑.总之，随着密码技术的进一步发展，以及计第机平安探讨的技术人员的不断努力，我信任具有更高性能、更高效率的密码加密体制将会诞生。参考文献:1胡道元，闵京华网络平安清华高校出版社2019年2冯登国，装定一密码学导引，科学出版社，2019年3卓光辉，祁明，周浩华数字签名技术的探讨和进展，2000年4曹珍富公钥密码学，黑龙江教化出版社，1993年