RSA 算法详解：从手算过程到逆向实战

RSA 听起来像某种高深的魔法，教科书里满屏的 $e, d, N, \phi$ 更让人头大。但先把它拆到能动手的尺度，核心运算其实很熟悉：整数乘法、求余数，以及寻找模逆元。

这次我们手算一把 RSA，再带着算出来的钥匙走进注册机的世界：如果私钥很难求，为什么修改验证程序里的公钥，仍然可能让自制注册码通过？

先记住这个问题，不急着回答。下面的小数字只用于演示，实际加密和签名还需要规范的编码方案。

一、手算 RSA：先造出一把能用的钥匙

选择两个不同的素数 $p=61$、$q=53$：

$$N = p q = 3233$$

$$\phi(N) = (p-1)(q-1) = 3120$$

选公钥指数 $e=17$，它与 3120 互质。接下来找一个 d，使：

$$17d \equiv 1 \pmod{3120}$$

也就是 17 × d 除以 3120，余数为 1。这个 d 就是 17 在模 3120 下的逆元。

1. d = 2753 到底怎么算出来？

先用辗转相除法：

3120 = 17 × 183 + 9
17   = 9 × 1 + 8
9    = 8 × 1 + 1

再倒着代回去，把 1 写成 17 和 3120 的整数倍之和：

1 = 9 - 8
  = 9 - (17 - 9)
  = 2 × 9 - 17
  = 2 × (3120 - 17 × 183) - 17
  = 2 × 3120 - 367 × 17

因此 -367 × 17 对 3120 取模等于 1。取正的代表值：

d = -367 + 3120 = 2753

验证：2753 × 17 = 46801 = 15 × 3120 + 1。

现在得到了：

公钥：$(e,N)=(17,3233)$。
私钥的核心参数：$(d,N)=(2753,3233)$。实际私钥格式通常还保存 p、q 以及用于加速的参数。

2. 加密：不用真的展开 65 的 17 次方

取明文整数 $M=65$，它满足 $0 \le M < N$。教科书里的加密运算是：

$$C = M^e \bmod N$$

直接计算 65^17 很大，但每次平方后都取模，中间数就可控了：

次方	平方并取模后的结果
`65^2 mod 3233`	992
`65^4 mod 3233`	`992^2 mod 3233 = 1232`
`65^8 mod 3233`	`1232^2 mod 3233 = 1547`
`65^16 mod 3233`	`1547^2 mod 3233 = 789`

因为 17 = 16 + 1，最后只需：

65^17 mod 3233
= 789 × 65 mod 3233
= 51285 mod 3233
= 2790

密文就是 2790。这就是模幂运算里“平方与乘法”的基本思路。

3. 解密：把原来的 65 找回来

用私钥指数计算：

$$M = C^d \bmod N = 2790^{2753} \bmod 3233 = 65$$

指数虽然大了，算法还是重复平方、按需相乘和取模。Python 的三参数 pow 可以直接完成这件事：

p, q = 61, 53
n = p * q
phi = (p - 1) * (q - 1)
e = 17
d = pow(e, -1, phi)

message = 65
ciphertext = pow(message, e, n)
recovered = pow(ciphertext, d, n)

print(d, ciphertext, recovered)

Python 3.8 及以上支持这里用负指数求模逆元，输出 2753 2790 65。

加密和解密的核心整数运算，都可以落到 pow(base, exponent, modulus)。但真实系统还要做消息编码、填充和错误处理，不能把整个加密协议等同于一次 pow。

4. 为什么能还原？

我们选择的 d 满足 $ed=1+k\phi(N)$。如果 M 与 N 互质，欧拉定理让 $M^{\phi(N)}$ 在模 N 下等于 1，因此连续两次模幂会回到 M。

如果 M 与 N 不互质，则可以分别在模 p、模 q 下讨论：M 被相应素数整除时两边都是 0；否则利用费马小定理。最后由中国剩余定理合并，仍能还原 0 ≤ M < N 的原值。

这解释了算法为什么工作，也提醒我们：输入范围和两个不同素数的条件，都在推导里发挥了作用。

二、公钥与私钥：加密和签名各自解决什么？

