rsa算法Python

RSA算法是一种非对称加密算法，它由三个主要步骤组成：密钥生成、加密和解密。下面是RSA算法的Python实现：

1. 密钥生成：
首先，选择两个不同的质数p和q，并计算它们的乘积n。然后，计算欧拉函数φ(n) = (p-1)(q-1)。接下来，选择一个整数e，满足1 < e < φ(n)且e与φ(n)互质。最后，计算e的模反元素d，使得(e * d) % φ(n) = 1。公钥为(n, e)，私钥为(n, d)。

2. 加密：
加密过程中使用公钥进行加密。将明文消息m转换为整数，并使用公式c = m^e mod n进行加密，其中c为密文。

3. 解密：
解密过程中使用私钥进行解密。将密文c使用私钥进行解密，即计算m = c^d mod n，得到明文消息m。

下面是一个简单的RSA算法的Python实现示例：

import random

def generate_keypair(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    
    # 选择一个与phi互质的整数e
    e = random.randrange(1, phi)
    gcd = lambda a, b: a if not b else gcd(b, a % b)
    while gcd(e, phi) != 1:
        e = random.randrange(1, phi)
    
    # 计算e的模反元素d
    def extended_gcd(a, b):
        if b == 0:
            return (a, 1, 0)
        else:
            d, x, y = extended_gcd(b, a % b)
            return (d, y, x - (a // b) * y)
    
    _, _, d = extended_gcd(e, phi)
    d = d % phi
    if d < 0:
        d += phi
    
    return ((n, e), (n, d))

def encrypt(public_key, message):
    n, e = public_key
    return pow(message, e, n)

def decrypt(private_key, encrypted_message):
    n, d = private_key
    return pow(encrypted_message, d, n)

# 示例用法
p = 61
q = 53
public_key, private_key = generate_keypair(p, q)
message = 123
encrypted_message = encrypt(public_key, message)
decrypted_message = decrypt(private_key, encrypted_message)

print("公钥：", public_key)
print("私钥：", private_key)
print("明文消息：", message)
print("加密后的消息：", encrypted_message)
print("解密后的消息：", decrypted_message)