毕业设计（论文）基于RSA的加密解密系统的设计与实现.doc

《毕业设计（论文）基于RSA的加密解密系统的设计与实现.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）基于RSA的加密解密系统的设计与实现.doc（31页珍藏版）》请在三一办公上搜索。

1、武汉工程大学邮电与信息工程学院毕业设计（论文）基于RSA的加密解密系统的设计与实现Based on RSA encryption and decryption system design and implementation学生姓名 学 号 专业班级 网络工程0701指导教师 2011年5月作者声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果，除了文中特别加以标注的地方外，没有任何剽窃、抄袭、造假等违反学术道德、学术规范的行为，也没有侵犯任何其他人或组织的科研成果及专利。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如本毕业设计（论文

2、）引起的法律结果完全由本人承担。毕业设计（论文）成果归武汉工程大学邮电与信息工程学院所有。特此声明。 作者专业： 作者学号： 作者签名： _年_月_日摘 要随着电子计算机的飞速发展，全球网络普遍化。人们的工作、生活、学习都离不开网络。然而在网络的互相交流、保证个人的安全、隐私非常的重要。本论文阐述了密码在网络生活中的重要作用。密码技术是保护信息安全的主要手段之一。它不仅具有保证信息机密性的信息加密功能，而且具有数字签名、身份验证、秘密分存、系统安全等功能。因此，使用密码技术不仅可以保证信息的机密性，而且可以保证信息的完整性和确定性，防止信息被篡改、伪造和假冒。RSA公钥密码算法是迄今为止在理论

3、上最为成熟、完善的公钥密码体制。 从提出到现在已经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。它是第一个既能用于数据加密也能用于数字签名和密钥分配与管理的算法。它易于理解和操作，也很流行。关键词：RSA 加密 解密 公钥AbstractAlong with the rapid development of computer, and a global network generalization. Peoples work, life and study is inseparable from the network. However, in the mutual

4、exchanges and communication network. Ensure personal security, privacy is very important. This paper expounds the password on the network to the important role of life. Password protect information security technology is one of the main means. It has not only ensuring information confidential inform

5、ation encryption functions, and with digital signatures, identity authentication, secret points to save, system security, and other functions. Therefore, using cipher technology can not only ensure the confidentiality of information, but also can ensure the completeness and uncertainty of informatio

6、n, prevent information tampered, forge and hypocrisy. RSA public-key cryptosystem is by far the most mature in theory, perfect public key cryptosystems. Now from pose to the test of experience various attacks for people to accept, gradually, generally, is now one of the most outstanding public-key s

7、cheme. It is the first can used for data encryption could also be used for digital signatures and key distribution and management of the algorithm. It is easy to understand and operation, is also very popular. Key Words： rsa ; encryption; decryption; Public key目 录第1章 RSA简绍21.1 什么是RSA21.2 RSA的速度31.3

8、加密算法的缺点31.4 RSA算法描述4第2章 RSA加密解密体质简介52.1 公钥密码算法52.2 RSA体质算法过程62.3 RSA体质的实现62.4 RSA的安全性72.5 RSA算法中的数字签名82.6 明文加密及密文解密8第3章 RSA算法介绍和需求分析93.1公钥加密算法RSA93.2 RSA算法介绍113.3 RSA算法需求分析123.4 RSA算法特点143.5 RSA的选择密文攻击153.6 RSA的公共模数攻击15第4章 RSA算法代码及运行结果174.1 RSA算法代码174.2 RSA算法结果分析24第5章 总结与展望25参考文献26致谢27第1章 RSA简绍一个公开环

9、境下的信息加密，在加密算法是公开的情况下，唯一能保证信息加密的是密钥。在常规的对称加密算法中，如DES，加密解密密钥是相同的，如信息的发送者和合法接收者使用相同的密钥，意味前提条件为信息发送者和合法接收者互相认识或者互相信任，而且意味着密钥将分布在通信的的每一个节点，由此带来了密钥管理问题。如果泄露了密钥意味着公开了所有密钥。如果是加密密钥和解密密钥不相同，我们可以把加密密钥公开作为公钥，信息合法的接收者保管解密密钥作为私钥，则以上提到的问题可以解决。公钥密码体制于1976年由W.Diffie和M.Hellman提出，同时，R.Merkle也独立提出了这一体制。这种密码体制采用了一对密钥加密密

