2. 数学基础与计算复杂性

现代密码学的安全性并非凭空宣称，而是建立在代数结构与计算复杂性假设之上。理解群、环、域，掌握模运算与欧几里得算法，区分 GF(p) 与 GF(2^n)，并认识计算复杂性类与可证明安全的基本思想，是读懂 RSA、ElGamal、AES、椭圆曲线密码等具体方案的必经之路。本章从“结构—运算—复杂度—安全”这条主线展开。

一、代数结构：群、环、域

一个群 (G, ·) 由一个集合 G 和一个二元运算“·”组成，需满足四条性质：封闭性（任意 a,b∈G，a·b∈G）、结合律（(a·b)·c = a·(b·c)）、存在单位元 e（a·e = e·a = a）、每个元素存在逆元（a·a⁻¹ = e）。若还满足交换律 a·b = b·a，则称为阿贝尔群（交换群）。密码学中大量使用有限阿贝尔群，例如模 n 的加法群 (Z_n, +) 和模 p 的乘法群 (Z_p*, ×)。

环 (R, +, ×) 在加法下构成阿贝尔群，乘法满足封闭性与结合律，且乘法对加法满足分配律。环不要求乘法有逆元，也不要求乘法交换。整数环 Z 是最典型的例子。

域 (F, +, ×) 是乘法也构成阿贝尔群（去掉零元后）的交换环，即每个非零元素都有乘法逆元。有理数域 Q、实数域 R 是无限域；密码学更关心有限域（伽罗瓦域），元素个数称为域的阶。有限域的阶必为素数幂 p^n，记作 GF(p^n)。

这三层结构是递进关系：域一定是环，环一定是加法群，但反之不成立。密码方案常把秘密放在某个有限域的乘法群中，因为“求逆容易、求离散对数困难”这一不对称性正是安全性的来源。

二、模运算与欧几里得算法

模运算把整数映射到有限集合。a mod n 表示 a 除以 n 的余数，取值范围 0 到 n−1。模运算对加、减、乘封闭，且满足 (a+b) mod n = ((a mod n)+(b mod n)) mod n，乘法同理。但除法不能直接进行，必须乘以逆元。

元素 a 在模 n 下存在乘法逆元，当且仅当 gcd(a, n) = 1。求逆元的标准工具是扩展欧几里得算法。它先通过欧几里得算法求最大公约数，再回代得到贝祖等式：

求 gcd(240, 46)：
240 = 5 × 46 + 10
 46 = 4 × 10 + 6
 10 = 1 × 6  + 4
  6 = 1 × 4  + 2
  4 = 2 × 2  + 0   → gcd = 2

回代求 240 与 46 的贝祖系数：
2 = 6 − 1×4
  = 6 − 1×(10 − 1×6) = 2×6 − 10
  = 2×(46 − 4×10) − 10 = 2×46 − 9×10
  = 2×46 − 9×(240 − 5×46) = 47×46 − 9×240
即 47×46 + (−9)×240 = 2

若 gcd(a, n) = 1，则存在 x, y 使 ax + ny = 1，于是 ax ≡ 1 (mod n)，x 就是 a 的逆元。例如求 17 在模 101 下的逆元：101 = 5×17 + 16，17 = 1×16 + 1，回代得 1 = 17 − 16 = 17 − (101 − 5×17) = 6×17 − 101，故 17⁻¹ ≡ 6 (mod 101)。验证：17×6 = 102 ≡ 1 (mod 101)，正确。这一过程在 RSA 密钥生成、椭圆曲线点运算、AES 的 S 盒构造中反复出现。

三、有限域 GF(p) 与 GF(2^n)

GF(p)（p 为素数）是最简单的有限域，元素为 {0, 1, …, p−1}，加法和乘法都在模 p 下进行。由于 p 是素数，每个非零元素都与 p 互素，因此都有逆元，构成域。RSA 中的模数 n = p·q 不是素数，所以 Z_n 只是环而非域，这正是 RSA 中需要小心处理“不可逆元素”的原因。

GF(2^n) 的元素是 n 位二进制串，可视为系数在 {0,1} 的多项式。加法就是按位异或（无进位），乘法是多项式相乘后对一个 n 次不可约多项式取模。例如 GF(2^8) 中，AES 使用不可约多项式 m(x) = x^8 + x^4 + x^3 + x + 1（即 0x11B）。两个字节相乘时，先做多项式乘法，再对 m(x) 约简。由于特征为 2，加法与减法相同，都是异或，这使硬件实现非常高效。

GF(p) 与 GF(2^n) 的差别决定了算法风格：前者适合大整数模运算（RSA、Diffie-Hellman），后者适合位运算与查表（AES、Reed-Solomon 纠错）。选择哪种域，取决于性能、硬件平台和安全参数。

四、计算复杂性类与可证明安全

密码学安全性依赖“某些问题很难算”。计算复杂性理论用资源（时间、空间）对问题分类。P 类是确定性图灵机多项式时间可解的问题，如整数加法、模幂运算。NP 类是给定候选解后可在多项式时间内验证的问题。密码学更关心单向函数与陷门单向函数：正向计算容易，反向求逆困难；若掌握陷门信息（如 RSA 的私钥 d），求逆又变容易。

常见困难问题包括：大整数分解（RSA 基础）、有限域离散对数（ElGamal、DH 基础）、椭圆曲线离散对数（ECC 基础）。这些问题目前没有已知多项式时间经典算法，但 Shor 算法在量子计算机上可多项式时间求解，因此后量子密码转向格、编码、多变量等新困难问题。

可证明安全的基本思想是“归约”：若存在一个多项式时间算法能攻破方案，则可用它构造出多项式时间算法求解底层困难问题，与假设矛盾。常见证明模型有随机预言机模型（RO）和标准模型。安全目标通常表述为 IND-CPA（选择明文攻击下的不可区分性）、IND-CCA（选择密文攻击）等。需要强调：可证明安全是相对假设的，若假设不成立或模型过强，证明并不保证现实绝对安全。

本章的要点可归纳为：群、环、域是逐层加强的代数结构；模运算中除法靠逆元，逆元靠扩展欧几里得算法；GF(p) 与 GF(2^n) 分别对应大整数运算与位运算两种实现风格；计算复杂性类刻画了“难”的含义，可证明安全则用归约把方案安全与困难问题假设连接起来。掌握这些，才能理解后续 RSA、AES、椭圆曲线等方案为何这样设计、安全性从何而来。