一、为什么密码学家需要抽象代数
初学密码学时，读者往往会分别接触 Diffie-Hellman 密钥交换、RSA 加密、椭圆曲线密码体制(ECC)以及基于配对(pairing)的方案。这些协议表面上各自独立：Diffie-Hellman 工作在大素数的乘法群上，RSA 依赖大整数分解的困难性，ECC 利用椭圆曲线上的点加法，而配对则将两个不同的群映射到第三个群中。然而，如果仅仅把它们当作孤立的算法来记忆，不但学习效率低下，更难以理解为什么安全参数需要那样选取、为什么某些攻击能够跨协议迁移。
抽象代数(abstract algebra)提供的正是一套将这些看似不同的对象统一起来的语言。在这一框架中，Diffie-Hellman 的安全性归结为”在某个循环群中求解离散对数问题(discrete logarithm problem, DLP)“，无论底层的群是整数模素数的乘法群、椭圆曲线群，还是更奇异的代数簇上的群——分析方法可以共享，安全归约可以统一书写。RSA 的正确性证明需要欧拉定理，而欧拉定理本身是拉格朗日定理(Lagrange’s theorem)在有限群上的直接推论。有限域(finite field)的结构定理决定了 AES 中 S 盒的代数设计以及纠错码在信道编码中的表现。基于格(lattice)的后量子密码方案则大量使用多项式环(polynomial ring)上的运算。
因此，掌握群(group)、环(ring)、域(field)这三层代数结构，对于任何希望深入理解密码学——而非仅仅调用库函数——的工程师与研究者而言，都是不可绕开的基础。本文将以密码学应用为线索，系统地引入这些核心概念，力求在严谨性与直觉之间取得平衡。
笔者认为，代数结构不仅仅是密码学的「工具箱」，它更像是密码学的「隐藏架构」——一旦你看到了这层架构，就再也无法忽视它。每一个密码协议的背后，都有一个代数结构在默默支撑：Diffie-Hellman 的交换律来自阿贝尔群，RSA 的正确性来自欧拉定理（群论的推论），AES 的代数免疫性来自有限域的结构。学习抽象代数不是为了「看起来更数学」，而是为了看穿密码方案的本质。
二、群的定义与基本性质
在给出严格定义之前，先建立一个直觉。群就是一个「可逆运算系统」——你有一堆对象，一种操作方式，操作的结果还在这堆对象中，你可以任意组合操作的顺序而不影响结果，有一个「什么都不做」的操作，而且每个操作都能被撤销。整数加法就是一个群：加减不出整数范围，先加 3 再加 5 等于加 8 跟顺序无关，加 0 什么都不变，加 3 可以用减 3 来撤销。
一个群(group)是一个集合 G 连同一个二元运算 · 组成的代数系统 (G, ·)，满足以下四条公理：
第一，封闭性(closure)：对任意 a, b ∈ G，运算结果 a · b 仍然属于 G。这一条保证了我们永远不会”算出”集合之外的东西。在密码学中，这意味着对消息进行加密或签名运算后，结果仍在同一个数学空间中，不需要额外的边界处理。
第二，结合律(associativity)：对任意 a, b, c ∈ G，有 (a · b) · c = a · (b · c)。结合律使得我们可以不加括号地书写多次运算的结果，这对于”重复平方法(square-and-multiply)“等高效幂运算算法的正确性至关重要。
第三，单位元(identity element)：存在元素 e ∈ G，使得对任意 a ∈ G 有 e · a = a · e = a。在整数加法群中，单位元是 0；在模 n 乘法群中，单位元是 1。
第四，逆元(inverse)：对任意 a ∈ G，存在元素 a⁻¹ ∈ G 使得 a · a⁻¹ = a⁻¹ · a = e。逆元的存在保证了运算的”可撤销性”。在密码学中，解密运算往往对应于加密运算的逆。
如果群还满足交换律(commutativity)，即对任意 a, b ∈ G 有 a · b = b · a，则称之为阿贝尔群(abelian group)或交换群。密码学中遇到的大部分群都是阿贝尔群——整数模 n 的加法群 (Z/nZ, +)、素数阶乘法群 (Z/pZ)* 、椭圆曲线群等均满足交换律。
群的阶(order)是集合 G 中元素的个数，记作 |G|。元素 a 的阶(order of an element)是使 aᵏ = e 成立的最小正整数 k。群的阶与元素的阶之间的关系是密码学参数选择的核心依据之一，后文讨论拉格朗日定理时会详细展开。
下面通过 Python 代码来展示整数模 n 加法群和乘法群的基本运算：
"""Z/nZ 上的群运算演示"""
def add_mod(a: int, b: int, n: int) -> int:
"""加法群 (Z/nZ, +) 中的运算"""
return (a + b) % n
def mul_mod(a: int, b: int, n: int) -> int:
"""乘法群 (Z/nZ)* 中的运算"""
return (a * b) % n
def power_mod(base: int, exp: int, n: int) -> int:
"""重复平方法计算模幂，等价于 pow(base, exp, n)"""
result = 1
base = base % n
while exp > 0:
if exp & 1:
result = mul_mod(result, base, n)
exp >>= 1
base = mul_mod(base, base, n)
return result
def inverse_mod(a: int, n: int) -> int:
"""扩展欧几里得算法求乘法逆元"""
if a == 0:
raise ValueError("0 没有乘法逆元")
g, x, _ = extended_gcd(a % n, n)
if g != 1:
raise ValueError(f"{a} 在模 {n} 下没有逆元（gcd={g}）")
return x % n
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
"""返回 (gcd, x, y) 使得 a*x + b*y = gcd"""
if a == 0:
return b, 0, 1
g, x1, y1 = extended_gcd(b % a, a)
return g, y1 - (b // a) * x1, x1
# 验证：模 7 乘法群
p = 7
print(f"(Z/{p}Z)* 的元素：", [a for a in range(1, p)])
for a in range(1, p):
inv = inverse_mod(a, p)
print(f" {a} * {inv} ≡ {mul_mod(a, inv, p)} (mod {p})")这段代码实现了模运算下的加法、乘法、模幂以及求逆运算。扩展欧几里得算法(extended Euclidean algorithm)是密码学中最基础的工具之一，RSA 密钥生成、椭圆曲线点运算、格基约化等场景中都会频繁用到。
三、子群、陪集与拉格朗日定理
给定群 (G, ·)，如果 H ⊆ G 且 H 在同一运算下也构成群，则称 H 为 G 的子群(subgroup)，记作 H ≤ G。判定子群最常用的等价条件是：H 非空，且对任意 a, b ∈ H，有 a · b⁻¹ ∈ H。
子群的概念在密码学中无处不在。例如，在素数 p 的乘法群 (Z/pZ)* 中，所有二次剩余(quadratic residue)构成一个指数为 2 的子群；Schnorr 签名方案选择的就是 (Z/pZ)* 中一个素数阶 q 的子群来工作，从而在保证安全性的同时减小签名长度。
对于子群 H ≤ G 和任意元素 a ∈ G，集合 aH = {a · h : h ∈ H} 称为 H 的一个左陪集(left coset)。陪集有一个关键性质：任意两个左陪集要么完全相同，要么完全不相交。因此，群 G 可以被划分为若干互不相交的陪集，每个陪集的大小恰好等于 |H|。
由此立即得到拉格朗日定理(Lagrange’s theorem)：如果 G 是有限群，H 是 G 的子群，那么 |H| 整除 |G|。商 [G : H] = |G| / |H| 称为 H 在 G 中的指数(index)。
拉格朗日定理有一系列密码学中至关重要的推论。首先，任何元素 a ∈ G 的阶必定整除 |G|。这意味着对任意 a ∈ G，有 a^|G| = e。将此结论应用于 (Z/pZ)，其中 |G| = p - 1，便得到费马小定理(Fermat’s little theorem)：对任意不被 p 整除的整数 a，有 a^(p-1) ≡ 1 (mod p)。进一步推广到 (Z/nZ)，其中 |G| = φ(n)（欧拉函数），便得到欧拉定理(Euler’s theorem)：a^φ(n) ≡ 1 (mod n)。RSA 的正确性——即 m^(ed) ≡ m (mod n)——正是欧拉定理的直接应用。
其次，拉格朗日定理告诉我们，如果一个群的阶是素数 p，那么它没有非平凡子群(除了 {e} 和自身)。这在椭圆曲线密码学中意义重大：选择一条阶为素数的椭圆曲线，可以保证曲线群中不存在低阶子群，从而避免小子群攻击(small subgroup attack)。
对于密码学的参数选择，拉格朗日定理意味着：如果我们希望离散对数问题的求解需要至少 2^128 次运算，那么工作群的阶中必须包含一个至少 256 位的素因子。否则，攻击者可以利用 Pohlig-Hellman 算法将问题分解到各个小素因子对应的子群上逐一求解，从而大幅降低计算复杂度。
四、循环群与生成元
如果群 G 中存在一个元素 g，使得 G 中的每一个元素都可以写成 g 的某个幂次 gᵏ，则称 G 为循环群(cyclic group)，g 为 G 的生成元(generator)，记作 G = ⟨g⟩。
循环群是密码学中最核心的代数对象。所有素数阶有限群都是循环群——这是抽象代数中的一个基本定理，也是椭圆曲线密码学能够工作的根本原因。选定一条素数阶椭圆曲线后，任意非单位元的点都是生成元，这使得参数选择变得简单。
对于 n 阶循环群 G = ⟨g⟩，其生成元的个数恰好等于欧拉函数 φ(n)。当 n 是素数时，φ(n) = n - 1，即除了单位元外的所有元素都是生成元。当 n 是合数时，只有阶恰好等于 n 的元素才是生成元。在 (Z/pZ)* 中寻找生成元(通常称为原根, primitive root)是 Diffie-Hellman 参数设置中的一个实际步骤。
离散对数问题(discrete logarithm problem, DLP)可以精确地表述为：给定循环群 G = ⟨g⟩ 及元素 h ∈ G，求整数 x 使得 gˣ = h。这个问题的困难性是 Diffie-Hellman 密钥交换、ElGamal 加密、Schnorr 签名等一大类协议安全性的基石。
循环群的一个重要性质是：n 阶循环群 G 的子群与 n 的因子一一对应——对于 n 的每一个正因子 d，G 恰好有一个 d 阶子群，且该子群也是循环群，由 g^(n/d) 生成。这一结构完全由群的阶决定，与群的具体”实现”无关。正是这种高度的结构透明性，使得密码分析者能够利用群的阶的因式分解来设计攻击(如 Pohlig-Hellman 算法)，也使得密码设计者知道应当选择什么样的参数来抵御这些攻击。
五、群同态与商群
在理解同态之前，先想象两个不同的计算系统——比如整数加法和时钟上的加法。它们「形状不同」，但有某种内在的相似性：在整数上做完加法再投影到时钟上，和先投影再在时钟上做加法，结果是一样的。这种「先算后映射=先映射后算」的性质，就是同态的本质。
群同态(group homomorphism)是保持群运算结构的映射。具体地说，从群 (G, ·) 到群 (H, ) 的映射 φ: G → H 称为同态，如果对任意 a, b ∈ G，有 φ(a · b) = φ(a) φ(b)。
同态的核心概念包括：核(kernel)，即 ker(φ) = {a ∈ G : φ(a) = eH}，它总是 G 的正规子群(normal subgroup)；像(image)，即 im(φ) = {φ(a) : a ∈ G}，它是 H 的子群。
正规子群 N ◁ G 满足对任意 g ∈ G 有 gNg⁻¹ = N。对于阿贝尔群，每个子群都是正规子群。正规子群的重要性在于：它允许我们构造商群(quotient group) G/N，其元素是 N 的陪集，运算定义为 (aN)(bN) = (ab)N。商群的构造在密码学中对应着”将大问题投影到小空间”的思想。
用一个具体例子来展示商群的构造。考虑整数加法群 Z 及其子群 3Z = {…, -6, -3, 0, 3, 6, …}（所有 3 的倍数）。3Z 是 Z 的正规子群（因为 Z 是阿贝尔群）。商群 Z/3Z 由三个陪集组成：
- 0 + 3Z = {…, -6, -3, 0, 3, 6, …}（所有被 3 整除的整数）
- 1 + 3Z = {…, -5, -2, 1, 4, 7, …}（所有除以 3 余 1 的整数）
- 2 + 3Z = {…, -4, -1, 2, 5, 8, …}（所有除以 3 余 2 的整数）
这三个陪集在加法下构成一个群。例如，(1 + 3Z) + (2 + 3Z) = (1 + 2) + 3Z = 3 + 3Z = 0 + 3Z，因为 3 ∈ 3Z。这正是「时钟算术 mod 3」——加到 3 就回绕到 0。Z/3Z 就是我们熟悉的模 3 运算，而商群的构造揭示了模运算「回绕」的代数本质。
一个经常被忽视的观点是，商群的概念为「模运算为什么会回绕（wrap around）」提供了最深层的解释。当我们写 7 mod 3 = 1 时，我们其实是在说：7 和 1 属于同一个陪集 1 + 3Z。模运算不是简单的「取余数」——它是将无穷的整数世界投影到一个有限的商群上。理解了这一点，你就理解了为什么密码学中的几乎所有运算都在「模某个数」的空间里进行：因为我们需要有限的、可计算的代数结构，而商群恰恰是从无限结构中「雕刻」出有限结构的数学工具。
第一同构定理(first isomorphism theorem)将上述概念联系起来：对于群同态 φ: G → H，有 G/ker(φ) ≅ im(φ)。这里 ≅ 表示同构(isomorphism)，即存在一个双射同态。第一同构定理是抽象代数中最重要的结构性工具之一。
下面用一个具体的例子来贯穿同态、核和第一同构定理。定义映射 φ: (Z, +) → (Z/6Z, +)，其中 φ(n) = n mod 6。验证 φ 是同态：φ(3 + 4) = φ(7) = 7 mod 6 = 1，而 φ(3) + φ(4) = 3 + 4 = 7 ≡ 1 (mod 6)，两者相等。φ 的核是所有映射到 0 的整数，即 ker(φ) = 6Z = {…, -12, -6, 0, 6, 12, …}——恰好是 6 的所有倍数。φ 的像是整个 Z/6Z（因为对任意 r ∈ {0, 1, …, 5}，φ(r) = r）。第一同构定理告诉我们 Z/ker(φ) = Z/6Z ≅ im(φ) = Z/6Z，即商群 Z/6Z 与像同构——在这个例子中它们恰好就是同一个群。
在密码学中，同态的概念直接对应于同态加密(homomorphic encryption)的核心思想。如果加密函数 E 满足 E(m₁) ⊕ E(m₂) = E(m₁ + m₂)，其中 ⊕ 是密文空间上的运算，+ 是明文空间上的运算，那么 E 就是从明文群到密文群的一个同态。Paillier 加密系统和 ElGamal 加密系统分别满足加法同态和乘法同态性质。全同态加密(fully homomorphic encryption, FHE)则进一步要求同时保持加法和乘法两种运算的同态性，这已经超越了群同态的范畴，需要环同态的框架。
从更深层的视角来看，加密本身就是一个从明文空间到密文空间的同态映射。如果 E(m₁ + m₂) = E(m₁) ⊕ E(m₂)，那么加密函数 E 保持了加法结构——这不仅仅是同态加密的定义，它揭示了一个根本事实：密码学中的「结构保持」与「结构隐藏」之间存在深刻的张力。完全隐藏结构的加密（如 AES）不支持同态运算；保持结构的加密（如 Paillier）允许密文上的计算但可能泄露部分代数关系。从工程实践来看，理解这个张力，就是理解现代密码学设计空间的一把钥匙。
商群的概念在椭圆曲线同源(isogeny)密码学中也有重要应用。给定椭圆曲线 E 及其子群 K，同源映射 φ: E → E/K 恰好将 E 映射到以 K 为核的商群对应的另一条椭圆曲线上。SIKE/SIDH 等后量子候选方案的安全性就建立在计算同源映射的困难性之上。
六、环与理想
环(ring)在群的基础上引入了第二种运算。一个环 (R, +, ·) 由一个集合 R 和两种二元运算——加法 + 与乘法 · ——组成，满足：(R, +) 构成阿贝尔群；乘法满足结合律；乘法对加法满足左右分配律(distributive law)。
如果乘法满足交换律，则称为交换环(commutative ring)。如果存在乘法单位元 1，则称为含幺环(ring with unity)。如果一个交换含幺环中没有零因子(zero divisor)——即 a · b = 0 必然意味着 a = 0 或 b = 0——则称为整环(integral domain)。
最基本的环是整数环 (Z, +, ·)。对密码学更重要的是模 n 整数环 Z/nZ：加法和乘法都取模 n。当 n 是素数 p 时，Z/pZ 中每个非零元素都有乘法逆元，因此 Z/pZ 实际上构成一个域。当 n 是合数时(例如 RSA 中 n = pq)，Z/nZ 中存在零因子：p · q ≡ 0 (mod n)，而 p 和 q 都不为零。零因子的存在正是 RSA 安全性的代数本质——如果攻击者能找到 n 的零因子，就相当于分解了 n。
环中的理想(ideal)类似于群中的正规子群。一个子集 I ⊆ R 称为 R 的理想，如果 I 是 (R, +) 的子群，且对任意 r ∈ R, a ∈ I 有 r · a ∈ I 且 a · r ∈ I。由单个元素 a 生成的理想 (a) = {r · a : r ∈ R} 称为主理想(principal ideal)。Z 中的每个理想都是主理想——由某个整数 n 生成的理想 (n) = nZ 正是 n 的所有倍数组成的集合。
商环(quotient ring) R/I 的构造完全类比于商群：其元素是 I 的陪集 a + I，加法和乘法分别定义为 (a + I) + (b + I) = (a + b) + I 和 (a + I)(b + I) = (ab) + I。模运算 Z/nZ 实际上就是整数环 Z 关于理想 nZ 的商环。
多项式环(polynomial ring)在密码学中的地位极为重要。给定一个环 R，R 上的多项式环 R[x] 由所有以 R 中元素为系数的多项式组成，加法和乘法按照通常的多项式运算定义。后量子密码学中最有前途的方向之一——基于格的密码学(lattice-based cryptography)——大量使用商环 Z[x]/(xⁿ + 1) 上的运算。NIST 已经标准化的 ML-KEM(原 CRYSTALS-Kyber)和 ML-DSA(原 CRYSTALS-Dilithium)方案的核心运算都在这种多项式商环上进行。选择 xⁿ + 1(其中 n 是 2 的幂)作为模多项式的原因在于：它是分圆多项式(cyclotomic polynomial)，使得商环具有良好的代数性质，同时允许使用数论变换(NTT)进行高效的多项式乘法。
七、域与有限域概览
域(field)是一个交换含幺环，其中每个非零元素都有乘法逆元。等价地说，域是一个集合 F，配备加法和乘法两种运算，使得 (F, +) 构成阿贝尔群（加法群），(F {0}, ·) 构成阿贝尔群（乘法群），且乘法对加法满足分配律。
有理数集 Q、实数集 R、复数集 C 都是域，但它们是无限域。密码学中更关心的是有限域(finite field)，也称伽罗瓦域(Galois field)，通常记作 GF(q) 或 F_q。有限域的存在性与唯一性定理是代数学中最优美的结果之一：对于每一个素数幂 q = pⁿ，恰好存在一个(在同构意义下)q 阶有限域；反过来，有限域的阶必然是某个素数的幂次。
当 n = 1 时，GF(p) 就是我们熟悉的 Z/pZ，即模素数 p 的整数运算。这是最简单的有限域，也是 RSA 和经典 Diffie-Hellman 所依赖的基本代数结构。
当 n > 1 时，GF(pⁿ) 的构造需要用到多项式环和商环的理论。具体做法是：在 GF(p)[x] 中选择一个 n 次不可约多项式(irreducible polynomial) f(x)，然后构造商环 GF(p)[x]/(f(x))。这个商环恰好是一个 pⁿ 阶有限域。不可约多项式在有限域构造中的作用类似于素数在整数中的作用——正如 Z/nZ 当且仅当 n 是素数时才构成域，GF(p)[x]/(f(x)) 当且仅当 f(x) 不可约时才构成域。
最经典的密码学应用是 GF(2⁸) = GF(256)，它是 AES(高级加密标准)中 S 盒设计的代数基础。AES 选择的不可约多项式为 f(x) = x⁸ + x⁴ + x³ + x + 1。在这个域中，每个字节(8 位)对应一个多项式，字节之间的加法对应多项式系数的模 2 加法(即按位异或)，乘法对应多项式乘法后模 f(x)。S 盒的核心操作是在 GF(2⁸) 中求乘法逆元，这赋予了 AES 良好的抗差分分析和抗线性分析能力。
椭圆曲线密码学也大量使用有限域。定义在 GF(p) 上的椭圆曲线(如 secp256k1、P-256)和定义在 GF(2ⁿ) 上的椭圆曲线(如 NIST B-283)分别适用于不同的硬件实现场景。基于配对的密码学(pairing-based cryptography)则需要在有限域的扩域(extension field)上进行运算——例如 BN256 曲线上的 Ate 配对将椭圆曲线上的两个点映射到 GF(p¹²) 的乘法群中。
有限域的乘法群 GF(q)* 总是一个 q - 1 阶的循环群。这一事实将域论与群论联系了起来：有限域上的离散对数问题，本质上就是其乘法群(一个循环群)中的离散对数问题。
八、中国剩余定理
中国剩余定理(Chinese Remainder Theorem, CRT)是数论与代数中最古老也最实用的定理之一。其名称源于《孙子算经》中的”物不知数”问题。
定理陈述如下：设 m₁, m₂, …, mₖ 是两两互素(pairwise coprime)的正整数，令 M = m₁ · m₂ · … · mₖ。则对于任意整数 a₁, a₂, …, aₖ，同余方程组
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)在模 M 下恰好有唯一解。
更代数化地表述：当 gcd(m, n) = 1 时，环同构 Z/mnZ ≅ Z/mZ × Z/nZ 成立。这个同构不仅保持加法结构，也保持乘法结构，是一个环同构。
证明的核心思路是构造性的。令 Mᵢ = M / mᵢ，由于 mᵢ 与 Mᵢ 互素，存在 Mᵢ 的模 mᵢ 逆元 yᵢ，即 Mᵢ · yᵢ ≡ 1 (mod mᵢ)。则解为 x = Σᵢ aᵢ · Mᵢ · yᵢ (mod M)。
CRT 在密码学中最著名的应用是 RSA-CRT 加速。标准 RSA 解密需要计算 c^d mod n，其中 n = p · q，d 和 n 都是很大的数，直接计算模幂的代价很高。利用 CRT，可以将这一计算分解为两个较小的模幂运算：
m_p = c^(d mod (p-1)) mod p
m_q = c^(d mod (q-1)) mod q然后用 CRT 合并 m_p 和 m_q 得到 m mod n。由于模幂运算的复杂度大约与模数位长的三次方成正比，将一个 2048 位的模幂分解为两个 1024 位的模幂，速度大约提升四倍。几乎所有实际的 RSA 实现(包括 OpenSSL、BoringSSL 等)都采用了 CRT 优化。
CRT 与秘密共享(secret sharing)之间也有深刻的联系。Asmuth-Bloom 秘密共享方案直接基于 CRT 构造：选择两两互素的模数 m₁ < m₂ < … < mₙ，使得任意 t 个模数的乘积大于所有模数中最小的 n - t + 1 个的乘积。秘密 s 被编码为满足特定同余条件的数，分发给各参与方。任意 t 个参与方可以利用 CRT 恢复秘密，而少于 t 个参与方则信息论意义上无法获得任何关于秘密的信息。
以下 Python 代码演示了 CRT 的实现及其在 RSA 解密加速中的应用：
"""中国剩余定理(CRT)实现与 RSA-CRT 演示"""
from functools import reduce
from math import gcd
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
"""返回 (gcd, x, y) 使得 a*x + b*y = gcd"""
if a == 0:
return b, 0, 1
g, x1, y1 = extended_gcd(b % a, a)
return g, y1 - (b // a) * x1, x1
def crt(remainders: list[int], moduli: list[int]) -> int:
"""
中国剩余定理：给定余数列表和模数列表，返回唯一解。
要求模数两两互素。
"""
assert len(remainders) == len(moduli)
# 检查模数两两互素
for i in range(len(moduli)):
for j in range(i + 1, len(moduli)):
assert gcd(moduli[i], moduli[j]) == 1, \
f"模数 {moduli[i]} 和 {moduli[j]} 不互素"
M = reduce(lambda a, b: a * b, moduli)
x = 0
for a_i, m_i in zip(remainders, moduli):
M_i = M // m_i
_, y_i, _ = extended_gcd(M_i, m_i)
x += a_i * M_i * y_i
return x % M
# 经典示例：孙子算经的"物不知数"问题
# x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
result = crt([2, 3, 2], [3, 5, 7])
print(f"物不知数：x = {result}")
print(f" 验证：{result} mod 3 = {result % 3}, "
f"{result} mod 5 = {result % 5}, "
f"{result} mod 7 = {result % 7}")
# RSA-CRT 加速演示
print("\n--- RSA-CRT 解密加速 ---")
p, q = 61, 53 # 小素数用于演示
n = p * q # n = 3233
phi_n = (p - 1) * (q - 1) # φ(n) = 3120
e = 17
_, d, _ = extended_gcd(e, phi_n)
d = d % phi_n # 私钥指数
message = 2023
ciphertext = pow(message, e, n)
print(f"明文: {message}, 密文: {ciphertext}")
# 标准 RSA 解密
m_standard = pow(ciphertext, d, n)
print(f"标准解密: {m_standard}")
# RSA-CRT 解密
d_p = d % (p - 1)
d_q = d % (q - 1)
m_p = pow(ciphertext, d_p, p)
m_q = pow(ciphertext, d_q, q)
m_crt = crt([m_p, m_q], [p, q])
print(f"CRT 解密: {m_crt}")
print(f"两种方法一致: {m_standard == m_crt}")
# Garner 算法——更高效的 CRT 合并（仅两个模数时）
_, q_inv, _ = extended_gcd(q, p)
q_inv = q_inv % p
h = (q_inv * (m_p - m_q)) % p
m_garner = m_q + h * q
print(f"Garner 算法: {m_garner}")
print(f"三种方法一致: {m_standard == m_crt == m_garner}")代码中还展示了 Garner 算法，它是 CRT 在两个模数情形下的一种更高效的实现方式，避免了计算大乘积 M，在实际 RSA 实现中更为常用。
九、从代数到密码构造
至此，我们已经建立了群、环、域三层代数结构的基本框架。现在让我们回顾这些结构如何映射到具体的密码学构造，形成一个完整的图景。
Diffie-Hellman 密钥交换与 ElGamal 加密工作在一个循环群 G = ⟨g⟩ 上。协议的安全性依赖于计算性 Diffie-Hellman 假设(CDH)或判定性 Diffie-Hellman 假设(DDH)，这些假设的本质是：在循环群中，已知 g, gᵃ, gᵇ，计算或判定 gᵃᵇ 是困难的。群可以是 (Z/pZ)* 的素数阶子群，也可以是椭圆曲线群——代数框架完全一致，只是底层群的选择不同。
RSA 的正确性建立在环 Z/nZ 的结构之上（其中 n = pq），而其安全性则依赖于大整数分解问题的困难性。CRT 提供的环同构 Z/nZ ≅ Z/pZ × Z/qZ 不仅给出了 RSA 解密的加速方法，也揭示了 RSA 问题的代数结构——如果攻击者能计算这个同构(即分解 n)，就能直接解密。
椭圆曲线密码学(ECC)的底层群是定义在有限域 GF(p) 或 GF(2ⁿ) 上的椭圆曲线 E 的有理点群 E(GF(q))。这个群上的离散对数问题——给定点 P 和 Q = kP，求整数 k——目前没有已知的亚指数时间算法(对于一般椭圆曲线)，这使得 ECC 在相同安全级别下所需的密钥长度远小于基于 (Z/pZ)* 的方案。256 位的椭圆曲线密钥提供的安全性大约等价于 3072 位的 RSA 密钥。
基于配对的密码学(pairing-based cryptography)利用双线性映射 e: G₁ × G₂ → G_T，其中 G₁, G₂ 是椭圆曲线群，G_T 是有限域扩域的乘法群的子群。配对满足双线性性：e(aP, bQ) = e(P, Q)^(ab)。这一性质使得三方一轮密钥协商(Joux 协议)、基于身份的加密(IBE)、属性基加密(ABE)等高级密码学原语成为可能。从代数的角度看，配对是从两个群到第三个群的群同态的自然推广。
基于格的密码学(lattice-based cryptography)是后量子密码学的主力方向。其核心代数结构是多项式环 Z_q[x]/(xⁿ + 1)，即整系数多项式模 q 和模 xⁿ + 1 形成的商环。在这个环上，学习带误差问题(Ring-LWE)和模学习带误差问题(Module-LWE)提供了安全性的计算困难性假设。环的结构赋予了这些方案高效的实现——利用数论变换(NTT)，多项式乘法可以在 O(n log n) 时间内完成——同时保持了足够的安全性。
回顾全文，我们看到一条从具体到抽象、再从抽象回到具体的路径。整数模运算引导我们建立群的概念；群的结构定理(拉格朗日定理、循环群分类)为密码学参数选择提供了理论依据；群同态为同态加密提供了代数框架；环与理想将乘法引入讨论，为 RSA 和格密码学提供了工具；域的理论——特别是有限域的存在性与唯一性——为 AES、ECC 和配对密码学奠定了基础；中国剩余定理则以一种优雅的方式将环的分解转化为计算效率的提升。
对于希望进一步深入的读者，后续文章将详细讨论有限域上的具体算术实现(包括 Montgomery 乘法、Barrett 约减、Karatsuba 乘法等)，以及椭圆曲线群上的高效点运算。这些都是将抽象代数的美丽理论转化为安全、高效的密码系统的关键工程环节。
密码学百科系列 · 第 32 篇
← 上一篇：OpenSSL/BoringSSL 架构 | 系列目录 | 下一篇：有限域算术 →