rsa加密算法c++实现原理

RSA加密算法是一种非对称加密算法，它的安全性基于大质数分解的难度。在实现RSA加密算法时，需要进行以下步骤：

1. 选择两个大质数p和q，计算它们的乘积N=p*q。

2. 计算欧拉函数φ(N)=(p-1)*(q-1)。

3. 选择一个整数e，满足1<e<φ(N)且e与φ(N)互质。

4. 计算e关于φ(N)的模逆元d，即满足(e*d)%φ(N)=1的最小正整数d。

5. 公钥为(N,e)，私钥为(N,d)。

6. 加密时，将明文M转化为整数m，计算密文C=m^e mod N。

7. 解密时，将密文C转化为整数c，计算明文M=c^d mod N。

以下是C++代码实现：

#include<bits/stdc++.h>
using namespace std;

// 定义大数类型
typedef long long ll;

// 计算a的b次方对c取模的结果
ll qmi(ll a, ll b, ll c){
    ll res = 1 % c;
    while(b){
        if(b & 1) res = res * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return res;
}

// 判断是否为质数
bool is_prime(ll x){
    if(x < 2) return false;
    for(ll i = 2; i <= sqrt(x); i++){
        if(x % i == 0) return false;
    }
    return true;
}

// 生成指定范围内的随机质数
ll get_prime(ll l, ll r){
    ll x = rand() % (r - l + 1) + l;
    while(!is_prime(x)) x = rand() % (r - l + 1) + l;
    return x;
}

// 求最大公约数
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

// 求模逆元
ll get_inv(ll a, ll b){
    if(b == 1) return 1;
    ll d = get_inv(b, a % b);
    return (1 - a * d) / b + b;
}

// 生成RSA公私钥对
void RSA(ll &p, ll &q, ll &n, ll &e, ll &d){
    // 选择两个大质数p和q，计算N=p*q
    p = get_prime(10000, 50000), q = get_prime(10000, 50000);
    n = p * q;

    // 计算欧拉函数φ(N)
    ll phi = (p - 1) * (q - 1);

    // 选择e，满足1<e<phi且e与phi互质
    e = rand() % phi + 1;
    while(gcd(e, phi) != 1) e = rand() % phi + 1;

    // 计算d，使得e*d mod phi = 1
    d = get_inv(e, phi);
}

int main(){
    srand(time(NULL));
    ll p, q, n, e, d;
    RSA(p, q, n, e, d);
    cout << "公钥：" << n << " " << e << endl;
    cout << "私钥：" << n << " " << d << endl;

    ll m;
    cout << "请输入明文m：";
    cin >> m;

    // 加密
    ll c = qmi(m, e, n);
    cout << "密文c：" << c << endl;

    // 解密
    ll mm = qmi(c, d, n);
    cout << "解密后的明文：" << mm << endl;

    return 0;
}

其中，get_prime函数用于生成指定范围内的随机质数；gcd函数用于求最大公约数；get_inv函数用于求模逆元。RSA函数用于生成RSA公私钥对，输入为p和q的上下界，输出为p、q、n、e和d。加密时，将明文m使用公钥加密得到密文c；解密时，将密文c使用私钥解密得到明文m。