2015密码学课程设计报告 (2)

1、课 程 设 计 报 告题目：SPN和RSA密码算法的快速实现与安全性分析课程名称： 密码学 专业班级： 信安二班 学 号： 姓 名： 指导教师： 报告日期： 2015.9.20 计算机科学与技术学院密码学课程设计任务书题目：SPN和RSA密码算法的快速实现与安全性分析课题内容：（1）原始SPN（教材上）算法的实现。（2）对上述算法进行线性密码分析及差分密码分析（求出所有32比特密钥）。（3）增强以上SPN的安全性（如增加分组的长度、密钥的长度、S盒、轮数等）。（4）对原始及增强的SPN进行随机性检测，对检测结果进行说明。（5）生成RSA算法的参数（如p、q、N、私钥、公钥等）。（6）快速实现R

2、SA（对比模重复平方、蒙哥马利算法和中国剩余定理）。（7）结合RSA和增强后的SPN实现文件（或通信）的加解密。课题任务要求：（1） 掌握线性、差分分析的基本原理与方法。（2） 体会位运算、预计算在算法快速实现中的作用。（3） 可借助OpenSSL、GMP、BIGINT等大数运算库的低层基本函数，实现过程中必须体现模重复平方、中国剩余定理和蒙哥马利算法的过程。（4） 独立完成课程设计内容，现场演示并讲解。（5） 课程设计完成后一周内，提交课程设计报告。主要参考文献（由指导教师选定）（1） 密码学原理与实践（第三版）. DouglasR.Stinson著，冯登国译，电子工业出版社，2009（2）

3、 应用密码学：协议算法与C源程序（第二版）. Bruce Schneier著，吴世忠等译，机械工业出版社，2014同组设计者 无47目录绪论11、实验目的22、实验内容及基本要求22.1 SPN算法22.2 RSA算法22.3 文件的加解密以及随机性检测23、实验原理33.1 SPN算法33.2 RSA算法73.3 文件加解密与随机性检测74、实验过程84.1 SPN算法84.2 RSA算法204.3 文件加解密与随机性检测265、结果分析375.1 SPN算法375.2 RSA算法405.3文件加解密与随机性检测426、实验心得和体会45绪论课题背景和意义当前，重视实验与实践教育是各国高等教

4、育界的发展潮流，实验与实践教学与理论教学是相辅相成的，具有同等重要的地位。它是在开放教育的基础上，为配合理论教学、培养学生分析问题和解决问题的能力以及加强训练学生专业实践能力而设置的教学环节；对于完成教学计划、落实教学大纲，确保教学质量，培养学生分析问题、解决问题的能力和实践操作技能更具有特别重要的意义。密码学是信息安全与保密技术的核心，是一门实践性非常强的课程，实践教学是培养密码技术应用性人才的重要途径，实践教学质量的好环，实际上也决定了应用型人才培养质量的高低。因此，加强密码学课程实践教学环节，提高实践教学质量，对培养高质量的应用型人才至关重要。密码学是研究编制密码和破译密码的技术科学。研

5、究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学。总称密码学。课程设计的主要研究工作本次课程设计是以课堂中所学的密码学的内容为基础，使用Code Blocks、Microsof Visual C+作为开发工具，使用了GMP大数库。系统具有SPN加解密、RSA加解密、文件加解密三个主要的功能，包括简单的SPN算法的实现、线性差分分析，加强SPN算法的实现，RSA加解密，文件加解密等子模块。能够满足对任意大小的文件进行加解密。文件加解密的设计合理，在保证了速度的同时，也没有占用太大的内存空间。1、 实验目的通过课程设计，使学生进一步熟悉密

