### 实现RSA加密算法 在不依赖任何外部库的情况下，可以利用Python的标准库`random`和内置的大数运算功能来实现基本的RSA加密算法。下面展示了一个简化版的RSA加密/解密过程。 #### 密钥生成 为了创建公私钥对，需要先定义两个大素数p和q，并计算n=p*q作为模数。接着求得欧拉函数φ(n)=(p-1)*(q-1)，并选取一个小于φ(n)且与其互质的整数e作为公钥的一部分；最后通过扩展欧几里得算法找到d使得(e*d)%φ(n)=1，则(d,n)即为对应的私钥[^1]。 ```python import random from math import gcd def is_prime(num): """判断num是否为素数""" if num <= 1 or (num % 2 == 0 and num > 2): return False sqrt_num = int(pow(num, 0.5)) + 1 for divisor in range(3, sqrt_num, 2): if num % divisor == 0: return False return True def generate_large_prime(bits=128): """生成指定位长度的大素数""" while True: candidate = random.getrandbits(bits) if is_prime(candidate): return candidate def mod_inverse(a, m): """求a关于m的乘法逆元""" a, b, u = 0, m, 1 while not a: q, r = divmod(b, m) s = u - q * a a, b, u = b % m, a, s if abs(u) >= m // 2: u -= m * ((u > 0) - (u < 0)) return u def generate_keypair(keysize=16): """生成一对公私钥""" p = generate_large_prime(keysize//2) q = generate_large_prime(keysize//2) n = p * q phi_n = (p - 1) * (q - 1) e = 65537 # 常见的选择是费马素数F_4=2^16+1 d = mod_inverse(e, phi_n) public_key = {'e': e, 'n': n} private_key = {'d': d, 'n': n} return public_key, private_key ``` #### 加密与解密 对于消息M（假设已经转换成数字形式），其加密C=M^e%n，而解密则为M=C^d%n。这里需要注意的是，在实际应用中通常会对明文进行填充以防止某些攻击方式，但在本例中省略了这部分细节以便专注于核心逻辑[^2]。 ```python def encrypt(message_int, pub_key): """使用公钥加密消息""" cipher_text = pow(message_int, pub_key['e'], pub_key['n']) return cipher_text def decrypt(cipher_text, priv_key): """使用私钥解密密文""" message_int = pow(cipher_text, priv_key['d'], priv_key['n']) return message_int ``` 以上代码提供了一种基于纯Python标准库构建简单RSA系统的方案。然而值得注意的是，此方法并不适用于生产环境中的安全通信需求——它缺乏必要的优化措施以及对抗各种潜在威胁的能力。因此建议在真实场景下采用成熟的第三方库如PyCryptodome等来进行更专业的密码学操作[^3]。