用Python3写RSA加密算法和解密算法

以下是一个简单的 Python3 RSA 加密和解密代码：

import random

# 求最大公因数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 求模反元素
def modinv(a, m):
    if gcd(a, m) != 1:
        return None # 如果 a 和 m 不互质，则不存在模反元素
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (
            u1 - q * v1, u2 - q * v2, u3 - q * v3, v1, v2, v3
        )
    return u1 % m

# 生成公钥和私钥
def generate_keypair(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = random.randrange(1, phi)
    while gcd(e, phi) != 1:
        e = random.randrange(1, phi)
    d = modinv(e, phi)
    return (e, n), (d, n)

# 加密函数
def encrypt(public_key, plaintext):
    e, n = public_key
    ciphertext = [pow(ord(char), e, n) for char in plaintext]
    return ciphertext

# 解密函数
def decrypt(private_key, ciphertext):
    d, n = private_key
    plaintext = [chr(pow(char, d, n)) for char in ciphertext]
    return ''.join(plaintext)

# 测试
p, q = 61, 53
public_key, private_key = generate_keypair(p, q)
plaintext = 'Hello World!'
ciphertext = encrypt(public_key, plaintext)
decrypted_text = decrypt(private_key, ciphertext)
print('加密前：', plaintext)
print('加密后：', ciphertext)
print('解密后：', decrypted_text)

这段代码中使用了两个大素数 p 和 q 生成了公钥和私钥，使用了欧拉函数 phi、模反元素和快速幂算法进行加密和解密。需要注意的是，这里加密和解密的文本都必须是 ASCII 码，如果需要加密中文等非 ASCII 码字符，可使用 Base64 等编码方式将其转换为 ASCII 码。