6、码算法以及算法安全性的基本概念和原理；培养学生将密码理论和技术应用于实际的能力，使学生具备实施数据加解密和基本的密码分析的能力。2、 实验内容及基本要求2.1 SPN算法的编程实现（1）了解书本中对称密码体制的内容，熟练掌握并实现教材中的SPN算法；（2）线性分析：了解线性分析的原理，通过对明密文对的线性分析，配合暴力破解，破解出初始加密密钥；（3）差分分析：了解差分分析的原理，通过对明密文对的差分分析，配合暴力破解，破解出初始加密密钥；（4）通过增加分组长度，秘钥长度，S盒、轮数等方式，增强上述SPN算法的安全性。2.2 RSA的参数生成以及快速实现（1）生成RSA算法的参数；（2）通过中国

7、剩余定理，蒙哥马利算法，模重复平方算法，快速实现RSA；（3）通过调用时钟对三种解密方法的时间开销进行测试。2.3 文件的加解密以及随机性检测（1）结合RSA和增强后的SPN算法实现文件的加解密；（2）密文的随机性反映了密码的强度，对原始的和增强后的SPN算法进行随机性检测，对检测的结果进行说明。3、 实验原理3.1 SPN算法3.1.1代换置换网络（SPN）SPN就是一类特殊的迭代置换密码，一个SPN包括两个变换，分别记s和p，其中s就是对一L个比特的向量，用另一个L比特的向量来代替它，置换p则用来置换Lm个比特，打乱一个长度为Lm比特的向量内部各个比特的顺序。将要给出的SPN由Nr轮组成，

8、先用异或操作混入该轮的轮秘钥，再用s经行m次代换，再用p进行一次置换，基于s和p，下面给出一个SPN的具体算法。加密过程使用如下算法描述：w0=xfor r=1 to Nr-1 ur=wr-1kr / 白化 for i=1 to m do vr=s(ur) / 代替wr=(vrp(1),vrp(2),.,vrp(lm) / 置换uNr=wNr-1kNrfor i=1 to m do vNr=s(uNr) / 代替y=vNrkNr+1 / 白化output y其中该SPN的第一个和最后一个操作都是异或轮秘钥，这叫做白化，白话可以使一个不知道秘钥的攻击者无法开始一个加解密操作。最后具体的过程如下图

9、3.1所示：图3.1 SPN加密算法3.1.2线性密码分析线性密码分析是一种已知明文攻击，在一个明文比特集与最后一轮即将进行代换的输入状态比特子集之间找到一个概率线性关系，即存在一个子集使得其中元素的异或表现出非随机的分布，使用大量的用同一未知秘钥K加密的明密文对，对每一个明密文对，将用所有可能的候选秘钥来对最后一轮解密密文，对每一个候选秘钥，计算包含在线性关系式中的相关转态比特的异或值，然后确定上述线性关系是否成立，如果成立，就在对应于特定候选秘钥的计数器上加1，在这个过程的最后，计数器离明密文对数的一半最远的候选秘钥含有那些秘钥比特的正确值。在线性分析的过程中不需要对全部密钥空间进行穷举，

10、只需要对随机变量有影响的密钥比特进行穷举，这些密钥比特称为候选子密钥。在计算出候选子秘钥的正确值之后，采用穷举的办法，暴力破解出秘钥其余比特的正确值，最终得到完整的秘钥。线性分析的具体算法如下：线性攻击(T, T, s-1) ： for (L1,L2)=(0,0) to (F,F) / L1,L2表示候选子密钥k5和k5do CountL1,L2=0 / 每个候选子密钥分配一个计数器并初始化为0for each (x,y) T for (L1,L2)=(0,0) to (F,F) v4 = L1yv4 = L2yu4 = s-1(v4)u4 = s-1(v4)z = x5x7x8u46u48u

11、414u416 / 计算随机变量值if z=0 then CountL1,L2 +;max = -1for (L1,L2)=(0,0) to (F,F) CountL1,L2 = | CountL1,L2 - T/2 |if CountL1,L2 max max = CountL1,L2 maxkey = (L1,L2)Output(maxkey) / maxkey即为所求子密钥3.1.3差分密码分析差分密码分析是一种选择明文攻击，我们首先产生大量的四元组（x,x*,y,y*），其中异或值x=xx*是固定的，明文x与x*通过同一个秘钥K加密得到y与y*。对这些四元组中的每一个，将应用所有可能的

12、候选秘钥来对改密码的最后一轮经行解密。对于每一个候选秘钥，计算某些转态比特的值，并确定他们的异或是否有一个确定的值，如果是就把对应于特定候选秘钥的计数器加1。在这个过程的最后，对应计数器数值最大的候选秘钥就是正真秘钥特定比特的取值。在差分分析的过程中不需要对全部密钥空间进行穷举，只需要对随机变量有影响的密钥比特进行穷举，这些密钥比特称为候选子密钥。在计算出候选子秘钥的正确值之后，采用穷举的办法，暴力破解出秘钥其余比特的正确值，最终得到完整的秘钥。差分分析的具体算法如下：for (L1,L2)=(0,0) to (F,F) / L1,L2表示候选子密钥k5和k5do CountL1,L2=0 /

13、 每个候选子密钥分配一个计数器并初始化为0for each (x,x*,y,y*) T if (y=y* and y=y*) then / 只考虑y和y=0 for (L1,L2)=(0,0) to (F,F) v4 = L1yv4 = L2yu4 = s-1(v4)u4 = s-1(v4)(v4)*= L1(y)*(v4)* = L2(y)*(u4)* = s-1(v4) *)(u4)* = s-1(v4)*)(u4)=u4(u4)*(u4)=u4(u4)*if (u4)=0110 and (u4) = 0110) then CountL1,L2 +; max = -1for (L1,L2)

