数学基础：模运算、最大公约数、欧拉函数、费马小定理、中国剩余定理与群环域
密码学的一切安全性最终都归结为数学难题的不可解性。无论是RSA、ECC还是AES，其底层运算都建立在数论与抽象代数的基础之上。本章聚焦于六个核心数学工具：模运算、最大公约数（GCD）、欧拉函数、费马小定理、中国剩余定理（CRT）以及群环域的基本概念。这些工具并非孤立的公式，而是构成密码算法设计、密钥生成、加解密效率优化和安全性证明的完整逻辑链条。理解它们之间的内在联系，是掌握后续所有密码协议的前提。
2.1 模运算：密码学的算术舞台
模运算（Modular Arithmetic）是密码学中最基础的运算规则。其核心思想是：对于正整数 n，任意整数 a 除以 n 的余数记为 a mod n。两个整数 a 和 b 若满足 (a - b) 能被 n 整除，则称它们模 n 同余，记作 a ≡ b (mod n)。这一看似简单的定义，却为密码学提供了"单向性"的天然土壤——正向计算容易，逆向求解困难。
核心原理：同余类与模逆元
模运算将整数集划分为 n 个同余类，每个同余类中的数在模 n 意义下等价。例如模 7 运算中，1、8、15、-6 都属于同一个同余类。密码学中更关注的是模逆元：若 a·b ≡ 1 (mod n)，则称 b 是 a 模 n 的逆元，记作 a⁻¹。模逆元的存在条件是 gcd(a, n) = 1，即两者互素。模逆元是RSA私钥计算、椭圆曲线点运算中不可或缺的工具。
操作流程：快速幂取模
实际工程中，指数运算的规模极大（如RSA中指数为2048位），直接计算不可行。必须使用快速幂取模算法（Square-and-Multiply）：
// 计算 a^b mod n，时间复杂度 O(log b)
function modPow(a, b, n):
result = 1
a = a % n
while b > 0:
if b % 2 == 1: // 当前位为1
result = (result * a) % n
a = (a * a) % n // 平方
b = b >> 1 // 右移一位
return result该算法将指数按二进制展开，每次迭代处理一个比特位，将乘法次数从 O(b) 降至 O(log b)。例如计算 3²⁰⁴⁸ mod 65537，仅需约 2048 次乘法，毫秒级完成。
案例拆解：Diffie-Hellman密钥交换中的模运算
在Diffie-Hellman协议中，双方共享素数 p=23 和原根 g=5。Alice选择私钥 a=6，计算 A = 5⁶ mod 23 = 15625 mod 23 = 8 并发送给Bob；Bob选择私钥 b=15，计算 B = 5¹⁵ mod 23 = 19 并发送给Alice。随后Alice计算共享密钥 K = 19⁶ mod 23 = 2，Bob计算 K = 8¹⁵ mod 23 = 2。双方得到相同的密钥 2，而窃听者仅知道 p=23, g=5, A=8, B=19，要还原私钥需要求解离散对数问题，在 p 足够大时计算上不可行。
2.2 最大公约数与扩展欧几里得算法
最大公约数（GCD）是数论中最古老的概念之一，在密码学中承担着密钥合法性校验和模逆元计算的双重职责。两个整数 a 和 b 的最大公约数记作 gcd(a, b)，是能同时整除两者的最大正整数。
核心原理：欧几里得算法
欧几里得算法基于一个简单事实：gcd(a, b) = gcd(b, a mod b)。通过反复应用该等式，将问题规模逐步缩小，直至余数为 0。例如计算 gcd(252, 105)：252 mod 105 = 42，105 mod 42 = 21，42 mod 21 = 0，因此 gcd = 21。该算法的时间复杂度为 O(log min(a,b))，效率极高。
扩展欧几里得算法：求解模逆元
扩展欧几里得算法不仅计算 gcd，还能找到整数系数 x 和 y，使得 ax + by = gcd(a, b)。当 gcd(a, n) = 1 时，x 即为 a 模 n 的逆元。这是RSA密钥生成中计算私钥指数 d 的核心步骤。
| 步骤 | 被除数 | 除数 | 商 | 余数 | x | y |
|---|---|---|---|---|---|---|
| 1 | 252 | 105 | 2 | 42 | 1 | -2 |
| 2 | 105 | 42 | 2 | 21 | -2 | 5 |
| 3 | 42 | 21 | 2 | 0 | 5 | -12 |
由表可知，252×5 + 105×(-12) = 21，即 gcd = 21。若求 105 模 252 的逆元，需满足 gcd(105, 252) = 21 ≠ 1，故不存在逆元——这验证了逆元存在的充要条件。
2.3 欧拉函数与费马小定理
欧拉函数 φ(n) 定义为小于 n 且与 n 互素的正整数个数。它是RSA算法安全性的理论基石，也是连接数论与群论的桥梁。
核心原理：欧拉函数的计算
若 n 的素因子分解为 n = p₁ᵏ¹ · p₂ᵏ² · ... · pᵣᵏʳ，则：
φ(n) = n · (1 - 1/p₁) · (1 - 1/p₂) · ... · (1 - 1/pᵣ)
特别地，当 n = p·q（p、q为不同素数）时，φ(n) = (p-1)(q-1)。这正是RSA密钥生成的基础。欧拉定理进一步指出：若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)。当 n 为素数 p 时，φ(p) = p-1，欧拉定理退化为费马小定理：a^(p-1) ≡ 1 (mod p)。
判断方法：素数判定与欧拉函数计算流程
- 对 n 进行素因子分解（工程中常用Miller-Rabin素性检测配合Pollard's Rho算法）；
- 根据分解结果套用欧拉函数公式；
- 验证 gcd(a, n) = 1 后应用欧拉定理或费马小定理。
实战场景：RSA密钥生成中的欧拉函数
选择 p=61, q=53，则 n = 3233，φ(n) = 60×52 = 3120。选择公钥指数 e=17（需满足 gcd(e, φ(n)) = 1），计算私钥 d = e⁻¹ mod 3120 = 2753。加密消息 m=65：c = 65¹⁷ mod 3233 = 2790。解密：m = 2790²⁷⁵³ mod 3233 = 65。整个过程的安全性依赖于：已知 n 但无法有效分解出 p 和 q，从而无法计算 φ(n) 和私钥 d。
2.4 中国剩余定理：并行化与加速的利器
中国剩余定理（CRT）解决的是同余方程组的求解问题：给定两两互素的模数 m₁, m₂, ..., mₖ 和余数 a₁, a₂, ..., aₖ，求满足 x ≡ aᵢ (mod mᵢ) 的唯一解（模 M = m₁·m₂·...·mₖ 意义下）。
核心原理：构造性证明
CRT的求解分为三步：首先计算 Mᵢ = M / mᵢ；然后求 Mᵢ 模 mᵢ 的逆元 tᵢ；最后组合 x = Σ(aᵢ · Mᵢ · tᵢ) mod M。该定理的价值不仅在于存在性，更在于给出了显式的构造方法。
操作流程：CRT求解步骤
输入: 模数 m₁, m₂, ..., mₖ (两两互素), 余数 a₁, a₂, ..., aₖ
输出: x (0 ≤ x < M)
1. 计算 M = m₁ × m₂ × ... × mₖ
2. 对每个 i:
a. Mᵢ = M / mᵢ
b. tᵢ = Mᵢ⁻¹ mod mᵢ (使用扩展欧几里得算法)
3. x = (Σ aᵢ × Mᵢ × tᵢ) mod M
4. 返回 x案例拆解：RSA-CRT加速解密
以RSA私钥 (n=3233, d=2753, p=61, q=53) 为例，解密密文 c=2790：
- 计算 dₚ = d mod (p-1) = 2753 mod 60 = 53，d_q = d mod (q-1) = 2753 mod 52 = 49；
- 计算 mₚ = 2790⁵³ mod 61 = 4，m_q = 2790⁴⁹ mod 53 = 12；
- 计算 q⁻¹ mod p = 53⁻¹ mod 61 = 38；
- 组合：m = m_q + q × [(mₚ - m_q) × q⁻¹ mod p] = 12 + 53 × [(4-12) × 38 mod 61] = 12 + 53 × [(-8)×38 mod 61] = 12 + 53 × 1 = 65。
对比直接计算 2790²⁷⁵³ mod 3233，CRT方法将指数从 2753 位降至 53 位和 49 位，运算量大幅减少。在2048位RSA中，CRT加速效果更为显著。
2.5 群、环、域：抽象代数视角
群、环、域是抽象代数中层层递进的代数结构，为密码学提供了严谨的数学框架。理解这些结构有助于判断算法在何种"空间"中运算，以及该空间是否满足安全性所需的性质。
核心原理：三种代数结构的定义
| 结构 | 集合 + 运算 | 关键性质 | 密码学应用 |
|---|---|---|---|
| 群 | G + 二元运算 * | 封闭性、结合律、单位元、逆元 | 椭圆曲线点群、Diffie-Hellman循环群 |
| 环 | R + 加法 + 乘法 | 加法构成交换群；乘法满足结合律和分配律 | 多项式环（AES的GF(2⁸)） |
| 域 | F + 加法 + 乘法 | 环的基础上，非零元对乘法构成交换群 | 有限域GF(p)、GF(2ⁿ)（ECC、AES） |
有限域 GF(p)（p为素数）是最常用的密码学域，其元素为 {0, 1, ..., p-1}，加减乘除均通过模 p 运算实现。GF(2ⁿ) 则用于AES等对称密码，其元素为 n 位二进制串，加法为异或，乘法为多项式乘法后模不可约多项式。
判断方法：识别代数结构
判断一个集合是否构成群，需逐一验证四条公理；若进一步满足交换律则为交换群（阿贝尔群）。环要求加法构成交换群且乘法满足结合律和分配律。域则要求乘法在非零元集合上也构成交换群。例如，整数集 Z 对加法构成群，但对乘法不构成群（因为除 ±1 外无逆元）；有理数集 Q 对加法和乘法构成域。
实战场景：椭圆曲线密码中的群运算
椭圆曲线 E: y² = x³ + ax + b 上的点（包括无穷远点 O）构成一个交换群。点的加法定义为：过 P 和 Q 的直线与曲线交于第三点 R'，R' 关于 x 轴的对称点即为 P+Q。该群的阶（元素个数）记为 n，密码学中要求 n 为大素数。椭圆曲线离散对数问题（ECDLP）的困难性远高于普通离散对数，因此 ECC 能用更短的密钥达到同等安全强度——256位ECC与3072位RSA安全性相当。