RSA加密算法实现C++

RSA算法是一种非对称加密算法，它通过两个密钥（公钥和私钥）来进行加密和解密。以下是C++实现RSA加密算法的示例代码：

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

//计算a^b mod n的值
int modpow(int a, int b, int n){
    int res = 1;
    while(b > 0){
        if(b & 1){
            res = (res * a) % n;
        }
        a = (a * a) % n;
        b >>= 1;
    }
    return res;
}

//判断一个数是否为素数
bool isPrime(int n){
    if(n < 2) return false;
    int sqrtn = sqrt(n);
    for(int i = 2; i <= sqrtn; i++){
        if(n % i == 0) return false;
    }
    return true;
}

//计算欧拉函数phi(n)的值
int phi(int n){
    int res = n;
    if(n % 2 == 0){
        res /= 2;
        while(n % 2 == 0) n /= 2;
    }
    for(int i = 3; i <= sqrt(n); i += 2){
        if(n % i == 0){
            res = res / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1) res = res / n * (n - 1);
    return res;
}

//生成RSA密钥对
void genRSAKey(int &n, int &e, int &d){
    int p, q;
    do{
        p = rand() % 100 + 1;
    }while(!isPrime(p));
    do{
        q = rand() % 100 + 1;
    }while(!isPrime(q));
    n = p * q;
    int phi_n = phi(n);
    do{
        e = rand() % (phi_n - 2) + 2;
    }while(__gcd(e, phi_n) != 1);
    d = 1;
    while((d * e) % phi_n != 1){
        d++;
    }
}

//RSA加密
int RSAEncrypt(int m, int e, int n){
    return modpow(m, e, n);
}

//RSA解密
int RSADecrypt(int c, int d, int n){
    return modpow(c, d, n);
}

int main(){
    int n, e, d;
    genRSAKey(n, e, d); //生成RSA密钥对
    cout << "公钥: (" << n << ", " << e << ")" << endl;
    cout << "私钥: (" << n << ", " << d << ")" << endl;
    int m;
    cout << "请输入要加密的明文: ";
    cin >> m;
    int c = RSAEncrypt(m, e, n); //加密
    cout << "加密后的密文: " << c << endl;
    int m2 = RSADecrypt(c, d, n); //解密
    cout << "解密后的明文: " << m2 << endl;
    return 0;
}

上述代码实现了RSA算法的关键步骤，包括生成RSA密钥对、RSA加密和RSA解密。其中，`modpow`函数用于计算幂取模，`isPrime`函数用于判断一个数是否为素数，`phi`函数用于计算欧拉函数的值，`genRSAKey`函数用于生成RSA密钥对，`RSAEncrypt`函数用于加密，`RSADecrypt`函数用于解密。在实际应用中，需要将生成的RSA密钥对保存起来以备后续使用。