0x9a.com
RSA 算法详解：从手算过程到逆向实战
RSA 听起来像是某种高深莫测的魔法，教科书里满屏的 $e, d, n, \phi$ 更是让人头大。但对于程序员来说，它的本质其实出奇的简单——就是几个大整数在做取模运算。
今天我们不掉书袋，不搞那些让人昏昏欲睡的定理证明。咱们来点刺激的：手算一把 RSA，然后化身黑客，看看如何通过修改二进制（Patch）来制作一个“伪造”的注册机。
一、 手算 RSA：见证奇迹的时刻
RSA 的核心逻辑其实就三步：造锁、锁上、打开。
为了演示，我们不用那种几千位的庞然大物，只选两个袖珍素数 $p=61$ 和 $q=53$，带你走一遍这个神奇的过程。
1. 打造钥匙 (Key Generation)
我们要造出一把公钥（给大家用的保险箱）和一把私钥（自己藏好的钥匙）。
- 第一步：找两个素数
- 随便选：$p = 61, q = 53$
- 第二步：算出模数 N
- 这就是那个“大锁”：$N = p \times q = 3233$
- 第三步：算出欧拉函数 $\phi(N)$
- 这是个中间秘密：$\phi(N) = (p-1)(q-1) = 3120$
- 第四步：选个公钥指数 e
- 要求：比 $\phi(N)$ 小，且跟它互质。
- 我们就选：$e = 17$
-
第五步：算出私钥指数 d
- 这是最关键的一步！我们要找一个数 $d$，让它满足：$d \cdot 17 \equiv 1 \pmod{3120}$
- 算出来：$d = 2753$
💡 为什么 d = 2753？（点击查看数学魔法）
简单来说，我们要找一个数字 $d$，使得 $(d \times 17) \div 3120$ 的余数等于 1。
验证一下：
1. $2753 \times 17 = 46801$
2. $46801 \div 3120 = 15 \dots$ 余数 $1$Bingo！$2753$ 就是我们要找的私钥指数。
最终成果：
🔑 公钥：$(17, 3233)$ —— 拿去给人加密用。
🗝️ 私钥：$(2753, 3233)$ —— 自己藏好别丢了。
2. 加密：发送秘密数字
公式：$C \equiv M^e \pmod N$
假设我要发给你一个数字 65（明文 $M$）。
我就用你的公钥算一下：
$65^{17} \pmod{3233} = 2790$
发出的密文就是 2790。
3. 解密：还原真相
公式：$M \equiv C^d \pmod N$
你收到了 2790，拿出你的私钥一算：
$2790^{2753} \pmod{3233} = 65$
神奇吧？原来的数字 65 又回来了！这就是数学的魅力。
💡 程序员的顿悟：
仔细看上面的公式，你会发现一个惊人的事实：加密和解密，代码竟然是一模一样的！
在计算机眼里，它们都是调用同一个函数
pow(base, exponent, modulus)：
- 加密：
pow(明文, e, N)- 解密：
pow(密文, d, N)所谓的加密和解密，无非就是把不同的数字扔进同一个“模幂运算”的机器里罢了。
二、 公钥与私钥：加密与签名的『角色分工』
很多初学者容易搞混公钥和私钥的用途。其实记住两个核心场景，就永远不会忘：
1. 加密通信 (Confidentiality) —— “我要给你发情书”
- 场景：Alice 想给 Bob 发一条秘密消息，不想被别人看到。
- 操作：Alice 拿 Bob 的公钥把消息锁上（加密）。
- 结果：只有拥有对应私钥的 Bob 才能打开（解密）。
- 口诀：公钥加密，私钥解密。
- 比喻：就像 Bob 在家门口放了一个带投信口的保险箱（公钥）。谁都可以往里面塞信（加密），但只有拿着钥匙的 Bob （私钥） 才能打开箱子拿出信件。
2. 数字签名 (Authentication) —— “这真的是我写的”
- 场景：Bob 发了一条公告，大家担心是有人冒充 Bob 发的。
- 操作：Bob 用自己的私钥对消息（的哈希值）盖个章（签名）。
- 结果：大家拿 Bob 的公钥来验证这个章是不是真的。
- 口诀：私钥签名，公钥验签。
- 比喻：Bob 有一枚独一无二的私章（私钥），他在文件上盖了章。大家手里都有 Bob 的印章备案（公钥），拿来一比对，如果纹路一致，就证明这文件确实是 Bob 签发的，而且没人篡改过。
3. 谁在明，谁在暗？
- 所有人可见：公钥 $(e, N)$、加密后的密文、签名结果。
- 打死不能说：私钥 $d$。还有生成 $N$ 的两个“祖宗”素数 $p$ 和 $q$，以及中间产物 $\phi(N)$。因为一旦它们泄露，算出 $d$ 也就是一眨眼的事。
4. 灵魂拷问：公钥私钥能不能反过来用？
既然数学公式 $M^{ed} \equiv M \pmod N$ 是对称的，那能不能把 $(d, N)$ 公开当公钥，把 $(e, N)$ 藏起来当私钥？
理论上可以，但工程上是找死。
原因在于效率与习惯。
为了让加密速度飞快，我们在生成密钥时，通常会固定选一个很小的 $e$（最常用的是 65537，二进制只有两个 1，算起来极快）。
然后根据这个 $e$ 算出巨大的 $d$。
- 如果你把巨大的 $d$ 公开当公钥，把小小的 $e=65537$ 当私钥藏起来...
- 黑客：嘿嘿，我就猜你的私钥是 65537，一试一个准！
除非你生成的 $e$ 也是一个巨大的随机数（此时 $e$ 和 $d$ 地位真正平等），但那样加密会变得巨慢无比，失去了 RSA “公钥加密快”的优势。
三、 为什么 RSA 坚不可摧？
1. 单向陷门函数 (The Trapdoor)
想象你把两种颜色的油漆（$p$ 和 $q$）倒进桶里混合（相乘得到 $N$）。
- 正向操作（混合）：非常容易。计算机算 $p \times q$ 只要微秒级。
- 逆向操作（分离）：看着混合后的颜色，想要还原出原本是哪两种颜色，这在数学上极其困难。
这就是陷门：除非你有钥匙（知道其中一个素数），否则你无法通过 $N$ 反推出 $d$。
2. 为什么分解 N 那么难？
对于 2048 位的 RSA 模数，它有 600 多位十进制数字。即便动用全世界所有的算力，也要算到宇宙毁灭才能分解出来。这就是 RSA 安全的底气。
3. 为什么非要是 2 个素数？
-
如果是 1 个素数 ($N=p$)：
那 $\phi(N) = N-1$。黑客拿到 $N$ 直接减 1 就得到了 $\phi(N)$，私钥直接秒破。这就是后面我们要讲的“素数 Patch”破解原理。 -
如果是 3 个及更多素数：
虽然能用，但在同样的 $N$ 长度下，素数因子越多，每个因子就越小。因子越小，被特定算法（如 ECM）找到概率就越大。所以 2 个大素数 是目前公认的最佳平衡点。
四、 也不要高兴得太早：RSA 的那些坑
如果你在生成钥匙的时候偷懒，分分钟会被数学家教做人。这里有一份避雷指南：
1. 坑一：选了太小的 d (Wiener Attack)
如果你为了解密快，选了一个很小的 $d$（当 $d < N^{0.25}$ 左右时），攻击者可以通过连分数展开，在几秒钟内算出你的 $d$。
2. 坑二：选了离得太近的 p 和 q (Fermat Attack)
如果 $p$ 和 $q$ 挨得太近，攻击者可以在 $\sqrt{N}$ 附近快速搜到因子。
3. 坑三：裸奔的 RSA (No Padding)
教科书上的 $C = M^e \pmod N$ 叫 Raw RSA。现实中绝对不能直接用。
- 确定性问题：加密相同的 "Hello"，密文永远一样。黑客可以查表猜内容。
-
小明文攻击：如果 $M$ 很小且 $e$ 也很小，使得 $M^e < N$，那攻击者直接对密文 $C$ 开 $e$ 次方根就能得到明文 $M$（比如 $e=3$ 时特别危险）。
🕵️♂️ 演示：e=3 时的立方根攻击
当 $e=3$ 且 $M < N^{1/3}$ 时，$M^3 < N$，直接计算：
# 攻击示例 c = pow(m, 3, n) # 加密：C = M³ mod N recovered_m = int(c ** (1/3)) # 开立方根 # 如果 M³ < N，则 recovered_m == m这种情况下无需 any 密码学知识，纯数学计算即可破解！
解决方案：加点料 (Padding)
为了解决这些问题，我们需要在明文 $M$ 前后加一些随机数，这就叫 Padding。
-
PKCS#1 v1.5：
- 地位：老前辈，Windows XP 时代的标配。
- 做法：在明文前面硬塞一串非零的随机字节。
- 缺点：虽然解决了确定性问题，但因为它对错误格式的报错有规律，容易被黑客利用（Bleichenbacher 攻击），通过不断尝试发送畸形密文来推断出明文。现在不推荐用于加密，只建议用于签名兼容。
-
OAEP (Optimal Asymmetric Encryption Padding)：
- 地位：现任带头大哥，最稳健的方案。
- 原理：它引入了哈希函数（如 SHA-256）和掩码生成函数 (MGF)。它不仅仅是拼接随机数，而是把随机数生成一个掩码，跟明文进行异或（XOR）运算。
- 优点：哪怕明文只变动一个比特，整个密文都会面目全非。而且它对错误信息的处理非常严格，让黑客无从下手。
正确姿势：新系统开发请无脑选 OAEP。
五、 骨灰级硬核 已知 $(e, d, N)$，能不能求 $p, q$？
这是一个经常被问到的问题：“如果我的私钥 $d$ 泄露了，我能不能只换个私钥，继续用原来的公钥 $(e, N)$？”
答案是：绝对不行！
因为知 $d$ 必知 $p, q$。一旦攻击者拿到了你的私钥 $d$，他不仅能解密，还能通过数学算法迅速分解出你的模数 $N$ 是哪两个素数乘出来的。
1. 原理简述
我们知道 $ed \equiv 1 \pmod{\phi(N)}$，也就是说 $ed - 1$ 是 $\phi(N)$ 的倍数。
而 $\phi(N) = (p-1)(q-1)$ 是个偶数，所以 $ed-1$ 肯定包含了很多个因子 2。
利用随机化算法（类似 Miller-Rabin 素性测试的逆过程），我们可以利用这个性质快速找到 $N$ 的非平凡因子。
2. 代码验证
别光说不练，这就有一段 Python 代码。只要给它 $e, d, N$，它就能瞬间把 $p$ 和 $q$ 吐出来：
import random
import math
def crack_factors(e, d, n):
k = e * d - 1
t = 0
# 把 k 变成 2^t * r 的形式
while k % 2 == 0:
k //= 2
t += 1
r = k
while True:
g = random.randint(2, n - 1)
y = pow(g, r, n)
if y == 1 or y == n - 1:
continue
for i in range(1, t):
x = pow(y, 2, n)
if x == 1:
# 找到了！gcd(y - 1, n) 就是其中一个因子
p = math.gcd(y - 1, n)
q = n // p
return p, q
if x == n - 1:
break
y = x
# 测试一下
N = 3233
e = 17
d = 2753
p, q = crack_factors(e, d, N)
print(f"成功分解: p={p}, q={q}")
# 输出: 成功分解: p=61, q=53
结论：私钥泄露 = 模数作废。必须重新生成 $p$ 和 $q$，换个全新的 $N$。
六、 黑客时间：从 8-bit 音乐说起
如果你经历过 Windows 98/XP 时代，一定对“注册机”（Keygen）这个词记忆犹新。
那时候的注册机简直就是一种数字艺术品：双击打开，满屏闪烁的霓虹色字符，背景里循环播放着极具感染力的 8-bit/Chiptune 音乐。你只需要输入用户名，点击 "Generate"，啪地一声，一串完美的注册码就跳了出来。
最关键的是：你不需要修改软件本身，直接输入就能用。
1. 为什么以前的注册机不需要 Patch？
在那个“前 RSA 时代”，大多数软件采用的是对称逻辑：
- 锁和钥匙是一对：软件里藏着一个算法（可能是简单的异或、位移或者自定义的数学变换）。
- 逻辑对称：验证注册码的逻辑，反过来就是生成注册码的逻辑。
- 黑客视角：只要反编译软件，在代码里找到了这把藏着的“钥匙”，就能写出注册机。
2. RSA：打破规则的“单向墙”
当开发者开始使用 RSA 后，黑客们发现老套路不灵了。钥匙在作者家里，软件里只有公钥。即便你把汇编代码翻烂了，也找不到那把生成注册码的私钥 $d$。
3. 终极奥义：移花接木 (Patching)
既然拿不到作者的钥匙，黑客们决定：既然钥匙我拿不走，我就把你的锁给换了！
这就是为什么现在的破解通常是“注册机 + 补丁（Patch）”套餐：
- 第一步（换锁）：黑客修改软件的二进制文件，把作者硬编码在里面的模数 $N$ 替换成黑客自己生成的 $N'$。
- 第二步（配钥匙）：黑客使用自己那一套密钥对里的私钥 $d'$ 来写注册机。
⚠️ 安全提醒：现代软件普遍采用代码签名和完整性校验机制来防止未经授权的修改。
4. 骚操作：把 N Patch 成素数
如果黑客不想自己重新生成一套复杂的密钥对，还有一个更“骚”的招式：把 N 变成素数。
假设软件原本的模数 $N$ 是一个 1024 位的巨大合数，黑客直接用 16 进制编辑器把它改成一个非常接近的素数 $N_{prime}$。
之所以这么做，是因为在 1024 位的数字海洋里，素数分布得非常密集。黑客往往只需要改动模数末尾的一个字节，就能把它“微调”成一个素数——这种“改一字节而动全身”的优雅，正是黑客们孜孜不倦的追求。
这一改，RSA 的数学大厦就原地崩塌了：
- 合数 N 下：$\phi(N)$ 是个天大的秘密，必须知道 $p$ 和 $q$ 才能算。
- 素数 N 下：$\phi(N_{prime}) = N_{prime} - 1$。全世界都知道了！
黑客现在可以瞬间写出针对这个 Patch 版软件的注册机：
# 针对素数 N 的极致注册机逻辑
# 1. 提取软件里被 Patch 后的素数 N_prime
# 2. 计算私钥 d_prime
d_prime = pow(e, -1, N_prime - 1)
# 3. 输入用户名 hash_user，生成注册码
license = pow(hash_user, d_prime, N_prime)
当你在软件里输入这个 license 时，被 Patch 过的软件运行验证公式：
$ \text{license}^e \pmod{N_{prime}} $
结果正好等于 hash_user。破解成功。
七、 时代的变迁：为什么 RSA 正在慢慢退场？
虽然 RSA 是经典，但现在的 HTTPS 证书、比特币等几乎清一色地转向了 ECC（椭圆曲线加密）。
1. 钥匙长度的“指数爆炸”
RSA 的安全性靠“堆长度”来维持。为了保持同等的安全强度，RSA 的密钥长度需要迅速膨胀：
| 安全强度 | RSA 密钥长度 | ECC 密钥长度 | 差距 | 标准来源 |
|---|---|---|---|---|
| 128 位 (标准) | 3072 位 | 256 位 | ~12 倍 | NIST P-256 |
| 256 位 (极高) | 15360 位 | 512 位 | ~30 倍 | Brainpool P-512r1 |
2. 性能：移动端的救星
由于 ECC 的密钥短得多，它在计算开销、带宽占用和电池能耗上全面超越了 RSA。在手机和 IoT 设备上，ECC 是绝对的主角。
3. 终极噩梦：量子计算机 (Shor's Algorithm)
如果说 ECC 只是在性能上优于 RSA，那么量子计算机就是它们的“灭霸”。
- 毁灭打击：Shor 算法证明了，只要量子计算机的量子比特（Qubits）足够多，它就能在多项式时间内分解大整数（秒杀 RSA）和计算离散对数（秒杀 ECC）。
- 团灭：也就是说，一旦量子计算机成熟，我们现在互联网基石的 RSA 和 ECC 全都要完蛋。
- 未来：后量子密码学 (PQC)
为了应对这一天，密码学家们正在加紧制定 PQC (Post-Quantum Cryptography) 标准。这些新算法（如基于格的 Kyber、Dilithium 等）是专门设计来抵抗量子攻击的。
所以，RSA 的退休，不仅是因为 ECC 更快，更是为了迎接即将到来的量子时代。
八、 推荐实践工具
如果你想亲手验证一下文中提到的 RSA 计算过程，手动处理那些大数显然太痛苦了。这里推荐一个功能极其强大的在线工具：
这个工具非常适合用来“复现”文章里的每一步。你可以尝试输入不同的素数 $p$ 和 $q$，看看 $N$ 和 $\phi(N)$ 是如何生成的；或者输入密文，利用计算出的 $d$ 来验证解密结果。
总结
RSA 的美妙在于它利用了质数最纯粹的性质。
- 开发者建议：不要手写 RSA 实现，务必使用 OAEP 填充，并且给你的程序加上完整性校验，防止 $N$ 被掉包。
- 学习者建议：试着用 Python 跑一遍下面的代码，你会对这个“陷门”有更深的理解。
# 一个简单的 Python 示例
m = 65
p, q = 61, 53
n = p * q
phi = (p-1) * (q-1)
e = 17
# 计算私钥 d
d = pow(e, -1, phi)
# 加密
c = pow(m, e, n)
print(f"密文: {c}")
# 解密
m_orig = pow(c, d, n)
print(f"还原明文: {m_orig}")
# 演示：如果 N 是素数，如何瞬间计算私钥
n_prime = 3251 # 一个素数
d_hack = pow(e, -1, n_prime - 1)
print(f"素数 N 下的私钥: {d_hack}")
⚠️ 免责声明：本文讨论的攻击手法仅用于理解 RSA 弱点和安全设计，实际应用需遵守法律法规。请勿将文中技术用于非法破解商业软件或其他违法行为。