1. 加密通信：谁能读这条消息？

Alice 想给 Bob 发秘密消息，就用 Bob 的公钥加密；Bob 用自己的私钥解密。可以把它想成一个人人都能投信、只有主人能打开的信箱。

关键是公钥必须确实属于 Bob。如果 Alice 拿到的是冒充者的公钥，数学过程再正确，消息也会交给错误的人。

2. 数字签名：谁认可了这份内容？

Bob 发布公告时，用私钥签名；大家用可信的 Bob 公钥验签。验证通过说明签名与消息、密钥相匹配，并不自动证明公告内容真实。

签名不是简单的“私钥加密消息”：标准签名方案包含哈希和专门的编码规则。RSA 加密可以使用 RSAES-OAEP，RSA 签名可以使用 RSASSA-PSS；二者不能互换。RFC 8017

3. 哪些参数不能泄露？

公钥中的 e、N 可以公开。d、p、q 则必须保密；对于两个不同素数的 RSA，知道 $\phi(N)$ 也足以恢复因子：

p + q = N - phi(N) + 1
p × q = N

有了和与积，就能解出 p、q。前面的例子给出 p+q=114、pq=3233，得到的就是 61 和 53。

4. 数学对称，能把公私钥反过来用吗？

核心模幂关系有对称性，但已经生成的密钥对不能因此随意交换用途。常见 e 固定为 65537，根本没有秘密可言；即便把它藏起来，别人也很容易猜到。

让两个指数都变大，也不能省掉正确的密钥生成与方案设计。真实接口中，加密、签名、解密和验签各自有明确用途，按规范使用，比依赖公式外观的对称性更可靠。

三、为什么公开 N，却不容易得到 d？

对于前面的 3233，试除很快就能找到 53 和 61。真实 RSA 则使用大得多、按规范生成的素数。

一旦分解 N，攻击者就可以像我们一样计算欧拉函数并求 d。困难在于：针对适当生成的大模数，已知经典通用分解算法的成本很高。

这里不应说“绝对不可破解”或“只能靠分解”。RSA 求逆与整数分解并未被一般性地证明完全等价；实现缺陷、填充预言机和密钥泄露，也可能绕过直接分解这条路。

为什么通常用两个素数？

如果把 N 直接选成素数，那么 $\phi(N)=N-1$ 就公开了。在 e 与 N-1 互质时，任何人都能计算逆元，这显然不是我们要的密钥结构。

三个或更多素数也能构造 multi-prime RSA，规范中确实有相应形式。因子数量、各自长度、攻击成本、私钥运算速度和实现支持之间存在取舍，不能把“两素数”解释成数学上唯一可行的选择。RFC 8017 密钥类型

记住素数 N 的问题，后面讨论 Patch 时会再次用到它。

四、算法成立，不代表每种用法都安全

1. p、q 太接近，或者 d 太小

如果 p、q 太接近，可以从 $\sqrt{N}$ 附近寻找平方差，用 Fermat 分解法较快找到因子。

私钥指数过小也可能带来攻击。经典 Wiener 攻击利用连分数；在使用模 phi 的密钥关系、两个素数满足 $p < q < 2p$ 等条件下，常见充分条件是 $d < \frac{1}{3}N^{1/4}$。这个界限不是对所有密钥和攻击方法都适用的统一安全分界线。相关工作始于 Wiener 对短私钥指数的研究。

因此应使用成熟库的密钥生成功能，而不是自己挑几个“看着够大”的数字。

2. 裸 RSA：模运算可能根本没发生

如果直接把消息整数放进 M^e mod N，加密相同消息总会得到相同密文。

当 e=3 且 $M^3<N$ 时，取模甚至不会改变结果。比如 M=65、N=1000003：

C = 65^3 = 274625

只需精确求整数立方根，就能还原 65。下面用整数二分，避免 int(c ** (1/3)) 的浮点误差：

def integer_cube_root(value):
    if value < 0:
        raise ValueError('只处理非负整数')
    low, high = 0, value + 1
    while low + 1 < high:
        middle = (low + high) // 2
        if middle**3 <= value:
            low = middle
        else:
            high = middle
    return low


