网络安全基础教程报告
题 目 ：学 号 ：专业及班级 ：姓 名 ：日 期 ：
RSA加 密 算 法 1108040205 计网1102班 李雪飞 2013.11.26
一、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算法应用规范介绍参见： http://www.rsasecurity.com/rsalabs/node.asp?id=2146 ，这些API内部支持的算法不仅仅只有RSA，但是RSA是数字签名和证书中最常用的)，用户程序可以直接使用java标准库中提供的API进行数字签名和证书的各种操作。
二、算法原理
1．选择两个不同的大素数p、q
(目前两个数的长度都接近512bit是安全的）； 2. 计算n = p*q。
3. 计算n的欧拉函数 t=(p-1)(q-1)。
4. 选择整数e作为公钥，使e与t互素，且1 5. 用欧几里得算法计算d作为私钥,使d*e=1 mod t。 6. 加密：C=M^e mod n 7. 解密：M＝C^d mod n=(M^e)^d mod n= M^e^d mod n 。 三、RSA算法的各环节 RSA算法是1978年由R.L.Rivest，A.Shamir和L.Adleman提出的一种用数论构造的、 也是迄今为止理论上最为成熟完善的公钥密码体制。RSA的理论基础是数论中的欧拉定理,它的的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解 难度等价。 3.1 RSA公钥加密解密概述 RSA算法采用下述加密/解密变换。 1．密钥的产生 ①选择两个保密的大素数P和q。 ②计算N=p q，≯(N) =(p-1)(g-1)，其中≯(N)是N的欧拉函数值。 ③选择一个整数e，满足l ④计算私钥d(解密密钥)，满足e d≡l(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 3.2 RSA签名算法 并非所有的公开密钥系统，均可同时达到秘密性与数字签名功能。一般而言， 一公开密钥系统若作为密码系统，则无法作为数字签名，反之亦然。只有很少数 的系统可同时作为密码系统和数字签名，如本文讨论的RSA系统。RSA签名算 法如下： 设N=p q，且p和q是两个大素数，e和d满足e d≡l(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)= e DB (EB(x，y))，然后利用A的验证算法来检查x’=x=y modN是否成立。 3.3 大数运算处理． RSA依赖大数运算，目前主流RSA算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于等于64位，即：0xffffffffffffffff也就是18446744073709551615，这远远达不到RSA的需要，于是需要专门建立大数运算库来解决这一问题。最简单的办法是将大数当作数组进行处理，数组的各元素也就是大数每一位上的数字，通常采用最容易理解的十进制数字0~9。然后对“数字数组” 编写加减乘除函数。但是这样做效率很低，因为二进制为1024位的大数在十进制下也有三百多位，对于任何一种运算，都需要在两个有数百个元素的数组空间上多次重循环，还需要许多额外的空间存放计算的进退位标志及中间结果。另外，对于某些特殊的运算而言， 采用二进制会使计算过程大大简化，而这种大数表示方法转化成二进制显然非常麻烦，所以在某些实例中则干脆采用了二进制数组的方法来记录大数，当然这样效率就更低了。一个有效的改进方法是将大数表示为一个n进制数组，对于目前的32位系统而言n可以取值为2的32次方，即0x100000000，假如将一个二进制为1024位的大数转化成0x10000000进制，就变成了32位，而每一位的取值范围不再是二进制的0~ 1或十进制的0~9，而是0~0xffffffff我们正好可以用一个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，0 任何整数运算最终都能分解成数字与数字之间的运算，在Oxl00000000进制下其“数字\最大达到Ox腼筒，其数字与数字之间的运算，结果也必然超出了目前32位系统的字长。在VC++中，存在一个int64类型可以处理64位的整数，所以不用担心这一问题，而在其它编译系统中如果不存在64位整形，就需要采用更小的进制方式来存储大数，例如16位的WORD类型可以用来表示0x10000进制。但效率更高的办法还是采用32位的DWORD类型。 3.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=2r×M+1。 2．选择随机数A 3．若AM mod N =l，则N通过随机数A的测试。 4．让A取不同的值对N进行5次测试，若全部通过则判定N为素数。 若N通过一次测试，则N为合数(非素数)的概率为25％，若N通过t次测试，则为合数(非素数)的概率为1／4t。事实上取t为5时，N为合数的概率为1／128，N为素数的概率已经大于99．99％。 四、代码实现： 1.采用C++语言进行本次实验的编写，实验的代码如下： #include int candp(int a,int b,int c) { int r=1; b=b+1; while(b!=1) { r=r*a; r=r%c; b--; } printf(\return r; } void main() { int p,q,e,d,m,n,t,c,r; char s; printf(\scanf(\n=p*q; printf(\t=(p-1)*(q-1);
网络安全RSA算法的实现实验报告
