手写RSA算法：用Python从零实现非对称加密与数字签名

先说个普遍现象：很多人学了几年密码学，真问起RSA该怎么实现，第一反应是调库。cryptography库一行sign，一行verify，完事。但你要是问他公钥和私钥到底是怎么算出来的，为什么别人拿到公钥也没法解密，多半就说不清了。我一直觉得，像 RSA 这种奠定现代网络安全基础的算法，不亲手实现一遍，始终隔着一层迷雾。

这篇文章我就带你用纯 Python，把 RSA 从密钥生成到加解密、再到签名验签，完整地手写一遍。不依赖任何第三方密码学库，只靠标准库里的random和math，大约两百行代码。你会亲眼看着一串明文变成天书般的密文再原样变回来，也会亲手算出那个"不可能被破解"的私钥。适合正在啃密码学教材的学生，也适合那些工作中天天用 RSA，却从没拆开看过它内部结构的开发者。

1. 先搞清楚RSA到底在解决什么问题

在动手写代码之前，我建议先花两分钟想明白 RSA 存在的意义。不是因为它算法经典所以学它，而是因为它解决了两个非常实际的问题：密钥分发和身份认证。

先看密钥分发。对称加密算法，比如 AES，加密和解密用的是同一把钥匙。这把钥匙怎么安全地送到对方手里？你通过网络发过去，中间人截获了怎么办？线下碰头交接，成本又太高。这就成了一个死循环：要加密通信，得先安全地共享密钥；要安全共享密钥，又得有一套安全的通信方式。RSA 这类公钥密码学出现之前，这个问题困扰了密码学界很多年。

公钥密码学的思路很巧妙：把加密能力与解密能力分开。公钥是公开的，谁都可以拿去用；私钥只有你自己知道，绝不外传。别人用你的公钥加密一段内容发给你，只有你手里的私钥能解开，中间人截获密文也没用。这就像在门口挂了一个信箱，任何人都能往里面投信，但只有拿钥匙的你能打开取信。加密和解密不再是同一把钥匙，这就是"非对称"三个字的来源。

再看身份认证。你怎么向别人证明一条消息确实是你发出的，而不是别人冒充的？RSA 的签名功能解决了这个问题：你用私钥对消息做"签名"，别人用你的公钥去验证。能通过验证，就说明这条消息一定是持私钥的人签发的，因为全世界只有你能算得出这个签名。这相当于你给文件盖上了一个无法伪造的私章。

RSA 之所以能同时做到这两件事，靠的就是那套著名的数学结构。这套结构设计得极其精巧：加密容易，解密难；但有秘密信息时，解密又变得很容易。这个"秘密信息"就是私钥，它在数学上表现为大整数的质因数分解。换句话说，RSA 的安全性建立在"大整数难分解"这个公认的计算难题上，而不是建立在算法保密上。接下来我们就把这套数学结构一层层拆开。

2. RSA的数学根基：模运算、欧拉定理与单向陷门函数

2.1 模运算：时钟上的算术

RSA 里面所有运算都在"模 n"的有限世界里进行。什么是模运算？简单说就是"取余数"。9 除以 4 得 2 余 1，所以 9 mod 4 = 1。最直观的类比是时钟：现在是 11 点，过 2 小时是几点？13 点，但钟面上显示 1 点。在这个例子里，"钟面"就是模 12，11 + 2 ≡ 1 (mod 12)。模运算的世界里，数字永远在 0 到 n-1 之间循环，怎么加、怎么乘都不会跑出去。

模运算有个特别重要的性质：先取模再运算和先运算再取模，结果一样。比如 (a mod n) × (b mod n) 再取模，等于 (a × b) 直接取模。这个性质让计算量大幅减小，也让"模幂"（算 a 的 b 次方再取模）可以用平方-乘算法高效完成。Python 里pow(a, b, n)就是专门干这件事的，底层已经优化得很好，这也是我们能快速跑通 RSA 的关键之一。

2.2 欧拉函数与欧拉定理：RSA的核心引擎

接下来是欧拉函数 φ(n)，它表示小于 n 且与 n 互质的正整数个数。什么叫互质？就是最大公约数为 1。比如 φ(8) = 4，因为在 1 到 8 之间，与 8 互质的是 1、3、5、7 这四个数。

