python实现rsa加解密算法

RSA是一种非对称加密算法，其中公钥和私钥共同构成了一对密钥。下面是Python实现RSA加解密算法的代码示例：

import random

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

def multiplicative_inverse(e, phi):
    # 扩展欧几里得算法求乘法逆元
    d = 0
    x1, x2 = 0, 1
    y1, y2 = 1, 0
    temp_phi = phi
    while e > 0:
        temp1 = temp_phi // e
        temp2 = temp_phi - temp1 * e
        temp_phi = e
        e = temp2

        x = x2 - temp1 * x1
        y = y2 - temp1 * y1

        x2 = x1
        x1 = x
        y2 = y1
        y1 = y

    if temp_phi == 1:
        d = y2

    return d

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

def encrypt(pk, plaintext):
    # 将明文加密成密文
    key, n = pk
    cipher = [pow(ord(char), key, n) for char in plaintext]
    return cipher

def decrypt(pk, ciphertext):
    # 将密文解密成明文
    key, n = pk
    plain = [chr(pow(char, key, n)) for char in ciphertext]
    return ''.join(plain)

if __name__ == '__main__':
    p = 17
    q = 19
    public, private = generate_keypair(p, q)
    message = 'Hello, world!'
    cipher = encrypt(public, message)
    print('Encrypted:', cipher)
    plain = decrypt(private, cipher)
    print('Decrypted:', plain)

在上面的代码中，使用generate_keypair函数生成公钥和私钥，encrypt函数对明文进行加密，decrypt函数对密文进行解密。

其中multiplicative_inverse函数实现了扩展欧几里得算法求乘法逆元，gcd函数实现了求最大公因数的欧几里得算法。

使用示例中的p和q生成的公钥和私钥不太安全，实际应用中需要使用更大的质数进行生成。