用Python实现RSA算法

RSA算法是一种非对称加密算法，常用于数据加密和数字签名。下面是用Python实现RSA算法的步骤：

1. 选择两个不同的质数p和q，并计算它们的乘积n：n = p * q。
2. 计算n的欧拉函数值φ(n)：φ(n) = (p-1) * (q-1)。
3. 选择一个整数e，使得1 < e < φ(n)，且e与φ(n)互质。e称为公钥指数。
4. 计算e的模反元素d，使得d * e ≡ 1 (mod φ(n))。d称为私钥指数。
5. 公钥为(n, e)，私钥为(n, d)。
6. 加密：将明文m转换为整数M，计算密文C = M^e mod n。
7. 解密：将密文C计算出明文m = C^d mod n。

下面是用Python实现RSA算法的示例代码：

import random

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

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

def generate_keypair(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    
    # Choose e such that 1 < e < phi and gcd(e, phi) = 1
    e = random.randrange(1, phi)
    while gcd(e, phi) != 1:
        e = random.randrange(1, phi)
    
    # Compute d as the modular inverse of e
    _, d, _ = extended_gcd(e, phi)
    d = (d % phi + phi) % phi
    
    return (n, e), (n, d)

def encrypt(public_key, message):
    n, e = public_key
    encrypted_message = [pow(ord(char), e, n) for char in message]
    return encrypted_message

def decrypt(private_key, encrypted_message):
    n, d = private_key
    decrypted_message = [chr(pow(char, d, n)) for char in encrypted_message]
    return ''.join(decrypted_message)

# Example usage
p = 61
q = 53
public_key, private_key = generate_keypair(p, q)

message = "Hello, RSA!"
encrypted_message = encrypt(public_key, message)
decrypted_message = decrypt(private_key, encrypted_message)

print("Original message:", message)
print("Encrypted message:", encrypted_message)
print("Decrypted message:", decrypted_message)