搜索
课程设计报告------------------RSA算法实现院（系）：专业：班级：学生：学号：指导教师：2012年10月10日目录1.RSA算法介绍与应用现………………………………….32.算法原理…………………………………………………..33.RSA算法数论基础………………………………………..43.1.单向和陷门单向函数………………………………………..43.2.同余及模运算………………………………………………..43.3.欧拉函数、欧拉定理和费尔马定理………………………..53.4.乘法逆元及其求法…………………………………………..5.4.RSA算法的各环节………………………………………..64.1.RSA公钥加密解密概述…………………………………….64.2.RSA签名算法………………………………………………64.3.大数运算处理………………………………………………..74.4.大素数的产生………………………………………………..85.RSA的安全性……………………………………………..86.代码实现：………………………………………………..107.RSA算法结果分析……………………………………….157.1.主界面初始化…………………………………………………157.2.设置密钥……………………………………………………..157.3.对明文加密……………………………………………………167.4.对密文解密……………………………………………………178.总结与展望………………………………………………..179.参考文献…………………………………………………181.RSA算法介绍与应用现状RSA公开密钥加密算法自20世纪70年代提出以来，已经得到了广泛认可和应用。发展至今，电子安全领域的各方面已经形成了较为完备的国际规范。RSA作为最重要的公开密钥算法，在各领域的应用数不胜数。RSA在硬件方面，以技术成熟的IC应用于各种消费类电子产品。RSA在软件方面的应用，主要集中在Internet上。加密连接、数字签名和数字证书的核心算法广泛使用RSA。日常应用中，有比较著名的工具包OpenSSL(SSL，SecuritySocketLayer,是一个安全传输协议，在Internet上进行数据保护和身份确认。OpenSSL是一个开放源代码的实现了SSL及相关加密技术的软件包，由加拿大的EricYang等发起编写的。OpenSSL应用RSA实现签名和密钥交换，已经在各种操作系统得到非常广泛的应用。另外，家喻户晓的IE浏览器，自然也实现了SSL协议，集成了使用RSA技术的加密功能，结合MD5和SHA1，主要用于数字证书和数字签名，对于习惯于使用网上购物和网上银行的用户来说，几乎天天都在使用RSA技术。RSA更出现在要求高度安全稳定的企业级商务应用中。在当今的企业级商务应用中，不得不提及使用最广泛的平台j2ee。事实上，在j2se的标准库中，就为安全和加密服务提供了两组API：JCA和JCE。JCA(JavaCryptographyArchitecture)提供基本的加密框架，如证书、数字签名、报文摘要和密钥对产生器；JCA由几个实现了基本的加密技术功能的类和接口组成，其中最主要的是java.security包，此软件包包含的是一组核心的类和接口，Java中数字签名的方法就集中在此软件包中。JCE(JavaCryptographyExtension)在JCA的基础上作了扩展，JCE也是由几个软件包组成，其中最主要的是javax.crypto包，此软件包提供了JCE加密技术操作API。javax.crypto中的Cipher类用于具体的加密和解密。在上述软件包的实现中，集成了应用RSA算法的各种数据加密规范(RSA算法应用规范介绍参见：=2146，这些API内部支持的算法不仅仅只有RSA，但是RSA是数字签名和证书中最常用的)，用户程序可以直接使用java标准库中提供的API进行数字签名和证书的各种操作。单机应用程序使用RSA加密尚比较少见，例如使用RSA加密任意一个文件。RSA算法可以简单叙述如下：密钥生成取素数p，q，令n=p×q.取与(p-1)×(q-1)互素的整数e，由方程d×e=1(mod(p-1)×(q-1))解出d，二元组(e,n)作为公开密钥，二元组(d,n)作为私有密钥．加密解密b=aemodn，c=bdmodn.2.算法原理1．选择两个不同的大素数p、q(目前两个数的长度都接近512bit是安全的）；2.计算n=p*q。3.计算n的欧拉函数t=(p-1)(q-1)。4.选择整数e作为公钥，使e与t互素，且1et。5.用欧几里得算法计算d作为私钥,使d*e=1modt。6.加密：C=M^emodn7.解密：M＝C^dmodn=(M^e)^dmodn=M^e^dmodn。3.RSA算法数论基础RSA算法的数学理论基础在密码学中需要使用到许多数学理论，例如数论、信息论、复杂度理论等，它们是设计密码系统及协议不可或缺的工具，其中数论是密码学中(尤其是公开密钥密码系统中)最重要的数学基础，因此有必要对有关数论理论做一介绍。下面介绍RSA算法的数学基础知识。3.1单向和陷门单向函数RSA的安全性主要取决于构造其加密算法的数学函数的求逆困难性，这同大多数公钥密码系统一样(譬如EIGamal算法就是基于离散对数问题的困难性)，我们称这样的函数为单向函数。单向函数不能直接用作密码体制，因为如果用单向函数对明文进行加密，即使是合法的接收者也不能还原出明文，因为单向函数的逆运算是困难的。与密码体制关系更为密切的陷门单向函数，即函数及其逆函数的计算都存在有效的算法，而且可以将计算函数的方法公开。单向和陷门单向函数的概念是公钥密码学的核心，它对公钥密码系统的构造非常重要，甚至可以说公钥密码体制的设计就是陷门单向函数的设计。定义2.1：令函数f是集合A到集合B的映射，以f：A→B表示。若对任意x1≠x2，x1,x2∈A，有f(x1)≠f(x2)，则称f为1一l映射，或可逆函数。定义2.2：一个可逆函数厂，若它满足：1．对所有X∈A，易于计算f(x)；2．对“几乎所有x∈A，由f(x)求x“极为困难”，以至于实际上不可能做到。则称f为单向函数(One-wayfunction)上述定义中的“极为困难”是对现有计算机能力和算法而言的，Massey称此为视在困难性，相应的函数称之为视在单向函数。以此来和本质上的困难性相区分。目前，还没有人能够从理论上证明单向函数是存在的。3.2同余及模运算同余：假定有三个整数a，b，n(n≠0)，当我们称a在模n时与b同余，是指当且仅当a与b的差为n的整数倍，即a-b=kn，其中k为任一整数。若a与b在模n中同余，我们可写为a≡b(modn)或nl(a-b)。剩余类(ResidueClass)：很明显地，利用同余概念，所有整数在模n中被分成n个不同的剩余类；为n所整除的数(即余数为0)为一剩余类，被n所除余数为1的数为另一剩余类，余2的数又为一剩余类，以此类推。完全剩余系(CompleteSetofResidues)：若将每一剩余类中取一数为代表，形成一个集合，则此集合称为模n的完全剩余系，以Zn表示。很明显地，集合(0，l，2，．．．，n-1}为模n的一完全剩余系。从0到n-1的整数组成的集合构成了模n的“完全剩余系”。这意味着，对每一个整数a，它的模n剩余是从0到n-1之间的某个整数。所谓运算amodn表示求a被n除的余数，成为模运算。既约剩余系(ReducedSetofResidues)：在模n的完全剩余系中，若将所有与n互素的剩余类形成一个集合，则称此集合为模n的既约剩余系，以Zn表示。例如n=10时，{0，1，2，3，4，5，6，7，8，9)为模10的完全剩余系；而{1，3，7，9)为模10的既约剩余系。3.3欧拉函数、欧拉定理和费尔马定理欧拉函数≯(n)：是一个定义在正整数上的函数，其值等于序列0，1，2，3，……n-1中与n互素的数的个数。即fn为模n既约剩余系中所有元素的个数。由定义知，当P是素数时，≯(p)=P-1。定理2．1欧拉定理：若m，a为正整数，有gcd(a，m)=l(gcd，GreatestCommonDivisor，最大公约数)，则a≯(m)(modm)。其中≯m称为欧拉函数，它是比m小但与m互素的正整数个数。欧拉定理也有一种等价形式：a≯(m)+1=a(modm)。定理2．2设P和q是两个不同的素数，n=p×q，则≯(n)=(p-1)×(q-1)，对任意的x∈Zn及任意的非负整数k，有xk≯(n)+1≡x(modn)。定理3费尔马定理：如果P是素数，且gcd(m,p)=l(可表示为(m,p)=1)，则mp-1≡l(modp)，费尔马定理还存在另一种等价形式：如果P是素数，m是任意正整数，则mp≡m(modp)。对于素数P来说，≯(p)=p-1，所以费尔马定理实际是欧拉定理的一个推论。费尔马定理和欧拉定理及其推论在构成了RSA算法的主要理论基础。3.4乘法逆元及其求法乘法逆元的定义：若ab≡l(modn)，则称b为a在模n的乘法逆元，b可表示为a-1。利用Euclid(欧几里德)算法(辗转相除法)求乘法逆元：己知a及n且(a,n)=1，求aa–l=1(modn)。欧几里德算法是古希腊数学家欧几里德给出的求两个自然数的最大公约数的方法，如果(a，n)=1，则b一定存在。首先介绍利用欧几里德算法求gcd(a，n)的方法，再介绍求乘法逆元的方法。令r0=n，rl=a，a≤n，利用辗转相除法可得r0=r1+g1+r20≤r2rlr1=r2g2+r30≤r3r2::rj-2=rj-lgj-1+rj0≤rjrj-1rm-3=rm-2gm-2+rm-10≤rm-1rm-2rm-2=rm-1gm-1+rm0≤rmrm-1rm-1=rmgm则rm为a及n的最大公因子。(欧几里德算法求gcd的主要概念在于：若c=dg+r，则(c，d)=(d，r)。因此在上述算法中，(a，n)=(r0，r1)=(rl，r2)=……=(r(m-1)，rm)=(rm，o)=rm。可以通过举例说明利用欧几里德算法求逆元的方法，如：求1001b=lmod3837，b是1001关于模3837的乘法逆元。因为(1001，3837)=l，而3837=3×1001+8341001=1×834+167834=4×167+166167=1×166+1所以l=167—166=167--(834--4×167)=5×167—834=5×(1001—834)一834=5×1001--6×834=5×1001--6×(3837—3×1001)=23×1001--6×3837因此23×1001≡l(mod3837)，故1001关于模3837的乘法逆元为23。一般求乘法逆元以欧几里德算法为佳。4.RSA算法的各环节RSA算法是1978年由R.L.Rivest，A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制。RSA的理论基础是数论中的欧拉定理,它的的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。4.1RSA公钥加密解密概述RSA算法采用下述加密/解密变换。1．密钥的产生①选择两个保密的大素数P和q。②计算N=pq，≯(N)=(p-1)(g-1)，其中≯(N)是N的欧拉函数值。③选择一个整数e，满足le≯(N)，且gcd(≯(N)，e)≡1。④计算私钥d(解密密钥)，满足ed≡l(mod≯(N))，d是e在模≯(N)下的乘法逆元。⑤以(e,n)为公钥，(d,N)为密钥，销毁p，q，≯(N)。2．加密加密时首先将明文比特串进行分组，使得每个分组对应得串在数值上小于N，即分组的二进制长度小于l092N。然后，对每个明文分组M，作加密运算：C