欧拉函数有个极好的性质：当 p 和 q 是两个不同的素数时，φ(pq) = (p-1)(q-1)。这个看似简单的公式，是整个 RSA 的心脏。为什么？因为 p 和 q 是你自己选的秘密素数，你知道 φ(n) 的值；但外人只知道 n，不知道 p 和 q，就难以算出 φ(n)。这种信息不对称，直接构成了公私钥的不对称。

再往下走一步，就是欧拉定理：如果 a 与 n 互质，那么 a^φ(n) ≡ 1 (mod n)。翻译成人话：跟 n 互质的数，在模 n 的世界里自乘 φ(n) 次，一定会回到 1。这就像钟表走了整整一圈，指针回到原点。

RSA 正是把这个定理用到了极致。假设我们选定公钥指数 e 和私钥指数 d，让它们满足：

ed ≡ 1 (mod φ(n))

也就是说 ed = kφ(n) + 1。那么对任意明文整数 m（m 与 n 互质），就有：

m^(ed) ≡ m^(kφ(n)+1) ≡ (m^φ(n))^k × m ≡ 1^k × m ≡ m (mod n)

你看到没有？先做 e 次方、再做 d 次方，恰好回到原点。这就是为什么"公钥加密、私钥解密"能成立。加密是求 m^e mod n，解密是求 c^d mod n，一正一反，像变魔术一样变回了原样。而签名验签就是把这个过程反过来：私钥计算 m^d mod n，公钥计算 s^e mod n，同样成立。

（严格来说，欧拉定理要求 m 与 n 互质。当 m 恰好是 p 或 q 的倍数时，欧拉定理不直接适用。但这个情况发生的概率极低，而且可以分段证明 RSA 依然成立，教材里通常归为"细节"，不影响整体理解。）

2.3 单向陷门函数：为什么公钥公开也没事

现在来到 RSA 安全性的核心概念：单向陷门函数。一个函数是"单向"的，意思是正着算很容易，反着算极难。拿乘法举例：两个素数相乘得到一个大整数，这是小学乘法；但给一个大整数，找出哪两个素数相乘得到它，这就是"大整数分解问题"，当数足够大时（比如 2048 位），算到宇宙毁灭都算不完。

RSA 的关键在于：这个函数有一个"后门"，也就是陷门。知道秘密信息 p、q（也就是私钥的根源）的人，可以轻松分解 n、算出 φ(n)、推出私钥 d；不知道的人，面对 2048 位的大整数 n 就只能望洋兴叹。公钥 n 和 e 可以公开，因为公开它们不会暴露 p 和 q 的任何线索。这就是"公钥公开也没事"的原因。

明白了这些，数学地基就打好了。下面开始动手写代码。

3. 动手前的准备：环境、标准库与整体结构规划

3.1 环境准备与标准库选型

写 RSA 不需要安装任何第三方包，Python 标准库就足够了。我用的 Python 3.8 以上版本，主要是看中它原生支持任意精度的整数。C 语言里 int 是固定长度的，而 Python 的 int 可以无限膨胀，算 2048 位甚至 4096 位的大整数毫无压力，这对实现密码学算法是巨大的便利。

用到的标准库只有三个：

• random：生成随机数，用于挑选素数候选和 Miller-Rabin 素性检测的随机基。
• math：提供gcd最大公约数函数。
• time：在演示阶段统计密钥生成耗时。

如果非要用第三方库，cryptography和rsa确实一行能出结果，但那就失去了动手的意义。调库验证不了你对数学原理的理解。我在这个项目里刻意绕开所有现成密码学库，所有数学工具都自己写，这样每一步都看得见、摸得着。当然，这也意味着这段教学代码绝不用于生产环境——这一点我在最后一章会详细解释。

3.2 整体结构规划：模块化拆解

动笔之前，我把整个实现拆成了几个功能独立的模块，这样代码逻辑清晰、方便测试：

这个划分看起来简单，但对初学者特别友好。你可以先单独测试每一个函数，再串起来跑全流程。我写的时候也是这个顺序：先保证mod_inverse正确，再测is_prime，最后才组装密钥生成和加解密。这里给你一个建议：每写完一个函数，立刻在交互式环境里跑两个测试用例，不要全写完再调试，那样报错时定位问题会非常痛苦。

4. 大素数生成实战：Miller-Rabin素性检测从原理到代码

4.1 为什么不直接试除：1024位的恐怖规模

