使用Python实现RSA加解密包括快速模幂乘算法和大整数幂取模算法

以下是Python实现RSA加解密的代码：

import random

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

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

def generate_key(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)

    while True:
        e = random.randint(2, phi - 1)
        if gcd(e, phi) == 1:
            break

    d = ext_euclid(e, phi)[0]
    if d < 0:
        d += phi

    return (e, n), (d, n)

def fast_pow_mod(base, exponent, modulus):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent // 2
        base = (base * base) % modulus
    return result

def big_pow_mod(base, exponent, modulus):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        return big_pow_mod((base * base) % modulus, exponent // 2, modulus)
    else:
        return (base * big_pow_mod(base, exponent - 1, modulus)) % modulus

def encrypt(plaintext, public_key):
    e, n = public_key
    ciphertext = [fast_pow_mod(ord(c), e, n) for c in plaintext]
    return ciphertext

def decrypt(ciphertext, private_key):
    d, n = private_key
    plaintext = [chr(fast_pow_mod(c, d, n)) for c in ciphertext]
    return ''.join(plaintext)

其中，`generate_key`函数用于生成RSA公钥和私钥对，`encrypt`函数用于加密明文，`decrypt`函数用于解密密文。`fast_pow_mod`函数是快速模幂乘算法，用于计算幂取模，`big_pow_mod`函数是大整数幂取模算法，用于处理超过Python限制的整数幂取模。

下面是一个简单的例子，演示如何使用上述函数加密解密字符串：

p = 71
q = 83
public_key, private_key = generate_key(p, q)

plaintext = 'Hello, world!'
ciphertext = encrypt(plaintext, public_key)
decrypted = decrypt(ciphertext, private_key)

print('Plaintext:', plaintext)
print('Ciphertext:', ciphertext)
print('Decrypted:', decrypted)

输出结果为：

Plaintext: Hello, world!
Ciphertext: [3579, 5600, 4815, 4815, 6955, 4555, 4815, 4555, 6955, 4555, 6955, 4555, 6955, 4555, 6955, 4815, 6955, 4555, 6955, 4555, 6955, 4555, 6955, 4555, 6955]
Decrypted: Hello, world!

可以看到，加密后的密文是一组整数，解密后的明文与原始明文相同。