【学习/笔记】RSA算法的c++实现

emmm先转载一篇文章吧
RSA算法原理（一）
非常推荐的一篇文章，我原本就想写个讲RSA算法的文章，然后发现这篇文章基本就可以满足我的要求了，所以就直接转过来了。
这里主要讲c++代码。

#include <bits/stdc++.h>
#include <math.h>
#include<ctime>
using namespace std;
#define randomInt(a,b) (rand()%(b-a+1)+a)

typedef long long int ll;
#define int ll
 
 struct rsakeys{
     int p, q, n, fn, d, e;
 };
 
 rsakeys* rsakey;
 
ll mod_mul(ll a, ll b, ll mod){
    ll res = 0;
    while (b){
        if (b & 1)
            res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}
 
ll mod_pow(ll a, ll n, ll mod){
    ll res = 1;
    while (n){
        if (n & 1)
            res = mod_mul(res, a, mod);
        a = mod_mul(a, a, mod);
        n >>= 1;
    }
    return res;
}
 
// Miller-Rabin随机算法检测n是否为素数
bool Miller_Rabin(ll n){
    if (n == 2)
        return true;
    if (n < 2 || !(n & 1))
        return false;
    ll m = n - 1, k = 0;
    while (!(m & 1))
    {
        k++;
        m >>= 1;
    }
    for (int i = 1; i <= 20; i++)  // 20为Miller-Rabin测试的迭代次数
    {
        ll a = rand() % (n - 1) + 1;
        ll x = mod_pow(a, m, n);
        ll y;
        for (int j = 1; j <= k; j++)
        {
            y = mod_mul(x, x, n);
            if (y == 1 && x != 1 && x != n - 1)
                return false;
            x = y;
        }
        if (y != 1)
            return false;
    }
    return true;
}

int gcd(int a,int b){
      int r;
      while(b){
          r=a%b;
          a=b;
          b=r;
      }
      return a;
}

int creat_prime(){
    int tmp = 4;
    while(!Miller_Rabin(tmp))tmp=rand();
    return tmp;
}

int create_keys(rsakeys* key){
    srand((unsigned)time(NULL));
    
    key->p = creat_prime();
    cout<<"Your p is: "<<key->p<<endl;
    key->q = creat_prime();
    cout<<"Your q is: "<<key->q<<endl;
    
    key->n=key->p*key->q;
    cout<<"Your n is: "<<key->n<<endl;
    key->fn = (key->p-1) * (key->q-1);
    cout<<"Your fn is: "<<key->fn<<endl;
    
    while(1){
        key->e = rand()%key->fn;
        if(gcd(key->e,key->fn)==1)break;
    }
    cout<<"Your e is: "<<key->e<<endl;
    
    int k = 1;
    while((k*key->fn+1)%key->e){
        k++;
    }
    key->d = (k*key->fn+1)/(key->e);
    cout<<"Your d is: "<<key->d<<endl;
}

int create_keys_by_pq(int p, int q, rsakeys* key){
    cout<<p<<" "<<q<<endl;
    key->n = p * q;
    cout<<"Your n is: "<<key->n<<endl;
    key->fn = (p-1) * (q-1);
    cout<<"Your fn is: "<<key->fn<<endl;
    
    while(1){
        key->e = rand()%key->fn;
        if(gcd(key->e,key->fn)==1)break;
    }
    cout<<"Your e is: "<<key->e<<endl;
    
    int k = 1;
    while((k*key->fn+1)%key->e){
        k++;
    }
    key->d = (k*key->fn+1)/(key->e);
    cout<<"Your d is: "<<key->d<<endl;
}

int write_to_file(rsakeys* key){
    ofstream d, e, n;
    
    d.open("d");
    d<<key->d;
    e.open("e");
    e<<key->e;
    n.open("n");
    n<<key->n;
    
    d.close();e.close();n.close();
    return 0;
}

int read_file(rsakeys* key){
    ifstream d, e, n;
    
    d.open("d");
    d>>key->d;
    e.open("e");
    e>>key->e;
    n.open("n");
    n>>key->n;
    
    d.close();e.close();n.close();
    return 0;
}

signed main(){
    rsakey = (rsakeys*)malloc(sizeof(rsakeys));
    cout<<"============================================================"<<endl;
    cout<<"1. Creat keys and write to file."<<endl;
    cout<<"2. Creat keys by given p and q and write to file."<<endl;
    cout<<"3. Read keys from file."<<endl;
    cout<<"4. Encrypt a number."<<endl;
    cout<<"5. Decrypt a number."<<endl;
    cout<<"============================================================"<<endl;
    
    int d, e, n;
    while(1){
        char command[64];
        ll msg;
        ll key;
        ll inn;
        scanf("%s",command);
        if(!strcmp(command,"1")){
            create_keys(rsakey);
            write_to_file(rsakey);
        }
        if(!strcmp(command,"2")){
            int p,q;
            cin>>p>>q;
            create_keys_by_pq(p,q,rsakey);
            write_to_file(rsakey);
        }
        if(!strcmp(command,"3")){
            read_file(rsakey);
        }
        if(!strcmp(command,"4")){
            scanf("%d",&msg);
            cout<<mod_pow(msg,rsakey->e,rsakey->n)<<endl;
        }
        if(!strcmp(command,"5")){
            scanf("%d",&msg);
            cout<<mod_pow(msg,rsakey->d,rsakey->n)<<endl;
        }
    }
    return 0;
}

就酱啦，再扔篇参考文章溜了。。。
[[2]RSA密码的实现-你也能看的懂的python实现方法][2]