密钥生成第一步，是得到两个大素数 p 和 q。问题来了：怎么判断一个随机生成的数是素数？

最简单的思路是试除法：从 2 开始一个一个除到平方根。对小数没问题，但 RSA 需要的是 512 位甚至 1024 位的素数。这个量级的整数大约有 10^154 到 10^308 那么大，试除法需要的步骤比宇宙中的原子数量还多几个数量级。这条路直接堵死。

所以实战中用的是 Miller-Rabin 素性检测，一种概率性算法。它不能 100% 判定一个数是素数，但可以把误判概率压到比雷劈还低。我在代码里默认做 40 轮测试，误判概率不超过 4^(-40)，大约是 10^(-24)，这个数量级在实际应用中完全可以忽略。

4.2 Miller-Rabin的原理：费马小定理与二次探测

Miller-Rabin 建立在费马小定理之上：如果 n 是素数，那么对任意与 n 互质的 a，都有 a^(n-1) ≡ 1 (mod n)。如果某个 a 使得 a^(n-1) 不等于 1，那 n 肯定是合数；但如果等于 1，n 不一定是素数，因为存在一些合数（比如 561）对所有 a 都满足这个条件，它们叫 Carmichael 数。

为了区分 Carmichael 数，Miller-Rabin 又引入了二次探测。原理是：如果 n 是素数，那么方程 x² ≡ 1 (mod n) 的解只有 x ≡ 1 或 x ≡ -1（也就是 n-1）。我们把 n-1 写成 d × 2^r 的形式，从 a^d 开始，连续平方 r 次。如果过程中某个 x 平方后变成 1，但平方前的值既不是 1 也不是 n-1，就说明 n 是合数。

把这两个定理合在一起，就形成了 Miller-Rabin 的完整流程：随机选一个基 a，先算 x = a^d mod n，然后循环平方 r 次。只要出现 x = n-1 或 x = 1，这一轮就通过；否则 n 一定是合数。多轮测试下来，合数很难蒙混过关。

4.3 代码实现：小素数筛除与Miller-Rabin组合

直接上代码。我写了一个is_prime函数，先用小素数列表快速筛掉大部分合数，再进入 Miller-Rabin 主体，这样性能最好：

import random def is_prime(n, k=40): """Miller-Rabin素性检测，外加小素数试除优化""" if n < 2: return False # 先用小素数试除，快速过滤掉一大批合数 small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] for p in small_primes: if n % p == 0: return n == p # 将 n-1 写成 d * 2^r 的形式 d = n - 1 r = 0 while d % 2 == 0: d //= 2 r += 1 # 随机基，做 k 轮 Miller-Rabin 测试 for _ in range(k): a = random.randrange(2, n - 1) x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True def generate_prime(bits): """生成一个 bits 位的大素数""" while True: candidate = random.getrandbits(bits) # 确保最高位为1（位数正确），最低位为1（奇数） candidate |= (1 << bits - 1) | 1 if is_prime(candidate): return candidate

这里有两个细节值得注意。

第一，生成候选数时为什么要candidate |= (1 << bits - 1) | 1？设最高位为 1，是为了保证生成的数确实是 bits 位，而不是随到一个小数。设最低位为 1，是为了保证它是奇数，因为大于 2 的素数都是奇数，这样能跳过所有偶数候选，生成效率直接翻倍。

第二，random.getrandbits(bits)生成的是一个 bits 位的随机数。对于 512 位的素数，按素数密度估算，平均每检查约 177 个奇数就能命中一个素数。实测下来，生成一个 512 位素数通常不到 0.5 秒，配合 Miller-Rabin 的 40 轮测试，既快又稳。

5. 密钥生成全流程：从p、q到公私钥对的完整推导

5.1 生成p和q：为什么要求它们"差不多大"

有了generate_prime，密钥生成就水到渠成了。先分别生成两个位数相同的大素数 p 和 q，然后立刻计算n = p * q和phi = (p - 1) * (q - 1)。

这里有一个容易被忽略的细节：p 和 q 的位数要相同，且差值不能太小。如果 p 和 q 一个特别大一个特别小，攻击者可以用费马分解法快速突破。举个例子，如果 p 和 q 非常接近，n 的平方根跟 p、q 也很接近，费马分解就能在较短时间内把 n 拆开。所以工程标准做法是生成位数相同的 p 和 q，并且各自随机，不指定具体的差值，让概率本身保证大差异。