10、钥和解密密钥（且从解密密钥推出加密密钥是不可行的），这一对密钥中，一个可以公开（称之为公钥），另一个为用户专用（私钥）。RSA算法是目前应用最广的公钥密码，有Rivest，Shamir和Adleman在1977年提出，它基于一个非常简单的数论难题，很容易将两个素数相乘，但分解该乘积却十分艰难，从而，该乘积可以公开且可作为加密密钥。不能从该乘积恢复出这俩个素数。解密密钥需要用到这两个素数。从而用很简单的形式实现了非常可靠的密码系统。1.1 RSA算法简介RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考

11、验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。1.2 RSA的速度由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右。1.3 加密算法的缺点（1）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。（2）RSA的安全性依赖于大数的

12、因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构： 这个固有的问题来自于公钥密码系统的最有用的特征每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way Hash Function对文档作HASH处理，或同时使用不同的签名算法。除了利用公共模数，人们还尝试一些利用解密指数或

13、等等攻击.（3）速度太慢,由于RSA 的分组长度太大，为保证安全性，n 至少也要 600 bitx以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。为了速度问题,目前人们广泛使用单,公钥密码结合使用的方法,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然后用RSA来给文件密钥加密,极好的解决了单钥密码的密钥分发问题。1.4 RSA算法描述RSA的安全性依赖

14、于大数分解。公钥和私钥都是两个大素数（ 大于 100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 1.1密钥的生成(1)选择两个大素数， 和。计算： 和欧拉函数值： (2)随机取一整数,且和互素。此时求的满足： 则 （3）将和作为公开密钥，作为私人密钥。 其中，, , ,和都是私密的陷门（四项并不是相互独立的），这些信息是不可以泄漏的。1.2加密（1）获得信息接收者的公开密钥（2）将明文分组：, , ,使得每个, ,1,2，（3）对每一组明文组用以下公式变换 e（4）得到密文,，1.3解密（1）对每一组密文做解密变换 d（2）合并分组得到明文，,，第2

15、章 RSA加密解密体质简介RSA 公钥密码算法是迄今为止在理论上最为成熟、完善的公钥密码体制。 从提出到现在已经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。它是第一个既能用于数据加密也能用于数字签名和密钥分配与管理的算法。它易于理解和操作，也很流行。因为它既可用于加密,又可用于签名,并为用户的公开密钥签发公钥证书、发放证书、管理证书等,提高了服务质量，所以, RSA 公开密钥密码在当今的信息交换过程中已得到广泛的应用和实践，RSA 公钥密码体制在世界许多地方已经成为事实上的标准。2.1 公钥密码算法公钥密码算法最主要的特点是加密和解密使用不同的密钥，且加密密钥能公开

16、，而仅需保守解密密钥的机密的密码算法。在这种加密算法中，从公开的加密密钥无法推导出保密的解密密钥，也无法从加密密钥和密文恢复出相应的明文。最有影响的公钥密码算法是RSA，它能抵抗到目前为止己知的所有密码攻击。RSA算法是第一个既能用于数据加密也能用于数字签名的算法，算法的名字以发明者的名字命名。RSA算法的安全性依赖于大数分解问题的难解性。算法中使用的公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。RSA算法在ISAKMP/Oakley框架中被用做一种可能的身份认证方式。Diffie-Hellman密钥交换算法是ISAK

17、MPIOakley框架的一个关键组成部分。在一个密钥协商会话的开始阶段通信参与方通过使用Diffe-Hellman算法产生双方共享的密钥，这些密钥将被用于密钥协商协议的后续步骤。在实际应用中，人们通常将对称密钥算法和公钥密码算法结合在一起使用，以实现最佳性能。即使用某个对称密钥密码体制来加密需传递的机要信息，而同时使用RSA等非对称密钥密码体制来传送DES的密钥。这样就可以综合发挥两种密码体制的优势，即DES高速简便性和RSA密钥管理的方便和安全性。2.2 RSA体质算法过程RSA密码体制使用了模的非负最小完全剩余系中的运算，这里n是两个不同的素数和的乘积。RSA体制的算法过程如下： 首先产生

