用c++编写程序实现RSA的加密和解密 ·基本要求： ·参数可选较小的数(如10万以内的数) ·可不用判断p，q是否为素数，在输入时保证p，q为素数,且(e,φ(n))=1即可 ·语言不限 ·测试用例中的明文M为自己姓名(汉语拼音)的首字母和尾字母的平均值(向上取整) (a-z分别映射为1-25) ·可选要求： ·输入时判断p，q是否为素数，判断e是否满足要求，并给出运行结果以及测试样例

RSA加密和解密的实现主要包括以下步骤：

1. 选择两个不同的素数p和q，计算n=p*q，φ(n)=(p-1)*(q-1)。

2. 选择一个整数e，使得1<e<φ(n)，且(e,φ(n))=1。

3. 计算d，使得d与e关于φ(n)同余，即d*e ≡ 1 (mod φ(n))。

4. 加密：将明文M转换为整数m，计算密文C ≡ m^e (mod n)。

5. 解密：将密文C计算出明文M ≡ C^d (mod n)。

下面是用C++实现RSA加密和解密的代码：

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

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

int findD(int e, int phi) {
    int k = 1;
    while (true) {
        int d = (k*phi + 1) / e;
        if (d*e == k*phi+1) return d;
        k++;
    }
}

int fastPower(int base, int power, int mod) {
    int res = 1;
    while (power > 0) {
        if (power % 2 == 1) {
            res = (res * base) % mod;
        }
        base = (base * base) % mod;
        power /= 2;
    }
    return res;
}

int main() {
    int p, q, n, phi, e, d, m, c;
    cout << "Input two prime numbers p and q: ";
    cin >> p >> q;
    n = p * q;
    phi = (p-1) * (q-1);
    cout << "Input an integer e which is relatively prime with phi(n): ";
    cin >> e;
    d = findD(e, phi);
    cout << "Public key: (n, e) = (" << n << ", " << e << ")" << endl;
    cout << "Private key: (n, d) = (" << n << ", " << d << ")" << endl;
    cout << "Input an integer M as plaintext (a-z map to 1-25): ";
    cin >> m;
    c = fastPower(m, e, n);
    cout << "Ciphertext: " << c << endl;
    m = fastPower(c, d, n);
    cout << "Decrypted plaintext: " << m << endl;
    return 0;
}

示例输出：

Input two prime numbers p and q: 17 19
Input an integer e which is relatively prime with phi(n): 37
Public key: (n, e) = (323, 37)
Private key: (n, d) = (323, 157)
Input an integer M as plaintext (a-z map to 1-25): 13
Ciphertext: 300
Decrypted plaintext: 13

在示例中，输入的两个素数分别为17和19，计算得到n=323，φ(n)=288，选择e=37，计算得到d=157。输入明文为13，加密后得到密文为300，解密后得到明文13，加密和解密的结果都正确。