14、=(0,0) to (F,F) if CountL1,L2 max then max = CountL1,L2 maxkey = (L1,L2) Output(maxkey) / maxkey即为所求子密钥3.1.4加强的SPN算法与原有的初始的SPN算法大致相同，通过增加分组长度，秘钥长度，选择更复杂的S盒、增加轮数等方式，对上述SPN算法的安全性进行增强，在本次设计中改进后的SPN算法每一次对64比特的数据进行处理，采用AES的S盒，每一次对8比特的数据进行置换，一次S盒的操作需要8次置换，P盒将64比特中的数据进行重新排列，每一轮秘钥的长度也需要64比特，总共加密9轮，需要128比特的初

15、始秘钥。秘钥K也是通过一个长度为128比特的数组保存的，第一轮使用前64比特，之后每一轮向后移8位，作为新一轮的秘钥。3.2 RSA算法3.2.1 RSA密码体制由于在对称密码体制中，加解密使用的是同一个秘钥，所以加解密的双方必须交换秘钥，这就存在一个安全交换秘钥的问题，因此人们就提出了非对称的密码体制，也就是公钥密码体制，即接收方生成保密的私钥和相应的公开的公钥，发送方用公钥加密之后将加密的文件发给接收方，接收方就可以用相应的私钥解密，解决了对称密码体制秘钥交换的问题，其中RSA算法就是一种十分著名的公钥密码算法，RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘

