RSA 的数学,一行一行

#TL;DR

RSA 的密钥生成只需八行 Python。这八行里编码了 200 年的数论:费马小定理、欧拉函数、欧拉定理、Bézout 恒等式、扩展欧几里得算法。这篇文章把 (m^e)^d ≡ m (mod n) 背后的数学走一遍——它为什么成立、每一部分在做什么、以及为什么行业标准公钥指数是 e = 65537。这些都不需要超过高中代数的数学,但每一块对于让 RSA 不只是碰运气都是必要的。

#预备:模运算

RSA 里所有事都发生在对某个数取模之下。“模 n”意味着你只关心除以 n 的余数。两个数”在 mod n 意义下相等”,当且仅当它们之差是 n 的倍数:

17 ≡ 5 (mod 12)          因为 17 - 5 = 12
100 ≡ 4 (mod 12)         因为 100 - 4 = 96 = 8 × 12
-1 ≡ 11 (mod 12)         因为 -1 - 11 = -12

模运算保持加法和乘法。如果 a ≡ b (mod n) 且 c ≡ d (mod n),那么 a + c ≡ b + d (mod n)、a × c ≡ b × d (mod n)。这意味着你可以随时取模归一,不必计算巨大的中间值,只要一路保持 mod n。

幂也一样归一:a^k mod n 可以在从不让 a^k 变大的前提下算出来。平方-乘法幂运算大约要 log(k) 步:

