公钥密码体制：数论基础与 RSA 算法全流程

公钥密码学（非对称密码体制）通过引入单向陷门函数，彻底解决了对称密码体制在大型网络中密钥分发与管理的固有瓶颈。本篇系统阐明支持公钥密码的核心数论工具（辗转相除法、扩展欧几里得算法、欧拉定理、快速模幂），深入推导 RSA 算法的数学原理、加解密流程、全域正确性证明，以及工程实现中的双模数规范与安全填充要求。

---

一、非对称密码体制的提出背景与密钥分配问题

在对称密码体制中，任何一对想要进行保密通信的实体必须预先共享同一个秘密密钥。

• 若网络中存在 $N$ 个参与者，两两之间均需进行排他性保密通信，全网所需的独立对称密钥总数为两两组合数：
  $\binom{N}{2} = \frac{N(N - 1)}{2} = \Theta(N^2).$
  密钥总量呈二次方爆炸式增长。一个仅有 1000 人的网络，需要维护近 50 万个独立密钥，分发与存储代价不可承受。

1976 年，Diffie 与 Hellman 提出了公钥密码体制的思想：

• 每个参与者仅需独立生成一对密钥：公开的公钥（Public Key, $PK$）与保密的私钥（Private Key, $SK$）；
• 全网 $N$ 个参与者总共仅需生成并维护 $N$ 对密钥（$2N$ 个单钥）；
• 任何人均可获取接收方的公钥并加密消息，但只有持有对应私钥的合法接收方才能完成解密。

公钥密码的数学基础是单向陷门函数（Trapdoor One-Way Function）：正向计算在多项式时间内易于完成；在未知陷门（私钥）时，反向求解在计算复杂度上不可行；但一旦掌握特定陷门信息，反向求解同样可在多项式时间内高效完成。

---

二、欧几里得算法（辗转相除法）代数原理

整数除法基本定理指出：对于任意整数 $a, b$（设 $b > 0$），存在唯一的整数商 $q$ 与余数 $r$，满足：

$$a = q \cdot b + r,\qquad 0 \le r < b.$$

2.1 最大公约数的传递不变性

代数整除性质保证：任何同时整除 $a$ 与 $b$ 的公约数，必能整除二者的线性组合 $r = a - qb$；反之，任何同时整除 $b$ 与 $r$ 的公约数，亦必能整除 $a = qb + r$。因此，$a$ 与 $b$ 的公约数集合同 $b$ 与 $r$ 的公约数集合完全相同，其最大公约数（Greatest Common Divisor）恒等：

$$\gcd(a, b) = \gcd(b, r) = \gcd(b,\ a \bmod b).$$

通过不断以除数除以余数，余数序列严格单调递减（$b > r_1 > r_2 > \cdots \ge 0$），必然在有限步内收敛终止于余数为 0。最后一个非零余数即为最大公约数 $\gcd(a, b)$。

算例：计算 $\gcd(7469, 2464)$：

1. $7469 = 3 \times 2464 + 77$；
2. $2464 = 32 \times 77 + 0$。
   最后一个非零余数为 77，故 $\gcd(7469, 2464) = 77$。

---

三、扩展欧几里得算法（EEA）与模逆求解

裴蜀定理（Bézout's Identity）指出：对任意整数 $a, b$，恒存在整数系数 $s, t$，满足线性丢番图方程：

$$s \cdot a + t \cdot b = \gcd(a, b).$$

扩展欧几里得算法（Extended Euclidean Algorithm, EEA）在执行辗转相除的同时，通过反向代换求出这组整数解 $(s, t)$。

3.1 求解模逆元的判定依据

当且仅当 $\gcd(a, n) = 1$ 时，裴蜀等式为：
$s \cdot a + t \cdot n = 1.$
等式两端在模 $n$ 意义下展开：
$s \cdot a + t \cdot n \equiv s \cdot a + 0 \equiv 1 \pmod n \implies a^{-1} \equiv s \pmod n.$
系数 $s$ 即为 $a$ 模 $n$ 的乘法逆元。若算得的系数 $s$ 为负数，通过加上模数 $n$ 调整为最小正剩余：$s_{\text{norm}} = (s \bmod n + n) \bmod n$。

3.2 扩展欧几里得算法手算实例

例题：求解 $49^{-1} \pmod{640}$。

1. 第一阶段：前向辗转相除（记录除法整商）：
   • $640 = 13 \times 49 + 3$
   • $49 = 16 \times 3 + 1$
   • $3 = 3 \times 1 + 0$（最后一个非零余数为 1，确证互素，逆元存在）。