ciphertext = pow(65, 3, 1000003)
message = integer_cube_root(ciphertext)
print(message, message**3 == ciphertext)

输出 65 True。这里选择 N 只是为了展示“不发生模约减”这个条件，不是在生成生产密钥。这个攻击也不意味着 e=3 在任何规范方案中都能直接开根破解。

3. 填充不是随便加点随机数

实际加密需要明确的编码方案。OAEP 把消息、随机种子、哈希与掩码生成函数按规定组合起来，避免直接使用裸 RSA。

PKCS#1 v1.5 加密是另一种较老的方案。若实现泄露“填充是否合法”等可区分信息，可能出现 Bleichenbacher 一类攻击；OAEP 的实现也必须正确处理错误和时序，不能因为换了名字就认定没有侧信道。

新设计若选用 RSA 加密，应使用成熟库提供的 OAEP，并明确哈希等参数；RSA 签名则单独选择 PSS 等签名方案。OAEP 只能容纳有限长度的消息，实际大数据加密通常采用混合方案，用对称算法处理正文，而不是把文件直接塞进 RSA。RFC 8017 加密方案

五、已知 e、d、N，能不能求 p、q？

这关系到一个很实际的问题：私钥 d 泄露后，能不能保留 N，只换一组指数继续使用？

不应该。知道有效的 e、d、N，通常可以用随机化算法有效恢复 N 的素因子。

一般的 RSA 密钥关系要求 $ed-1$ 是 $\lambda(N)=\mathrm{lcm}(p-1,q-1)$ 的倍数。我们手算时使用更强的模 $\phi(N)$ 关系也成立，但不能反过来认定所有合规私钥都必须按 phi 求逆。

将 ed-1 拆成 2^t × r，其中 r 是奇数。选一个随机底数 g，从 g^r mod N 开始反复平方。如果遇到一个不等于 ±1、但平方后等于 1 的数 y，就能通过 gcd(y-1, N) 找到非平凡因子。

下面的代码面向有效的双素数 RSA 参数，设置了尝试上限，避免错误输入导致无限循环：

import math
import secrets


