RSA加密算法代码实现

以下是 C++ 代码实现 RSA 加密算法：

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// 计算 a 和 b 的最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

// 计算 a 的 b 次方对 n 取模的结果
int pow_mod(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;
}

// 生成公钥和私钥
void generate_keypair(int p, int q, int& n, int& e, int& d) {
    n = p * q;
    int Euler_n = (p - 1) * (q - 1);

    // 选择 e，使得 e 和 Euler_n 互质
    do {
        e = rand() % Euler_n + 1;
    } while (gcd(e, Euler_n) != 1);

    // 计算 d，使得 d * e = 1 (mod Euler_n)
    int k = 1;
    while (true) {
        if ((k * Euler_n + 1) % e == 0) {
            d = (k * Euler_n + 1) / e;
            break;
        }
        k++;
    }
}

// 加密明文 m
int encrypt(int m, int e, int n) {
    return pow_mod(m, e, n);
}

// 解密密文 c
int decrypt(int c, int d, int n) {
    return pow_mod(c, d, n);
}

int main() {
    srand((unsigned int)time(NULL)); // 设置随机数种子

    int p = 61, q = 53;
    int n, e, d;
    generate_keypair(p, q, n, e, d);

    cout << "p = " << p << endl;
    cout << "q = " << q << endl;
    cout << "n = " << n << endl;
    cout << "e = " << e << endl;
    cout << "d = " << d << endl;

    int m = 1234;
    int c = encrypt(m, e, n);
    int m_decrypted = decrypt(c, d, n);

    cout << "m = " << m << endl;
    cout << "c = " << c << endl;
    cout << "m_decrypted = " << m_decrypted << endl;

    return 0;
}

该程序使用了 rand 函数来生成随机数，需要包含头文件 `cstdlib` 和 `ctime`。

程序中首先定义了三个函数，分别是计算最大公约数 gcd，计算幂次方对模数取模的函数 pow_mod，以及生成公钥和私钥的函数 generate_keypair。

generate_keypair 函数中，首先计算 n 和 Euler_n，然后随机选择 e，判断 e 和 Euler_n 是否互质，如果不互质则重新选择 e。接着使用一个循环，计算 d，使得 d * e = 1 (mod Euler_n)。具体来说，从 k = 1 开始循环，判断 k * Euler_n + 1 是否能被 e 整除，如果能，则计算出 d 并退出循环。

encrypt 和 decrypt 函数分别用于加密和解密。

最后在主函数中，使用给定的质数 p 和 q 生成公钥和私钥，加密明文 m，并解密密文 c，输出结果。

注意，由于生成随机数的使用，每次运行程序的结果可能不同。