RSA密码体制RSA cryptosystem
摘要： 随着电子政务的快速应用，信息交换的安全越来越引起人们的关注。对网络的新的威胁与攻击不断出现，寻找一个可靠安全的加密算法迫在眉睫。RSA就是目前主流的公钥加密算法。本文着重分析RSA基本算法以及安全性问题，最后也提出了自己的一些想法与观点。
Abstract：With the rapid application of e-government, exchange of information security has drawn increasing attention. The network’s new emerging threats and attacks, so look for a reliable and secure encryption algorithms imminent..RSA is the current mainstream public key encryption algorithm. This article focuses on the basic RSA algorithm and security issues, and finally also made some of their own thoughts and ideas.
关键词: RSA算法 安全性 大整数分解 攻击
引言：
众所周知，在密码系统中，分发密钥是其中最弱的一个环节，如果入侵者能够偷取到密钥，则整个系统就毫无价值可言。在传统的对称密码中，加密密钥同解密密钥是相同的，这就使得密钥的保护变得比较复杂。而公钥密码的出现正好弥补了这个不足。在这个系统中，加密密钥和解密密钥并不相同。RSA算法可谓是经典中的经典，也是我比较推崇的一种算法。
1 RSA算法简要分析
RSA公钥密码算法是基于大素数分解的困难性，下面简要说明加密解密算法。
[1] 选择两个大的素数p和q（p、q之差要大，这点将在下文详细说明）。
[2] 计算出n=p*q, z=(p-1)(q-1)。
[3] 选择一个公钥e，使e跟z互质。
[4] 选择一个私钥d，使得d*e=1 mod z 。
[5] 加密时从明文x计算密文y算法如下： 。
[6] 解密时，从密文y计算明文x的算法如下：
从算法中可以知道每一个RSA用户有一个公钥和一个私钥公钥（e,n）公布出来，私钥自己保留。我们可以这样假设每个用户把自己的公钥公布到一个统一的地方就像一个电话簿一样。如果想找到某个用户的公钥给他发密文时，只需要到电话簿里找到就行。当然这就需要一个专门的密钥分发中心，以防止不良者伪造。
2 安全性分析
从上面的介绍可以看出RSA算法本身很简单，关键是选择正确的密钥。问题是公钥e和n和私钥d都是计算出来的，既然发布者可以计算出，那么攻击者也可以。可是不用担心，这才是RSA的强大之处，入侵者在得到公钥e ，n的情况下想计算出d那是相当困难的。攻击者只要知道公钥e和n好像就可以用试错法找到私钥d。攻击者要如何做呢？首先要用n分解出p和q。如果p和q很小，很容易就可以试解出来。但实际中没人会那么傻把p和q设那么小。因此要从n分解出p和q是相当复杂和耗时的。数学分析表明，n为100位数时，要七十多年才能求出p和q。而现在512bit（154位）、664bit(200位)已有实用产品。也有人想用1024bit的模。若以每秒可进行100万步的计算资源分解664bit大整数，这就需要将近1000年。我想等解出密码的那一天，攻击者所付出的代价肯定要比密码消息本身大得多。而且这么多年过去了，密码破译出来之后又有什么价值呢，谁还在意呢！这正是RSA的强大之处。可是随着科技的发展以及人们不断寻找更有效的攻击方法，或许将来对于分解大素数也不会是个特别复杂和耗时的工作。下面给出一些常用的攻击方法。
[1] 迭代攻击法：Simmons和Norris【1977】曾提出迭代或者循环攻击法。例如，给定一RSA的参数为（n,e,y）=(35,17,3)，可由： ，再由 。从而得到明文 。一般对明文x加密多次，直到再现x为止。Rivest【1978】证明当 和 中含有大素数因子，且n足够大时，这种攻击成功的概率为零。
[2] 选择明文攻击：一般攻击者是将某一信息做一下伪装，让拥有私钥的实体签署，然后经过计算就可以得到他想要的信息。从算法上无法解决这个问题。防护的措施有：一是可以采用更好的公钥协议。另一条就是绝不对陌生人送来的随机文档签名。
3 RSA的优缺点
优点：上文介绍了这么多，相信对RSA的优点略有了解。RSA算法是第一个能同时运用于加密和数字签名的算法，也易于理解和操作。在安全方面也经受了多年来的各种攻击的考验，逐渐为人们接受。而且由RSA系统分发公钥的方式可以知道它适合大量用户的使用。解决了大量用户使用时密钥管理的难题。这是公钥密码系统相对于对称密码体系最突出的优点。
缺点：
(1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密．
(2)速度太慢，由于RSA的分组长度太大，为了保证安全性，n至少也要600bf以上，使运算代价很高，尤其是速度较慢，较对称算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式化的标准．目前，SET(Secure Electronic Trabsaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥．因为速度问题，目前人们广泛采用单、公钥结合使用的方法，优缺点互补：单钥密码加密速度快，人们用它来加密较长的文件，然后用RsA来给文件密钥加密，极好的解决了单钥的密钥分发问题．
4 对于RSA安全问题的思考
RSA在设置密钥时参数的选择也很讲究，前文在RSA简要分析时曾提到p和q之差要大。下面我将着重在p、q选取的问题上阐述我自己的一些想法。
在选择p、q时，如果p、q之差较小，则可由n=p*q估计出 ，则由 上式右边为小的平方数，可以试验给出p、q的值。如当n=164009,估计 ， 得出 。
我们知道攻击RSA的最大难点就是分解大素数的复杂与耗时，如果能找出一种能够减少计算量的算法，就会大大减小攻击所付出的代价。由上面的灵感我们不妨在p、q做文章。
1) 先求出 ，取整设为a。 ， 分别为p、q与a的差值。
2) 由： 得出：
3) 接下来可以由循环法找出x、y的值，并最终求出p、q检验直到符合为止。因为x、y的差值比p、q的差值小得多，因此可以大大较少计算量。
备注：由于作者能力有限，文中难免会有很多不足及论证不够充分的地方，望读者给予指导更正。
参考文献和网址
【1】 王育民，刘建伟 《通信网的安全》 西安电子科技大学出版社 2005年
【2】 Atul Kahate 《密码学与网络安全》 清华大学出版社 2005年
【3】 Niels Ferguson，Bruce Schneider 《密码学实践》 电子工业出版社 2005
【4】 杨义先，钮必忻 《应用密码学》 北京邮电出版社 2005年
【5】 谢朝海 《RSA攻击进展》 北京理工大学信息技术学院
