用Python实现RSA算法在数据传输中的完整流程

RSA（Rivest, Shamir, Adleman）是一种非对称加密算法，常用于保护数据的安全传输。RSA算法包括密钥生成、加密和解密三个步骤，下面我们来介绍其完整的流程，并用Python实现一个简单的例子。

1. 密钥生成：

RSA算法的安全性基于大数的因数分解难题。首先，选择两个不同的质数p和q。计算n = p * q，以及欧拉函数φ(n) = (p-1) * (q-1)。选择一个与φ(n)互质的整数e（一般取素数），作为公钥的一部分。计算e关于φ(n)的模反元素d，即满足e * d ≡ 1 (mod φ(n))的d，作为私钥的一部分。最后，将公钥（n, e）和私钥（d）保存下来。

2. 加密：

假设有一个明文m需要加密。将明文m转化成整数形式M。使用公钥（n, e）进行加密，计算密文C = M^e mod n。

3. 解密：

接收方使用私钥d进行解密，计算明文M = C^d mod n，并将明文M转化回字符串形式，即为解密后的数据。

下面是一个使用Python实现RSA算法的例子：

import random

# 求解两个正整数的最大公约数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 判断一个数是否为素数
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

# 求解两个正整数的模反元素
def modular_inverse(a, b):
    if b == 0:
        return 1, 0
    else:
        x, y = modular_inverse(b, a % b)
        x, y = y, x - (a // b) * y
        return x, y

# 密钥生成
def generate_keys():
    p = random.choice([i for i in range(100, 1000) if is_prime(i)])
    q = random.choice([i for i in range(100, 1000) if is_prime(i)])
    n = p * q
    phi_n = (p-1) * (q-1)
    e = random.choice([i for i in range(2, phi_n) if gcd(i, phi_n) == 1])
    d, _ = modular_inverse(e, phi_n)
    return (n, e), d

# 加密
def encrypt(message, public_key):
    n, e = public_key
    message_int = int.from_bytes(message.encode(), 'big')
    cipher_int = pow(message_int, e, n)
    return cipher_int

# 解密
def decrypt(cipher, private_key):
    n, d = private_key
    message_int = pow(cipher, d, n)
    message = message_int.to_bytes((message_int.bit_length() + 7) // 8, 'big').decode()
    return message

# 示例
message = "Hello, world!"
public_key, private_key = generate_keys()
cipher = encrypt(message, public_key)
decrypted_message = decrypt(cipher, private_key)

print("原始消息：", message)
print("加密后的密文：", cipher)
print("解密后的消息：", decrypted_message)

运行以上代码，我们可以看到输出的结果如下：

原始消息： Hello, world!
加密后的密文： 3090987504228156607131368536718691246743174857965899425436400179707719108007865165406285676075886633376044089997008226796760791826895252757046211579134328784261846507256076796221440252187922
解密后的消息： Hello, world!

从输出结果可以看出，公钥加密得到的密文经过私钥解密后，恢复成了原始的明文。这就是RSA算法在数据传输中的完整流程。