16、积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。RSA算法描述如下：（1） 参数生成选择两个互异的大素数p和q，n是二者的乘积，即n=pq，使(n)=(p-1)(q-1)为欧拉函数。随机选取正整数e，使其满足gcd(e, (n) =1，即e和(n) 互质，则将(n,e)作为公钥。求出正数d，使其满足ed=1(mod(n)，则将(n,d)作为私钥。（2） 加密算法对于明文M，由C=Me(mod n)，得到密文C。（3） 解密算法对于密文C，由M=Cd(mod n)，得到明文M。3.2.2 RSA参数生成在本次课程设计中采用的是GMP大数库，使用了大数库中基于大数的一些加法，乘法，求逆等

17、基本运算。RSA参数的生成过程如下：（1） 生成两个大素数p，q，p!=q；（2） n=pq,且(n)=(p-1)(q-1)；（3） 随机选择随机数e（1e(n)），使其满足gcd(e, (n) =1；（4） d=b-1mod(n)；（5） 公钥为（n,e）, 私钥为（p,q,a）；3.3 文件加解密与随机性检测3.3.1 加密体制本次加密算法采用RSA与加强的SPN相结合的密码体制，发送方选择一个秘钥，用其对文件进行加密，再用接收方的公钥E对K进行加密后，将秘钥的密文和文件的密文一同发送给接受方，接收方先用私钥解密出秘钥K，再用秘钥K解密加密的文件。在加强的SPN加密文件时，采用的是CBC模

18、式。3.3.2 短块处理由于加强的SPN每一次加密都是对64比特的数据进行变换，在文件的加密操作中，文件的大小可能并不是64比特的整数倍，就需要对最后一次加密进行短块处理，本次设计中所采用的方法是不足64比特的部分先用0填充，在最后一个字节即最后8个比特用需要填充的比特的个数转换成2进制数填充。3.3.3 随机性检测密文的随机性反映了密码的强度，对原始的和增强后的SPN算法，使用老师所给的检测工具进行随机性检测，并对检测的结果进行说明。4、实验过程4.1 SPN算法4.1.1 代换置换网络（SPN）（1）数据结构与基本设计思想本次实验中采用两个长度为16的整形数组结构保存相应的明文和密文，加密

19、过程的使用的S盒和P盒也是采用两个含有16个整形元素的数组进行保存，便于进行相应的操作。解密过程与加密过程类似。秘钥K也是通过一个长度为32比特的数组保存的，第一轮使用前16比特，之后每一轮向后移4位，作为新一轮的秘钥，每一轮对秘钥进行异或操作时，只需要相应的指针向后移动便可。加密过程可以参考实验原理中已经给出的算法，实现比较简单，解密过程则是对加密过程的逆操作，使用的S盒的逆与P盒的逆通过预计算用长度为16的整形数组保存。（2）S盒操作首先取出需要转换的原文的4比特，转化成对应的10进制数之后通过S盒进行置换，再转换成相应的二进制数保存在原数组中。具体代码如下：void Sboxop(int

20、 *plain) int i,m=0; for(i=3;i=N;i=i+4) int temp=0; for(m=i-3;m=i-3;m-) plainm = temp % 2; temp = temp / 2; （3）p盒操作首先设立一个16个整形元素的缓存区数组，将待转化的数组复制保存在缓存区中，再通过P盒进行置换，将置换之后的写回原数组中。具体代码如下：void Pboxop(int *plain) int i; int tempN; for (i = 0; i N; i+) tempi = plaini; for(i = 0; i N; i+) plain(pboxi-1) = tem

21、pi;（4）加解密算法的实现与课本上所给的算法相同，解密算法就是一个逆过程，总的来说比较简单。void Encrypt(int* plain,int*cipher) int nr=5,i,j; for (i = 0; i N; i+) cipheri = plaini; for (i = 0; i nr-2; i+) Xor(cipher,key + 4*i); Sboxop(cipher); Pboxop(cipher); Xor(cipher,key + 4*i); i+; Sboxop(cipher); Xor(cipher,key + 4*i); for(j=0;jN;j+) prin

22、tf(%d,cipherj); printf(n);void Decrypt(int *cipher,int* plain) int i,nr=5,j; for (i = 0; i =0; i-) Pboxnop(plain); Sboxnop(plain); Xor(plain,key + 4*i); for(j=0;jN;j+) printf(%d,plainj); printf(n);4.1.2 线性密码分析（1）明密文对的生成调用简单的SPN算法，产生8000对明密文对，写入文件中保存，具体代码如下：int main(void)int plainN,i,cipherN,nr=5,j;

23、FILE *fin; fin=fopen(E:pairs.txt,w);for(j=0;j8000;j+) for(i = 0; i 16; i+) plaini = rand() % 2; for(i=0;iN;i+) fprintf(fin,%d ,plaini); fprintf(fin,n); for (i = 0; i N; i+) cipheri = plaini; for (i = 0; i nr-2; i+) Xor(cipher,key + 4*i); Sboxop(cipher); Pboxop(cipher); Xor(cipher,key + 4*i); i+; Sbo

24、xop(cipher); Xor(cipher,key + 4*i); for(i=0;iN;i+) fprintf(fin,%d ,cipheri); fprintf(fin,n); fclose(fin);（2）候选子秘钥的计算线性密码分析在一开始猜测部分比特的与课本上描述的算法完全相同，首先从文件中读取出已经生成的明密文对，8000对，保存在两个数组中，进行线性分析，分析出来的正确的候选秘钥通过change函数，放入最终猜测的32比特的秘钥中正确的位置，具体代码实现如下：int Count256,xM16,yM16,j,L12564,L22564,v24,v44,i,z,maxkey,k

25、32; FILE *fin; fin=fopen(E:pairs.txt,r); for(i=0;iM;i+) for(j=0;jN;j+) fscanf(fin,%d,&xij); for(j=0;jN;j+) fscanf(fin,%d,&yij); fclose(fin); for(j=0;j=0;i-) L2ji=k%2; k=k/2; for(i=3;i=0;i-) L1ji=k%2; k=k/2; for(i=0;i256;i+) Counti=0; for(i=0;i8000;i+) for(j=0;j256;j+) Xorl(L1j,yi+4,v2); Xorl(L2j,yi+

26、12,v4); Sboxnop(v2); Sboxnop(v4); z=(xi4+xi6+xi7+v21+v23+v41+v43)%2; if (z=0) Countj=Countj+1; int Max=-1; for(i=0;iMax) Max=Counti; maxkey=i; change(k,maxkey,31,28);maxkey=maxkey/16;change(k,maxkey,23,20);（3）穷举法猜测完整秘钥对于剩下的24位没有猜测出来的秘钥，通过穷举法，对于每一个可能的秘钥，依次用其去加密10个明文，并与已知的正确的密文比较，若是全部通过，则便是正确的秘钥。其中cha

27、nge函数也是在最终猜测的秘钥中选择正确的位置，放入猜测具体数值，spn函数就是spn算法，具体代码的实现如下：int i1,i2,i3,i4,i5,i6,i7,i8,i9,cipherN;for(i1=0;i116;i1+) change(k,i1,3,0);for(i2=0;i216;i2+) change(k,i2,7,4);for(i3=0;i316;i3+) change(k,i3,11,8);for(i4=0;i416;i4+) change(k,i4,15,12);for(i5=0;i516;i5+) change(k,i5,19,16);for(i6=0;i616;i6+) c

28、hange(k,i6,27,24); i9=0; for(i8=0;i810;i8+) spn(xi8,cipher,k); for(i=0;iN;i+) if(cipheri!=yi8i) i9=1; break; if(i9=1) break; if(i9=0) for(i7=0;i732;i7+) printf(%d,ki7); if(i7+1)%4)=0) printf( ); printf(n); system(pause); return 1; 4.1.3 差分密码分析（1）明密文对的生成调用简单的SPN算法，产生500对明密文对，写入文件中保存，具体代码如下：int main(v

29、oid)int plainN,i,cipherN,nr=5,j,xN; FILE *fin; fin=fopen(E:pairscf.txt,w);for(j=0;j500;j+) for(i = 0; i 16; i+) plaini = rand() % 2; Xorl(plain,xl,x); for(i=0;iN;i+) fprintf(fin,%d ,plaini); fprintf(fin,n); for (i = 0; i N; i+) cipheri = plaini; for (i = 0; i nr-2; i+) Xor(cipher,key + 4*i); Sboxop(

30、cipher); Pboxop(cipher); Xor(cipher,key + 4*i); i+; Sboxop(cipher); Xor(cipher,key + 4*i); for(i=0;iN;i+) fprintf(fin,%d ,cipheri); fprintf(fin,n); /对X进行处理 for(i=0;iN;i+) fprintf(fin,%d ,xi); fprintf(fin,n); for (i = 0; i N; i+) cipheri = xi; for (i = 0; i nr-2; i+) Xor(cipher,key + 4*i); Sboxop(cip

31、her); Pboxop(cipher); Xor(cipher,key + 4*i); i+; Sboxop(cipher); Xor(cipher,key + 4*i); for(i=0;iN;i+) fprintf(fin,%d ,cipheri); fprintf(fin,n); fprintf(fin,n); fclose(fin);（2）候选子秘钥的计算差分密码分析在一开始猜测部分比特的与课本上描述的算法完全相同，首先从文件中读取出已经生成的明密文对，500对，保存在两个数组中，进行差分分析，分析出来的正确的候选秘钥通过change函数，放入最终猜测的32比特的秘钥中正确的位置，具

32、体代码实现如下：int Count256,x1M16,x2M16,y1M16,y2M16,j,L12564,L22564,v24,v44,i,maxkey,vl24,vl44,u24,u44,Max,k32; FILE *fin; fin=fopen(E:pairscf.txt,r); for(i=0;iM;i+) for(j=0;jN;j+) fscanf(fin,%d,&x1ij); for(j=0;jN;j+) fscanf(fin,%d,&y1ij); for(j=0;jN;j+) fscanf(fin,%d,&x2ij); for(j=0;jN;j+) fscanf(fin,%d,&

33、y2ij); fclose(fin); for(j=0;j=0;i-) L2ji=k%2; k=k/2; for(i=3;i=0;i-) L1ji=k%2; k=k/2; for(i=0;i256;i+) Counti=0; for(i=0;iM;i+) if(y1i0=y2i0&y1i1=y2i1&y1i2=y2i2&y1i3=y2i3&y1i8=y2i8&y1i9=y2i9&y1i10=y2i10&y1i11=y2i11) for(j=0;j256;j+) Xorl(L1j,y1i+4,v2); Xorl(L2j,y1i+12,v4); Sboxnop(v2); Sboxnop(v4);

34、Xorl(L1j,y2i+4,vl2); Xorl(L2j,y2i+12,vl4); Sboxnop(vl2); Sboxnop(vl4); Xorl(v2,vl2,u2); Xorl(v4,vl4,u4); if(u20=0&u21=1&u22=1&u23=0&u40=0&u41=1&u42=1&u43=0) Countj+; Max=-1; for(i=0;iMax) Max=Counti; maxkey=i; change(k,maxkey,31,28);maxkey=maxkey/16;change(k,maxkey,23,20);（2）穷举法猜测完整秘钥这部分的内容与线性分析中相应内

35、容完全一样，最终得到32比特的正确秘钥。4.1.4加强的SPN算法（1）数据结构与基本设计思想本次实验中采用两个长度为64的整形数组结构保存相应的明文和密文，加密过程的使用的S盒和P盒也是采用两个分别含有256和64个整形元素的数组进行保存，便于进行相应的操作。解密过程与加密过程类似。秘钥K也是通过一个长度为128比特的数组保存的，第一轮使用前64比特，之后每一轮向后移8位，作为新一轮的秘钥，每一轮对秘钥进行异或操作时，只需要相应的指针向后移动便可。加密过程可以参考实验原理中已经给出的算法，实现比较简单，解密过程则是对加密过程的逆操作，使用的S盒的逆与P盒的逆通过预计算保存在相应的数组中。（2

36、）S盒与P盒操作与未加强前的操作基本一致，每一次分别对64比特的数据进行相应的操作。（3）加解密算法的实现具体算法如下所示：void Encrypt1(int* plain1,int*cipher1) int nr=10,i,j; for (i = 0; i N1; i+) cipher1i = plain1i; for(j=0;jN1;j+) printf(%d,cipher1j); if(j+1)%4=0) printf( ); printf(n); for (i = 0; i nr-2; i+) Xor1(cipher1,key1 + 8*i); Sboxop1(cipher1); Pb