第二个细节是 p 和 q 不能相等。如果 p = q，那么 n 就是一个完全平方数，φ(n) = p(p-1) 而不是 (p-1)^2，整条数学链路就断了。虽然随机生成时两个数相等的概率极低，代码里我还是加了if p == q: continue的防护，这个习惯很好，防御性编码在任何项目里都不会错。

5.2 公钥指数e：为什么是65537

公钥指数 e 的选择也是个讲究活。我在代码里直接固定为65537，也就是 2^16 + 1。为什么选这个数？

第一，它是一个费马数，而且被证明是素数。e 与 φ(n) 互质的概率极高（只要 φ(n) 不是 65537 的倍数），这样gcd(e, phi) != 1的失败分支几乎永远不会触发。

第二，65537 的二进制形式是10000000000000001，只有两个位是 1。在快速模幂算法中，指数二进制里 1 的个数决定了乘法操作的次数，0 的个数决定平方操作的次数。指数 65537 时只需要 1 次乘法和 16 次平方，加解密速度非常快。相比之下，随便选个有几十个 1 的随机指数，计算成本会成倍上升。

第三，从安全角度考虑，e 不能选太小。如果 e = 3，而明文 m 又很小，以至于 m^3 还小于 n，那么直接对密文开三次方就能还原明文。65537 足够大，能够有效规避这类低指数攻击。

5.3 私钥d的秘密：扩展欧几里得算法

私钥 d 是 e 在模 φ(n) 下的乘法逆元，也就是满足 ed ≡ 1 (mod φ(n)) 的数。求乘法逆元的经典算法是扩展欧几里得算法。普通欧几里得算法大家很熟，辗转相除求最大公约数；扩展版本在求 gcd 的同时，还记录了如何把 gcd 表示成 a 和 b 的线性组合：gcd(a, b) = ax + by。

当 gcd(e, φ(n)) = 1 时，扩展欧几里得得到的 x 就满足 e·x + φ(n)·y = 1。两边同时模 φ(n)，就得到 e·x ≡ 1 (mod φ(n))，所以 x 就是我们要找的 d。不过 x 可能是负数，所以最后return x % m把它转成正数。

代码实现如下：

def extended_gcd(a, b): """扩展欧几里得算法，返回 (g, x, y) 使得 a*x + b*y = g""" 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 def mod_inverse(a, m): """求 a 在模 m 下的乘法逆元""" g, x, _ = extended_gcd(a, m) if g != 1: raise ValueError(f"{a} 在模 {m} 下没有乘法逆元") return x % m

这里递归实现的代码很简洁，但初学者可能觉得绕。你可以用小例子手推一遍：比如求 17 在模 3120 下的逆元。3120 = 17 × 183 + 9，17 = 9 × 1 + 8，9 = 8 × 1 + 1，回代能得到系数 2753。这个例子稍后还会用到。

有了这些基础工具，密钥生成函数就出来了：

