Python实现RSA算法：从入门到实践

RSA算法简介RSA算法是一种非对称加密算法，被广泛应用于信息安全领域。它使用一对密钥：公钥用于加密，私钥用于解密。

Python实现以下是用 Python 实现 RSA 算法的示例代码：pythonimport 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 n = p * q

# 计算 φ(n)    phi = (p - 1) * (q - 1)

# 选择 e，确保 e 和 φ(n) 互质    e = random.randrange(1, phi)    while gcd(e, phi) != 1:        e = random.randrange(1, phi)

# 计算 d，满足 (d * e) % φ(n) = 1    gcd, d, _ = extended_gcd(e, phi)    if d < 0:        d += phi

# 返回公钥和私钥    public_key = (e, n)    private_key = (d, n)    return public_key, private_key

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

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

选择两个素数 p 和 qp = 61q = 53

生成公钥和私钥public_key, private_key = generate_keypair(p, q)

明文plaintext = 'Hello, World!'

使用公钥加密ciphertext = encrypt(plaintext, public_key)print('Encrypted Message:', ciphertext)

使用私钥解密decrypted_message = decrypt(ciphertext, private_key)print('Decrypted Message:', decrypted_message)

代码解读：

1. 辅助函数: gcd 计算最大公约数， extended_gcd 是扩展欧几里得算法， generate_keypair 用于生成公钥和私钥对。

2. 加密函数: encrypt 函数使用公钥对明文进行加密。

3. 解密函数: decrypt 函数使用私钥对密文进行解密。

4. 主程序: 选择两个素数 p 和 q (示例中使用较小的素数), 生成公钥和私钥, 使用公钥加密明文，并使用私钥解密密文。

安全提示需要注意的是，本示例仅用于演示 RSA 算法的基本原理，不适用于实际的加密应用。在实际使用中，应该使用更大的素数和更复杂的安全措施来保护密钥。