18、密钥，过程如下： （1）随机产生两个长度为位的素数和。 （2）计算公钥；（是位的长度）。 （3）随机产生一个加密密钥，2=keyE=（n）-1，其中GCD（keyE，（n）=1。 注意这是保证解密密钥keyEkeyD mod()(n)=1有解的充要条件，（n）称为n的欧拉函数，值为：（n）=（P-1）*（Q-1）。 （4）求解解密密钥keyD=keyE-1 mod （n） ，keyE-1为解密密钥keyD的逆元 ，此公式原方程为（keyEkeyD mod(n)=1）。 由此公钥，加密密钥和解密密钥全部产生。 其次，对明文加密或对密文进行解密，过程如下： （1）加密： C = MkeyE mod

19、 publicKey；其中M表示明文，C表示密文。 （2）解密： M = CkeyD mod publicKey； 其中M表示明文，C表示密文。2.3 RSA体质的实现RSA密码体制的实现是一个比较复杂的过程，它涉及到素数的产生、大整数模运算等数学运算。RSA体制中，p、q均为大的素数，如何有效地产生大素数将是实现RSA体制所需解决的第一个问题。 通常情况下，人们使用一种概率算法来产生大素数。这是因为p、q都是大素数，如果使用因子分解的办法来求素数p、q，这样的难度与对RSA进行攻击（既分解大合数）实际上是相同的，在计算机是可行的。 概率算法的工作过程一般并不着眼于产生素数，而是首先随机地产生

20、一个大奇数，然后使用概率性算法判定该奇数是否为素数（这样的过程一般称为素性检测）。2.4 RSA的安全性RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。若n被因式分解成功，则RSA便被攻破。还不能证明对RSA攻击的难度和分解n的难度相当，但也没有比因式分解n更好的攻击方法。已知n，求

21、得F(n)（n的欧拉函数），则p和q可以求得。因为根据欧拉定理，F(n) = (p-1)(q-1) = pq (p + q) + 1。和(p q )2 = (p + q)2 4pq；据此列出方程，求得p和q。另一个攻击RSA的方法是根据C ae mod n 来计算C1/e mod n。这种攻击方式没有一种普遍的实现方法，也不知道是否其难度与对n因式分解相当。但是在一些特殊的情况下，当多个相关的信息用同样的密钥加密时，可能很容易被攻破。当然也有其他一些方法，不是面向完全攻破RSA，而只是希望得到一部分信息或者针对RSA的实现用非一般性的手段来攻击即使买通某些人得到保密密钥也是一种方法！为安全起见

22、，对p和q要求：p和q的相差不大；(p-1)和(q-1)有大素数因子；gcd(p-1,q-1)很小，满足这样条件的素数称做安全素数。RSA的出现使得大整数分解因式这一古老的问题再次被重视，近些年来出现的不少比较高级的因数分解方法使“安全素数”的概念也在不停的演化。所以，选择传统上认为是“安全素数”并不一定有效的增加安全性，比较保险的方法就是选择足够大的素数。因为数越大，对其分解因式的难度也就越大！对n和密钥长度的选择取决于用户保密的需要。密钥长度越大，安全性也就越高，但是相应的计算速度也就越慢。由于高速计算机的出现，以前认为已经很具安全性的512位密钥长度已经不再满足人们的需要。1997年，R

23、SA组织公布当时密钥长度的标准：个人使用768位密钥，公司使用1024位密钥，而一些非常重要的机构使用2048位密钥。当时的人们预计到个人使用的768位密钥将在两年后就会生存期满，那么也就是指今年！所以密钥长度的选取也要考虑到这个长度不再具效力的预计时间。RSA的安全性并不能仅靠密钥的长度来保证。在RSA算法中，还有一种值得注意的现象，那就是存在一些n = pq，使得待加密消息经过若干次RSA变换后就会恢复成原文。这不能不说是RSA本身具有的一个缺点，选择密钥时必须注意避免这种数。2.5 RSA算法中的数字签名 RSA既可以用来加密数据，也可以用于身份认证。和Hash签名相比，在公钥系统中，由

