二、数学基础：模运算、最大公约数、欧几里得算法、扩展欧几里得算法、素数、同余与有限域基本概念
密码学本质上建立在数论与抽象代数的基石之上。无论是RSA、ECC还是AES，其安全性最终都归结为若干数学难题的难解性。本章将系统梳理模运算、最大公约数（GCD）、欧几里得算法、扩展欧几里得算法、素数、同余关系以及有限域的基本概念。这些内容不仅是后续学习公钥密码、数字签名和哈希函数的基础，更是理解密码协议安全模型的必备工具。我们将从最朴素的整数除法出发，逐步构建起通往现代密码学的数学阶梯。
2.1 模运算与同余关系
核心原理：模运算（Modular Arithmetic）是密码学中最基础的运算规则。给定正整数 n，任意整数 a 除以 n 的余数称为 a 模 n 的余数，记作 a mod n。同余关系则定义了两个整数在模 n 意义下是否"等价"：若 (a - b) 能被 n 整除，则称 a 与 b 模 n 同余，记作 a ≡ b (mod n)。同余关系是等价关系，它将整数集划分为 n 个等价类，每个等价类称为一个模 n 的剩余类。
模运算具有与普通算术类似的性质：加法、减法、乘法在模 n 下封闭，且满足交换律、结合律和分配律。但除法需要特殊处理——只有在除数与模数互素时，模逆元才存在。这一特性直接引出了扩展欧几里得算法的应用场景。
| 运算性质 | 表达式 | 密码学应用示例 |
|---|---|---|
| 加法封闭性 | (a + b) mod n | 流密码中的密钥流生成 |
| 乘法封闭性 | (a × b) mod n | RSA 加密中的模幂运算 |
| 模逆元存在条件 | gcd(a, n) = 1 | RSA 私钥计算 d ≡ e⁻¹ (mod φ(n)) |
| 幂运算 | aᵇ mod n | Diffie-Hellman 密钥交换 |
2.2 最大公约数与欧几里得算法
判断方法或操作流程：最大公约数（Greatest Common Divisor, GCD）指两个整数共有约数中最大的一个。欧几里得算法（Euclidean Algorithm）基于一个简单而深刻的观察：gcd(a, b) = gcd(b, a mod b)。通过反复应用带余除法，将问题规模逐步缩小，直至余数为零，此时除数即为最大公约数。
// 欧几里得算法伪代码
function gcd(a, b):
while b ≠ 0:
temp = b
b = a mod b
a = temp
return a
// 示例：计算 gcd(252, 105)
// 252 = 2×105 + 42
// 105 = 2×42 + 21
// 42 = 2×21 + 0
// 结果：gcd(252, 105) = 21欧几里得算法的时间复杂度为 O(log min(a, b))，即使对于数百位的超大整数（如 RSA 密钥中的素数），也能在毫秒级完成计算。这一效率使得它成为密码学中不可或缺的基础工具。
2.3 扩展欧几里得算法与模逆元
核心原理：扩展欧几里得算法（Extended Euclidean Algorithm）在计算 gcd(a, b) 的同时，还能找到整数系数 x 和 y，使得 ax + by = gcd(a, b)。当 gcd(a, n) = 1 时，该等式变为 ax + ny = 1，两边同时模 n，得到 ax ≡ 1 (mod n)，即 x 就是 a 在模 n 下的乘法逆元。
// 扩展欧几里得算法伪代码
function extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
else:
(g, x1, y1) = extended_gcd(b, a mod b)
x = y1
y = x1 - (a // b) * y1
return (g, x, y)
// 示例：求 17 在模 3120 下的逆元
// extended_gcd(17, 3120) 返回 (1, 2753, -15)
// 验证：17 × 2753 = 46801 = 15 × 3120 + 1 ✓2.4 素数基础与素性检测
判断方法或操作流程：素数是大于 1 且只能被 1 和自身整除的自然数。素数在密码学中扮演着核心角色：RSA 的安全性依赖于大素数分解的困难性，Diffie-Hellman 依赖于有限域上离散对数的难解性。素数的分布规律（素数定理）表明，在 n 附近素数的密度约为 1/ln(n)，这为随机生成大素数提供了理论依据。
实际应用中，我们使用概率性素性检测算法（如 Miller-Rabin）来快速判断大数是否为素数。Miller-Rabin 算法通过多次随机基测试，可以将误判概率降低到 4^(-k)（k 为测试轮数）。对于 1024 位的素数，通常进行 20-40 轮测试即可达到足够的安全性。
| 素性检测算法 | 类型 | 时间复杂度 | 误判概率 | 应用场景 |
|---|---|---|---|---|
| 试除法 | 确定性 | O(√n) | 0 | 小素数（< 10¹²） |
| Miller-Rabin | 概率性 | O(k log³ n) | 4^(-k) | RSA/DH 大素数生成 |
| AKS 算法 | 确定性 | O(log⁶ n) | 0 | 理论证明，实际较少使用 |
2.5 有限域基本概念
核心原理：有限域（Finite Field），又称伽罗瓦域（Galois Field），是包含有限个元素的域。密码学中最常用的有限域有两种：素数域 GF(p)（p 为素数）和二进制域 GF(2ⁿ)。域必须满足加法、减法、乘法、除法（除零外）四种运算封闭，且满足交换律、结合律和分配律。
在 GF(p) 中，所有运算都在模 p 下进行。例如在 GF(7) 中：3 + 5 = 8 mod 7 = 1，4 × 6 = 24 mod 7 = 3。域中每个非零元素都有乘法逆元，这使得除法运算成为可能。GF(2ⁿ) 则常用于 AES 加密的 S 盒构造和椭圆曲线密码学，其元素可以表示为二进制多项式。
2.6 案例拆解：从欧几里得到 RSA 密钥生成
案例背景与目标：假设我们需要为一个安全通信系统生成 RSA 密钥对。系统要求：模数 n 为 1024 位，公钥指数 e 固定为 65537（一个常用的素数）。我们需要完成素数选取、模数计算、欧拉函数计算、私钥推导的完整流程。
关键输入数据与操作步骤：
- 素数选取：使用 Miller-Rabin 算法生成两个 512 位素数 p 和 q。假设生成 p = 0xF72...（512位），q = 0xB3E...（512位）。
- 计算模数：n = p × q（1024位）。
- 计算欧拉函数：φ(n) = (p-1)(q-1)。
- 验证公钥指数：确认 gcd(e, φ(n)) = 1，即 e 与 φ(n) 互素。
- 计算私钥：使用扩展欧几里得算法求解 e × d ≡ 1 (mod φ(n))，得到 d。
- 销毁中间值：安全删除 p、q、φ(n) 的临时副本。
结果与复盘：生成的公钥为 (n, e)，私钥为 (n, d)。整个过程中，扩展欧几里得算法是计算私钥 d 的关键步骤。若 e 与 φ(n) 不互素，则必须重新选择 e 或重新生成素数。实际工程中，还需要考虑侧信道攻击防护、素数生成时的随机性质量、以及 p 和 q 的差值不能过小等安全约束。