实验三 RSA算法代码实现
代码实现结果:
四、实验要求
1、在RSA算法中，求解私钥d可以采用扩展欧几里得算法和线性代入法两种方法，但这两种方法的计算效率很低（即计算d要花费很多时间，特别是数次乘积运算占用了大量计算时间，使得RSA时间复杂度增加），请你通过网络或自己设计一种及一种以上更为高效的求解d的方法，并写出详细计算过程。
2、用VC调试实验步骤给出的RSA加解密程序，结合原理分析程序中密钥是如何产生的？如何加密的？如何解密的？并在程序中给于解释。
3、你还能采用别的方法自主设计RSA公钥密码算法吗？如果能请列出相关代码。
【参考答案】
1. 在RSA算法中，求解私钥d可以采用以下方法：
① 扩展欧几里得算法(模幂乘法运算)
② 线性代入法(模幂乘法运算)
③ 平方-乘法：按平方计算模指数运算
④ 一种二进制查表方幂模快速计算方法：该方法根据指数二进制形式结构进行分组计算，记忆典型操作数，通过查表法大量减少了乘法次数。
⑤ 采用分解计算和内联汇编方法加速RSA算法的执行
⑥ 设计规划密钥空间
2.
【代码分析】
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int Euclid(int a, int n)//n>a,求n和a的最大公因数为1
{
int x,y,r;
x=n;y=a;
for (int i=0;;)
{
if(y==0)
return x;//a=0
if(y==1)
return y;//a=1
r=x%y;//a≠0,1,r=n%a
x=y;
y=r;
}
}
double extenEuclid(double a,double n)//利用扩展的Euclid计算a^-1 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"<<endl;//a=0,无乘法逆元
}
if(y3==1)
return y2;//a=1,a%n=1
Q=int(x3/y3);//Q=[n/a]
t1=x1-Q*y1;//t1=x1=1
t2=x2-Q*y2;//t2=Q
t3=x3-Q*y3;//t3=n-Qa,相当于d原理中的1=de-xfn
x1=y1;x2=y2;x3=y3;
y1=t1;y2=t2;y3=t3;//返回d的结果
}
}
bool Rabin(int a,int n)//Miler-Rabin素性测试算法对一个给定的大数进行测试
{
vector<int> b;//判断一个变量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;k<b.size();k++)
cout<<b[k];
cout<<endl;
int 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;
}//b为素数
if(d!=1)
return false;//不为素数
return true;
}
double quickindex1(double a,double m, double n)//实现a^m mod n 的运算
{
vector<int> b;
unsigned double N=m;//公钥m=e
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;
}//将m表示成二进制形式
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;
}//空格变为00
else
{
m[i]=cypher[j]-64;//A的ASCII码为65，65-64=1
if(m[i]<10)
{
m[i+1]=m[i];//m[i+1]=1,m[i]=0,所以A为01
m[i]=0;
}
else
{
m[i+1]=m[i]%10;//例如Z的ASCII码为90，90-64=26，m[i+1]=26%10=6,m[i]=[26/10]=2,所以Z对应的数字为26
m[i]=m[i]/10;
}
}
j++;
}
for(int k2=0;k2<2*strlen(cypher);k2++)
cout<<m[k2];
cout<<endl;//输出明文字母变换数据的结果
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];//两个字母一组，例如AB为0102
n++;
}
for(;c[n-1]<1000;)//最后一个数填充零，不过此例可要可不要
c[n-1]*=10;
}
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);//明文字母变数字的过程，输出结果将I LOVE......变为090012152205....
for(int k1=0;c[k1]!='\0';k1++)
cout<<c[k1]<<" ";//将4位数字整理成有效的十进制数并再次输出，目的在于后面加密计算，例如“I ”的数字0900整理后为900，“LO”的数字1215整理后为1215“ L”0020整理为20
//选取两个素数p=563，q=823
double n=0,fn=0,p=563,q=823,d=0;
n=p*q;fn=(q-1)*(p-1);
for(double e=2;e<fn;e+=3)
{
if(Euclid(e,fn)==1)
break;
} //选e使得与fn的最大公因数为1
d=extenEuclid(e,fn);//求d=e^-1 mod fn
cout<<endl<<"密码和密钥 e d and n:";
cout<<e<<" "<<d<<" "<<n<<endl;
//加密过程
cout<<endl<<"加密：";
for(int i=0;c[i]!='\0';i++)
{
a[i]=quickindex1(c[i],e,n);//实现c=E(m)=m^e mod n的运算,例如第一个加密为900^5 mod 563*823=389807
cout<<a[i]<<" ";//输出密文信息
}
cout<<endl<<"解密:";
//解密过程
for(int j=0;a[j]!='\0';j++)
{
b[j]=quickindex1(a[j],d,n);//实现m=D(c)= c^d mod n,例如第一个解密为389807^92393 mod 563*823=900
cout<<b[j]<<" ";
}
cout<<endl;
}
第二篇：RSA算法C语言代码
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
char s[100],*c;
int n,e,d,i,C,j,k=0,len;
int str[100],b[30];
unsigned gcd(unsigned a, unsigned b ) {
if(a%b==0)
return b;
else
return gcd(b,a%b);
}
void Egcd(int a, int b,int &x, int &y) { //ax-by=1 if(b==0||a==0)
{
x=1;
y=0;
return ;
}
if(a<b)
{
Egcd(a,b%a,x,y);
x=(int)(b*y+1)/a;
}
else
{
Egcd(a%b,b,x,y);
y=(int)(a*x-1)/b;
}
}
void RSA()
{
int p,q,N,Y;
printf("请输入素数p和q:");
scanf("%d %d",&p,&q);
n=p*q;
N=(p-1)*(q-1);
//printf("n=%d N=%d\n",n,N);
srand( (unsigned)time( NULL ) ); //初始化随机数
while(1) //产生随机整数e，e与N互质 {
e=rand()%N;
// printf("e==%d\n",e);
if(e==0)
continue;
if(gcd(N,e)==1)
{
break;
}
}
//printf("e=%d\n",e);
Egcd(e,N,d,Y);
// printf("d=%d Y=%d\n",d,Y);
printf("公钥PU={e=%d,n=%d}\n",e,n);
printf("私钥PR={d=%d,n=%d}\n",d,n);
}
void encrypt() //加密函数
{
len=strlen(s);
//hgprintf("len=%d\n",len);
for(i=0;i<len;i++) //去掉s[100]中的空格
{
if(s[i]<97||s[i]>122)
{
b[k]=i;
k++;
for(j=i;j<len-1;j++)
{
s[j]=s[j+1];
}
len--;
}
}
s[len]='\0'; //结束符
printf("密文是：");
for(i=0;i<len;i++)
{
C=1;
//printf("shiji=%d\n",s[i]-97); for(int j=0;j<e;j++)
{
C=(C*(s[i]-97))%n;
// printf("C=%ld\n",C); }
str[i]=C;
printf("%d ",str[i]);
}
printf("\n");
}
void decrypt() //解密函数 {
c=(char*)malloc(len*sizeof(int));
for(i=0;i<len;i++) //实现解密 {
C=1;
for(int j=0;j<d;j++)
{
C=(C*(str[i]))%n;
// printf("C=%ld\n",C); }
// printf("C=%d\n",C);
c[i]=C+97;
}
c[i] = '\0';
// puts(c);
for(int z=0;z<k;z++) //加空格 {
for(i=0; i<len; i++)
{
if (i==b[z])
{
for(j=len;j>i;j--)
{
c[j]=c[j-1];
}
c[i]=' ';
len++;
b[z+1]=b[z+1]+(z+1);
break;
}
}
}
c[len] = '\0';
printf("明文：");
puts(c);
}
int function()//系统功能选择页面
{
int choice;
printf("==============================================================\n"); printf(" 欢迎进入RSA算法 \n"); printf(" 1--加密 \n"); printf(" 2--解密 \n"); printf(" 3--退出 \n"); printf("==============================================================\n"); printf("请输入要选择的功能号：");
scanf("%d",&choice);
return choice;
}
int main()
{
int function();
int fc;
printf("请输入初始明文(小写)：");
gets(s);
// puts(s);
RSA(); //提供私钥和公钥
while(1)
{
fc=function();
if(fc==1) //加密
encrypt();
else if(fc==2) //解密
decrypt() ;
else if(fc==3)
break;
else
printf("输入有误，请重新输入！/n");
}
return 0;
}