编写程序实现rsa算法

RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，由三位科学家在1977年提出。它主要包含两个关键过程：密钥生成和数据加密解密。

1. 密钥生成：
- **素数选择**：选取两个大质数p和q。
- **n = p * q**：计算它们的乘积作为公钥(n)的值，公开分享给任何人。
- **欧拉函数φ(n) = (p-1)(q-1)**：计算n的一半减去每个质因数的减一结果。
- **e**（公钥指数）：选择一个小于φ(n)且与φ(n)互质的整数，通常是65537（因为这个值常见且高效）。
- **d**（私钥指数）：找到一个整数d，满足(d * e) % φ(n) = 1，即模反元素，用于解密。

2. 数据加密：
- **加密消息**：将明文信息M转换成整数，然后用公钥(e, n)加密为C = M^e mod n。

3. 数据解密：
- **解密密文**：接收者使用私钥(d, n)计算C^d mod n，得到原始明文M。

为了编写实际的RSA算法，你需要使用数学库支持大数运算，并按照上述步骤实现相应的加密和解密函数。下面是一个简单的Python示例：

from Crypto.Util.number import inverse

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

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

def modinv(a, m):
    g, x, _ = egcd(a, m)
    if g == 1:
        return x % m

def generate_keys(p, q):
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = 65537
    d = modinv(e, phi_n)
    return (e, n), (d, n)

# 更具体的代码会处理输入验证、大数操作等细节