def mod_exp(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        exp >>= 1
        base = (base * base) % mod
    return result

mod_exp(65, 17, 3233)  # 65^17 mod 3233 = 2790

Python 的内置 pow(base, exp, mod) 会替你做这个。这是让 RSA 在真实密钥长度下变得可行的引擎——不经过中间爆炸就把一个 2048 位的数升到 2048 位的指数。

#费马小定理

1640 年,Pierre de Fermat 写下了一个后来成为公钥密码学基石之一的结论:

若 p 是素数,a 不被 p 整除,则 a^(p-1) ≡ 1 (mod p)。

举例,取 p = 7、a = 3:

3^6 = 729 = 104 × 7 + 1
所以 3^6 ≡ 1 (mod 7)

把 1 到 6 的任意 a 代进 a^6 mod 7,结果都是 1。这不是巧合——它反映了模 p 的乘法群的结构。

费马定理接近 RSA 所需,但还不够。RSA 不在素数模下工作——它在 n = pq(两个素数的乘积)模下工作。为此,需要它的推广。

#欧拉函数与欧拉定理

推广来自一个世纪后的莱昂哈德·欧拉。他定义了欧拉函数 φ(n),即小于 n 且与 n 互素(除 1 外不共享任何因子)的正整数的个数:

φ(1) = 1
φ(7) = 6    (1, 2, 3, 4, 5, 6 全部与 7 互素)
φ(12) = 4   (1, 5, 7, 11 与 12 互素)

当 p 是素数时,从 1 到 p-1 的一切都与 p 互素,所以 φ(p) = p - 1。这就回到了费马定理。

对 RSA 来说最重要的性质,是 φ 在互素数乘积上的行为:

φ(mn) = φ(m) × φ(n)        当 gcd(m, n) = 1

特别地,对两个不同的素数 p 和 q:

φ(pq) = φ(p) × φ(q) = (p - 1)(q - 1)

这就是 RSA 密钥生成所用的公式。如果你知道 p 和 q,就能直接算出 φ(n)。如果你只知道 n = pq,就得先分解 n——而对大 n 做分解正是 RSA 假定困难的那个问题。

欧拉定理推广了费马:

若 gcd(a, n) = 1,则 a^φ(n) ≡ 1 (mod n)。

对两个不同素数构成的 n = pq:

a^((p-1)(q-1)) ≡ 1 (mod pq)     当 gcd(a, pq) = 1

RSA 里其他所有等式都建立在这一条之上。

#RSA 等式:为什么 (m^e)^d ≡ m (mod n)

RSA 选公钥指数 e 和私钥指数 d,使得:

e × d ≡ 1 (mod φ(n))

也就是说,d 是 e 在模 φ(n) 下的模逆。它存在当且仅当 gcd(e, φ(n)) = 1,这也是为什么 e 必须与 φ(n) 互素。

基于这个关系,下面是”加密—再解密”为什么能把消息还原出来的推导。对任何消息 m:

(m^e)^d = m^(ed)                             指数法则
        = m^(1 + k·φ(n))                     因为 ed ≡ 1 (mod φ(n)),故 ed = 1 + k·φ(n),k 为某整数
        = m · m^(k·φ(n))                     拆分指数
        = m · (m^φ(n))^k                     再用一次指数法则
        ≡ m · (1)^k  (mod n)                 若 gcd(m, n) = 1,由欧拉定理
        ≡ m (mod n)

加密用 e 打乱,解密用 d 还原。两步互相抵消,因为 ed “差不多等于 1”(具体地说:1 再加一个 φ(n) 的倍数),而欧拉定理又说:任何与 n 互素的数升到 φ(n) 的倍数,结果就是 1。

边界情形——当 gcd(m, n) ≠ 1,也就是 m 是 p 或 q 的倍数——用中国剩余定理单独论证也依然成立。但这个情形在密码学上没什么意思:如果你的”消息”正好是 n 的某个素因子的倍数,那等同于你把这个因子泄露了,本来就是灾难。

#求 d:扩展欧几里得算法

给定 e 和 φ(n),怎么算出满足 e × d ≡ 1 (mod φ(n)) 的 d?

工具是扩展欧几里得算法。标准的欧几里得算法通过反复做除法求 gcd(a, b)。扩展版还会另外算出整数 x、y,使得:

a × x + b × y = gcd(a, b)                    Bézout 恒等式

若 gcd(e, φ(n)) = 1,则存在整数 x、y,满足:

e × x + φ(n) × y = 1

两边同时对 φ(n) 取模:

e × x ≡ 1 (mod φ(n))

于是 d = x mod φ(n)。Python 从 3.8 起内置了这件事,写作 pow(e, -1, phi):

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

phi = 3120
e = 17
g, d, _ = extended_gcd(e, phi)
d = d % phi   # 归一化到 [0, phi)
# d = 2753,且确实有 17 * 2753 = 46801 = 15 * 3120 + 1

RSA 那篇里那个神奇的 d = 2753 就是这么算出来的。没有猜测,没有搜索——这是扩展欧几里得算法作用在公钥指数和 φ(n) 上的一个确定性结果。

#为什么 e = 65537

实际中,公钥指数 e 不是随机选的。有一条很强的约定——几乎是全行业通用的——e = 65537。为什么偏偏是这个数?

65537 是 2^16 + 1。它有三个有用的性质:

• 它是素数。 素数 e 自动与任何 φ(n) 互素(除非 φ(n) 能被 65537 整除,对随机选出的 p、q 来说,这近乎不可能)。
• 它的二进制表示非常稀疏。 65537 的二进制是 10000000000000001。用平方-乘法法对 17 位指数做幂运算,只需要 17 次平方加 1 次乘法,公钥操作(加密、签名验证)因此非常快。
• 它够大,避免了小指数攻击。 针对 RSA 的臭名昭著的小指数攻击(尤其是 e = 3)利用了这一点:如果 m 足够小,m^e 可能还没超过 n,那模归一其实没归一什么。攻击者就可以直接在整数域里对密文开 e 次方。e = 65537 对任何非退化消息来说,m^e 几乎必然大于 n,这条路也堵死了。

你也可以选别的 e,但 65537 是那个刚刚好的选择:素数、做幂运算很快、又大到安全。你用过的每一个 TLS 库在生成 RSA 密钥时基本都在用 e = 65537。

#素数 p 和 q

密钥生成会挑两个素数再相乘。怎么挑很重要:

• p 和 q 必须足够大。 RSA 的安全性依赖于分解 n = pq 不可行。现代密钥用 1024 位素数,乘出 2048 位 n。4096 位已经成为长期密钥的标准。
• p 和 q 的大小必须差不多(差个几位以内)。如果一大一小,费马分解法或椭圆曲线分解法能迅速找出那个小的因子。
• p - 1 和 q - 1 不应该只由小因子构成。 否则 Pollard 的 p-1 算法能高效分解 n。“强素数”是为此而设计的;现代 RSA 实现一般把这当作不存在的问题处理,因为在随机生成下偶然撞到弱素数的概率小到可以忽略。
• p 和 q 必须独立随机生成。 如果野外有两把 RSA 密钥碰巧共享了同一个素因子,gcd(n1, n2) 立刻暴露这个共享因子,两把密钥同时破。2012 年研究者就发现,公共互联网上一部分 HTTPS 密钥彼此共享因子,原因是嵌入式设备上损坏的 RNG。

素数生成的做法是:随机取一个合适位长的奇数,跑概率素性检验(通常是 Miller-Rabin)直到通过。一个 1024 位的随机奇数大约有 1/700 的概率是素数,所以一般得试几百个候选才能出一个。

#填充:数学里跳过的那块

到此为止我们讲的这种朴素数学 RSA——“把 m 加密成 m^e mod n”——叫做教科书 RSA,而它在实战中并不安全。它有几种弱点:

• 它是确定性的。同一条消息加密两次得到相同密文;攻击者能看出你又发了同样的消息,能做字典。
• 它是可延展的。给出 c = m^e mod n,攻击者可以构造 c × 2^e mod n,它解密后是 2m mod n——一条看起来合法、由你原密文”炮制”出来的新密文。
• 短消息容易遭小指数攻击。
• 把同一条消息发给多个接收方(Håstad 攻击),有时能被恢复。

真实的 RSA 会在做幂运算之前,把消息包进一个填充方案里,既随机化又加上结构。现代 RSA 加密用 OAEP(Optimal Asymmetric Encryption Padding),签名用 PSS(Probabilistic Signature Scheme)。更老的系统用的是 PKCS#1 v1.5 填充,它被反复用 Bleichenbacher(1998 年)之类的攻击打穿,新实现里经常还能被重新找到同一族漏洞。

重点是:我们刚走完的这套数学,是原语。基于它搭出的密码系统要小心得多。RSA 那篇为了讲清楚主干悄悄把这个区别略过;教科书 RSA 和 RSA-OAEP 之间,真正的差别是几十年的攻击与修补。

#数学真正证明了什么

如果你一路看下来:RSA 的安全性,依赖于一个猜想——“分解大 n 在计算上不可行”——外加一把 300 年前的定理。那个猜想正是量子计算机会打破的。那些定理则是欧拉 18 世纪就证过的,它们不会跑。

RSA 那篇把密钥生成描述成 Rivest 在逾越节家宴之后那个晚上想出的”数学、证明、算法”。他那天晚上真正拼起来的东西是:1761 年的欧拉定理、公元前 300 年的扩展欧几里得算法,加上一组使得分解问题很难的素数选择。闪光点在于把这些拼在一起。零件都已经摆在那儿——他只是看出它们可以合成一把锁加一把钥匙。

五十年后,每一个在浏览器里建立过安全连接的人,都一直在用那八行代码。