2. 第二阶段：反向线性组合回代：
   从倒数第二个等式中将余数 1 隔离出来：
   $1 = 49 - 16 \times 3.$
   将第一式中的余数 $3 = 640 - 13 \times 49$ 代入替换：
   $1 = 49 - 16 \times (640 - 13 \times 49) = 49 - 16 \times 640 + 208 \times 49 = 209 \times 49 - 16 \times 640.$
3. 第三阶段：提取逆元系数并取模：
   $209 \times 49 \equiv 1 \pmod{640} \implies 49^{-1} \equiv 209 \pmod{640}.$
4. 乘回自检：
   $49 \times 209 = 10241 = 16 \times 640 + 1 \equiv 1 \pmod{640}.$
   验算无误。

---

四、欧拉函数 $\varphi(n)$ 与欧拉定理

4.1 欧拉函数定义与性质

欧拉函数 $\varphi(n)$（Euler's Totient Function）定义为小于或等于 $n$ 的正整数中与 $n$ 互素的整数个数：

$$\varphi(n) = \big|\{ k \in \mathbb{N} \mid 1 \le k \le n,\ \gcd(k, n) = 1 \}\big|.$$

核心性质：

1. 若 $p$ 为素数，因 $1$ 到 $p-1$ 均与 $p$ 互素，故：
   $\varphi(p) = p - 1.$
2. 欧拉函数为积性函数：若 $\gcd(a, b) = 1$，则 $\varphi(ab) = \varphi(a)\varphi(b)$。
3. RSA 模数特例：对于合数 $n = pq$（其中 $p, q$ 为互异奇素数）：
   $\varphi(n) = (p - 1)(q - 1).$
   容斥原理证明：在集合 $\{1, 2, \dots, pq\}$ 中，$p$ 的倍数有 $q$ 个（$p, 2p, \dots, qp$），$q$ 的倍数有 $p$ 个（$q, 2q, \dots, pq$），公倍数 $pq$ 被多扣除了一次。因此与 $n$ 互素的元素总数为：
   $\varphi(pq) = pq - q - p + 1 = (p - 1)(q - 1).$

4.2 欧拉定理与费马小定理

欧拉定理（Euler's Theorem）：
若整数 $a$ 与模数 $n$ 互素（即 $\gcd(a, n) = 1$），则：

$$a^{\varphi(n)} \equiv 1 \pmod n.$$

费马小定理（Fermat's Little Theorem）：
当模数退化为素数 $p$ 时，$\varphi(p) = p - 1$。对任意不能被 $p$ 整除的整数 $a$（$p \nmid a$）：

$$a^{p - 1} \equiv 1 \pmod p.$$

指数同余降幂准则：
若 $\gcd(a, n) = 1$，在计算 $a^k \bmod n$ 时，指数 $k$ 可以直接在模 $\varphi(n)$ 的意义下进行约简：
$a^k \equiv a^{k \bmod \varphi(n)} \pmod n.$

---

五、模幂快速计算：平方-乘算法（Square-and-Multiply）

在密码学中，加解密涉及计算 $x^e \bmod n$，其中底数、指数与模数通常长达数千比特。若直接计算 $x^e$，中间数值将导致计算机内存溢出。
平方-乘算法（快速幂）利用指数 $e$ 的二进制表示，将模乘法次数从 $O(e)$ 指数级压缩至 $O(\log_2 e)$ 对数级。

设指数 $e$ 的二进制展开式为：
$e = (1 b_{t-1} b_{t-2} \cdots b_1 b_0)_2.$

5.1 自高位向低位（MSB to LSB）标准执行流程

1. 初始化累加器为 $R = x \bmod n$（对应最高有效位 1）；
2. 从次高位 $b_{t-1}$ 开始向低位依次扫描每一个比特位 $b_i$（从 $b_{t-1}$ 至 $b_0$）：
   • 每一步必执行模平方：$R \leftarrow (R \cdot R) \bmod n$（数学含义：指数值翻倍，对应二进制向左逻辑移位追加 0）；
   • 若当前比特 $b_i = 1$，追加一次模乘底数：$R \leftarrow (R \cdot x) \bmod n$（数学含义：指数值加 1，将二进制末位的 0 置换为 1）。
3. 循环结束，输出最终结果 $R$。

二进制比特 $b_i$	算术操作	指数演变物理含义
任意比特	必执行一次平方	$R \leftarrow R^2 \bmod n$（指数翻倍）
仅当 $b_i = 1$	追加一次乘基数	$R \leftarrow R \cdot x \bmod n$（指数自增 1）

