编程实现RSA密码系统c++

下面是一个简单的C++实现RSA密码系统的示例代码，包含了密钥生成、加密和解密过程。

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

using namespace std;

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

// 求模反元素
int modInverse(int a, int m)
{
    a = a % m;
    for (int x = 1; x < m; x++)
        if ((a * x) % m == 1)
            return x;
    return 1;
}

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

    // 选择e
    do {
        e = rand() % phi + 1;
    } while (gcd(e, phi) != 1);

    // 计算d
    d = modInverse(e, phi);
}

// 加密
int encrypt(int m, int e, int n)
{
    return (int)pow(m, e) % n;
}

// 解密
int decrypt(int c, int d, int n)
{
    return (int)pow(c, d) % n;
}

// 测试
int main()
{
    srand(time(NULL));

    int p = 61;
    int q = 53;
    int n, e, d;

    generateKeys(p, q, n, e, d);

    int m = 123;
    int c = encrypt(m, e, n);
    int dm = decrypt(c, d, n);

    cout << "p = " << p << endl;
    cout << "q = " << q << endl;
    cout << "n = " << n << endl;
    cout << "e = " << e << endl;
    cout << "d = " << d << endl;
    cout << "m = " << m << endl;
    cout << "c = " << c << endl;
    cout << "dm = " << dm << endl;

    return 0;
}

说明：

1. `gcd`函数求最大公约数，用于选择e时判断e是否与phi(n)互质。
2. `modInverse`函数求模反元素，用于计算d。
3. `generateKeys`函数用于生成公钥和私钥，其中p和q是两个大素数，n = p * q，e是随机选择的与phi(n)互质的整数，d是e的模反元素。
4. `encrypt`函数用于加密，公式为：c = m^e mod n。
5. `decrypt`函数用于解密，公式为：m = c^d mod n。
6. 在测试中，选择p = 61，q = 53，m = 123进行测试。