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[500],k=0,i;
    __int64 c, d;
    for(;m!=0;m>>=1){
        if(m%2==0)
            b[k]=0;
        else
            b[k]=1;
        k++;
    }
    c=0;
    d=1;
    for(i=k;i>=0;i--){
        c=2*c;
        d=(d*d)%n;
        if(b[i]==1){
            c=c+1;
            d=(d*a)%n;
        }
        //printf("%lld ",c);
        //printf("%lld\n",d);
    }
    return d;
}
//確定性測試
//n素數
bool RSA::Prime_test(__int64 n){
    __int64 r=2;
    while(r<Sqrt(n)){
        if(n%r==0)
            return false;
        r=r+1;
    }
    return true;
}
//概率測試
//n為素數，a<n
bool RSA::Witness(__int64 a,__int64 n){
    __int64 m=n-1;
    __int64 b[500],k=0,i;
    __int64 d,x;
    for(;m!=0;m>>=1){
        if(m%2==0)
            b[k]=0;
        else
            b[k]=1;
        k++;
    }
    d=1;
    for(i=k;i>=0;i--){
        x=d;
        d=(d*d)%n;
        if(d==1&&x!=1&&x!=n-1)
            return true;//合數
        if(b[i]==1)
            d=(d*a)%n;
    }
    if(d!=1)
        return true;//合數
    return false;//可能是素數
}
//歐幾里德演算法
__int64 RSA::Euclid(__int64 a,__int64 b){
    __int64 x=b,y=a,r=0;
    if(y>0){
        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=1,x2=0,x3;
    __int64 y1=0,y2=1,y3;
    __int64 t1,t2,t3,q;
    x3=(n>=a)?n:a;//大的數
    y3=(n>=a)?a:n;//小的數
    while(1){
        if(y3==0){
            *d=x3;
            return false;
        }
        if(y3==1){
            *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=0; //
    int times=0;//測試素數次數
    __int64 a,n=0;
    while(flag==0){
        //步驟1
        step_1:flag=0;
        n = (__int64)(rand()%(RAND_MAX_64 - RAND_MIN_64+1))+RAND_MIN_64;    
        n=(n/2)*2+1;
            printf("%lld%\r",n);
        //步驟2
        if(Prime_test(n)==false){
            //返回步驟1
            goto step_1;
        }
        else{
            //步驟3
            step_3:a = (__int64)(rand()%(n-1-0+1))+1;//0<a<n
            //步驟4
            if(Witness(a,n)==true){
                //返回步驟1
                goto step_1;
            }
            else{
                times++;
                if(times>=Times){
                    flag=1;
                    return n;
                }
                else{
                    //返回步驟3
                    goto step_3;
                }
            }
        }
    }
    return 0;
}
//密鑰的生成
void RSA::getKey(){
    this->p = get_Prime();
    this->q = get_Prime();
    this->n = this->p*this->q;//n=p*q
    this->o = (this->p-1)*(this->q-1);//φ(n)=(p-1)(q-1)
    do{
        this->e = (__int64)(rand()%(this->o+1));//0<e<φ(n)
    }while(1==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 = 1 ,up = num;
   if(up > Max_64) up = Max_64;
   __int64 mk = 0;
   while(low <= up){
      mid = (low + up) / 2;
      if(mid * mid > num){
         up = mid - 1;
      }
      else{
         low = mid + 1;
         mk = mid;
      }
   }
   return mk;
}

TEST.cpp
#include"RSA.h"
#include<stdio.h>

int main(){
         __int64 M=0,C=0;
        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 0;
}