def square_and_multiply(x, e, n):
    r = 1
    x = x % n
    for bit in bin(e)[2:]: # 从最高有效位向低位迭代
        r = (r * r) % n
        if bit == '1':
            r = (r * x) % n
    return r

手算实例：计算 $x^{13} \bmod n$。
指数 $13 = (1101)_2$：

• 扫描到最高位 1：初始 $R = x$；
• 扫描到第 2 位 1：平方得 $x^2$，乘基数得 $x^3$；
• 扫描到第 3 位 0：平方得 $x^6$（该步不乘基数，但平方不可省）；
• 扫描到第 4 位 1：平方得 $x^{12}$，乘基数得 $x^{13}$。
  全过程仅需 3 次平方与 2 次乘法。每一步均立即取模，数值始终不超过 $n^2$。

---

六、RSA 算法全生命周期流程与双模数规范

6.1 算法流程五步法

flowchart TD
    S1["1. 选取两个独立大素数 p, q (保密)"] --> S2["2. 计算模数 n = p * q (公开)"]
    S2 --> S3["3. 计算欧拉函数 φ(n) = (p-1)*(q-1) (保密)"]
    S3 --> S4["4. 选取公钥指数 e，满足 gcd(e, φ(n)) = 1 (公开)"]
    S4 --> S5["5. 用 EEA 求解私钥指数 d ≡ e^(-1) (mod φ(n)) (严格保密)"]

1. 密钥生成：
   • 选取两个独立的大素数 $p, q$；
   • 计算公开模数 $n = pq$；
   • 计算保密的欧拉函数值 $\varphi(n) = (p - 1)(q - 1)$；
   • 选取公开加密指数 $e$，满足 $1 < e < \varphi(n)$ 且满足互素条件：$\gcd(e, \varphi(n)) = 1$（工程中通常选用费马素数 $e = 65537 = 2^{16} + 1$，因其二进制仅有两位为 1，能极快加速平方-乘算法）；
   • 计算私钥解密指数 $d$，满足：
     $d \equiv e^{-1} \pmod{\varphi(n)},\qquad 1 < d < \varphi(n);$
   • 公钥元组发布为 $(n, e)$，私钥元组严格保密为 $(d)$。
2. 加密过程：
   将明文编码为整数 $x \in \{0, 1, \dots, n-1\}$，计算密文：
   $y = x^e \bmod n.$
3. 解密过程：
   接收密文 $y \in \{0, 1, \dots, n-1\}$，恢复明文：
   $x = y^d \bmod n.$

[!IMPORTANT]
双模数严格区分规范（考试极高频失分点）：

• 在指数层面（密钥生成、求模逆 $d$、指数约简降幂）：必须使用保密的欧拉函数值 $\varphi(n)$ 作为模数；
• 在数据层面（明文、密文、实际加解密多项式求模）：必须使用公开的模数 $n$ 作为模数。
  混淆两者将导致计算推导彻底失真。

6.2 完整教学算例推导

参数设定：选取素数 $p = 5, q = 11$。

1. 计算模数：$n = 5 \times 11 = 55$；
2. 计算欧拉函数：$\varphi(n) = (5 - 1)(11 - 1) = 4 \times 10 = 40$；
3. 选取公钥指数：选 $e = 3$，核查 $\gcd(3, 40) = 1$ 合法；
4. 计算私钥 $d$：由 $3d \equiv 1 \pmod{40}$，因 $3 \times 27 = 81 = 2 \times 40 + 1$，解得 $d = 27$；
5. 加密明文 $x = 9$：
   $y = 9^3 \bmod 55 = 729 \bmod 55 = 14;$
6. 解密密文 $y = 14$：
   $x' = 14^{27} \bmod 55.$
   利用平方-乘展开算得 $14^{27} \equiv 9 \pmod{55}$，精确还原明文 $x = 9$。

---

七、RSA 算法全域正确性证明：基于中国剩余定理（CRT）

目标：证明对任意整数 $x \in \mathbb{Z}_n$，恒有 $x^{ed} \equiv x \pmod n$。

根据私钥构造，$e \cdot d \equiv 1 \pmod{\varphi(n)}$，即存在非负整数 $k$ 使得：
$ed = 1 + k \cdot \varphi(n) = 1 + k(p - 1)(q - 1).$

若明文 $x$ 与模数互素（$\gcd(x, n) = 1$），根据欧拉定理，$x^{\varphi(n)} \equiv 1 \pmod n$，直接得出：
$x^{ed} = x^{1 + k\varphi(n)} = x \cdot (x^{\varphi(n)})^k \equiv x \cdot 1^k \equiv x \pmod n.$

