rsa加密算法c++

RSA是一种非常流行的公钥加密算法，可以用于加密和解密数据。以下是C++实现RSA加密算法的示例代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <string>

using namespace std;

bool is_prime(int n) {
    if (n == 2 || n == 3) {
        return true;
    }
    if (n == 1 || n % 2 == 0) {
        return false;
    }
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int mod_pow(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;
}

int mod_inverse(int a, int n) {
    int t = 0, new_t = 1;
    int r = n, new_r = a;
    while (new_r != 0) {
        int quotient = r / new_r;
        int tmp_t = new_t;
        new_t = t - quotient * new_t;
        t = tmp_t;
        int tmp_r = new_r;
        new_r = r - quotient * new_r;
        r = tmp_r;
    }
    if (r > 1) {
        return -1; // a is not invertible
    }
    if (t < 0) {
        t += n;
    }
    return t;
}

int generate_random_prime(int min_value, int max_value) {
    int n = rand() % (max_value - min_value + 1) + min_value;
    while (!is_prime(n)) {
        n = rand() % (max_value - min_value + 1) + min_value;
    }
    return n;
}

int main() {
    srand((unsigned)time(NULL));
    int p = generate_random_prime(100, 1000);
    int q = generate_random_prime(100, 1000);
    int n = p * q;
    int phi = (p - 1) * (q - 1);
    int e = 0;
    do {
        e = rand() % phi + 1;
    } while (gcd(e, phi) != 1);
    int d = mod_inverse(e, phi);
    cout << "Public key (n, e): (" << n << ", " << e << ")" << endl;
    cout << "Private key (n, d): (" << n << ", " << d << ")" << endl;
    string message;
    cout << "Enter a message to be encrypted: ";
    getline(cin, message);
    cout << "Original message: " << message << endl;
    int len = message.size();
    for (int i = 0; i < len; i++) {
        int c = message[i];
        int encrypted_c = mod_pow(c, e, n);
        cout << encrypted_c << " ";
    }
    cout << endl;
    return 0;
}

该示例代码实现了一个简单的RSA加密算法，首先生成两个随机质数p和q，并计算n和phi的值。然后随机选择一个整数e作为公钥，计算其关于phi的模逆d作为私钥。接下来输入要加密的消息，并将消息中的每个字符c加密为encrypted_c，最后输出加密后的消息。