RSA算法的C实现课程设计报告.doc

课程设计报告-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。日常应用中，有比较著名的工具包Open SSL(SSL，Security Socket Layer,是一个安全传输协议，在Internet上进行数据保护和身份确认。Open SSL是一个开放源代码的实现了SSL及相关加密技术的软件包，由加拿大的Eric Yang等发起编写的。Open SSL应用RSA实现签名和密钥交换，已经在各种操作系统得到非常广泛的应用。另外，家喻户晓的IE浏览器，自然也实现了SSL协议，集成了使用RSA技术的加密功能，结合MD5和SHA1，主要用于数字证书和数字签名，对于习惯于使用网上购物和网上银行的用户来说，几乎天天都在使用RSA技术。RSA更出现在要求高度安全稳定的企业级商务应用中。在当今的企业级商务应用中，不得不提及使用最广泛的平台j2ee。事实上，在j2se的标准库中，就为安全和加密服务提供了两组API：JCA和JCE。 JCA (Java Cryptography Architecture)提供基本的加密框架，如证书、数字签名、报文摘要和密钥对产生器； JCA由几个实现了基本的加密技术功能的类和接口组成，其中最主要的是java.security包，此软件包包含的是一组核心的类和接口，Java中数字签名的方法就集中在此软件包中。JCE(Java Cryptography Extension) 在JCA的基础上作了扩展，JCE也是由几个软件包组成，其中最主要的是javax.crypto包，此软件包提供了JCE加密技术操作API。javax.crypto中的Cipher类用于具体的加密和解密。在上述软件包的实现中，集成了应用RSA算法的各种数据加密规范(RSA算法应用规范介绍参见： /rsalabs/node.asp?id=2146 ，这些API内部支持的算法不仅仅只有RSA，但是RSA是数字签名和证书中最常用的)，用户程序可以直接使用java标准库中提供的API进行数字签名和证书的各种操作。单机应用程序使用RSA加密尚比较少见，例如使用RSA加密任意一个文件。RSA算法可以简单叙述如下：取素数p，q，令n=pq.取与(p-1)(q-1)互素的整数e，由方程de=1 (mod (p-1)(q-1)解出d，二元组(e,n)作为公开密钥，二元组(d,n)作为私有密钥b=ae mod n，c=bd mod n.2.算法原理1选择两个不同的大素数p、q (目前两个数的长度都接近512bit是安全的）；2. 计算n = p*q。 3. 计算n的欧拉函数 t=(p-1)(q-1)。4. 选择整数e作为公钥，使e与t互素，且1e t。5. 用欧几里得算法计算d作为私钥,使d*e=1 mod t。6. 加密：C=Me mod n7. 解密：MCd mod n=(Me)d mod n= Med mod n。3.RSA算法数论基础RSA算法的数学理论基础在密码学中需要使用到许多数学理论，例如数论、信息论、复杂度理论等， 它们是设计密码系统及协议不可或缺的工具，其中数论是密码学中(尤其是公开密钥密码系统中)最重要的数学基础，因此有必要对有关数论理论做一介绍。下面介绍RSA算法的数学基础知识。3.1单向和陷门单向函数RSA的安全性主要取决于构造其加密算法的数学函数的求逆困难性，这同大多数公钥密码系统一样(譬如EIGamal算法就是基于离散对数问题的困难性)，我们称这样的函数为单向函数。单向函数不能直接用作密码体制，因为如果用单向函数对明文进行加密，即使是合法的接收者也不能还原出明文，因为单向函数的逆运算是困难的。与密码体制关系更为密切的陷门单向函数，即函数及其逆函数的计算都存在有效的算法，而且可以将计算函数的方法公开。单向和陷门单向函数的概念是公钥密码学的核心，它对公钥密码系统的构造非常重要，甚至可以说公钥密码体制的设计就是陷门单向函数的设计。定义2. 1：令函数f是集合A到集合B的映射，以f：AB表示。若对任意x1x2，x1,x2A，有f(x1)f(x2)，则称f为1一l映射，或可逆函数。定义2. 2：一个可逆函数厂，若它满足： 1对所有XA，易于计算f(x)； 2对“几乎所有xA，由f(x)求x“极为困难”，以至于实际上不可能做到。则称f为单向函数 (One-way function) 上述定义中的“极为困难”是对现有计算机能力和算法而言的，Massey称此为视在困难性，相应的函数称之为视在单向函数。以此来和本质上的困难性相区分。目前，还没有人能够从理论上证明单向函数是存在的。3.2同余及模运算同余：假定有三个整数a，b，n(n0)，当我们称a在模n时与b同余，是指当且仅当a与b的差为n的整数倍，即a-b=kn，其中k为任一整数。若a与b在模n中同余， 我们可写为a b(mod n)或n l(a-b)。剩余类(Residue Class)：很明显地，利用同余概念，所有整数在模n中被分成n个不同的剩余类；为n所整除的数(即余数为0)为一剩余类，被n所除余数为1的数为另一剩余类，余2的数又为一剩余类，以此类推。完全剩余系(Complete Set of Residues)：若将每一剩余类中取一数为代表，形成一个集合，则此集合称为模n的完全剩余系，以Zn表示。很明显地，集合(0，l， 2，n-1为模n的一完全剩余系。从0到n-1的整数组成的集合构成了模n的“完全剩余系”。这意味着，对每一个整数a，它的模n剩余是从0到n-1之间的某个整数。所谓运算a mod n表示求a被n除的余数，成为模运算。既约剩余系(Reduced Set of Residues)：在模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。定理21欧拉定理：若m，a为正整数，有g c d(a，m)=l(g c d，Greatest Common Divisor，最大公约数)，则a(m) (mod m)。其中m称为欧拉函数，它是比m小但与m互素的正整数个数。欧拉定理也有一种等价形式：a(m)+1 =a(mod m)。 定理22设P和q是两个不同的素数，n=pq，则(n)=(p-1)(q-1)，对任意的xZn及任意的非负整数k，有x k(n)+1x (mod n)。定理3费尔马定理：如果P是素数，且g c d(m ,p)=l(可表示为(m , p)=1)， 则mp-1l(mod p)，费尔马定理还存在另一种等价形式：如果P是素数，m是任意正整数，则mpm(mod p)。对于素数P来说， (p)=p-1，所以费尔马定理实际是欧拉定理的一个推论。费尔马定理和欧拉定理及其推论在构成了RSA算法的主要理论基础。3.4乘法逆元及其求法乘法逆元的定义：若a bl(mod n)，则称b为a在模n的乘法逆元，b可表示为a-1。利用Euclid(欧几里德)算法(辗转相除法)求乘法逆元：己知a及n且(a ,n) =1，求a a l=1(mod n)。欧几里德算法是古希腊数学家欧几里德给出的求两个自然数的最大公约数的方法，如果(a，n)=1，则b一定存在。首先介绍利用欧几里德算法求g c d(a，n)的方法，再介绍求乘法逆元的方法。令r0=n，r l=a，an，利用辗转相除法可得r0=r1+g1+r2 0r2 r l r1=r2g2+r3 0r3r 2 : :rj-2=r j-l g j-1+rj 0r jr j-1 rm-3=rm-2 gm-2+rm-1 0rm-1rm-2 rm-2=rm-1 gm-1+rm 0r mrm-1 rm-1= r m gm 则r m为a及n的最大公因子。(欧几里德算法求g c d的主要概念在于：若c=d g + r， 则(c，d)=(d，r)。因此在上述算法中，(a，n)=(r0，r1) =(r l，r2)= (r(m-1)，r m)=(r m，o)=r m。可以通过举例说明利用欧几里德算法求逆元的方法，如：求1001b=lmod 3837， b是1001关于模3837的乘法逆元。因为(1001，3837)=l，而3837=31001+834 1001=1834+1 67 834=4167+166 167=1 166+1所以l=167166=167-(834-4167)=5167834 =5(1001834)一834 =51001-6834 =51001-6(383731001) =23 1001-63837 因此231001l(mod 3837)，故1001关于模3837的乘法逆元为23。一般求乘法逆元以欧几里德算法为佳。4.RSA算法的各环节RSA算法是1978年由R.L.Rivest，A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制。RSA的理论基础是数论中的欧拉定理,它的的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。4.1 RSA公钥加密解密概述RSA算法采用下述加密/解密变换。1密钥的产生选择两个保密的大素数P和q。计算N=p q，(N) =(p-1)(g-1)，其中(N)是N的欧拉函数值。选择一个整数e，满足le(N)，且g c d(N)，e)1。计算私钥d(解密密钥)，满足e dl(mod(N)，d是e在模(N)下的乘法逆元。 以(e, n)为公钥，(d ,N)为密钥，销毁p，q，(N)。2加密加密时首先将明文比特串进行分组，使得每个分组对应得串在数值上小于N， 即分组的二进制长度小于l092N。然后，对每个明文分组M，作加密运算： C=E k(M)=M e mod N 3解密对密文分组的解密运算为：M=D k (C) =C d mod N 由定理1和定理2可以证明解密运算能恢复明文M 4.2 RSA签名算法并非所有的公开密钥系统，均可同时达到秘密性与数字签名功能。一般而言， 一公开密钥系统若作为密码系统，则无法作为数字签名，反之亦然。只有很少数的系统可同时作为密码系统和数字签名，如本文讨论的RSA系统。RSA签名算法如下： 设N=p q，且p和q是两个大素数，e和d满足e dl(mod (N)。公开密钥：N，e 私有密钥：d 签名过程：发送方使用自己的私钥d对明文m进行数字签名变换： y=x d mod N：并将加密后的消息和签名y发送给接收方； 验证过程：接收方使用发送方的公钥e对收到的消息y进行数字签名验证变换x=ye mod N，并使用发送方的密钥解密恢复消息x，比较x与x，如果x=x则证实发送方的身份合法。这样，用户A若想用RSA签名方案对消息x签名，他只需公开他的公钥N和e，由于签名算法是保密的，因此A是唯一能产生签名的人，任何要验证用户A 签名的用户只需查到A的公钥即可验证签名。对于实现签名和公钥加密的组合，常用方法是：假定通信双方为A和B。对于明文x，A计算他的签名y=x d mod N，然后利用B的公开加密函数EB对信息对(x, y)加密得到Z，将密文Z传送给B，当B收到密文Z后，他首先用他的解密函数DB来解密得到(x，y)=DB (Z)= DB (EB(x，y)，然后利用A的验证算法来检查x=x=y e mod N是否成立。4.3 大数运算处理 RSA依赖大数运算，目前主流RSA算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于等于64位，即：0xffffffffffffffff也就是18446744073709551615，这远远达不到RSA的需要，于是需要专门建立大数运算库来解决这一问题。最简单的办法是将大数当作数组进行处理，数组的各元素也就是大数每一位上的数字，通常采用最容易理解的十进制数字09。然后对“数字数组”编写加减乘除函数。但是这样做效率很低，因为二进制为1024位的大数在十进制下也有三百多位，对于任何一种运算，都需要在两个有数百个元素的数组空间上多次重循环，还需要许多额外的空间存放计算的进退位标志及中间结果。另外，对于某些特殊的运算而言， 采用二进制会使计算过程大大简化，而这种大数表示方法转化成二进制显然非常麻烦，所以在某些实例中则干脆采用了二进制数组的方法来记录大数，当然这样效率就更低了。一个有效的改进方法是将大数表示为一个n进制数组，对于目前的32位系统而言n可以取值为2的32次方，即0x100000000，假如将一个二进制为1024位的大数转化成0x10000000进制，就变成了32位，而每一位的取值范围不再是二进制的0 1或十进制的09，而是00xffffffff我们正好可以用一个32位的DWORD(如：无符号长整数，unsigned long)类型来表示该值。所以1024位的大数就变成一个含有32个元素的DWORD数组，而针对DWORD 数组进行各种运算所需的循环规模至多32次而已。例如大数1 8446744073709551 61 5，等于0Xffffffff ffffffff其表示方式就相当于十进制的99：有两位，只是每位上的元素不是9而都是0xffffffff。而18446744073709551616等于0x00000001 00000000 00000000，就相当于十进制的100：有三位，第一位是l，其它两位都是0，如此等等。在实际应用中，“数字数组的排列顺序采用低位在前高位在后的方式，这样，大数A就可以方便地用数学表达式来表示其值： X=Xi r i (r=0x100000000，0Xi r) 任何整数运算最终都能分解成数字与数字之间的运算，在Oxl00000000进制下其“数字最大达到Ox腼筒，其数字与数字之间的运算，结果也必然超出了目前32位系统的字长。在VC+中，存在一个int64类型可以处理64位的整数，所以不用担心这一问题，而在其它编译系统中如果不存在64位整形，就需要采用更小的进制方式来存储大数，例如16位的WORD类型可以用来表示0x10000进制。但效率更高的办法还是采用32位的DWORD类型。4.4 大素数的产生根据RSA算法的加解密变换，需要产生两个保密的大素数作为基础运算。在2000年前欧几里德证明了素数有无穷多个，这自然的就引出一个问题：既然素数有无穷个，那么是否有一个计算素数的通项公式?两千年来，数论学的一个重要任务，就是寻找一个可以表示全体素数的素数普遍公式。为此，人类耗费了巨大的心血。希尔伯特认为，如果有了素数统一的素数普遍公式，那么这些哥德巴赫猜想和孪生素数猜想都可以得到解决。“研究各种各样的素数分布状况，一直是数论中最重要和最有吸引力的中心问题之一。关于素数分布性质的许多著名猜想是通过数值观察计算和初步研究提出的，大多数至今仍未解决”。因此，欲得到素数，必须另寻出路。大素数的产生应是现代密码学应用中最重要的步骤。几乎所有的公开密钥系统均需要用到大的素数，若此素数选用不当，则此公开密钥系统的安全性就岌岌可危。一般而言，素数的产生通常有两种方法，一为确定性素数产生方法，一为概率性素数产生方法，目前后者是当今生成素数的主要方法。所谓概率性素数产生法，是指一种算法，其输入为一奇数，输出为两种状态YES或NO之一。若输入一奇数n，输出为NO，则表示11为合数，若输出为YES，则表示n为素数的概率为1-r，其中r为此素数产生法中可控制的任意小数，但不能为0。此类方法中较著名的有Solovay-Strassen算法、Lehmann算法、Miller-Rabin算法等。在实际应用中，一般做法是先生成大的随机整数，然后通过素性检测来测试其是否为素数。数论学家利用费尔马定理研究出了多种素数测试方法，目前最快的算法是Miller-Rabin(拉宾米勒)测试算法(也称为伪素数检测)，其过程如下：首先选择一个待测的随机数N计算r，2r是能够整除N-1的2的最大幂数。1计算M，使得N=2rM+1。2选择随机数AN。3若AM mod N =l，则N通过随机数A的测试。4让A取不同的值对N进行5次测试，若全部通过则判定N为素数。若N通过一次测试，则N为合数(非素数)的概率为25，若N通过t次测试，则为合数(非素数)的概率为14t。事实上取t为5时，N为合数的概率为1128，N为素数的概率已经大于9999。5. RSA的安全性密码学所讨论的系统，其安全性是最高的评价准则。再好的密码系统，若安全性不足则一文不值，同时，密码系统的安全性很难用理论证明(事实上证明一个安全系统是安全的很难，但若该系统不安全，证明它是不安全的则很容易). RSA从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。但是在特定的条件下，RSA实现细节的疏忽会导致对RSA算法的有效攻击。因此，对RSA体制实现的各个环节进行充分考虑，避免安全性缺陷是非常有必要的。RSA的安全性分析:理论上，RSA的安全性取决于因式分解模数N的困难性。从严格的技术角度上来说这是不正确的，在数学上至今还未证明分解模数就是攻击RSA的最佳方法， 也未证明分解大整数就是NP问题(表示那些能在多项式时间内利用“不确定性 图灵机可以求解的问题)。事实情况是，大整数因子分解问题过去数百年来一直是令数学家头疼而未能有效解决的世界性难题。人们设想了一些非因子分解的途径来攻击RSA体制，但这些方法都不比分解n来得容易。因此，严格地说，RSA的安全性基于求解其单向函数的逆的困难性。RSA单向函数求逆的安全性没有真正因式分解模数的安全性高，而且目前人们也无法证明这两者等价。许多研究人员都试图改进RSA体制使它的安全性等价于因式分解模数。对RSA算法的攻击主要有以下几种： 1对分解模数N的攻击分解模数N是最直接也是最显然的攻击目标，同时也是最困难的。攻击者可以合法的获得公开密钥e和模数N；如果N=p q被因式分解，则攻击者通过p、q便可计算出(N)=(p-1)(q-1)，进而e dl(mod (N)而得到解密密钥d，大整数分解研究一直是数论与密码理论研究的重要课题。2对RSA的选择密文攻击选择密文攻击是攻击者对RSA等公钥算法最常用的攻击，也是最有效的攻击手段之一。选择密文攻击通常是由RSA加密变换的性质诱发的，常见的对RSA的选择密文攻击有三种： 明文破译。攻击者获得某用户A使用公钥e加密的密文y=x e (mod n)，并试图恢复出消息x。随机选取rn，计算y1=r e (mod n )，这意味，r=y1d(mod n)。计算y2=(yy1)(mod n)。令t=r-1 (mod n )，则t=y1d(mod n )，现在攻击者请A对消息y2，进行签名，得到S=y2d (mod n)。攻击者计算t l=t s=(y1-d y2d)(mod n)=(y1-dy1dyd)(mod n)= yd (mod n)=x，得到明文。骗取仲裁签名。在有仲裁情况下，若某用户A有一个文件要求仲裁，可先将其送给仲裁T，T使用RSA的解密密钥进行签名后送给A。攻击者有一个消息想要T签名，因为由于可能有伪造的时戳或来自非法使用者的消息，T并不签名。但攻击者可用下述方法获得T的签名。令攻击者的消息为X，他首先任选一个数N， 计算y=Ne (mod n)(e是T的公钥)，然后计算M=y x，送给T，T将签名结果M d mod n送给攻击方，则有： M d N一1(y x)d N-1(x d y d N-1)x d NN-1x d(mod n)攻击者成功骗取T对x的签名。伪造合法签名。攻击者利用自己伪造的两个消息x1和x2，来拼凑所需要的x3=(x1x2)(mod n)。攻击者如果得到用户A对而和x2的签名x1d(mod n)和x2d(mod n)，就可以计算屯的签名，x3d=(x1d(mod n)(x2d(mod n)(mod n)。3对RSA小指数攻击这类攻击专门针对RSA算法实现的细节。采用小的e、d可以加快加密和验证签名的速度，而且所需的存储空间小，但是如果e、d太小，则容易受到小指数攻击，包括低加密指数攻击和低解密指数攻击。通过独立随机数字对明文消息x进行填充，这样使得x e(mod n)xe，可以有效地抗击小指数攻击。4对RSA共模攻击在RSA公钥密码的实现中，为简化问题，可能会采用给每个人相同的n值， 但不同的指数值e和d。这样做的问题是，如果同一信息用两个不同的指数加密， 这两个指数是互素的，则不需要任何解密密钥就能恢复明文。设m是明文，两个加密密钥分别为e1，e2，共同的模数为n，两个密文为： c1=m e1 mod n c2=me2 mod n 由于el，e2是互素的，由扩展的欧几里德算法可以找到r和s，使之满足 Re1+se2=1假设r是负数(其中必有一个为负数)，再次使用欧几里德算法可以求得Ct对模数N的逆元c1-1，故可以得到(c1-1)-r c2r(mod n)mre1mse2(mod n)三m(mod n) 即密码分析者知道n，e1，e2，c1和c2，则可以恢复出明文m。5关于RSA算法的明文部分信息安全性同RSA算法一样，大多数的公钥密码体制的安全性是建立在单向函数之上的， 即所谓的单向函数模型密码体制。RSA算法使用的单向函数的安全性是基于大数分解的困难性，即攻击者在多项式时间内不能分解模数n。但这并不能保证攻击者很难使用概率方法来推算明文的某些特征或用二进制表示某个或某些比特的值(即明文的部分信息)。攻击者通过获取明文消息的部分信息，进而可以破译或恢复整个明文信息。这就是RSA安全性的另一个重要方面，可以称之为比特安全性， 即RSA算法中密文所泄漏的有关明文二进制表示的某些有效位的部分安全性。关于RSA体制部分信息安全性的最好结果是由W.Aiexi等人得出的。他们证明了任何由密文E(x)(E为加密函数)以不小于12+1ploy(N)的正确概率猜对最末有效位的算法F，都可诱导出一种由密文E(x)破译出x的相对于算法F的非确定多项式算法，即所谓的最末有效位12+lploy(N)安全性。6. 代码实现：#include#include#includetypedef int Elemtype;Elemtype p,q,e;Elemtype fn;Elemtype m,c;int flag=0;typedef void(*Msghandler)(void);struct MsgMapchar ch;Msghandler handler;/*公钥*/struct PUElemtype e;Elemtype n;pu;/*私钥*/struct PRElemtype d;Elemtype n;pr;/*判定一个数是否为素数*/bool test_prime(Elemtype m)if(m=1)return false;else if(m=2)return true;elsefor(int i=2;i0)binn=b%2;n+;b/=2;/*初始化主界面*/void Init()cout*endl;cout* Welcome to use RSA encoder *endl;cout* 1.setkey *endl;cout* 2.加密 *endl;cout* 3.解密 *endl;cout* 4.退出 *endl;cout*endl;coutpress a key:in2?in1:in2);Elemtype b=(in1in2?in1:in2);in1=a;in2=b;/*求最大公约数*/Elemtype gcd(Elemtype a,Elemtype b)order(a,b);int r;if(b=0)return a;elsewhile(true)r=a%b;a=b;b=r;if(b=0)return a;break;/*用扩展的欧几里得算法求乘法逆元*/Elemtype extend_euclid(Elemtype m,Elemtype bin)order(m,bin);Elemtype a3,b3,t3;a0=1,a1=0,a2=m;b0=0,b1=1,b2=bin;if(b2=0)return a2=gcd(m,bin);if(b2=1)return b2=gcd(m,bin);while(true)if(b2=1)return b1;break;int q=a2/b2;for(int i=0;i=0;i-)f=(f*f)%n;if(bini=1)f=(f*a)%n;return f;/*产生密钥*/void produce_key()coutpq;while(!(test_prime(p)&test_prime(q)cout输入错误，请重新输入!endl;coutpq;pr.n=p*q;pu.n=p*q;fn=(p-1)*(q-1);coutfn为：fnendl;coute;while(gcd(fn,e)!=1)coute输入错误，请重新输入!endl;coute;pr.d=(extend_euclid(fn,e)+fn)%fn;pu.e=e;flag=1;cout公钥(e,n）:pu.e,pu