### RSA加密算法的Python实现 RSA加密算法是一种非对称加密技术，广泛应用于数据加密和数字签名。以下是使用Python实现RSA加密算法的具体方法和代码示例。 #### 1. 数学基础 在实现RSA之前，需要理解其数学原理，包括以下几个关键概念： - **互素**：两个数的最大公因数为1[^1]。 - **欧拉定理**：如果 \(a\) 和 \(n\) 互素，则 \(a^{\phi(n)} \mod n = 1\)，其中 \(\phi(n)\) 是欧拉函数[^1]。 - **求模逆元**：给定整数 \(a\) 和 \(m\)，若存在整数 \(x\) 满足 \(ax \equiv 1 \mod m\)，则 \(x\) 称为 \(a\) 的模逆元。 - **取模运算**：\(a \mod b\) 表示 \(a\) 被 \(b\) 整除后的余数。 #### 2. 算法步骤 以下是RSA算法的主要步骤： - **密钥生成**： 1. 随机选择两个大质数 \(p\) 和 \(q\)。 2. 计算 \(n = p \times q\)。 3. 计算欧拉函数 \(\phi(n) = (p-1)(q-1)\)。 4. 选择一个整数 \(e\)（\(1 < e < \phi(n)\)），使得 \(e\) 与 \(\phi(n)\) 互素。 5. 计算 \(d\)，即 \(e\) 的模逆元，满足 \(ed \equiv 1 \mod \phi(n)\)。 公钥为 \((n, e)\)，私钥为 \((n, d)\)[^1]。 - **加密过程**： 给定明文 \(m\)（\(m < n\)），计算密文 \(c = m^e \mod n\)[^4]。 - **解密过程**： 给定密文 \(c\)，计算明文 \(m = c^d \mod n\)[^4]。 #### 3. Python代码实现 以下是一个完整的RSA加密算法的Python实现： ```python import random from math import gcd def is_prime(num): if num <= 1: return False for i in range(2, int(num**0.5) + 1): if num % i == 0: return False return True def generate_prime(bits=10): while True: p = random.getrandbits(bits) if is_prime(p): return p 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 generate_keypair(p, q): n = p * q phi = (p - 1) * (q - 1) e = random.randint(1, phi) while gcd(e, phi) != 1: e = random.randint(1, phi) d = mod_inverse(e, phi) return ((n, e), (n, d)) def encrypt(public_key, plaintext): n, e = public_key cipher = [pow(ord(char), e, n) for char in plaintext] return cipher def decrypt(private_key, ciphertext): n, d = private_key plain = [chr(pow(char, d, n)) for char in ciphertext] return ''.join(plain) # 示例 p = generate_prime() q = generate_prime() public, private = generate_keypair(p, q) message = "Hello" encrypted_msg = encrypt(public, message) decrypted_msg = decrypt(private, encrypted_msg) print(f"Public Key: {public}") print(f"Private Key: {private}") print(f"Original Message: {message}") print(f"Encrypted Message: {encrypted_msg}") print(f"Decrypted Message: {decrypted_msg}") ``` #### 4. 注意事项 - 如果要加密的消息长度超过模数 \(n\)，可以将消息分割成多个短消息分别加密[^2]。 - 在实际应用中，通常使用库如 `rsa` 或 `Crypto` 来简化实现[^3]。 --- ###