RSA加密算法C++代码

RSA加密算法是一种非对称加密算法，以下是++代码实现：

#include <iostream>
#include <cmath>
using namespace std;

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

// 获取一个指定范围内的随机质数
int get_random_prime(int min_val, int max_val) {
    int n = rand() % (max_val - min_val + 1) + min_val;
    while (!is_prime(n)) {
        n = rand() % (max_val - min_val + 1) + min_val;
    }
    return n;
}

// 求最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// 扩展欧几里得算法求逆元
int ext_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = ext_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// RSA加密
int rsa_encrypt(int m, int e, int n) {
    int c = 1;
    for (int i = 0; i < e; i++) {
        c = (c * m) % n;
    }
    return c;
}

// RSA解密
int rsa_decrypt(int c, int d, int n) {
    int m = 1;
    for (int i = 0; i < d; i++) {
        m = (m * c) % n;
    }
    return m;
}

int main() {
    // 选择两个不相等的质数p和q
    int p = get_random_prime(100, 1000);
    int q = get_random_prime(100, 1000);
    while (p == q) {
        q = get_random_prime(100, 1000);
    }

    // 计算n=p*q, phi(n)=(p-1)*(q-1)
    int n = p * q;
    int phi_n = (p - 1) * (q - 1);

    // 选择一个与phi(n)互质的数e，计算d=e^(-1) mod phi(n)
    int e = 65537;
    int x, y;
    int d = ext_gcd(e, phi_n, x, y);
    if (d != 1) {
        cout << "error: e and phi(n) are not coprime" << endl;
        return 0;
    }
    d = (x % phi_n + phi_n) % phi_n;

    // 显示公钥和私钥
    cout << "public key: (" << e << ", " << n << ")" << endl;
    cout << "private key: (" << d << ", " << n << ")" << endl;

    // 加密和解密
    int m = 123456;
    int c = rsa_encrypt(m, e, n);
    int m2 = rsa_decrypt(c, d, n);
    cout << "m = " << m << endl;
    cout << "c = " << c << endl;
    cout << "m2 = " << m2 << endl;

    return 0;
}

需要注意的是，RSA加密算法使用的是大数计算，需要使用高精度库或者自己实现高精度计算。此处为了方便起见，没有使用高精度库。