使用 Python 实现 RSA 加密

昨晚快十二点，我正准备关电脑，有同事在群里丢了一句： “哥，Python 里能不能自己写个 RSA，加密个小东西，不想装一堆库。” 我一看这问题，困意没了，顺手就给他撸了个 demo。今天把思路完整说一遍，你照着抄一份就能跑起来。

先把 RSA 这事说人话

别一上来就一堆公式，先搞清楚它到底干嘛的。

RSA 其实就两件事：

• 生成一对钥匙：

• 公钥：给谁都行（n, e）
• 私钥：自己藏好（n, d）

• 加密 / 解密：

• 加密：cipher = m^e mod n
• 解密：m = cipher^d mod n

m 是明文（先要变成数字），cipher 是密文，mod n 就是取模。

你可以粗暴理解成： “我造了一个巨大的锁（n），配两把钥匙，一个只能上锁（e），一个只能开锁（d），从数学上保证你拿上锁的那把反推不开另一把。”

钥匙到底怎么造出来？

理论版步骤是这样的，别慌，后面有完整 Python 代码：

1. 随机挑两个足够大的素数 p 和 q
2. 算它们的乘积 n = p * q（这个就是那把“巨锁”）
3. 算欧拉函数 φ(n) = (p-1)*(q-1)
4. 选一个整数 e，要求 1 < e < φ(n) 且和 φ(n) 互质（一般直接用 65537）
5. 算出 d，满足：e * d ≡ 1 (mod φ(n))，也就是 d 是 e 在 φ(n) 里的“乘法逆元”

最后：

• 公钥：(n, e)
• 私钥：(n, d)

核心难点其实就俩： 一个是“找素数”，一个是“求乘法逆元”。Python 都能帮你搞定。

先写一版“教学用”的 RSA（别拿去生产）

这版代码故意写简单一点，好看懂，但强度肯定不够，只适合你本地玩玩原理。

先搞几个数学小工具：判断素数、求最大公因数、扩展欧几里得、求逆元。

import random
from math import gcd
defis_probable_prime(n: int) -> bool:
"""特别简陋的素数判断，只适合小一点的数，教学用"""
if n < 2:
returnFalse
if n in (2, 3):
returnTrue
if n % 2 == 0:
returnFalse
    i = 3
while i * i <= n:
if n % i == 0:
returnFalse
        i += 2
returnTrue
defgenerate_prime(bits: int) -> int:
"""生成一个 bits 位的素数（非常粗暴版本）"""
whileTrue:
# 生成一个 bits 位的随机奇数
        n = random.getrandbits(bits) | 1
# 确保最高位是 1，保证位数够
        n |= (1 << (bits - 1))
if is_probable_prime(n):
return n
defextended_gcd(a: int, b: int):
"""扩展欧几里得算法，返回 (g, x, y) 使得 a*x + b*y = g = gcd(a, b)"""
if b == 0:
return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
return g, x, y
defmod_inverse(a: int, m: int) -> int:
"""求 a 在模 m 下的乘法逆元：a * x ≡ 1 (mod m)"""
    g, x, _ = extended_gcd(a, m)
if g != 1:
raise ValueError("逆元不存在")
return x % m

有了这几个之后，生成 RSA 密钥就简单了：

defgenerate_keypair(bits: int = 512):
"""生成一对 RSA 密钥（教学用，bits 小而且没做严格素数测试）"""
# 1. 生成两个素数 p, q
    p = generate_prime(bits // 2)
    q = generate_prime(bits // 2)
while p == q:
        q = generate_prime(bits // 2)
    n = p * q
    phi = (p - 1) * (q - 1)
# 2. 选择 e，一般直接用 65537，如果不互质就往上加
    e = 65537
if gcd(e, phi) != 1:
        e = 3
while gcd(e, phi) != 1:
            e += 2
# 3. 计算 d
    d = mod_inverse(e, phi)
    public_key = (n, e)
    private_key = (n, d)
return public_key, private_key

再来把“字符串 ↔ 整数”封一下，因为 RSA 算法本质只认整数：

defbytes_to_int(b: bytes) -> int:
return int.from_bytes(b, byteorder="big")
defint_to_bytes(n: int) -> bytes:
# 自动按需要的字节数转换
    length = (n.bit_length() + 7) // 8
return n.to_bytes(length, byteorder="big")

加密 / 解密函数就很优雅了，用 Python 自带的 pow：

defrsa_encrypt(message: bytes, public_key):
    n, e = public_key
    m = bytes_to_int(message)
if m >= n:
raise ValueError("明文太长了，换更大的 key 或者做分块 / 混合加密")
    c = pow(m, e, n)
return c
defrsa_decrypt(cipher: int, private_key):
    n, d = private_key
    m = pow(cipher, d, n)
return int_to_bytes(m)

随便跑个小 demo：

if __name__ == "__main__":
    public_key, private_key = generate_keypair(512)  # 位数越大越安全，也越慢
    msg = "hello, RSA with Python!"
    plaintext = msg.encode("utf-8")
    cipher = rsa_encrypt(plaintext, public_key)
    print("密文（整数）:", cipher)
    decrypted = rsa_decrypt(cipher, private_key)
    print("解密后:", decrypted.decode("utf-8"))

这套跑通之后，你脑子里对 RSA 的流程基本就立住了：

• 先造钥匙（generate_keypair）
• 字符串转 bytes，再转 int
• pow(m, e, n) 加密
• pow(c, d, n) 解密

现实世界里怎么用？别自己造轮子

上面那版有几个致命问题：

• 素数测试太简陋
• 没有任何填充（padding），理论上能被各种数学攻击玩坏
• 密钥长度也不够大

实际项目里，一般都是用现成轮子，比如 PyCryptodome。大概长这样：

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
defgenerate_keys_prod(bits: int = 2048):
    key = RSA.generate(bits)
    private_key_pem = key.export_key()
    public_key_pem = key.publickey().export_key()
return public_key_pem, private_key_pem
defencrypt_with_lib(plaintext: bytes, public_key_pem: bytes) -> bytes:
    pub_key = RSA.import_key(public_key_pem)
    cipher = PKCS1_OAEP.new(pub_key)
return cipher.encrypt(plaintext)
defdecrypt_with_lib(ciphertext: bytes, private_key_pem: bytes) -> bytes:
    pri_key = RSA.import_key(private_key_pem)
    cipher = PKCS1_OAEP.new(pri_key)
return cipher.decrypt(ciphertext)
if __name__ == "__main__":
    pub_pem, pri_pem = generate_keys_prod(2048)
    msg = b"real world rsa with padding"
    c = encrypt_with_lib(msg, pub_pem)
    p = decrypt_with_lib(c, pri_pem)
    print(p.decode("utf-8"))

你会发现，用库的时候，其实你根本不用管什么 p q φ(n)，也不用手写逆元，所有危险的细节人家都封好了。

这时候自己实现 RSA 的意义就成了两件事：

• 学会它的工作原理，面试聊到能张嘴说清楚
• 偶尔跑个 tiny demo，或者在一些不那么严肃的环境里用一下（例如课堂作业、CTF 题目之类）

差不多就这样，你要是现在从头把上面的代码打一遍、跑通一遍，RSA 的整个链路就算过脑子了： “怎么选素数 → 怎么算 d → 用 pow 幂模运算 → 字节和整数之间怎么互转 → 实战里交给现成库”。

要是你哪天面试被问“用 Python 实现一下 RSA”，你直接说： “我能纯 Python 写一版教学实现，也能用 PyCryptodome 给你来一套带 OAEP 填充的工程化版本”，气场就不一样了。