24、于生成签名的密钥只存储于用户的计算机中，安全系数大一些。RSA算法中数字签名技术实际上是通过一个哈希函数来实现的。数字签名的特点是它代表了文件的特征，文件如果发生改变，数字签名的值也将发生变化。不同的文件将得到不同的数字签名。一个最简单的哈希函数是把文件的二进制码累加，取最后的若干位。哈希函数对发送数据的双方都是公开的。2.6 明文加密及密文解密（1）明文加密用户加密密钥(3,33)将数字化明文分组信息加密成密文。由CMe (mod n)得：因此，得到相应的密文信息为：11，26，16。（2）密文解密用户B收到密文，若将其解密，只需要计算MCd (mod n)，即：用户B得到明文信息为：11，

25、05，25。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“key”。 第3章 RSA算法介绍和需求分析3.1公钥加密算法RSA传统的加密技术都是秘密密钥加密技术，也称单密钥加密技术。也就是说，消息发送者使用一把密钥将消息加密，而消息接收者须使用同一密钥将其解密。比如数据加密标准DES。这就产生了一个重要的密钥管理问题，如何告诉对方这个密钥。除非是在耳边小声告诉或者寄一封挂号信，如果在网路上传输，无论如何也不能保证这个宝贵的密钥不被一直肆机的敌人截获。这是一件很麻烦，有时甚至是做不到的事，特别是，如果你想和许许多多你根本不认识的人实现秘密通讯，用这种秘密密钥加密技术就根本不可能。公开

26、密钥加密技术解决了这个难题。在公开密钥加密技术中，加密密钥与解密密钥是不一样的。加密者可以将加密密钥公开，成为公开密钥，而仍将解密密钥保密，作为秘密密钥。任何人如果想向其发送加密消息，都可以找到公开密钥，然而，以其加密的消息却必须用加密者自己保留的秘密密钥才能解密，别人只知道公开密钥，因而无法阅读该消息。如果想向另一个人发送加密消息，则可以先去找他的公开密钥（既然是公开的，因而往往不用与他本人作事先联系，甚至不必认识他），然后用此密钥加密我想发送的消息给他，除了他本人之外，别人是无法阅读这个消息的。下面就要描述RSA加密算法的流程了：首先, 找出三个数： p、 q、 r，其中 p和q是两个相异

27、的质数， r 是与 (p-1)(q-1) 互质的数。接著, 找出 e, 使得 re 1 mod (p-1)(q-1)。这个 e 一定存在, 因为 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到了。 再来, 计算 n = pq。（n，e）便是 public key。（n，r）就是private key。 p和q应该被销毁掉（PGP为了用中国的同余理论加快加密运算保留了p和q， 不过它们是用IDEA加密过再存放的） 加密的过程是, 若待加密信息为 a, 将其看成是一个大整数, 假设 a = n 的话, 就将 a 表成 s 进位 (s = n, 通常取 s = 2t)，则每一位数均小于

28、 n，然後分段编码。接下来, 计算 C ae mod n, (0 = C n)。b 就是编码后的信息。解码的过程是, 计算 M br mod C (0 = c pq)，可以证明 M 和 a 其实是相等的。也就是需要得到的没有加密的信息。如果第三者进行窃听时, 他会得到几个数: m，n(=pq)，b。他如果要解码的话, 必须想办法得到 r。所以, 他必须先对 n 作质因数分解。如果他能够成功的分解n，得到这两个质数p和q，那么就表明此算法被攻破。RSA算法是利用了数学中存在的一种单向性。一般说来，许多数学中的函数都有“单向性”，这就是说，有许多运算本身并不难，但如果你想把它倒回去，作逆运算，那就

29、难了。最简单的例子：除法比乘法难，开方比乘方难，这是谁都知道的。对于RSA来说，用公开密钥加密后，如果想再通过公开密钥解密是很困难的。这个困难性就表现在对n的因式分解上。若n=pq被因式分解，（p-1）（q-1）就可以算出，继而算出解密密钥m。所以RSA算法的基础就是一个假设：对n的因式分解是很困难的。RSA算法在理论上的重大缺陷就是并不能证明分解因数绝对是如此之困难，也许我们日后可以找到一种能够快速分解大数的因数的算法，从而使RSA算法失效。如果有人偶然发现了快速将大数分解因数的方法，并将其保密，则他有可能在一段时间内获得极为巨大的力量。目前RSA被广泛应用于各种安全或认证领域，如web服务

