综合实验报告
( 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,且满足1 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, 1 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[q]对A[p]的试商来得到一个近似值,所以我们不能够直接计算C。但是,我们可以一步一步地逼近C。显然,(A[p]/B[q]-1)*0x10000**(p-q) 1、选取长度相等的两个大素数p和q,计算其乘积:n = pq 然后随机选取加密密钥e,使e和(p–1)(q–1)互素。 最后用欧几里德扩展算法计算解密密钥d,以满足 ed = 1(mod(p–1) ( q–1)) 即d = e–1 mod((p–1)(q–1)) e和n是公钥,d是私钥 2、加密公式如下: ci = mi^e(mod n) 3、解密时,取每一密文分组ci并计算: mi = ci^d(mod n) Ci^d =(mi^e)^d = mi^(ed) = mi^[k(p–1)(q–1)+1 ] = mi mi^[k(p–1)(q–1)] = mi *1 = mi 4、消息也可以用d加密用e解密 三、编程思路 编程思路总共分为以下部分: 1、 检验两个数是否互素; 2、 由欧拉公式算出相应的密钥d; 3、 实现幂函数的取余,从而得以进行解密或加密。 4、 实现主要函数编写。 实现RSA算法。并加解密。说明:为了方便实现,分组可以小一点,比如两个字母一组。 (1). 选择两个大的素数p和q(典型情况下为1024位) (2). 计算n = p * q 和 z =(p-1)*(q-1). (3). 选择一个与z互素的数,将它称为d (4). 找到e,使其满足e*d = 1 mod z 提前计算出这些参数以后,我们就可以开始执行加密了。首先将明文分成块,使得每个明文消息P落在间隔0*P 2 为了加密一个消息P,只要计算C=P^e(mod n) 即可。为了解密C,只要计算P=C^d(mod n)即可。可以证明,对于指定范围内的所有P,加密盒解密互为反函数。为了执行加密,你需要e和n;为了执行解密,你需要d和n。因此,公钥是有(e,n)对组成,而私钥是有(d,n)对组成。 实例:根据已知参数:p=3,q=11,M=2,计算公私钥,并对明文进行加密,然后对密 文进行解密。 由题意知:n = p * q=33,z =(p-1)*(q-1)=20,选d=7, 计算得e=3,所以 C=M^e(mod n)=8 M=C^d(mod n)=2 四、主要程序说明 1.关键环节 1.求模逆元的扩展欧几里德算法 原理:正整数a和b满足sn*a + tn*b =(a,b),当(a,b)=1 时,sn = a^-1 mod b 其中 s0 = 1,s1 = 0,sj = (sj-2) – (qj-1)*s(j-1;t0 = 0,tj = (tj-2) – (qj-1)*t(j-1) 输入大数 a和b 输出:a^-1 mod b 或0(不存在逆元) (1) s0 = 1,s1 = 0 (2) while b>0 do 1.1 q = a/b;s2 = s0-q*s1; 1.2 s0 = s1;s1 = s2; 1.3 t = b;b = a%b;a = t; (3) if a=1 return s0;else return 0; 2.明文(数值)长度要小于key_N,才符合RSA算法,否则很容易出错,我选择了一个大于key_N的明文,发现经过验证并不符合RSA算法。那么,处理那些明文(数值)很大的办法就是将明文分成一小段一小段,否则,解密的信息必然是一堆乱码(除非原明文数值并不大)。分成一小段之后,然后利用加密公式和解密公式对其进行处理,这样得到的结果就是准确结果了。 2.主要函数 公钥和私钥的生成void generate_key() (1)首先利用strongprime函数生成两个素数key_P_Q[0],key_P_Q[1],然后利用multiply函数得到key_N = key_P_Q[0] * key_P_Q[1],用subtract函数和add函数实现 key_Z = 3 (key_P_Q[0] - 1 ) * (key_P_Q[1] – 1) = key_N – (key_P_Q[0] + key_P_Q[1]) + 1。 (2)随机生成一个密钥key_D,然后利用extend_gcd函数求同余方程key_D *key_E mod key_Z = 1。得到key_E,作为公钥。 (3)至此将公钥(key_N,key_E)写入文件中,将私钥(key_N,key_D)写入文件中保存。 加密信息void encode_information() 将加密的信息长度判断是否大于key_N的长度,如果大于key_N的长度,应该将加密信息分成一小段一小段,各小段长度均小于key_N长度,然后利用读取已经保存在文件中的公钥和私钥,对加密信息每小段每小段进行加密,并将加密信息密文存放到加密文件中。加密将用到的函数为powmod(key_P,key_E,key_N, key_C)。 解密信息void decode_information() 解密信息和加密信息采用同样的道理,即利用保存好的密钥对密文一段一段进行解密。解密将用到的函数为Powmod(key_C,key_D,key_N,key_P) 五、实验结果 (1)公钥长度为1024位进行验证: 图(1)生成公钥和私钥 4
华北电力大学-网络信息安全综合实验报告



