RSA 算法
#include <iostream.h>#include <math.h>
long code(long m,long e,long n)//-----------加解密函数:用c=m^e(modn)加密，用m=c^d(modn)解密
{ long c=1;
e=e+1;
while(e!=1)
{
c=c*m;
c=c%n;
e--;
}
return c;
}
int gcd(long a,long b)//--------------------判断两个数是否互素
{
long r0=a;
long r1=b;
int q,temp;
while(r1!=0)
{
q=r0/r1;
temp=r0;
r0=r1;
r1=temp-q*r1;
}
if(r0==1)//------------------------------最大公因数为1时两数互素
return 1;
else return 0;
}
long privatekey(long a,long b)//-------------用欧几里德算法求私钥d
{
long r,r1=1;
long r0=b;
long s0,t0,e,s1,q,temprivatekey;
r1=a;
t0=0;
e=1;
s0=1;
s1=0;
q=r0/r1;
r=r0-q*r1;
while(r>0)
{
temprivatekey=t0-q*e;
t0=e;
e=temprivatekey;
temprivatekey=s0-q*s1;
s0=s1;
s1=temprivatekey;
r0=r1;
r1=r;
q=r0/r1;
r=r0-q*r1;
}
while(e<0)
{
e=e+b;
}
return e;
}
void main()//----------------------------------------主函数
{
long p,q,e,d,m,n,t;
cout<<"请输入两个素数 p,q: ";
cin>>p>>q;
n=p*q;
cout<<"n为 :"<<n<<endl;
t=(p-1)*(q-1);//------------------------------------欧拉函数值
cout<<"n的欧拉函数值 :"<<t<<endl;
cout<<"请输入公钥e: ";
cin>>e;//-------------------------------------------输入公钥e,满足t>e>1
int u;
u=gcd(e,t);//----------------------------------------判断e是否与n的欧拉函数值互素
if(1<e&&e<t&&u==0)
{
cout<<"请重新输入: ";
cin>>e;
}
int w;
cout<<"输入1加密,输入2解密:";
cin>>w;
switch(w)//--------------------------------------------w为1时加密，为2时解密
{
case 1 ://----------------------------------------------加密
{
cout<<"请输入明文:";
cin>>m;//---------------------------------------输入明文
if(m<=n)
cout<< "密文为:"<<code(m,e,n)<<endl;//----------明文数值小于n时直接加密
else
{
long i=0,g,h;
g=n;
h=m;
while(g!=0)//----------------------------------------求n的长度
{
g/=10;
i++;
}
long j=0;
while(h!=0)//----------------------------------------求明文长度
{
h/=10;
j++;
}
long x=0,long c;//-----------------------------数组c用来存放加密后的各个分组
int k=0;//-------------------------------------------k将记录明文分的组数
while(j!=0)
{
x=m/pow(10,j-i);
if(x>n)
{
x=x/10;
c=code(x,e,n);
m=m-x*pow(10,j-i+1);
j=j-1;
k++;
}
else
{
c=code(x,e,n);
m=m-x*pow(10,j-i);
j=j-2;
k++;
}
if(i>j)//----------------------------------------------最后一个分组的长度小于n的长度时直接加密
c=code(m,e,n);
}
cout<<"密文输出:";
for(long l=0;l<k;l++)
cout<<c;
cout<<endl;
}
break;
}
case 2 ://------------------------------------------------解密
{
cout<<"请输入密文:"<<endl;
cin>>m;
long d;
d=privatekey(e,t);
if(m<=n)
cout<< "密文为:"<<code(m,d,n)<<endl;
else
{
long i=0,g,h;
g=n;
h=m;
while(g!=0)
{
g/=10;
i++;
}
long j=0;
while(h!=0)
{
h/=10;
j++;
}
long x=0,long c;
int k=0;
while(j!=0)
{
x=m/pow(10,j-i);
if(x>n)
{
x=x/10;
c=code(x,d,n);
m=m-x*pow(10,j-i+1);
j=j-1;
k++;
}
else
{
c=code(x,d,n);
m=m-x*pow(10,j-i);
j=j-2;
k++;
}
if(i>j)
c=code(m,d,n);
}
for(long l=0;l<k;l++)
cout<<c;
cout<<endl;
}
break;
}
}
}
页:
[1]