信息安全技术-RSA算法的介绍与证明

RSA算法的介绍与证明学院名称：计算机与信息工程学院项目名称：RSA算法的介绍与证明组员：林娜莉李兴彬马子健阮雪妃张传旭胡文峰指导教师：陈培芝厦门理工学院二〇一五年六月RSA算法的介绍与证明摘要：RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。1、前言随着Internet的迅猛发展，基于Internet的各种应用也日新月异，日益增长。但是，由于Internet是一个极度开放的环境，任何人都可以在任何时间、任何地点接入Internet获取所需的信息，这也使得在Internet上信息传输及存储的安全问题成为影响Internet应用发展的重要因素。正因为如此，信息安全技术也就成为了人们研究Internet应用的新热点。信息安全的研究包括密码理论与技术、安全协议与技术、安全体系结构理论、信息对抗理论与技术、网络安全与安全产品等诸多领域。在其中，密码算法的理论与实现研究是信息安全研究的基础。而确保数据加密算法实现的可靠性和安全性对于算法理论应用到各种安全产品中起到了至关重要的作用。对各类电子信息进行加密，以保证在其存储，处理，传送以及交换过程中不会泄露，是对其实施保护，保证信息安全的有效措施。RSA公钥加密算法是1977年由RonRivest、AdiShamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。2、什么是RSARSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(SecureElectronicTransaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。C)RSA密钥长度随着保密级别提高，增加很快。这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：RonRivest,AdiShamir和LeonardAdleman。早在1973年，英国国家通信总局的数学家CliffordCocks就发现了类似的算法。但是他的发现被列为绝密，直到1998年才公诸于世。3、RSA算法的证明RSA加密算法随机选择两个大素数p和q，p!=q，p和q保密计算n=pq，n公开计算φ(n)=(p-1)(q-1),φ(n)保密随机选择整数e，1eφ(n)，且gcd(e,φ(n))=1,e公开计算d满足：de≡1(modφ(n)),d保密(n,e)是公钥，(n,d)是私钥明文m，密文c加密变换：c≡memodn解密变换：m≡cdmodn要证m≡cdmodn∵mn∴即证cd≡m(modn)又∵c≡memodn∴即证mde≡m(modn)∵de≡1(modφ(n))∴存在整数k使得de=k*φ(n)+1ifgcd(m,n)=1由欧拉定理mφ(n)≡1(modn)得mde≡mkφ(n)+1≡m(modn)else∵mn,n=pq,p和q是素数,p!=q∴m的因子必含有p或q中一个设m=cp且m%q!=0由费马小定理mq-1≡1(modq)得mkφ(n)≡mk(p-1)(q-1)≡1k(p-1)≡1(modq)设整数h使得mkφ(n)=hq+1两边同时乘以mmkφ(n)+1=hqm+m=hqcp+m=hcn+m∴mde≡mkφ(n)+1≡m(modn)p=43，q=59，n=43*59=2537，φ(n)=42*58=2435，e=13明文2106，计算密文c=210613mod2537过程如下：A0=2106A1≡21062≡560(mod2537)A2≡5602≡1549(mod2537)A3≡15492≡1936(mod2537)∵13二进制为1101∴210613≡A3*A2*A0≡1936*1549*2106≡2321(mod2537)得c=2321时间复杂度(loge)4、RSA的安全性分析随着计算机网络通信技术的发展,对信息安全的要求也越来越高,信息加密技术也需进一步的提高.为了提高数据在计算机网络传输过程中的安全性,文中应用了RSA非对称加密算法及RSA操作和RSA填充问题,并给出了RSA非对称加密算法在数字签名中的应用方案,经过测试证明该方案能够进一步提高数据在网络传输过程中的安全性.RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n必须选得大一些，因具体适用情况而定。当然也可以通过猜测(p-1)(q-1)的值来攻击RSA。但这种攻击没有分解n容易有些攻击专门针对RSA的实现。他们不攻击基本的算法，而是攻击协议。仅会使用RSA而不重视它的实现是不够的。实现细节也很重要。这就是对RSA的选择密文攻击。RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：(XM)^d=X^d*M^dmodn。前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-WayHashFunction对文档作HASH处理，或同时使用不同的签名算法。还有一种就是对RSA的公共模数攻击。若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那么该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：C1=P^e1modnC2=P^e2modn密码分析者知道n、e1、e2、C1和C2，就能得到P。因为e1和e2互质，故用Euclidean算法能找到r和s，满足：r*e1+s*e2=1假设r为负数，需再用Euclidean算法计算C1^(-1)，则(C1^(-1))^(-r)*C2^s=Pmodn另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e和d，而无需分解模数。解决办法只有一个，那就是不要共享模数n。5、RSA的速度由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右。6、RSA的选择密文攻击RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：XM)^d=X^d*M^dmodn前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-WayHashFunction对文档作HASH处理，或同时使用不同的签名算法。7、RSA的公共模数攻击若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那么该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：C1=P^e1modnC2=P^e2modn密码分析者知道n、e1、e2、C1和C2，就能得到P。因为e1和e2互质，故用Euclidean算法能找到r和s，满足：r*e1+s*e2=1假设r为负数，需再用Euclidean算法计算C1^(-1)，则(C1^(-1))^(-r)*C2^s=Pmodn另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无需分解模数。解决办法只有一个，那就是不要共享模数n。RSA的小指数攻击。有一种提高RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。8、RSA加密算法的缺点(1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。(2)安全性,RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。目前，人们已能分解140多个十进制位的大素数，这就要求使用更长的密钥，速度更慢；另外，目前人们正在积极寻找攻击RSA的方法，如选择密文攻击，一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：(XM)d=Xd*Mdmodn前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-WayHashFunction对文档作HASH处理，或同时使用不同的签名算法。除了利用公共模数，人们还尝试一些利用解密指数或φ（n）等等攻击。(3)速度太慢,由于RSA的分组长度太大，为保证安全性，n至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(SecureElectronicTransaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。为了速度问题,目前人们广泛使用单,公钥密码结合使用的方法,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然