import math def generate_keypair(bits=1024): """生成 (公钥, 私钥) 对，bits 是模数 n 的位数""" while True: p = generate_prime(bits // 2) q = generate_prime(bits // 2) if p == q: continue n = p * q if n.bit_length() != bits: continue phi = (p - 1) * (q - 1) e = 65537 if math.gcd(e, phi) != 1: continue d = mod_inverse(e, phi) return (e, n), (d, n)

生成 1024 位密钥时，p 和 q 各取 512 位，乘积 n 大概率恰好是 1024 位。n.bit_length() != bits这个检查是为了保证模数位数精准，虽然不检查也不影响加解密正确性，但密钥强度的指标就是 n 的位数，所以这个检查有实际意义。

6. 加密解密与签名验签：完整可运行的RSA代码

6.1 明文到整数的转换

RSA 的运算对象是整数，不是字符串。所以在加密之前，得把"Hello, RSA!"这样的字符串转成一个大整数。Python 里最方便的做法是int.from_bytes：

def string_to_int(s): return int.from_bytes(s.encode('utf-8'), 'big') def int_to_string(x): return x.to_bytes((x.bit_length() + 7) // 8, 'big').decode('utf-8')

int.from_bytes(..., 'big')的含义是把字节串按大端序解释为整数。比如 b'abc' 的三个字节分别是 97、98、99，转成整数就是 97×65536 + 98×256 + 99 = 6382179。反之，int_to_string需要把整数拆回字节，(x.bit_length() + 7) // 8是向上取整到整数字节数，这个细节容易踩坑——如果字节数算少了，还原出的字符串就是乱码。

注意：这种直接转换的编码方式有个硬限制：明文整数必须小于 n。如果字符串太长、位数超过 n，int.from_bytes出来的整数 >= n，加解密就会出错，因为模 n 的世界里根本容纳不下这个数。教学演示用小消息没问题，生产环境必须先对消息做哈希，再对摘要做签名，或者用 OAEP 之类的填充方案对消息分块。后面我会细说。

6.2 加密与解密：核心数学操作

加密和解密本身只有三行：

def encrypt(m, public_key): e, n = public_key return pow(m, e, n) def decrypt(c, private_key): d, n = private_key return pow(c, d, n)

看着简单，但背后的计算量可不小。m^e mod n 在 e 接近 65537、n 是 2048 位大整数时，直接算 m^e 再取模是天文数字，根本算不完。Python 内置的pow(a, b, n)三参数版本用了快速模幂算法，边乘边取模，计算量大约是 O(log e) 次乘法，所以 2048 位密钥的一次加密在毫秒级就能完成。这就是为什么我强烈建议用内置pow，而不是自己写一个(m ** e) % n——后者真的会把内存撑爆。

6.3 签名验签：角色的反转

签名验签的本质是加密解密的角色反转：私钥"加密"就是签名，公钥"解密"就是验签。数学上，因为 ed ≡ 1 (mod φ(n))，所以 m^(ed) ≡ m 和 m^(de) ≡ m 是等价的，e 和 d 的顺序可以互换。签名时用私钥的 d 对消息摘要做模幂，验签时用公钥的 e 对签名做模幂，如果结果等于原始摘要，签名就验证通过。

def sign(message_int, private_key): d, n = private_key return pow(message_int, d, n) def verify(signature_int, public_key): e, n = public_key return pow(signature_int, e, n)

需要单独说明的是：实际的 RSA 签名绝对不是直接对消息做私钥运算，而是先对消息计算密码学哈希（比如 SHA-256），再对哈希摘要做签名。这样做有两个原因。第一，摘要很短，比如 SHA-256 摘要只有 256 位，远远小于 2048 位的 n，避免了消息过长的问题。第二，对原文直接签名存在选择明文攻击的风险，攻击者可以诱导你签一些看起来无害但实际有特殊数学结构的消息。我在教学代码里直接对字符串整数签名，是为了简化演示，但你心里要清楚生产代码该怎么写。

6.4 汇总：完整可运行的代码

下面是所有代码的完整整合，保存为rsa_demo.py可以直接运行：

import random import math import time # ---------- 基础数学工具 ---------- def extended_gcd(a, b): """扩展欧几里得算法，返回 (g, x, y) 使得 a*x + b*y = g""" 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 def mod_inverse(a, m): """求 a 在模 m 下的乘法逆元""" g, x, _ = extended_gcd(a, m) if g != 1: raise ValueError(f"{a} 在模 {m} 下没有乘法逆元") return x % m # ---------- 素性检测与素数生成 ---------- def is_prime(n, k=40): """Miller-Rabin素性检测，外加小素数试除优化""" if n < 2: return False small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] for p in small_primes: if n % p == 0: return n == p d = n - 1 r = 0 while d % 2 == 0: d //= 2 r += 1 for _ in range(k): a = random.randrange(2, n - 1) x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True def generate_prime(bits): """生成一个 bits 位的大素数""" while True: candidate = random.getrandbits(bits) candidate |= (1 << bits - 1) | 1 if is_prime(candidate): return candidate # ---------- RSA 密钥生成 ---------- def generate_keypair(bits=1024): """生成 (公钥, 私钥) 对，bits 是模数 n 的位数""" while True: p = generate_prime(bits // 2) q = generate_prime(bits // 2) if p == q: continue n = p * q if n.bit_length() != bits: continue phi = (p - 1) * (q - 1) e = 65537 if math.gcd(e, phi) != 1: continue d = mod_inverse(e, phi) return (e, n), (d, n) # ---------- 加密解密 ---------- def encrypt(m, public_key): e, n = public_key return pow(m, e, n) def decrypt(c, private_key): d, n = private_key return pow(c, d, n) # ---------- 签名验签 ---------- def sign(m, private_key): d, n = private_key return pow(m, d, n) def verify(s, public_key): e, n = public_key return pow(s, e, n) # ---------- 字符串与整数互转（仅用于演示，消息需小于 n） ---------- def string_to_int(s): return int.from_bytes(s.encode('utf-8'), 'big') def int_to_string(x): return x.to_bytes((x.bit_length() + 7) // 8, 'big').decode('utf-8') # ---------- 演示 ---------- if __name__ == "__main__": print("正在生成 1024 位 RSA 密钥对...") start = time.time() pub_key, priv_key = generate_keypair(bits=1024) print(f"密钥生成耗时：{time.time() - start:.2f} 秒") e, n = pub_key d, _ = priv_key print(f"公钥 e = {e}") print(f"公钥 n = {n}") print(f"私钥 d = {d}") # 加解密演示 plaintext = "Hello, RSA!" m = string_to_int(plaintext) print(f"\n明文：{plaintext}") print(f"明文整数 m = {m}") c = encrypt(m, pub_key) print(f"加密后 c = {c}") m2 = decrypt(c, priv_key) print(f"解密后 m' = {m2}") print(f"还原明文：{int_to_string(m2)}") # 签名验签演示 message = "重要的合同金额：1000000元" msg_int = string_to_int(message) sig = sign(msg_int, priv_key) print(f"\n签名 sig = {sig}") recovered = verify(sig, pub_key) print(f"验签还原 = {int_to_string(recovered)}")

注意依赖关系：这段代码里我同时用了random、math、time三个标准库。如果某个函数你只想单独测试，记得先补齐对应的 import。

7. 跑通演示并看懂输出：密钥生成耗时与参数选择

7.1 关键输出解读：真实的一次运行长什么样

我自己在笔记本上跑这段代码，1024 位密钥的生成耗时通常在 1 到 3 秒之间，具体取决于你机器的 CPU 性能和随机数运气。所谓"运气"，是因为素数的生成是概率性的，随机出的候选数可能很快命中素数，也可能接连试很多个都是合数。

因为每次运行随机种子不同，实际的n和d都是完全不同的巨大数字。n 是一个 309 位左右的十进制数（1024 位约等于 308 到 309 位十进制数字），打印在终端里会占据好几行。即便两个人跑同一段代码，生成的密钥也几乎不可能重复，这正是 RSA 安全性的又一个体现：密钥空间足够大，大到撞车概率可以忽略不计。

上面代码里我特意把公钥指数e单独打印出来，你会看到它永远是 65537。这是设计使然，n 和 d 天天变，e 始终不变。这个形式上的"不变量"也提醒我们：公钥的公开部分里，真正需要保护的是 n 的位数和强度，而不是 e 的值。

用经典教学参数可以更直观地验证全流程。取 p=61、q=53，则 n=3233，φ(n)=3120，e=17，d=2753。加密明文 m=65，计算 65^17 mod 3233。手推一下：65^2 ≡ 992，65^4 ≡ 1232，65^8 ≡ 267，65^16 ≡ 163，65^17 = 163×65 ≡ 896 (mod 3233)，所以密文 c=896。解密时 896^2753 ≡ 65，明文回来了。这个经典例子我每次讲解时都愿意提一遍，因为它数值小、可手算，能帮你亲眼看到数学公式是如何一步步转起来的。

7.2 密钥位数怎么选：从512到4096的权衡

位数是 RSA 安全性的核心指标。我做个简单对比：

我不建议把教学代码里的默认值直接当生产参数用。当前业界公认的底线是 2048 位，重点应用建议 4096 位。位数越大，n 的分解难度呈指数级上升，但生成时间和加解密耗时也会明显增加。你可以亲手试试把generate_keypair(bits=512)跑一遍，再改成bits=4096跑一遍，感受一下时间差异——这是理解"安全性和性能权衡"最直观的方式。我实测下来，512 位几乎是瞬间完成，2048 位大概要 5 到 15 秒，4096 位则在几十秒级别，如果机器差一点，等得你怀疑人生。

8. 踩坑记录与安全须知：教材RSA与实战RSA的关键差距

8.1 素性检测的常见误区

第一，k轮数别设太小。有些简化版文章把 Miller-Rabin 写成只要 3、5 轮测试，那是对教学场景的简化。我自己一开始图省事把k=10，生成小素数时没发现问题，但换成大数后心里总觉得不踏实。后来统一改成 40 轮，生成一个 1024 位密钥的耗时也没增加多少，但错误率降到了极低水平。在安全敏感的密码学场景，省什么都不能省测试轮数。

第二，小素数筛除不是可选项。做过一组对照实验：同样的 512 位候选数，不先筛小素数直接进 Miller-Rabin，整体耗时大约是带筛除版本的好几倍。原因很简单，大量合数能被 2、3、5 这种小素数整除，与其跑一轮完整的 Miller-Rabin 才发现不是素数，不如一次取模操作直接筛掉。这段优化的代码很有价值，别嫌它啰嗦。

第三，随机数生成器的质量会影响安全性。random模块的随机性不是密码学安全的，它更适合模拟和教学。在真实生产环境里，应该用secrets模块或操作系统的密码学安全随机源来生成密钥材料。我在教学代码里用random是因为它方便，但你要知道这个区别——这也是一些安全审计会盯得特别紧的细节。

8.2 教材RSA与生产级RSA：填充方案为什么必不可少

你现在实现的这段代码，在密码学里有个专门的称呼："教科书式 RSA"（Textbook RSA）。它能在教学中完美展示数学原理，但如果直接拿到生产环境用，会有一堆安全问题。

最大的问题是：教科书 RSA 是确定性的。同样的明文，每次加密得到的密文完全一样。攻击者看到两个相同的密文，就能判断原始明文相同，这泄露了信息。更危险的是，如果明文空间很小（比如只有 0 到 9 的数字），攻击者可以预先算好所有明文的密文，做一张对照表，拿到密文直接查表还原明文。

还有可延展性攻击：攻击者拿到他人的密文 c = m^e mod n，不需要知道 m，就能构造出 2m 的密文（2^e × c mod n）。在某些协议里，这种数学上的"可操作性"会造成灾难性后果。

所以生产环境必须使用填充方案。常见的是 PKCS#1 v1.5 和 OAEP（最优非对称加密填充）。它们会在加密前给消息加上随机填充字节，让同样的明文每次加密都产生不同的密文，并且对密文的微小改动高度敏感——任何一位被篡改，解密后得到的明文就会面目全非，从而整体丧失意义。

8.3 常见攻击与防护建议：一张速查表

把实操中可能遇到的问题整理成一张排查表，方便你对照参考：

另外有一个常见的共模攻击值得知道：如果多个系统不小心共用了同一个 n，只是 e 和 d 不同，攻击者拿到两个公钥 e1、e2，对同一个明文 m 加密得到 c1、c2，只要 gcd(e1, e2) = 1，就能通过扩展欧几里得算法还原出明文 m。所以永远不要跟别人共用同一个 n，这相当于把私钥的秘密拱手让人。

关于侧信道攻击，像时序攻击、功耗攻击，真实物理环境里确实存在。教科书代码里裸奔的pow计算，在智能卡这类设备上可能因为运算时间差异泄露私钥信息。好在主流密码学库的内部实现都做了常数时间化处理，所以我的终极建议是：教学代码用来自学没问题，生产环境一定用经过安全审计的成熟密码学库。自己写的算法，自己心里爽可以，别拿去加密任何真实数据。

最后再分享一点个人体会

我第一次完整跑通 RSA 时，最深的感受是：原来"公钥能加密、私钥能解密"这个看似神奇的行为，背后就是几条数论定理的必然结果。欧拉定理像精准的齿轮，把加密和解密严丝合缝地咬合在一起；大整数分解的困难则像一道高墙，把没有私钥的攻击者永远挡在墙外。这种"数学变成了代码、代码又变成了安全"的实感，是单纯背公式完全体会不到的。

如果你也正在学 RSA，拿到代码后别只双击跑一遍就完事。我建议你做三件事：把bits改成 512 和 2048 对比一下密钥生成耗时，直观感受位数的威力；手动把e改成 3 试试低指数对性能的影响，再想想为什么实战不用它；最后把你自己的学号或一段简短文字作为明文，走一遍加解密全流程，亲手验证一下"同一个明文、同一把公钥、每次加密结果都一样"这个教科书 RSA 的特性。动手改代码的过程，比读十篇文章都有用。RSA 这个算法确实已经四十多岁了，但理解它的价值，任何时候都不过时。