RSA加密解密算法C++实现

RSA (Rivest-Shamir-Adleman) 算法是一种非对称加密技术，用于保护数据的安全传输。它由三个步骤组成：密钥生成、加密和解密。以下是C++实现RSA算法的一个简化版概述：

1. **密钥生成**：
- 选择两个大素数p和q。
- 计算n=p*q，这将是公钥的模数。
- 根据欧几里得定理计算欧拉函数phi(n)=(p-1)*(q-1)。
- 选取一个e，满足1<e<phi(n)，且gcd(e, phi(n))=1（即e与phi(n)互质）。e通常是一个小于phi(n)的公共因子。
- 使用扩展欧几里得算法找到d，使得(d*e)%phi(n)=1。d是私钥的一部分。

2. **加密**：
- 对明文消息m取模n（m < n），得到整数c。
- 使用公式 `c ≡ m^e mod n` 进行加密，其中c是密文，e是公钥指数。

3. **解密**：
- 使用公式 `m ≡ c^d mod n` 进行解密，其中d是私钥指数。

#include <bits/stdc++.h>
using namespace std;

// ...省略大素数检测和密钥生成部分...
void encrypt(int message, int modulus, int public_exponent, int& ciphertext) {
    ciphertext = pow(message, public_exponent, modulus);
}

int decrypt(int ciphertext, int modulus, int private_exponent) {
    return pow(ciphertext, private_exponent, modulus);
}

// ...其他辅助函数...

int main() {
    // 密钥生成和存储
    // ...省略实际生成过程...

    // 加密示例
    int message = 123;
    int ciphertext;
    encrypt(message, n, e, ciphertext);

    // 解密示例
    int plaintext = decrypt(ciphertext, n, d);
    cout << "Original message: " << plaintext << endl;

    return 0;
}