def recover_factors(e, d, n, attempts=64):
    k = e * d - 1
    if n <= 3 or n % 2 == 0 or k <= 0 or k % 2:
        raise ValueError('需要有效的奇数 RSA 模数与指数')

    power = 0
    while k % 2 == 0:
        k //= 2
        power += 1

    for _ in range(attempts):
        base = secrets.randbelow(n - 3) + 2
        factor = math.gcd(base, n)
        if 1 < factor < n:
            return tuple(sorted((factor, n // factor)))

        value = pow(base, k, n)
        if value in (1, n - 1):
            continue
        for _ in range(power):
            squared = pow(value, 2, n)
            if squared == 1:
                factor = math.gcd(value - 1, n)
                if 1 < factor < n:
                    return tuple(sorted((factor, n // factor)))
                break
            if squared == n - 1:
                break
            value = squared

    raise ValueError('未找到因子，请核对参数或增加尝试次数')


print(recover_factors(17, 2753, 3233))

输出 (53, 61)。尝试失败不能单独证明参数无效，但私钥泄露后的处置也不应等待攻击者成功演示：应重新生成包括 p、q、N 在内的密钥材料。

六、黑客时间：从 8-bit 音乐说起

如果你经历过 Windows 98/XP 时代，可能还记得那些注册机：闪烁的字符、循环播放的 Chiptune 音乐，输入用户名，点击 Generate，一串注册码就跳了出来。

其中一些注册机不需要修改软件本体。原因通常是验证程序里包含了足以重建注册码生成逻辑的算法或秘密；逆向分析后，生成器也就能被写出来。

这不是严格的“前 RSA 时代”。不同软件一直使用不同的许可设计。真正改变问题的是：生成注册码所需的秘密，是否必须留在客户端。

1. RSA 签名把钥匙留在作者手里

一种许可设计是：作者用私钥签名用户名、功能权限、到期时间等许可内容，客户端只内置公钥验签。

这时，把客户端翻个底朝天，也不应该找到生成签名所需的 d。正确实现的公钥验签，允许程序判断许可是否由作者签发，而不必持有签发能力。

签名消息还必须有无歧义的编码，并覆盖需要保护的字段；否则数学签名正确，业务解释仍可能出现漏洞。

2. 拿不到钥匙，就替换验证者信任的锁

假设一个教学验证程序只信任自己文件里保存的公钥，而且这个文件可以被修改。修改者可以生成自己的密钥对，替换程序信任的公钥，再用自己的私钥签发许可。

如果程序把 e 固定为 65537，新密钥也使用相同 e，那么示例中可能只需要替换模数 N；一般情况下，应把匹配的公钥参数一起替换。

这没有求出作者的私钥。它改变了验证程序信任谁。 自制注册码只对修改后的程序有效，原版仍会拒绝。

代码签名、可信更新链、外部验证和完整性保护可以提高这种修改的门槛，但完全由攻击者控制的本地检查也可能被一并改写。它们的作用取决于信任根放在哪里。

3. 更特别的例子：把 N 改成素数

还记得 $\phi(N)=N-1$ 吗？如果把教学验证器中的模数改成素数，并保证 e 与 N-1 互质，就可以直接求逆元。

用小数字完整演示一次：

import math


e = 17
original_n = 3233
prime_n = 3251
representative = 65

assert all(prime_n % divisor for divisor in range(2, math.isqrt(prime_n) + 1))
assert math.gcd(e, prime_n - 1) == 1
assert 0 <= representative < prime_n

d_prime = pow(e, -1, prime_n - 1)
license_value = pow(representative, d_prime, prime_n)

print('修改后验证：', pow(license_value, e, prime_n) == representative)
print('原版验证：', pow(license_value, e, original_n) == representative)

本例输出 True 和 False。模数变成素数后，修改者可以构造满足新验证方程的整数。

示例使用裸整数代表值，没有实现 PSS 或其他完整签名格式。真实程序能否接受这种修改，还取决于公钥合法性检查、签名编码、长度约束与完整性保护，不能只照着一次 pow 判断。

另外，“只改一个字节就能找到合适素数”并不总成立。一个字节只有 256 种取值，附近可能没有满足要求的候选；素数存在也还要满足逆元等条件。需要修改几个字节，是具体数据决定的。

七、RSA、ECC 与后量子算法

RSA 的经典安全强度并不等于模数位数。以 NIST 的强度对应表为例，约 128 位经典安全强度对应 3072 位 RSA 模数，以及适当选择的约 256 位椭圆曲线参数。NIST SP 800-57 Part 1 Rev.5

椭圆曲线方案通常能用更短的密钥和签名达到相应强度，但不能因此说所有运算都更快。签名、验签、密钥协商和具体实现的成本不同，小公钥指数的 RSA 验签也可能很高效。

量子计算则是另一类问题。足够大、具备容错能力的量子计算机可运行 Shor 算法，威胁 RSA 的整数分解基础，也威胁常见椭圆曲线方案的离散对数基础。单说“量子比特数量够多”还不完整，错误率和可执行电路深度同样重要。

后量子标准也不再只是“正在制定”：NIST 已于 2024 年发布 ML-KEM、ML-DSA、SLH-DSA 的首批标准。其中 ML-KEM 是密钥封装机制，后两者用于数字签名，不能把它们都当作 RSA 加密函数的直接替代品。NIST 首批后量子标准公告

具体系统怎样迁移，要看协议、兼容性和数据保密期限。理解 RSA，仍然有助于分清加密、签名、密钥管理与验证信任之间的关系。

再回到开头的问题

我们从 61 和 53 出发，求出了 2753，算出了 2790，也把 65 解了回来。随后，同一个模逆元的知识，又解释了素数模数为什么会让修改后的验证器失去原来的保护。

RSA 的数学关系保护的是既定密钥下的运算。如果验证程序连信任的公钥都被替换了，它就已经在回答另一个问题。

学习时可以继续修改这些小数字观察结果；做真实系统时，应把密钥生成、OAEP 加密、PSS 签名交给成熟实现，并认真设计公钥如何被可信地分发和使用。