Python实现RSA算法详解与代码实战

RSA算法核心原理简述

RSA（Rivest-Shamir-Adleman）是非对称加密体系的核心代表，广泛应用于信息加密与数字签名场景。该算法依赖大数分解的数学难题：生成一对公开共享的公钥与严格保密的私钥，发送方使用公钥加密，接收方使用私钥解密，即使通信信道被监听也无法反向推导明文。

Python环境准备与代码架构

为实现可独立运行的RSA教学示例，需确保运行环境为Python 3.8及以上版本（支持内置模逆元运算）。整体代码分为四个核心部分：质数校验与模数计算、欧拉函数处理、密钥对生成、以及基于模幂运算的加解密模块。所有逻辑封装于单一脚本中，便于直观对照数学公式进行调试。

第1步：确定质数并计算模数N

目的：建立RSA算法的基础乘法域，作为后续所有计算的基准 modulus。入口：定义两个不相等的大质数 p 和 q。动作：将输入质数相乘得到模数 N = p × q。重要参数：p 与 q 必须为真质数且长度相当。可观察完成状态：N 输出为固定整数，作为公钥与私钥的共同组成部分，且销毁原始 p、q 记录以符合安全规范。

第2步：计算欧拉函数φ(N)

目的：获取与 N 互质的正整数个数，用于约束指数选取范围。入口：利用上一步得到的 p 和 q。动作：应用公式 φ(N) = (p-1) × (q-1) 计算欧拉函数值。重要参数：φ(N) 必须严格大于 1。可观察完成状态：phi_n 变量赋值成功，为下一步寻找互质数提供区间依据。

第3步：生成公钥指数e与私钥指数d

目的：构建满足模逆关系的加密指数与解密指数。入口：e 与 d 均为待求整数。动作：遍历区间 [3, φ(N)-1] 寻找与 φ(N) 互质的数作为公钥指数 e；随后计算 e 关于 φ(N) 的模逆元得到私钥指数 d，满足 (e × d) ≡ 1 (mod φ(N))。重要参数：gcd(e, φ(N)) == 1 且 1 < e < φ(N)。可观察完成状态：e 与 d 均返回有效整数值，组合后形成完整密钥对。

第4步：实现加密与解密模块

目的：将数学映射转化为实际的数据变换操作。入口：明文消息 m、密文 c、密钥元组 (N, e) 或 (N, d)。动作：加密执行 c = m^e mod N，解密执行 m = c^d mod N。重要参数：输入消息需转换为小于 N 的整数。可观察完成状态：加密后的列表数据可通过私钥完全还原为初始明文序列，无精度丢失。

完整代码与运行验证

以下为整合上述步骤的Python 3标准实现。代码移除了旧版语法依赖，改用内置 math.gcd 与 pow() 提升执行效率，直接复制即可在终端运行查看控制台输出结果。

import math

def generate_keys(p=47, q=79):
    """生成公私钥对"""
    N = p * q
    phi_N = (p - 1) * (q - 1)
    
    # 寻找与phi_N互质的公钥指数e
    e = 0
    for candidate_e in range(3, phi_N):
        if math.gcd(candidate_e, phi_N) == 1:
            e = candidate_e
            break
    if e == 0:
        raise ValueError("未能找到符合条件的公钥指数e")
        
    # 计算模逆元获取私钥指数d
    d = pow(e, -1, phi_N)
    return ((N, e), (N, d))

def encrypt(plaintext, key):
    """使用公钥加密"""
    N, e = key
    return pow(int(plaintext), e, N)

def decrypt(ciphertext, key):
    """使用私钥解密"""
    N, d = key
    return pow(int(ciphertext), d, N)

if __name__ == "__main__":
    pub, pri = generate_keys(47, 79)
    messages = list(range(20, 30))
    
    encrypted = [encrypt(msg, pub) for msg in messages]
    decrypted = [decrypt(enc, pri) for enc in encrypted]
    
    print(f"Keys: {pub}, {pri}")
    print(f"Message: {messages}")
    print(f"Encrypted: {encrypted}")
    print(f"Decrypted: {decrypted}")

注意事项与性能优化建议

当前实现侧重于算法流程的教学演示。在实际生产环境中需注意以下安全与性能事项：

• 质数选择：示例中的 p=47 与 q=79 仅为便于手动验算的小数值。真实业务必须使用 2048 位以上的随机大质数，建议通过系统熵源或 secrets 模块生成。
• 数据块限制：纯文本数字直接取模运算存在消息空间上限（M < N）。传输长文本时需结合分块填充机制（如 PKCS#1 v1.5 或 OAEP）防止模式攻击。
• 性能差异：模幂运算 pow(base, exp, mod) 底层采用平方乘算法，时间复杂度为对数级，相比逐次相乘可大幅降低内存占用与CPU消耗。

以上就是Python实现RSA算法的详细内容，更多关于非对称加密与安全通信的资料请关注本站其它相关文章！