编写程序实现RSA算法，由键盘输入p、q、随机数e及明文m，输出私钥d、加密后的密文，解密后的明文

在编写程序实现RSA算法时，首先需要了解 RSA 算法的基本步骤：

1. **生成公钥和私钥**：
- 输入两个大素数 p 和 q，计算它们的最大公约数（gcd），若 gcd(p, q) ≠ 1，则这两个数不是质数，需重新选择。
- 计算 n = p * q，这是 RSA 的模数。
- 求欧拉函数 φ(n) = (p-1)(q-1)，选择一个与 φ(n)互质的整数 e（通常 e=65537 是一个常用的选择，因为它是安全且易于计算的），作为公钥的一部分。
- 私钥 d 是满足 d * e ≡ 1 mod φ(n) 的最小正整数，通过扩展欧几里得算法求解。

2. **用户输入和处理**：
- 用户从键盘输入公钥的指数 e，以及要加密的明文 m。
- 对于输入的明文 m，确保它小于等于模数 n。

3. **加密过程**（公钥操作）：
- 使用模幂运算（pow(m, e, n)）对明文 m 进行加密得到密文 c。

4. **解密过程**（私钥操作）：
- 解密时，使用私钥 d 和密文 c 计算出原始明文，即 pow(c, d, n)。

以下是简单的 Python 示例代码实现：

import math

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x

def mod_inv(a, m):
    g, x, _ = egcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

def rsa():
    # 输入部分
    p, q = map(int, input("请输入两个大素数 p, q: ").split())
    while gcd(p, q) != 1:
        print("错误，p和q必须是互质的大素数，请重新输入")
        p, q = map(int, input().split())

    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = int(input("请输入公钥指数 e: "))

    while math.gcd(e, phi_n) != 1:
        print("错误，e应与φ(n)互质，请重新输入")
        e = int(input())

    d = mod_inv(e, phi_n)
    
    # 明文和操作部分
    m = int(input("请输入明文 m: "))
    c = pow(m, e, n)  # 加密
    print(f"加密后的密文 c: {c}")

    if m <= n:
        m_prime = pow(c, d, n)  # 解密
        print(f"解密后的明文 m': {m_prime}")
    else:
        print("错误，明文超过模数限制")

rsa()