rsa加密算法python实现

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

import random

def gcd(a, b):
    while b:
        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 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 = mod_inverse(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)

if __name__ == '__main__':
    p = 37
    q = 79
    public_key, private_key = generate_keypair(p, q)
    message = 'Hello, world!'
    ciphertext = encrypt(public_key, message)
    decrypted_message = decrypt(private_key, ciphertext)
    print('Public key:', public_key)
    print('Private key:', private_key)
    print('Original message:', message)
    print('Encrypted message:', ciphertext)
    print('Decrypted message:', decrypted_message)

在上面的代码中，我们使用了Python内置的模块`random`来生成随机数，用于生成RSA的密钥对。`gcd`函数用于计算两个数的最大公约数，`mod_inverse`函数用于计算模反元素。`generate_keypair`函数用于生成RSA的密钥对，`encrypt`函数用于加密明文，`decrypt`函数用于解密密文。

在主函数中，我们先使用`generate_keypair`函数生成RSA的密钥对，然后使用`encrypt`函数加密明文，再使用`decrypt`函数解密密文，并输出结果。