30、器和浏览器信息安全、Email的安全和认证、对远程登录的安全保证和各种电子信用卡系统的核心。与单钥加密方法比较，RSA的缺点就是运算较慢。用RSA方法加密、解密、签名和认证都是一系列求模幂运算组成的。在实际应用中，经常选择一个较小的公钥或者一个组织使用同一个公钥，而组织中不同的人使用不同的n。这些措施使得加密快于解密而认证快于签名。一些快速的算法比如基于快速傅立叶变换的方法可以有效减少计算步骤，但是在实际中这些算法由于太复杂而不能广泛的使用，而且对于一些典型的密钥长度它们可能会更慢。3.2 RSA算法介绍RSA算法可以简单叙述如下：取素数p，q，令n=pq.取与(p-1)(q-1)互素的整数e

31、，由方程de=1 (mod (p-1)(q-1)解出d，二元组(e,n)作为公开密钥，二元组(d,n)作为私有密钥b=ae mod n，c=bd mod n.附录中给出了证明a=c (mod n).RSA公开密钥加密算法自20世纪70年代提出以来，已经得到了广泛认可和应用。发展至今，电子安全领域的各方面已经形成了较为完备的国际规范。RSA作为最重要的公开密钥算法，在各领域的应用数不胜数。RSA在硬件方面，以技术成熟的IC应用于各种消费类电子产品。RSA在软件方面的应用，主要集中在Internet上。加密连接、数字签名和数字证书的核心算法广泛使用RSA。日常应用中，有比较著名的工具包Open S

32、SL(SSL，Security Socket Layer,是一个安全传输协议，在Internet上进行数据保护和身份确认。Open SSL是一个开放源代码的实现了SSL及相关加密技术的软件包，由加拿大的Eric Yang等发起编写的。Open SSL应用RSA实现签名和密钥交换，已经在各种操作系统得到非常广泛的应用。另外，家喻户晓的IE浏览器，自然也实现了SSL协议，集成了使用RSA技术的加密功能，结合MD5和SHA1，主要用于数字证书和数字签名，对于习惯于使用网上购物和网上银行的用户来说，几乎天天都在使用RSA技术。RSA更出现在要求高度安全稳定的企业级商务应用中。在当今的企业级商务应用中，

33、不得不提及使用最广泛的平台j2ee。事实上，在j2se的标准库中，就为安全和加密服务提供了两组API：JCA和JCE。 JCA (Java Cryptography Architecture)提供基本的加密框架，如证书、数字签名、报文摘要和密钥对产生器； JCA由几个实现了基本的加密技术功能的类和接口组成，其中最主要的是java.security包，此软件包包含的是一组核心的类和接口，Java中数字签名的方法就集中在此软件包中。JCE(Java Cryptography Extension) 在JCA的基础上作了扩展，JCE也是由几个软件包组成，其中最主要的是javax.crypto包，此软件

34、包提供了JCE加密技术操作API。javax.crypto中的Cipher类用于具体的加密和解密。在上述软件包的实现中，集成了应用RSA算法的各种数据加密规范，这些API内部支持的算法不仅仅只有RSA，但是RSA是数字签名和证书中最常用的)，用户程序可以直接使用java标准库中提供的API进行数字签名和证书的各种操作。3.3 RSA算法需求分析实现RSA算法需要涉及以下几个方面的问题（1）挑选加密用的素数（2）如何提高机密算法的速度（3）加秘幂次e,解密幂次d的选取注：设a1、a2是两个整数，d是a1、a2的 最大公约数，记作d=(a1,a2)进行因式分解很困难，但是判定一个数是否是素数则简单

35、很多，所以试图分解随机数是不可取的，正确的做法是对产生的随机数测试是否为素数。测试的原理是Fermat小定理，对于一个待测试的奇数p，如果对于任意的小于p的w,应该有(w,p)=1，并且满足:wm-11(mod p)如果找到这个w，可以看成是p是素数的一个证据，如果p和w关系不满足Fermat小定理，则立刻知道p不是素数，找到一个证据可以认为p是素数的几率只有 50%，我们找到的证据越多，p是素数的证据越充分，由此可以认为找到k个证据，p不是素数的几率只有2-k。实际上还有一个例外，Carmichael数是所有小于它的数都可以是他的素数的证据，即满足Fermat小定理的形式，但Carmicha

36、el数是奇合数，但Carmichael满足一定条件，一个Carmichael数总是没有平方因子，而且当且仅当所有p是可整除m的素数，而p-1也可整除m-1时，一个没有平方因子的奇合数m是一个Carmichael数。所以按照这个条件排除Carmichael数。实际的做法是：（1）产生一个n为的随机数p；（2）设高位和低位为1，这样确保p有n位且为奇数；（3）检查确保p不能被任何小素数整除:如3,5,7，11等，可以用算法测试p对小于256或者2000的所有素数的整除性；（4）对某随机数wp运行如下测试，如果测试通过则另选一个a，做五次。测试方法如下：假定p是一个待测的奇数，设2s是可以整除p-1

37、的2的最高次幂，即p-1=2srStep1:选择一个数w，其中1w1则可以判定p不是素数；Step2:如果wr1(mod p)或wr-1(mod p)，则p可能是素数；Step3：s=1；Step4:如果ss，则w(2s)r)-1(mod p)，则p可能是素数，w(2sr)1(mod p)，则可能不是素数，否则s=s+1,重复step4：Step5：这时s=s，如果w(2sr)1(mod p),则p可能是素数。如果失败，则可以表明p不是素数，如果通过3、4测试们不是素数的几率就很低了。 RSA算法的加解密过程其实是一个幂运算和模运算相结合的过程，如果计算CMe(mod n)先计算Me,再计算M

