【学习/笔记】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]
[2]: https://blog.csdn.net/kinnisoy/article/details/91049381 “RSA密码的实现-你也能看的懂的python实现方法”