python实现rsa加解密算法

RSA是一种非对称加密算法，可以用于加密和解密数据。下面是Python实现RSA加解密算法的示例代码：

import random

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

def mod_inverse(a, m):
    if gcd(a, m) != 1:
        return None
    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 is_prime(n, k=5):
    if n <= 1:
        return False
    for i in range(k):
        a = random.randint(2, n - 1)
        if pow(a, n - 1, n) != 1:
            return False
    return True

def generate_keypair(p, q):
    if not (is_prime(p) and is_prime(q)):
        raise ValueError("Both numbers must be prime.")
    elif p == q:
        raise ValueError("p and q cannot be equal")
    n = p * q
    phi = (p - 1) * (q - 1)
    e = random.randint(1, phi - 1)
    g = gcd(e, phi)
    while g != 1:
        e = random.randint(1, phi - 1)
        g = gcd(e, phi)
    d = mod_inverse(e, phi)
    return (e, n), (d, n)

def encrypt(pk, plaintext):
    key, n = pk
    cipher = [(ord(char) ** key) % n for char in plaintext]
    return cipher

def decrypt(pk, ciphertext):
    key, n = pk
    plain = [chr((char ** key) % n) for char in ciphertext]
    return ''.join(plain)

if __name__ == '__main__':
    p = 61
    q = 53
    public, private = generate_keypair(p, q)
    message = 'Hello, World!'
    encrypted = encrypt(public, message)
    decrypted = decrypt(private, encrypted)
    print('Public key:', public)
    print('Private key:', private)
    print('Encrypted message:', encrypted)
    print('Decrypted message:', decrypted)

在这个示例中，我们使用了Python内置的随机数生成器模块`random`，以及一些基本的数学函数，例如求最大公约数和求模反元素。我们首先定义了一些辅助函数，例如判断素数、求模反元素等。然后我们实现了RSA的主要功能函数，包括生成公钥和私钥、加密和解密。最后我们使用一个简单的例子演示了如何使用这些函数进行加解密操作。