RSA算法

RSA.h
#ifndef _RSA_H
#define _RSA_H
#include<stdio.h>
#include<iostream>
#include<math.h>
/*
密钥产生：
1.随机选定两个大素数p, q.
2.计算公钥和私钥的公共模数 n = pq .
3.计算模数n的欧拉函数 φ(n) .
4.选定一个正整数e, 使1 < e < φ(n) , 且e与φ(n)互质.
5.计算d, 满足 de ≡ 1 (mod φ(n) ), (k为某个正整数).
6.n与e决定公钥, n与d决定私钥.
*/
/*
加密：C=M^e mod n
*/
/*
解密：C=M^d mod n
*/
//#define RAND_MAX_64 9223372036854775807//最大素数2^63-1
//#define RAND_MIN_64 2147483647//最小素数2^31-1
#define RAND_MAX_64 1000000
#define RAND_MIN_64 1000
#define Max_64 9223372036854775807
#define Times 10//测试素数次数class RSA
{
public:
RSA();
~RSA(void);
void encryption(__int64 *M,__int64 *C);
void decryption(__int64 *C,__int64 *M);
void getKey();//生成密钥
__int64 get_p(){return p;};
__int64 get_q(){return q;};
__int64 get_n(){return n;};
__int64 get_o(){return o;};
__int64 get_e(){return e;};
__int64 get_d(){return d;};
private:
__int64 Sqrt(__int64 num); //大数开平方根
__int64 get_Prime(); //得到大素数
__int64 mod(__int64 a,__int64 m,__int64 n);//快速求模
__int64 Euclid(__int64 a,__int64 b); //欧几里德算法
bool Prime_test(__int64 n); //确定性测试
bool Witness(__int64 a,__int64 n); //概率测试
bool Extended_Euclid(__int64 a,__int64 n,__int64 *d); //扩展的欧几里德算法
//公钥KU={e,n}
//私钥KR={d,p,q}/{d,n}
__int64 p;//素数p
__int64 q;//素数q
__int64 n;//n=p*q
__int64 o;//φ(n)=(p-1)(q-1)
__int64 e;//随机整数
__int64 d;//d=e^-1
};
#endif

RSA.cpp
#include"RSA.h"
//构造函数
RSA::~RSA(){};
//析构函数
RSA::RSA(){};
//加密
void RSA::encryption(__int64 *M,__int64 *C){
*C=RSA::mod(*M,this->e,this->n);
}
//解密
void RSA::decryption(__int64 *C,__int64 *M){
*M=RSA::mod(*C,this->d,this->n);
}
//快速求模
//d=a^m mod n b[k]=m=(101010010)
__int64 RSA::mod(__int64 a,__int64 m,__int64 n){
__int64 b[],k=,i;
__int64 c, d;
for(;m!=;m>>=){
if(m%==)
b[k]=;
else
b[k]=;
k++;
}
c=;
d=;
for(i=k;i>=;i--){
c=*c;
d=(d*d)%n;
if(b[i]==){
c=c+;
d=(d*a)%n;
}
//printf("%lld ",c);
//printf("%lld\n",d);
}
return d;
}
//确定性测试
//n素数
bool RSA::Prime_test(__int64 n){
__int64 r=;
while(r<Sqrt(n)){
if(n%r==)
return false;
r=r+;
}
return true;
}
//概率测试
//n为素数，a<n
bool RSA::Witness(__int64 a,__int64 n){
__int64 m=n-;
__int64 b[],k=,i;
__int64 d,x;
for(;m!=;m>>=){
if(m%==)
b[k]=;
else
b[k]=;
k++;
}
d=;
for(i=k;i>=;i--){
x=d;
d=(d*d)%n;
if(d==&&x!=&&x!=n-)
return true;//合数
if(b[i]==)
d=(d*a)%n;
}
if(d!=)
return true;//合数
return false;//可能是素数
}
//欧几里德算法
__int64 RSA::Euclid(__int64 a,__int64 b){
__int64 x=b,y=a,r=;
if(y>){
r=x%y;
x=y;
y=r;
}
return x;
}
//扩展的欧几里德算法
//d=e^-1 mod n
bool RSA::Extended_Euclid(__int64 a,__int64 n,__int64 *d){
__int64 x1=,x2=,x3;
__int64 y1=,y2=,y3;
__int64 t1,t2,t3,q;
x3=(n>=a)?n:a;//大的数
y3=(n>=a)?a:n;//小的数
while(){
if(y3==){
*d=x3;
return false;
}
if(y3==){
*d=y2;
return true;
}
q=x3/y3;
t1=x1-q*y1;
t2=x2-q*y2;
t3=x3-q*y3;
x1=y1;x2=y2;x3=y3;
y1=t1;y2=t2;y3=t3;
}
}
//得到大素数
__int64 RSA::get_Prime(){
int flag=; //
int times=;//测试素数次数
__int64 a,n=;
while(flag==){
//步骤1
step_1:flag=;
n = (__int64)(rand()%(RAND_MAX_64 - RAND_MIN_64+))+RAND_MIN_64;
n=(n/)*+;
printf("%lld%\r",n);
//步骤2
if(Prime_test(n)==false){
//返回步骤1
goto step_1;
}
else{
//步骤3
step_3:a = (__int64)(rand()%(n--+))+;//0<a<n
//步骤4
if(Witness(a,n)==true){
//返回步骤1
goto step_1;
}
else{
times++;
if(times>=Times){
flag=;
return n;
}
else{
//返回步骤3
goto step_3;
}
}
}
}
return ;
}
//密钥的生成
void RSA::getKey(){
this->p = get_Prime();
this->q = get_Prime();
this->n = this->p*this->q;//n=p*q
this->o = (this->p-)*(this->q-);//φ(n)=(p-1)(q-1)
do{
this->e = (__int64)(rand()%(this->o+));//0<e<φ(n)
}while(==Euclid(this->e,this->o));//e与φ(n)互质
//this->e = 3;
if(true==Extended_Euclid(this->e,this->o,&(this->d))){
while(this->d<=Sqrt(Sqrt(this->n))){
Extended_Euclid(this->e,this->o,&(this->d));
}
printf("密钥生成成功：%lld\n",this->d);
}
else{
RSA::getKey();
}
}
//大数开根
__int64 RSA::Sqrt(__int64 num){
__int64 low ,mid ,up;
low = ,up = num;
if(up > Max_64) up = Max_64;
__int64 mk = ;
while(low <= up){
mid = (low + up) / ;
if(mid * mid > num){
up = mid - ;
}
else{
low = mid + ;
mk = mid;
}
}
return mk;
}

TEST.cpp
#include"RSA.h"
#include<stdio.h>int main(){
__int64 M=,C=;
RSA rsa = RSA();
printf("----------生成密钥----------\n");
rsa.getKey();
printf("----------输出密钥----------\n");
printf("p:%lld\n",rsa.get_p());
printf("q:%lld\n",rsa.get_q());
printf("n:%lld\n",rsa.get_n());
printf("o:%lld\n",rsa.get_o());
printf("e:%lld\n",rsa.get_e());
printf("d:%lld\n",rsa.get_d());
printf("----------加密信息----------\n");
printf("请输入明文：\n");
scanf("%lld",&M);
rsa.encryption(&M,&C);
printf("加密后密文:%lld\n",C);
printf("----------解密信息----------\n");
printf("请输入密文：\n");
scanf("%lld",&C);
rsa.decryption(&C,&M);
printf("解密后明文:%lld\n",M); system("pause");
return ;
}