### Python实现RSA加密算法 以下是使用Python实现RSA加密算法的一个完整示例： #### 导入必要的库 为了完成RSA算法的实现，我们需要导入`random`模块来生成随机数，以及`math`模块来进行一些基本的数学运算。 ```python import random import math ``` #### 辅助函数定义 在正式实现之前，先定义几个辅助函数以便后续操作更加简洁清晰。 ##### 判断素数 判断一个给定的数字是否为素数是非常重要的一步，因为RSA依赖于两个大素数的选择。 ```python def is_prime(num): if num <= 1: return False for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: return False return True ``` ##### 计算最大公约数(GCD) 此函数用来验证所选的e值与φ(N)是否互质。 ```python def gcd(a, b): while b != 0: a, b = b, a % b return a ``` ##### 扩展欧几里得算法求模逆元 该部分用于找到满足条件 \( d \cdot e \equiv 1 (\text{mod} \ \varphi(N)) \) 的d值。 ```python def multiplicative_inverse(e, phi_n): def extended_gcd(aa, bb): lastremainder, remainder = abs(aa), abs(bb) x, lastx, y, lasty = 0, 1, 1, 0 while remainder: lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder) x, lastx = lastx - quotient*x, x y, lasty = lasty - quotient*y, y return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1) g, x, _ = extended_gcd(e, phi_n) if g != 1: raise ValueError('Modular inverse does not exist') else: return x % phi_n ``` #### 主体逻辑实现 现在可以构建整个RSA系统的主体框架了。 ```python 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 = p * q phi_n = (p-1) * (q-1) # Choose an integer e such that e and phi(n) are coprime e = random.randrange(1, phi_n) g = gcd(e, phi_n) while g != 1: e = random.randrange(1, phi_n) g = gcd(e, phi_n) # Use Extended Euclid's Algorithm to generate the private key d = multiplicative_inverse(e, phi_n) # Return public and private keys return ((n, e), (n, d)) ``` #### 加密和解密功能 最后提供简单的加密和解密方法供调用者使用。 ```python def encrypt(public_key, plaintext): n, e = public_key cipher = [(ord(char) ** e) % n for char in plaintext] return cipher def decrypt(private_key, ciphertext): n, d = private_key plain = [chr((char ** d) % n) for char in ciphertext] return ''.join(plain) if __name__ == '__main__': print("RSA Encrypter/ Decrypter") p = int(input("Enter a prime number (17, 19, 23, etc): ")) q = int(input("Enter another prime number (Not one you entered above): ")) try: public, private = generate_keypair(p, q) print(f"Public Key: {public}") print(f"Private Key: {private}") message = input("Enter a message to encrypt with your public key: ") encrypted_msg = encrypt(public, message) print(f"Your encrypted message is: {' '.join(map(str, encrypted_msg))}") decrypted_message = decrypt(private, encrypted_msg) print(f"Your decrypted message is: {decrypted_message}") except Exception as ex: print(ex) ``` 以上就是完整的基于Python语言下的RSA加解密流程演示[^1][^2]。