Python 实现 RSA 加密解密：代码示例及原理详解

以下是一个简单的 RSA 加密和解密的 Python 实现：

import random
import math

def gcd(a, b):
    while b != 0:
        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 is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def generate_keypair(p, q):
    if not (is_prime(p) and is_prime(q)):
        raise ValueError('Both numbers must be prime.')
    elif p == q:
        raise ValueError('p and q cannot be equal')
    # n = pq
    n = p * q
    # phi(n) = (p-1)(q-1)
    phi = (p - 1) * (q - 1)
    # Choose an integer e such that e and phi(n) are coprime
    e = random.randrange(1, phi)
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)
    # Calculate d such that ed = 1 (mod phi(n))
    d = mod_inverse(e, phi)
    # Return public and private keypair
    # Public key is (e, n)
    # Private key is (d, n)
    return ((e, n), (d, n))

def encrypt(public_key, plaintext):
    # Unpack the key into its components
    key, n = public_key
    # Convert each letter in the plaintext to numbers based on the character using a^b mod m
    cipher = [pow(ord(char), key, n) for char in plaintext]
    # Return the array of bytes
    return cipher

def decrypt(private_key, ciphertext):
    # Unpack the key into its components
    key, n = private_key
    # Generate the plaintext based on the ciphertext and key using a^b mod m
    plain = [chr(pow(char, key, n)) for char in ciphertext]
    # Return the array of bytes as a string
    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'
encrypted_msg = encrypt(public, message)
print('Encrypted message:', ''.join(map(str, encrypted_msg)))
decrypted_msg = decrypt(private, encrypted_msg)
print('Decrypted message:', decrypted_msg)

在这个示例中，我们使用 generate_keypair 函数生成 RSA 公钥和私钥。然后，我们使用 encrypt 函数将文本加密为数字数组，使用 decrypt 函数将加密的数字数组解密为文本。在这个示例中，我们使用 61 和 53 作为 p 和 q 的值，但您可以使用不同的值来生成不同的密钥。

RSA 算法原理

RSA 算法是一种非对称加密算法，它使用一对密钥：公钥和私钥。公钥可以公开发布，用于加密信息；私钥保密，用于解密信息。RSA 算法的安全性基于大数分解的困难性。

1. 密钥生成

   • 选择两个大素数 p 和 q。
   • 计算 n = p * q，n 是模数。
   • 计算欧拉函数 phi(n) = (p - 1)(q - 1)。
   • 选择一个随机数 e，满足 1 < e < phi(n) 且 gcd(e, phi(n)) = 1，e 是公钥。
   • 计算 d，满足 d * e = 1 (mod phi(n))，d 是私钥。

2. 加密

   • 将明文消息转换为数字表示 M。
   • 计算密文 C = M^e mod n。

3. 解密

   • 计算明文 M = C^d mod n。

使用说明

1. 运行代码，它会生成一对 RSA 密钥。
2. 使用 encrypt 函数对要加密的文本进行加密，将公钥作为第一个参数传入。
3. 使用 decrypt 函数对加密后的数字数组进行解密，将私钥作为第一个参数传入。

注意

• 在实际应用中，请使用更大的素数 p 和 q 来提高安全性。
• 保护好私钥，不要泄露给任何人。
• RSA 算法适合加密较短的文本，对于较长的文本，可以使用混合加密方案。