当前位置：首页 > 数据通信中的RSA加密算法的设计与实现毕业论文
第3章 数据加密中的RSA算法 目前企业面临的计算环境和过去有很大的变化，许多数据资源能够依靠网络来远程存取，而且越来越多的通讯依赖于公共网络公共网络（如 Internet），而这些环境并不保证实体间的安全通信，数据在传输过程可能被其它人读取或篡改。
加密将防止数据被查看或修改，并在原本不安全的信道上提供安全的通信信道，它达到以下目的：
保密性：防止用户的标识或数据被读取。 数据完整性：防止数据被更改。
身份验证：确保数据发自特定的一方。
3.1 RSA公钥密码体制概述
RSA公钥密码体制于1978年，由美国麻省理工学院Rivest,Shami:和Adleman二人提出的，至今为止仍被公认为是公钥密码体制中最优秀的加密算法，被认为是密码学发展史上的第二个里程碑.它是一种特殊的可逆摸指数运算的加密体制，其理论基础是数论中的一条重要论断:求两个大素数之积是容易的，而将一个具有大素数因子的合数进行分解却是非常困难的。除了用于加密之外，它还能用于数字签名和身份认证。RSA公钥密码体制过程描述如下:
(1)选取两个大素数p和q.
(2)计算n?pq（公开)，?(n)?pq?(p?q)?1欧拉函数)。
(3)随机选取正整数e, l?e??(n)，满足gcd(e,Φ(n))?1, e是公开的加密密钥。
(4)计算d，满足de?1(modΦ(n)). d是保密的解密密钥。 (5)加密变换:对明文c?Zn,明文为(Zn为明文空间)
c?memod n
(6)解密变换:对密文c?Zn,明文为m?cdmod n 可以证明，解密变换是加密变换的逆变换。 例:
(1)生成密钥:
*23?253; 选择两个互质的质数p?11, q?23, n?111) (q-1)?220取e?3 ; (p-由de (mod220)?1，得d=147;
所以，保密的解密密钥为d=147，公开的加密密钥公钥为e=3,n=253;明文空
??251, 252} 间为Zn?{0, 1, 2,(2)加密原文:
假设原文m的数字为16_5，用公钥加密原文。 C?1653 mod 253?110 (3)解码密文:
m?110147mod 253?165
A=C，由此可以看出RSA算法的一般过程。
3.2 RSA公钥密码体制安全性分析
RSA体制中，加密密钥e与大整数n是公开的，而解密密钥d与大素数p和q是保密的。虽然在RSA的加密与解密密钥建立后，p和q不再需要，但p和q也绝不能泄露。若n被分解，则也就不保密，e公开，d就可以计算出来，RSA便被破译。己知n，求得?(n)，则P和q可以求得。因为根据欧拉定理，
?(n)?pq?(p?q)?1，又有(p?q)2?(p?q)2?4pq据此列出方程:
??(n)?pq?(p?q)?1 ?22?(p?q)?(p?q)?4pq由以上方程组，可以求得p和q。因为p和q都是大素数，根据现在已知的结果，因子分解n是最好的算法，此时复杂性为:eln(n)lnln(n)
若n为200位于进制数，则用每秒107次运算的高速计算机，也要108年才能得到计算结果。可见，RSA的素数分解确实存在一定的难度。
为安全起见，对p和q要求:p和q的相差不大;(p-1)和(q-1)有大素数因子;gcd(p-l,q-1)很小，满足这样条件的素数称做安全素数。
RSA的出现使得大整数分解因式这一古老的问题再次被重视，近些年来出现的不少比较高级的因数分解方法使“安全素数”的概念也在不停的演化。所以，选择传统上认为是“安全素数”并不一定有效的增加安全性，比较保险的方法就是选择足够大的素数。因为数越大，对其分解因式的难度也就越大!对n和密钥长度的选择取决于用户保密的需要。密钥长度越大，安全性也就越高，但是相应的计算速度也就越慢。由于高速计算机的出现，以前认为己经很具安全性的512位密钥长度己经不再满足人们的需要。1997年，RSA组织公布当时密钥长度的标准:个人使用768位密钥，公司使用1024位密钥，而一些非常重要的机构使用2048位密钥。
3.3 RSA算法的缺点
RSA的缺点主要有：
A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。 B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。
3.4 本章小结
RSA算法在理论上的重大缺陷就是并不能证明分解因数绝对是困难的。RSA方法既可用于保密、也能用于签名和认证，许多流行的操作系统如微软、Apple, Sun和Novell都在其产品上融入了RSA。同时，RSA也被广泛应用于各种安全或认证领域，如web服务器和浏览器信息安全、Email的安全和认证、对远程登录的安全保证和各种电子信用卡系统的核心。硬件上，如安全电话、以太网卡和I智能卡也多采用RSA技术。而且几乎所有Internet安全协议如SMME, SSL不II SWAN都引入了RSA加密方法。IS09796标准把RSA列为一种兼容的加密算法，使得RSA的应用目前非常广泛。任何一种事物有出现、繁荣，也不可避免的会走向灭亡。在没有找到快速进行大整数分解因式方法的时候，RSA显示了不可比拟的优点。而当分解因式不再是难题的时候，RSA算法也就将失去存在的价值。
第4章 RSA数据加密中的实现 RSA算法,它是第一个既能用于数据加密也能用于数字签名的算法。它易于
理解和操作，也很流行。算法的名字就是发明者的名字：Ron Rivest, AdiShamir 和Leonard Adleman, 但RSA的安全性一直未能得到理论上的证明， RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题， RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。
RSA算法实现数据加密的主要步骤分为：
1、获取密钥，这里是产生密钥，实际应用中可以从各种存储介质上读取密钥。
2、加密。 3、解密。
4.1随机大素数的产生
公钥密码学需要大素数，因此，大素数的快速有效随机生成方法是公钥密码学中的一个重要问题，具有非常显著的实用价值。显然，通过对一个随机数进行因子分解，我们可以判断这个随机数是否为素数。如果这个随机数能被因子分解，则它不是素数，否则它一定是素数。但是，大素数的因子分解是一个复杂的问题，到现在还没有找到一个快速有效的算法来对大整数进行因子分解。因此，不能试图通过对随机数进行因子分解来生成大素数。正确的生成大素数的方法是对生成的随机数先测试它是否为
素数，而不是对它进行因子分解。这种素性测试比因子分解要容易得多，己经有许多素性测试方法能够确定一个随机数是否为素数。如果合数通过一个素性测试的概率足够小，则这个素性测试就是很可靠的。实际上，对于许多素性测试方法，合数通过测试的概率可以受到人为的控制，即是可以把合数通过测试的概率设定的足够小。
4.1.1素数的分布
要讨论素数的生成问题，首先要讨论素数的分布。素数的分布是极不均匀的，
素数越大，分布也就越稀疏。
首先，存在无穷多个素数。对此，我们可以证明。假设正整数中只有k个素数，设为p1 ,p2 ?pk。令n?p1p2?pk?1,则n>1。如果n是素数，则显然n与
p1 ,p2 ?pk都不相同，这与只有k个素数的假设相矛后。如果n不是素数，则n一定有一个素数
因子p?p?pi, i?1, 2, ?k，否则由于p|p1p2?pk以及p|n,所以p|1,这与p是素数相矛盾。故p与p1 ,p2 ?pk都不相同，这与只有k个素数的假设想矛盾。因
本文作者：...共分享92篇相关文档
