网络安全实验_RSA算法.docxVIP

网络安全作业 1．RSA 算法流程如下： (1)密钥生成算法流程： 随机地选择两个大素数 p和q (需)； 计算乘积n=px q； 计算欧拉函数z= (n)=(p-1)(q-1)。其数值等于小 于n并且与n互质的整数的个数。 选择一个随机数e,使e与z互质，且1ezo 计算 d,使d*e=1 mod z 。 其中，公钥 KP={e,n} ，私钥 KS={d,n} o (2) RSA 加密、解密的过程 首先将明文分块并数字化，每个数字化明文块的长度小于或等于 log 2n。然后对每个明文块M依次进行 加、解密： 加密：使用公钥 e和加密密文m,即C=Memod n； 解密：使用私钥d将密文c解密，获得明文 m,即M=cdmod n。 具体的数据结构与算法： (1 )存储大整数的数据结构： typedef struct { int length; unsigned int n[MAX]; } Lint; 这里大整数用65536进制表示并使用结构体Lint存储大整数。Lint由一个整型变量length和一个无符号整 型数组n[MAX]构成,length存储大整数的位数，n[MAX]具体存储每一位的值。 (2)具体的算法： 具体的算法主要参考了此书：振江等译?《密码编码学 一一加密方法的C与C十十实现(第二版)》.： 电子工业， 2003 具体的算法包括：基于上述数据结构的大整数的加、减、乘、除、模幂运算，求逆元运算，以及大素 数的判定等。这些算法的具体容都在原程序与其注释中。 源程序 此程序的开发环境是 Microsoft Visual studio 2008 。 (1) RSA 生成密钥源程序及运行结果 #includeiostream #includecmath using namespace std; void main() { int p,q; cout*****RSA 生成密钥算法 *****endlendl; cout 请输入两个较大的素数： endl; cinpq; coutp=p,q=qendl; int n,o; n=p*q; o=(p-1)*(q-1); coutn=n,o=oendl; cout?请从(0，0-1)中选择一个与vvovv互素的数 e： vvendl; int e,i; float d; cin?e; for(i=1;;i++) { d=(float)(o*i+1)/e; if(d-(int)d==0) break; } coutvve=vevv,d=vvdvve ndl; cout?公开密钥 Pk={e,n}={vvevv,vvnvv}vvendl; coutvv秘密密钥 Sk={d,n}={vvdvv,vvnvv}vvendl; coutvvendl; coutvv请输入要加密的正整数(以 -1结束)：vvendl; int m1[500],m3[500],m4[500]; double m2[500]; int j; for(j=0;jv500;j++) { cinm1[j]; if(m1[j]==-1) break; m2[j]=pow(m1[j],e); m4[j]=m2[j]/n; m3[j]=m2[j]-m4[j]*n; } coutvv密文为：vvendl; int k; for(k=0;kvj;k++) coutvvm3[k]vv; coutvvendl; } 程序运行结果及分析： *****Rgn生成密钥算迭***** 请输入两个较夫的素数： 343S55 43545 43 5 n=2075200587,0=207481348B 请从5, 2074813487中选择一个与20748￡3498互素的数6 45457 6=454657,4=4231 公幵霁月 Pk-e ,n -45465? fe^^tJSk=d,ri=4231,20?5200S8? 算法按照要求进行，生成的密钥也符合要求。 （2）RSA加密及解密算法实现源程序及运行结果 #include stdafx.h #include vstdio.h #include vstdlib.h #include vstring.h #include vtime.h #define MAX 200 /定义大整数的最大位数，200完全可以满足p与q达到768bit位的要求，可以选择更大的数 #define GREAT 1 //定义大整数比较时的返回值 #define EQUAL 0 #define LOW -1 33保证p与q达到512bit长#define PL 33 〃如果重新生成p与q, 33保证p与q达到512bit长 度。 typedef struct { int length; unsigned in