华北电力大学_网络信息安全综合实验报告.doc

. . . PAGE . . . 综合实验报告 ( 2013 -- 2014 年度第 1 学期) 名 称：网络信息安全综合实验 题 目： RSA公钥加密解密 院 系： 计算机系 班 级： 网络工程 学 号： 学生姓名： 指导教师： 李天 设计周数： 1 周 成 绩： 日期： 2013年1月18日 一、综合实验的目的与要求 要求：了解RSA产生公钥和私钥的方法，掌握RSA 的加密、解密过程，编写程序设计RSA 加解密工具。 RSA加解密参考：RSA的安全性依赖于大数分解，公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。密钥的产生： 1. 选择两个保密的大素数p和q； 2. 计算n=p*q和欧拉函数值E(n)=(p-1)(q-1)； 3. 选一整数e，且满足1eE(n)和gcd(E(n),e)=1； 4. 计算d，且满足d*e=1 mod E(n)； 5. 公钥为{e, n}，私钥{d, n}。 二、RSA算法的描述 1．RSA?依赖大数运算，目前主流RSA?算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于等于64位，即：0xffffffffffffffff，也就是18446744073709551615，这远远达不到RSA?的需要，于是需要专门建立大数运算库来解决这一问题。最简单的办法是将大数当作数组进行处理，也就是将大数用0—9这十个数字组成的数组进行表示，然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样做效率很低，因为二进制为1024位的大数其十进制也有三百多位，对于任何一种运算，都需要在两个有数百个元素的数组空间上做多重循环，还需要许多额外的空间存放计算的进退位标志及中间结果。另外，对于某些特殊的运算而言，采用二进制会使计算过程大大简化，这种大数表示方法转化成二进制显然非常麻烦，所以在某些实例中则干脆采用了二进制数组的方法来记录大数，这样效率就更低了。一个有效的改进方法是将大数表示为一个n?进制数组， n?可以取值为2?的16次方，即0x1000，假如将一个二进制为1024位的大数转化成0x1000进制，它就变成了64位，而每一位的取值范围就不是二进制的0—1或十进制的0—9，而是0-0xffff，我们正好可以用一个无符号整数来表示这一数值。所以1024位的大数就是一个有64个元素的unsigned?int数组，针对unsigned?int数组进行各种运算所需的循环规模至多64次而已。而且0x10000?进制与二进制，对于计算机来说，几乎是一回事，转换非常容易。加法: A=Sum[i=0?to?p](A[i]*0x10000**i) ； B=Sum[i=0?to?q](B[i]*0x10000**i)，p=q ； C=Sum[i=0?to?n](C[i]*0x10000**i)=A+B。如果用carry[i]记录每次的进位则有：C[i]=A[i]+B[i]+carry[i-1]-carry[i]*0x10000，其中carry[-1]=0。若A[i]+B[i]+carry[i-1]0xffffffff，则carry[i]=1；反之则carry[i]=0，若carry[p]=0，则n=p；反之则n=p+1。减法与加法同理。 因此：?C[i]=Sum[j=0?to?q](A[i-j]*B[j])+carry[i-1]-carry[i]*0x10000，其中carry[-1]=0，carry[i]=(Sum[j=0?to?q](A[i-j]*B[j])+carry[i-1])/0x10000，n=p+q-1，若carry[n]0，则n=n+1，C[n]=carry 除法 设A=Sum[i=0?to?p](A[i]*0x10000**i) ， B=Sum[i=0?to?q](B[i]*0x10000**i)，p=q，??C=Sum[i=0?to?n](C[i]*0x10000**i)=A/B。由于无法将B?对A?“试商”，我们只能转换成B[