代数结构概述
密码学大量使用抽象代数的概念。代数结构是定义了若干运算及其规则的集合。我们从简单到复杂依次介绍群、环、域。
群（Group）
一个群 (G, ★) 是集合 G 和一个二元运算 ★，满足四条公理：
- 封闭性：∀a, b ∈ G，a ★ b ∈ G
- 结合律：(a ★ b) ★ c = a ★ (b ★ c)
- 单位元：∃e ∈ G，使得 ∀a ∈ G，e ★ a = a ★ e = a
- 逆元：∀a ∈ G，∃a-1 ∈ G，使得 a ★ a-1 = e
若还满足交换律（a ★ b = b ★ a），则称为阿贝尔群（交换群）。
例子：
- (Z, +) 整数加法群——阿贝尔群，单位元为 0，a 的逆元为 -a
- (Zn*, ×) 模 n 乘法群——与 n 互素的数在模 n 乘法下构成的群
- 椭圆曲线上的点在"点加法"下构成群
环（Ring）
一个环 (R, +, ×) 有两个运算，满足：
- (R, +) 是阿贝尔群
- (R, ×) 满足封闭性和结合律
- 分配律：a × (b + c) = a × b + a × c
若乘法还有单位元（乘法恒等元 1），则称为含幺环。
例子：(Z, +, ×) 整数环；多项式环 Z[x]；模 n 整数环 Zn。
域（Field）
一个域 (F, +, ×) 是一个环，且 (F\{0}, ×) 也是阿贝尔群，即每个非零元素都有乘法逆元。
简单说：域中的元素可以做加、减、乘、除（除数非零），且结果仍在域中。
例子：有理数 Q、实数 R、复数 C 都是域。整数 Z 不是域（2 没有乘法逆元）。
有限域（Finite Field / 伽罗瓦域）
元素个数有限的域称为有限域，也叫伽罗瓦域（Galois Field），记作 GF(q) 或 Fq，其中 q 是元素个数。
有限域的存在性
有限域存在当且仅当其元素个数 q 是某个素数的幂，即 q = pn（p 为素数，n ≥ 1）。
- 当 n = 1 时，GF(p) = Zp，即模 p 的整数域（p 为素数）。
- 当 n > 1 时，GF(pn) 的元素是系数在 GF(p) 中的多项式，模某个不可约多项式。
GF(p) — 素数域
GF(p) = {0, 1, 2, ..., p-1}，加法和乘法都是模 p 运算。
例如 GF(7)：加法 3 + 5 = 1 (mod 7)；乘法 3 × 5 = 1 (mod 7)，所以 3 和 5 互为乘法逆元。
GF(2n) — 扩展域
AES 使用 GF(28)，即元素个数 256 的有限域。
GF(2n) 的元素可以表示为：
- 多项式表示：an-1xn-1 + ... + a₁x + a₀，系数 ai ∈ {0, 1}
- 二进制表示：直接用系数组成的 n 位二进制数，如 x⁶ + x⁴ + x + 1 → 01010011 → 0x53
加法：对应系数做模 2 加法，即 XOR（异或）。
乘法：多项式相乘后，模一个 n 次不可约多项式。AES 中使用的不可约多项式为 x⁸ + x⁴ + x³ + x + 1（0x11B）。
密码学应用
- AES：字节替换（S 盒）和列混合都在 GF(28) 中运算
- RSA：在 Zn 中运算，安全性依赖于 Zn 的结构
- 椭圆曲线密码（ECC）：曲线定义在有限域 GF(p) 或 GF(2n) 上
- 纠错码：如 Reed-Solomon 码在 GF(28) 上编码