#include"iostream"
#include"stdlib.h"
#include"time.h"
using namespace std;
typedef struct RSA_PARAM_Tag
{
unsigned __int64 p,q;
unsigned __int64 f;
unsigned __int64 n,e;
unsigned __int64 d;
unsigned __int64 s;
} RSA_PARAM;
const static long g_PrimeTable[]=
{
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97
};
const static long g_PrimeCount=sizeof(g_PrimeTable)/sizeof(long);
const unsigned __int64 multiplier=12747293821;
const unsigned __int64 adder=1343545677842234541;
class RandNumber
{
private:
unsigned __int64 randSeed;
public:
RandNumber(unsigned __int64 s=0);
unsigned __int64 Random(unsigned _int64 n);
}
RandNumber::RandNumber(unsigned __int64 s)
{
if(!s)
{
randSeed=(unsigned __int64)time(NULL);
}
else
{
randSeed=s;
}
}
unsigned __int64 RandNumber::Random(unsigned __int64 n)
{
randSeed=multiplier*randSeed+adder;
return randSeed%n;
}static RandNumber g_Rnd;
unsigned __int64 MulMod(unsigned __int64 a,unsigned __int64 b,unsigned __int64 n)
{
return a*b%n;
}
unsigned __int64 PowMod(unsigned __int64 &base,unsigned __int64 &pow,unsigned __int64 &n)
{
unsigned __int64 a=base,b=pow,c=1;
while(b)
{
while(!(b&1))
{
b>>=1;
a=MulMod(a,a,n);
} b--;
c=MulMod(a,c,n);
}return c;
}
long RabinMillerKnl(unsigned __int64 &n)
{
unsigned __int64 b,m,j,v,i;
m=n-1;
j=0;
while(!(m&1))
{
++j;
m>>=1;
}
b=2+g_Rnd.Random(n-3);
v=PowMod(b,m,n);
if(v==1)
{
return 1;
}
i=1;
while(v!=n-1)
{
if(i==j)
{
return 0;
}
// / v=(v*v)%n;
++i;
return 1;
}
}
long RabinMoller(unsigned __int64 &n,long loop)
{
long i;
for (i=0;i<g_PrimeCount;i++)
{
if(n%g_PrimeTable==0)
{
return 0;
}
}
for(i=0;i<loop;i++)
{
if(!RabinMliierKnl(n))
{
return 0;
}
}return 1;
}
unsigned __int64 RandomPrime(char bits)
{
unsigned __int64 base;
do
{
base=(unsigned long)1<<(bits-1);
base+=g_Rnd.Random(base);
base|=1;
}while(!RabinMillwe(base,30));
return base;
}
unsigned _int64 EuclidGcd(unsigned _int64 &p,unsigned _int64 &q)
{
unsigned __int64 a=p>q?p:q;
unsigned __int64 b=p<q?p:q;
unsigned __int64 t;
if(p==q)
{
return p;
}
else
{
while(b)
{
a=a%b;
t=a;
a=b;
b=t;
}
return a;
}
}
unsigned __int64 SteinGcd(unsigned __int64 &p,unsigned __int64 &q)
{
unsigned __int64 a=p>q?p:q;
unsigned __int64 b=p<q?p:q;
unsigned __int64 t,r=1;
if(p==q)
{
return p;
}
else
{
while((!(a&1))&&(!(b&1)))
{
r<<=1;
a>>=1;
b>>=1;
}
if(!(a&1))
{
t=a;
a=b;
b=t;
}
do
{
while(!(b&1))
{
b>>=1;
}
if(b<a)
{
t=a;
a=b;
b=t;
}
b=(b-a)>>=1;
}while(b);
return r*a;
}
}
unsigned _int64 Euclid(unsigned __int64 &a,unsigned __int64 &b)
{
unsigned __int64 m,e,i,j,x,y;
long xx,yy;
m=b;
e=a;
x=0;
y=1;
xx=1;
yy=1;
while(e)
{
i=m/e;
j=m%e;
m=e;
e=j;
j=y;
y*=i;
if(xx==yy)
{
if(x>y)
{
y=x-y;
}
else
{
y-=x;
yy=0;
}
}
else
{
y+=x;
xx=1-xx;
yy=1-yy;
} x=j;
}
if(xx==0)
{
x=b-x;
}
return x;
}
RSA_PARAM RsaGetParam(void)
{
RSA_PARAM Rsa={0};
unsigned __int64 t;
Rsa.p=RandomPrime(16);
Rsa.q=RandomPrime(16);
Rsa.n=Rsa.p*Rsa.q;
Rsa.f=(Rsa.p-1)*(Rsa.q-1);
do
{
Rsa.e=g_Rnd.Random(65536);
Rsa.e|=1;
}while(SteinGcd(Rsa.e,Rsa.f)!=1);Rsa.d=Euclid(Rsa.e, Rsa.f);
Rsa.s=0;
t=Rsa.n>>1;
while(t)
{
Rsa.s++;
t>>=1;
return Rsa;
}
}
void TestRSA(void)
{
RSA_PARAM r;
char pSrc[]="abcdefghijklmnopqrstuvwxyz";
const unsigned long n=sizeof(pSrc);
unsigned char *q,pDec[n];
unsigned __int64 pEnc[n];
unsigned long i;
r=RsaGetParam();
cout<<"p="<<r.p<<endl;
cout<<"q="<<r.q<<endl;
cout<<"f=(p-1)*(q-1)="<<r.f<<endl;
cout<<"n=p*q="<<r.n<<endl;
cout<<"e="<<r.e<<endl;
cout<<"d="<<r.d<<endl;
cout<<"s="<<r.s<<endl;
cout<<"Source:"<<pSrc<<endl;
q=(unsigned char *)pSrc:
cout<<"Encode:";
for(i=0;i<n;i++)
{
pEnc[i]=PowMod(q[i],r.e,r.e);
cout<<hex<<pEnc[i]<<" ";
}cout<<endl;
cout<<"Decode:";
for(i=0;i<n;i++)
{
pDec=PowMod(pEnc,r.d,r.n);
cout<<hex<<(unsigned long)pDec<<" ";
}cout<<endl;
cout<<(char *)pDec<<endl;
}
int main(void)
{
TestRSA();
return 0;
}
//这是我从网上找到的关于RSA加密的算法,但我的编译通不过，哪位大虾帮忙指点指点~~~
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
