rsa加密算法python实现

RSA加密算法是一种非对称加密算法，一般用于保护数据的机密性。下面是Python实现RSA加密算法的代码：

import random

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

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

def generate_keypair(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 = extended_gcd(e, phi)[0]
    return ((e, n), (d, n))

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

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

# Example usage:
p = 61
q = 53
public, private = generate_keypair(p, q)
print("Public key: ", public)
print("Private key: ", private)
message = "Hello, World!"
ciphertext = encrypt(public, message)
print("Ciphertext: ", ciphertext)
plaintext = decrypt(private, ciphertext)
print("Plaintext: ", plaintext)

在这个例子中，我们首先生成了两个随机的质数p和q，然后使用这两个质数生成了公钥和私钥。接下来，我们用公钥加密一个消息，然后用私钥解密该消息。最后，我们输出了加密后的密文和解密后的明文。