RSA算法 C语言

一、实验目的

掌握并实现RSA算法。

二、实验内容

利用C\\C++实现RSA算法的加、解密运算。 具体包括：

1) 利用扩展的EUCLID计算 a mod n 的乘法逆元； 2) Miller-Rabin素性测试算法对一个给定的大数进行测试； 3) 实现mkmodn的运算，并计算7563mod561；

4) 利用Fermat定理手工计算7563mod561，并与3）计算的结果对比； 5) 实现RSA算法。并对\"I LOVE THE PEOPLE'S REPUBLIC OF CHINA\"加解密。说

明：为了方便实现，分组可以小一点，比如两个字母一组。

字母及其数字编码 空格 00 A 01 B 02 C 03 D 04 E 05 F 06 G 07 H 08 I 09 J 10 K 11 L 12 M 13

字母及其数字编码 N 14 O 15 P 16 Q 17 R 18 S 19 T 20 U 21 V 22 W 23 X 24 Y 25 Z 26 三、实验步骤

#include

#include #include

using namespace std;

int Euclid(int a,int n)//n大于a { int x,y,r; x=n;y=a; for(int i=0;;) { if(y==0) return x; if(y==1) return y; r=x%y; x=y; y=r; } }

double extenEuclid(double a,double n)//利用扩展的EUCLID计算 a mod n 的乘法逆元 { double x1=1,x2=0,x3=n,y1=0,y2=1,y3=a,Q; double t1,t2,t3; for(int i=0;;) { if(y3==0) { return x3; cout<<\"no reverse\"<bool Rabin(int a,int n)//Miller-Rabin素性测试算法对一个给定的大数进行测试

{ }

vector b;

unsigned int N=n-1; for(int i=0,j=1;; i++) { if(j>N) break; if( (N>> i) & (unsigned int)1 ) b.push_back(1); else b.push_back(0); j*=2; }//将n-1表示成二进制形式 for(int k=0;kint d=1,x=0;

for(int ii=b.size()-1;ii>=0;ii--) { x=d; d=(d*d)%n; if(d==1&&x!=1&&x!=n-1) return false; if(b[ii]==1) d=(d*a)%n; }

if(d!=1) return false; return true;

double quickindex1(double a,double m,double n)//实现a^m mod n 的运算 { vector b; unsigned double N=m; for(int ii=0,j=1;;ii++) { if(j>N) break; if((N>>ii)& (unsigned double) 1) b.push_back(1); else b.push_back(0);

j*=2; } double c=0,d=1; for(int i=b.size()-1;i>=0;i--) { c*=2; d=(d*d)-int((d*d)/n)*n; if(b[i]==1) { c+=1; d=(d*a)-int((d*a)/n)*n; } } return d; }

void transfer(char cypher[],double c[]) { int m[100]={0}; for(int i=0,j=0;cypher[j]!='\\0';i+=2) { if(cypher[j]==' ') { m[i]=0;m[i+1]=0; } else { m[i]=cypher[j]-; if(m[i]<10) { m[i+1]=m[i]; m[i]=0; } else { m[i+1]=m[i]%10; m[i]=m[i]/10; } } j++; } for(int k2=0;k2<2*strlen(cypher);k2++) cout<}

void main() { double c[100]={0}; double a[100]={0}; double b[100]={0}; char cypher[]=\"I LOVE THE PEOPLE'S REPUBLIC OF CHINA\"; //对“我爱中华人民共和国”加解密 transfer(cypher,c);//字母变数字的过程 for(int k1=0;c[k1]!='\\0';k1++) cout<//选取两个素数p=563，q=823 double n=0, fn=0, p=563,q=823,d=0; n=p*q;fn=(q-1)*(p-1); //选e与fn互素

for(double e=2;ed=extenEuclid(e,fn);

cout<for(int k=0,n=0;k<2*strlen(cypher);k+=4) { c[n]=m[k]*1000+m[k+1]*100+m[k+2]*10+m[k+3]; n++; }

for(;c[n-1]<1000;)//最后一个数填充零,不过此例可要可不要 c[n-1]*=10;

cout<cout<cout<四、实验结果及分析