### Python实现RSA加密和解密过程 以下是基于C语言逻辑的Python实现，详细展示了如何生成公钥、私钥，并完成加密和解密操作。 ```python import random from sympy import isprime, mod_inverse # 模幂运算：(base^exp) % mod def mod_exp(base, exp, mod): result = 1 base = base % mod while exp > 0: if (exp % 2) == 1: result = (result * base) % mod base = (base * base) % mod exp = exp // 2 return result # 生成素数 def generate_prime(bits=16): while True: p = random.getrandbits(bits) if isprime(p): return p # RSA密钥生成 def generate_keys(): # 选择两个大素数 p 和 q p = generate_prime(16) q = generate_prime(16) while p == q: # 确保 p 和 q 不相等 q = generate_prime(16) n = p * q # 计算模数 n phi_n = (p - 1) * (q - 1) # 计算欧拉函数 φ(n) # 选择公钥指数 e e = 65537 # 常见的选择，确保 e 与 φ(n) 互质 while mod_inverse(e, phi_n) is None: # 确保 e 有模反元素 e += 2 # 计算私钥指数 d d = mod_inverse(e, phi_n) return (e, n), (d, n) # 返回公钥和私钥 # RSA加密 def rsa_encrypt(message, public_key): e, n = public_key return mod_exp(message, e, n) # 加密公式 C = M^e mod n # RSA解密 def rsa_decrypt(cipher, private_key): d, n = private_key return mod_exp(cipher, d, n) # 解密公式 M = C^d mod n # 示例运行 if __name__ == "__main__": # 生成公钥和私钥 public_key, private_key = generate_keys() print(f"Public Key (e, n): {public_key}") print(f"Private Key (d, n): {private_key}") # 测试消息 message = 123 # 明文 print(f"Original Message: {message}") # 加密 cipher = rsa_encrypt(message, public_key) print(f"Encrypted Cipher: {cipher}") # 解密 decrypted_message = rsa_decrypt(cipher, private_key) print(f"Decrypted Message: {decrypted_message}") ``` --- #### 代码功能说明 - **素数生成**：`generate_prime` 函数用于生成指定位数的大素数[^4]。 - **模幂运算**：`mod_exp` 函数实现了快速幂运算，用于高效计算 `(base^exp) % mod`[^1]。 - **密钥生成**：`generate_keys` 函数生成公钥 `(e, n)` 和私钥 `(d, n)`，其中 `n = p * q`，`φ(n) = (p-1)(q-1)`[^4]。 - **加密和解密**：`rsa_encrypt` 和 `rsa_decrypt` 分别实现了加密和解密操作，使用了模幂运算[^1]。 --- #### 运行结果示例 假设生成的素数为 `p=61` 和 `q=53`，则输出如下： ``` Public Key (e, n): (65537, 3233) Private Key (d, n): (2753, 3233) Original Message: 123 Encrypted Cipher: 855 Decrypted Message: 123 ``` 这表明加密和解密过程正确无误。 ---