先说个普遍现象很多人学了几年密码学真问起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 点。在这个例子里钟面就是模 1211 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。那么对任意明文整数 mm 与 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 整体结构规划模块化拆解动笔之前我把整个实现拆成了几个功能独立的模块这样代码逻辑清晰、方便测试模块职责关键函数基础数学工具扩展欧几里得、模逆元extended_gcd,mod_inverse素性检测与生成Miller-Rabin、生成大素数is_prime,generate_prime密钥生成生成公私钥对generate_keypair加解密整数明文的加密与解密encrypt,decrypt签名验签消息摘要的签名与验证sign,verify编码工具字符串与整数互转string_to_int,int_to_string这个划分看起来简单但对初学者特别友好。你可以先单独测试每一个函数再串起来跑全流程。我写的时候也是这个顺序先保证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 肯定是合数但如果等于 1n 不一定是素数因为存在一些合数比如 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, k40): 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 917 9 × 1 89 8 × 1 1回代能得到系数 2753。这个例子稍后还会用到。有了这些基础工具密钥生成函数就出来了import math def generate_keypair(bits1024): 生成 (公钥, 私钥) 对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_bytesdef 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)的含义是把字节串按大端序解释为整数。比如 babc 的三个字节分别是 97、98、99转成整数就是 97×65536 98×256 99 6382179。反之int_to_string需要把整数拆回字节(x.bit_length() 7) // 8是向上取整到整数字节数这个细节容易踩坑——如果字节数算少了还原出的字符串就是乱码。注意这种直接转换的编码方式有个硬限制明文整数必须小于 n。如果字符串太长、位数超过 nint.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, k40): 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(bits1024): 生成 (公钥, 私钥) 对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(bits1024) 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 的值。用经典教学参数可以更直观地验证全流程。取 p61、q53则 n3233φ(n)3120e17d2753。加密明文 m65计算 65^17 mod 3233。手推一下65^2 ≡ 99265^4 ≡ 123265^8 ≡ 26765^16 ≡ 16365^17 163×65 ≡ 896 (mod 3233)所以密文 c896。解密时 896^2753 ≡ 65明文回来了。这个经典例子我每次讲解时都愿意提一遍因为它数值小、可手算能帮你亲眼看到数学公式是如何一步步转起来的。7.2 密钥位数怎么选从512到4096的权衡位数是 RSA 安全性的核心指标。我做个简单对比模数位数十进制约略长度相对安全性密钥生成耗时参考典型用途512 位154 位数字已可破解极快百毫秒级仅教学演示1024 位309 位数字已不推荐秒级教学/旧系统2048 位617 位数字当前底线数秒到十几秒生产环境最低要求4096 位1234 位数字更安全十几秒到几十秒高安全场景我不建议把教学代码里的默认值直接当生产参数用。当前业界公认的底线是 2048 位重点应用建议 4096 位。位数越大n 的分解难度呈指数级上升但生成时间和加解密耗时也会明显增加。你可以亲手试试把generate_keypair(bits512)跑一遍再改成bits4096跑一遍感受一下时间差异——这是理解安全性和性能权衡最直观的方式。我实测下来512 位几乎是瞬间完成2048 位大概要 5 到 15 秒4096 位则在几十秒级别如果机器差一点等得你怀疑人生。8. 踩坑记录与安全须知教材RSA与实战RSA的关键差距8.1 素性检测的常见误区第一k轮数别设太小。有些简化版文章把 Miller-Rabin 写成只要 3、5 轮测试那是对教学场景的简化。我自己一开始图省事把k10生成小素数时没发现问题但换成大数后心里总觉得不踏实。后来统一改成 40 轮生成一个 1024 位密钥的耗时也没增加多少但错误率降到了极低水平。在安全敏感的密码学场景省什么都不能省测试轮数。第二小素数筛除不是可选项。做过一组对照实验同样的 512 位候选数不先筛小素数直接进 Miller-Rabin整体耗时大约是带筛除版本的好几倍。原因很简单大量合数能被 2、3、5 这种小素数整除与其跑一轮完整的 Miller-Rabin 才发现不是素数不如一次取模操作直接筛掉。这段优化的代码很有价值别嫌它啰嗦。第三随机数生成器的质量会影响安全性。random模块的随机性不是密码学安全的它更适合模拟和教学。在真实生产环境里应该用secrets模块或操作系统的密码学安全随机源来生成密钥材料。我在教学代码里用random是因为它方便但你要知道这个区别——这也是一些安全审计会盯得特别紧的细节。8.2 教材RSA与生产级RSA填充方案为什么必不可少你现在实现的这段代码在密码学里有个专门的称呼教科书式 RSATextbook RSA。它能在教学中完美展示数学原理但如果直接拿到生产环境用会有一堆安全问题。最大的问题是教科书 RSA 是确定性的。同样的明文每次加密得到的密文完全一样。攻击者看到两个相同的密文就能判断原始明文相同这泄露了信息。更危险的是如果明文空间很小比如只有 0 到 9 的数字攻击者可以预先算好所有明文的密文做一张对照表拿到密文直接查表还原明文。还有可延展性攻击攻击者拿到他人的密文 c m^e mod n不需要知道 m就能构造出 2m 的密文2^e × c mod n。在某些协议里这种数学上的可操作性会造成灾难性后果。所以生产环境必须使用填充方案。常见的是 PKCS#1 v1.5 和 OAEP最优非对称加密填充。它们会在加密前给消息加上随机填充字节让同样的明文每次加密都产生不同的密文并且对密文的微小改动高度敏感——任何一位被篡改解密后得到的明文就会面目全非从而整体丧失意义。8.3 常见攻击与防护建议一张速查表把实操中可能遇到的问题整理成一张排查表方便你对照参考问题原因解决方案/排查思路密钥生成慢得离谱候选数没设奇数位或者 Miller-Rabin 轮数过多确认 candidate加密后解密得到乱码明文整数 m ≥ n对消息分块或先做哈希再签名不要直接转超长字符串密的密文直接开根号能还原明文e 太小或明文太小使用 e65537生产环境配合 OAEP 填充生成的 p 和 q 相等随机数生成异常或 bits 位数太小确保 bits 至少 1024代码里加if p q: continue验签结果和原始消息不一致消息长度超过 n或int_to_string字节数算错检查(bit_length 7) // 8确保消息摘要小于 n多次加密同一明文产生相同密文教科书 RSA 确定性导致生产环境必须加随机化填充如 OAEP拿到私钥文件后无法导入私钥格式与解析器不匹配d和n必须成对且与公钥完全一致检查 PEM/DER 格式另外有一个常见的共模攻击值得知道如果多个系统不小心共用了同一个 n只是 e 和 d 不同攻击者拿到两个公钥 e1、e2对同一个明文 m 加密得到 c1、c2只要 gcd(e1, e2) 1就能通过扩展欧几里得算法还原出明文 m。所以永远不要跟别人共用同一个 n这相当于把私钥的秘密拱手让人。关于侧信道攻击像时序攻击、功耗攻击真实物理环境里确实存在。教科书代码里裸奔的pow计算在智能卡这类设备上可能因为运算时间差异泄露私钥信息。好在主流密码学库的内部实现都做了常数时间化处理所以我的终极建议是教学代码用来自学没问题生产环境一定用经过安全审计的成熟密码学库。自己写的算法自己心里爽可以别拿去加密任何真实数据。最后再分享一点个人体会我第一次完整跑通 RSA 时最深的感受是原来公钥能加密、私钥能解密这个看似神奇的行为背后就是几条数论定理的必然结果。欧拉定理像精准的齿轮把加密和解密严丝合缝地咬合在一起大整数分解的困难则像一道高墙把没有私钥的攻击者永远挡在墙外。这种数学变成了代码、代码又变成了安全的实感是单纯背公式完全体会不到的。如果你也正在学 RSA拿到代码后别只双击跑一遍就完事。我建议你做三件事把bits改成 512 和 2048 对比一下密钥生成耗时直观感受位数的威力手动把e改成 3 试试低指数对性能的影响再想想为什么实战不用它最后把你自己的学号或一段简短文字作为明文走一遍加解密全流程亲手验证一下同一个明文、同一把公钥、每次加密结果都一样这个教科书 RSA 的特性。动手改代码的过程比读十篇文章都有用。RSA 这个算法确实已经四十多岁了但理解它的价值任何时候都不过时。