38、e(mod n)，米的运算量非常巨大，而且保存Me也需要很大的存储空间，不失一般性地我们假设M,e,均为256位，我们将我们需要的log2（Me）=e*log2(M)=2264位来保存中间结果，可见采用直接的模幂运算是不可行的。加解密运算中的幂模运算我们可以乘法运算和求模运算实现，由于模运算对加法乘法运算可分配，即：(a+b)mod n=(a mod n)+(b mod n)(a*b)mod n=(a mod n)*(b mod n)所以可以对幂运算中和加法运算中的中间结果直接使用模运算，降低运算强度，可以说，这是我们进行简化的基础。加密幂次e和解密幂次d的选取根据第一部分RSA算法的描述，e

39、和d是相关的，其中的一个确定了，就可以确定另外一个，从安全的角度而言，e和d都应该大一些，否则如果e,d选取不当，会导致一定的安全问题。但e和d的选取在一定程度上也会影响到加密的速度。3.4 RSA算法特点RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问

40、题。 RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。 这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Ad

41、iShamir 和Leonard Adleman。 RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。 RSA的算法涉及三个参数，n、e1、e2。 其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。 e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod(p-1)*(q-1)=1。 (n及e1),(n及e2)就是密钥对。 RSA加解密的算法完全相同,设A为明文，B为密文，则：A=Be1 mod n；B=Ae2 mod n； e1和e2可以

42、互换使用，即： A=Be2 mod n；B=Ae1 mod n3.5 RSA的选择密文攻击RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：( XM )d = Xd *Md mod n 前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征-每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对

43、陌生人送来的随机文档签名，签名时首先使用 One-Way HashFunction 对文档作HASH处理，或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。3.6 RSA的公共模数攻击若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：C1 = Pe1 mod nC2 = Pe2 mod n密码分析者知道n、e1、e2、C1和C2，就能得到P。因为e1和e2互质，故用Euclidean算法能找到r和s，满足：r *

44、e1 + s * e2 = 1假设r为负数，需再用Euclidean算法计算C1(-1)，则( C1(-1) )(-r) * C2s = P mod n 另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e和 d，而无需分解模数。解决办法只有一个，那就是不要共享模数n。 RSA的小指数攻击。 有一种提高 RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被

45、研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。 RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准

46、化。目前，SET( Secure Electronic Transaction )协议中要求CA采用比特长的密钥，其他实体使用比特的密钥。 第4章 RSA算法代码及运行结果4.1 RSA算法代码#include #include #include typedef int Elemtype;Elemtype p,q,e;Elemtype fn;Elemtype m,c;int flag = 0;typedef void (*Msghandler) (void);struct MsgMap char ch;Msghandler handler;/* 公钥 */struct PU Elemtype e;Elemtype n; pu;/* 私钥 */struct PR Elemtype d;Elemtype n; pr;/* 判定一个数是否为素数