然而，在合法消息空间 $\mathbb{Z}_n$ 中，存在少数与 $n$ 不互素的元素（即 $x$ 为 $p$ 或 $q$ 的倍数）。为给出无漏洞的完备证明，需引入中国剩余定理（CRT）在模 $p$ 与模 $q$ 下分别讨论：

1. 考查模 $p$：
   • 情况 A：若 $x \equiv 0 \pmod p$（即 $p \mid x$），显然 $x^{ed} \equiv 0^{ed} \equiv 0 \equiv x \pmod p$；
   • 情况 B：若 $x \not\equiv 0 \pmod p$（即 $p \nmid x$），由费马小定理得 $x^{p-1} \equiv 1 \pmod p$。代入得：
     $x^{ed} = x \cdot \big(x^{p-1}\big)^{k(q-1)} \equiv x \cdot (1)^{k(q-1)} \equiv x \pmod p.$
     无论何种情形，同余式 $x^{ed} \equiv x \pmod p$ 恒成立，即 $p \mid (x^{ed} - x)$。
2. 考查模 $q$：
   完全同理对称可证：$q \mid (x^{ed} - x)$。
3. 模数合成：
   因为 $p$ 与 $q$ 为互异素数，二者的最小公倍数为 $\operatorname{lcm}(p, q) = pq = n$。根据代数整除性质：若两个互素数同时整除同一个数，则二者的乘积亦必整除该数：
   $n \mid (x^{ed} - x) \iff x^{ed} \equiv x \pmod n.$

证毕。该证明在数学上确证了：对于整个消息集合中的任意整数 $x \in \mathbb{Z}_n$，RSA 解密算法均能精确恢复原文。

---

八、大整数质因数分解的难解性与小模数试除攻击

从密文 $y \equiv x^e \pmod n$ 求解明文 $x$，本质是求解同余高次多项式的离散模根：

$$x^e - y \equiv 0 \pmod n.$$

在实数域中开方可通过数值逼近求解；而在离散模代数中，只要合数模数 $n$ 的因数分解未公开，求解合数模下的离散 $e$ 次根在计算复杂度上等价于大整数质因数分解。

小模数攻击范例：
设截获公钥 $n = 2623, e = 211$，密文 $y = 1141$：

1. 攻击者对较小模数 $n=2623$ 进行试除，在 $\sqrt{2623} \approx 51.2$ 范围内搜索素数，快速分解出 $2623 = 43 \times 61$；
2. 获知因数后，立即恢复出保密的欧拉函数值：$\varphi(n) = (43 - 1)(61 - 1) = 42 \times 60 = 2520$；
3. 利用扩展欧几里得算法求解模逆：$d \equiv 211^{-1} \pmod{2520} \implies d = 1051$；
4. 计算快速模幂：$x = 1141^{1051} \bmod 2623 = 1055$，非法解密成功。

在工程实践中，为保证抗攻击强度，$p$ 与 $q$ 必须为长度至少为 1024 比特（模数 $n$ 至少 2048 至 4096 比特）的强伪随机素数，使得目前最顶尖的数域筛法（GNFS）在计算上完全不可行。

---

九、教科书 RSA 的固有缺陷与工程填充方案（RSA-OAEP）

未经填充的纯数学 RSA（Textbook RSA）在工程落地中被严格禁止直接使用，其主要存在两大结构缺陷：

1. 确定性加密缺陷：
   相同公钥对相同明文的加密输出绝对唯一。若候选明文空间极小（例如消息仅为“买入”或“卖出”），攻击者可预先通过公钥加密所有候选明文，建立彩虹字典直接匹配密文，机密性荡然无存。
2. 可延展性与乘法同态（Multiplicative Homomorphism）：
   $E(x_1) \cdot E(x_2) = (x_1^e \bmod n)(x_2^e \bmod n) \equiv (x_1 x_2)^e \equiv E(x_1 x_2) \pmod n.$
   攻击者即使无法解密密文，也能通过篡改密文注入特定乘法因子，导致接收方解密出被操控的业务数据。

工程解决方案：
现代安全协议（如 TLS）必须采用最优非对称加密填充（RSA-OAEP, Optimal Asymmetric Encryption Padding）：

• 在明文数据前填充不可预测的真随机盐（Random Salt），并通过两个密码学散列函数构造成双 Feistel 结构；
• 保证同一份明文在每次加密时生成的密文均完全不同（概率性加密），彻底破坏乘法同态结构，提供抵抗自适应选择密文攻击（IND-CCA2）的安全保证。