37、oxop1(cipher1); Xor1(cipher1,key1 + 8*i); i+; Sboxop1(cipher1); Xor1(cipher1,key1 + 8*i); for(j=0;jN1;j+) printf(%d,cipher1j); if(j+1)%4=0) printf( ); printf(n);void Decrypt1(int *cipher1,int* plain1) int i,nr=10,j; for(j=0;jN1;j+) printf(%d,cipher1j); if(j+1)%4=0) printf( ); printf(n); for (i = 0;

38、i =0; i-) Pboxop1(plain1); Sboxnop1(plain1); Xor1(plain1,key1 + 8*i) for(j=0;jN1;j+) printf(%d,plain1j); if(j+1)%4=0) printf( );4.2 RSA算法4.2.1 RSA的参数生成算法（1）生成大素数算法本次实验采用的是GMP的大数库，在生成大素数这个环节中，调用了两个库函数，一个是mpz_nextprime (mpz_t rop, mpz_t op)用来置 rop 为比 op 大的下一个素数，再用mpz_probab_prime_p函数进行判定，这个函数首先做一些试除，然

39、后再作 Miller-Rabin 概率素性判别。进行20轮的判定，如果是合数，放弃这个数，在生成一个可能的大素数进行判定。具体的算法如下所示：void CreateBigPrime(mpz_t mpzPrime,int bits)int i,last_rand=0;char *char_rand = new char bits+1;char_rand0 = 1;char_randbits = 0;mpz_init(mpzPrime);dofor(i=1;ibits;i+)if(rand()=last_rand) printf(ERROR);last_rand = rand();char_ran

40、di = 0+(0x01&last_rand);mpz_set_str(mpzPrime,char_rand,2);mpz_nextprime(mpzPrime,mpzPrime);while(0=mpz_probab_prime_p(mpzPrime,PRIME_PROBABILITY);return;（2）RSA具体参数的生成这个过程也比较简单，通过生成素数算法生成512比特的素数p,q。求得他们的乘积n，通过p-1和q-1求出Fn，之后设置e为65537,通过gmp库中提供的求逆函数mpz_inver，得到d，所有参数生成完毕，具体算法如下图所示。void RSA(mpz_t p,mpz

41、_t q,mpz_t n,mpz_t fn,mpz_t e,mpz_t d)unsigned long rp=0,rq=0,e1=65537;mpz_t p0,q0; mpz_init(p0);mpz_init(q0); CreateBigPrime(p,512);srand( (unsigned)time( NULL ) ); CreateBigPrime(q,512);mpz_mul(n,p,q);/求出p、q 和n gmp_printf(素数p: %Zdn,p); gmp_printf(素数q: %Zdn,q);mpz_set_ui (e, e1) ; gmp_printf(e: %Zd

42、n,e); mpz_sub_ui(p0,p,1);mpz_sub_ui(q0,q,1);mpz_mul(fn,p0,q0); gmp_printf(fn: %Zdn,fn); mpz_invert(d,e,fn); gmp_printf(d: %Zdn,d); mpz_clear(p0);mpz_clear(q0);4.2.2 模重复平方算法模重复平方的思想是将指数n写成二进制形式n=n0+n1*2+nk-1*2k-1，令a=1（1）若n0=1，则计算a0=a*b(mod m),否则取a0=a，即计算a0=a*bn0(mod m)，再计算b1=b2(mod m).（2）若n1=1，则计算a1=a0*b1(mod m)