群论基础 — 从对称性到密码学的代数引擎

日期: 2026-10-29 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #数学 #群论 #抽象代数

---

今日目标

---

一、动机：为什么密码学从群论开始？

现代密码学（除了 hash 和对称加密一部分）几乎全部建立在 「在某个有限群里求解某个困难问题」 的范式上：

直觉：群是"做加法/乘法但保留结构"的最少代数对象；它给我们足够多的运算来"加密"，又足够少的运算来"难以反推"。

---

二、严格定义

2.1 群 (Group)

定义 2.1：集合 $G$ 配上二元运算 $\cdot: G \times G \to G$ 称为群，若满足四条公理：

1. 封闭性 (Closure)：$\forall a, b \in G,; a \cdot b \in G$
2. 结合律 (Associativity)：$(a \cdot b) \cdot c = a \cdot (b \cdot c)$
3. 单位元 (Identity)：$\exists e \in G,; \forall a \in G,; e \cdot a = a \cdot e = a$
4. 逆元 (Inverse)：$\forall a \in G,; \exists a^{-1} \in G,; a \cdot a^{-1} = a^{-1} \cdot a = e$

若额外满足 交换律 $a \cdot b = b \cdot a$，称为 Abelian 群 (阿贝尔群、加法群)。

2.2 例子

2.3 子群、陪集、Lagrange 定理

定义 2.2 (子群)：$H \subseteq G$ 是子群，若 $H$ 在 $G$ 的运算下也构成群。记 $H \le G$。

定义 2.3 (陪集)：$gH = {gh : h \in H}$ 称为 $H$ 的左陪集。

定理 2.4 (Lagrange 定理)：若 $G$ 有限群，$H \le G$，则 $|H| \mid |G|$（$H$ 的阶整除 $G$ 的阶）。

推论：$\forall a \in G,; \text{ord}(a) \mid |G|$，且 $a^{|G|} = e$。

2.4 元素的阶

定义 2.5：元素 $a \in G$ 的阶是最小正整数 $k$ 使得 $a^k = e$，记 $\text{ord}(a) = k$。若不存在则 $\text{ord}(a) = \infty$。

2.5 循环群与生成元

定义 2.6：$G$ 是循环群若存在 $g \in G$ 使 $G = {g^0, g^1, g^2, \dots}$。$g$ 称为 生成元 (generator)。

定理 2.7：阶为 $n$ 的循环群同构于 $(\mathbb{Z}/n\mathbb{Z}, +)$。

定理 2.8 (Fermat 小定理 → 群论形式)：若 $p$ 素数，$a \not\equiv 0 \pmod p$，则 $a^{p-1} \equiv 1 \pmod p$。这是 Lagrange 在 $(\mathbb{Z}/p\mathbb{Z})^*$ 上的特例。

定理 2.9 (Euler 定理)：$\gcd(a, n) = 1 \Rightarrow a^{\varphi(n)} \equiv 1 \pmod n$。

---

三、完整推导：证明 $(\mathbb{Z}/n\mathbb{Z})^*$ 是群

这是密码学最常用的群，必须把每条公理走一遍。

集合：$(\mathbb{Z}/n\mathbb{Z})^* = {a \in {1,\dots,n-1} : \gcd(a,n) = 1}$。

运算：$a \cdot b := ab \bmod n$。

(1) 封闭性

若 $\gcd(a,n)=\gcd(b,n)=1$，则 $\gcd(ab,n)=1$。

证明：设素数 $p \mid n$，则 $p \nmid a, p \nmid b \Rightarrow p \nmid ab$。所以 $\gcd(ab, n) = 1$，进而 $ab \bmod n \in (\mathbb{Z}/n\mathbb{Z})^*$。$\blacksquare$

(2) 结合律

继承自整数乘法的结合律。

(3) 单位元

$e = 1$，因 $1 \cdot a \equiv a \pmod n$。

(4) 逆元（关键）

断言：$\gcd(a, n) = 1 \Rightarrow \exists a^{-1} \in (\mathbb{Z}/n\mathbb{Z})^*$。

证明 (扩展欧几里得)：由 Bezout 恒等式，$\exists x, y \in \mathbb{Z}, ax + ny = 1$。模 $n$ 得 $ax \equiv 1 \pmod n$。所以 $a^{-1} = x \bmod n$。$\blacksquare$

反过来：若 $\gcd(a,n)>1$，则不存在 $x$ 使 $ax \equiv 1$（否则 $\gcd \mid 1$ 矛盾）。这就是为什么必须排除非互素元素。

推论：$|(\mathbb{Z}/n\mathbb{Z})^*| = \varphi(n)$

其中 $\varphi$ 是 Euler totient 函数。当 $n=p$ 素数时 $\varphi(p) = p-1$。

---

四、直觉与图像：为什么群论像「钟表」

把 $(\mathbb{Z}/12\mathbb{Z}, +)$ 想成钟面：

• 元素：0, 1, 2, ..., 11
• 加法：顺时针走
• 单位元：0（不动）
• 逆元：$5^{-1} = 7$（往前走 5 等于往后走 7）

循环群的几何：所有元素都在一个圈上，由生成元一步步走完。

子群：钟面上的子周期。如 ${0, 4, 8}$ 是 12 步钟的子群（每 4 步一跳）。验证：$|H|=3 \mid 12 = |G|$（Lagrange）。

密码学直觉：DLP 困难的本质是「告诉你 $g^x$，反推 $x$」——在钟面上这容易，但在 $|G| = 2^{256}$ 的群里，钟面有 $2^{256}$ 个位置，无法穷举。

---

五、代码实现

5.1 计算元素阶 + 验证 Lagrange

"""
Day 181: 群论基础 — 元素阶 / 子群 / Lagrange 定理验证
"""
from math import gcd
from functools import reduce


def euler_phi(n: int) -> int:
    """欧拉函数 φ(n) = (Z/nZ)* 的阶"""
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result


def order_of_element(a: int, n: int) -> int:
    """计算 a 在 (Z/nZ)* 中的阶"""
    if gcd(a, n) != 1:
        raise ValueError(f"{a} 不在 (Z/{n}Z)* 中")
    k = 1
    cur = a % n
    while cur != 1:
        cur = (cur * a) % n
        k += 1
    return k


def units_mod(n: int) -> list:
    """返回 (Z/nZ)* 的所有元素"""
    return [a for a in range(1, n) if gcd(a, n) == 1]


def is_generator(g: int, n: int) -> bool:
    """判断 g 是否是 (Z/nZ)* 的生成元 (原根)"""
    phi = euler_phi(n)
    return order_of_element(g, n) == phi


# ========== 演示 ==========
if __name__ == "__main__":
    # 例 1: (Z/7Z)* 是 6 阶循环群
    n = 7
    G = units_mod(n)
    print(f"(Z/{n}Z)* = {G}, |G| = {len(G)}")
    for a in G:
        ord_a = order_of_element(a, n)
        print(f"  ord({a}) = {ord_a}, 整除 {len(G)}? {len(G) % ord_a == 0}")

    # 例 2: 找 (Z/7Z)* 的所有原根
    primitive_roots = [g for g in G if is_generator(g, n)]
    print(f"原根: {primitive_roots}")

    # 例 3: Fermat 小定理验证 a^(p-1) ≡ 1 (mod p)
    p = 13
    for a in range(1, p):
        assert pow(a, p - 1, p) == 1, f"FLT 失败 a={a}"
    print(f"Fermat 小定理在 p={p} 上对所有 a 验证通过")

    # 例 4: Lagrange 定理验证 — 子群 {1, 2, 4} ⊂ (Z/7Z)*
    H = [1, 2, 4]
    # 检查封闭性
    for a in H:
        for b in H:
            assert (a * b) % n in H
    print(f"H = {H} 是 (Z/7Z)* 的子群, |H|={len(H)} | |G|={len(G)}: {len(G) % len(H) == 0}")

运行输出：

(Z/7Z)* = [1, 2, 3, 4, 5, 6], |G| = 6
  ord(1) = 1, 整除 6? True
  ord(2) = 3, 整除 6? True
  ord(3) = 6, 整除 6? True
  ord(4) = 3, 整除 6? True
  ord(5) = 6, 整除 6? True
  ord(6) = 2, 整除 6? True
原根: [3, 5]
Fermat 小定理在 p=13 上对所有 a 验证通过
H = [1, 2, 4] 是 (Z/7Z)* 的子群, |H|=3 | |G|=6: True

5.2 群同态示例

def homomorphism_demo():
    """演示群同态 φ: Z → Z/6Z, φ(x) = x mod 6"""
    # 性质: φ(a+b) = φ(a) + φ(b) mod 6
    for a in range(-10, 11):
        for b in range(-10, 11):
            assert (a + b) % 6 == ((a % 6) + (b % 6)) % 6
    print("同态 φ(a+b) = φ(a) + φ(b) 验证通过")

---

六、密码学应用关联

6.1 群论 → DLP 困难性

在循环群 $G = \langle g \rangle$ 中：

• DLP：给定 $g, h \in G$，求 $x$ 使 $g^x = h$。
• CDH：给定 $g, g^a, g^b$，求 $g^{ab}$。
• DDH：区分 $(g, g^a, g^b, g^{ab})$ 和 $(g, g^a, g^b, g^c)$。

DH 密钥交换 (1976)：

1. Alice 选 $a$，发 $A = g^a$
2. Bob 选 $b$，发 $B = g^b$
3. 共享密钥 $K = A^b = B^a = g^{ab}$
4. 攻击者看到 $g, g^a, g^b$，要算 $g^{ab}$ 即 CDH。

6.2 群的选择

• 乘法群 $(\mathbb{Z}/p\mathbb{Z})^*$：$p$ 需 ≥ 2048 bit
• 椭圆曲线群 $E(\mathbb{F}_p)$：$p \approx 256$ bit 即可达 128-bit 安全
• 配对群：支持双线性映射 $e(g_1^a, g_2^b) = e(g_1, g_2)^{ab}$

6.3 子群攻击的根源

若群 $G$ 有小阶子群 $H$，攻击者可强制密钥落入 $H$，把 DLP 难度从 $|G|$ 降到 $|H|$。所以协议常要求群的阶是大素数（无非平凡子群）。

---

七、真实参数

secp256k1 的群结构

p = 2^256 - 2^32 - 977 (大素数)
群 G = E(F_p), |G| = n (大素数)
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
   ≈ 2^256
余因子 h = 1  (这是好性质: G 没有小阶子群)

对比 Curve25519：余因子 $h=8$，所以协议必须显式 clamp 私钥的低 3 bit。

---

八、常见陷阱

1. 「逆元一定存在」是错的：在 $\mathbb{Z}/n\mathbb{Z}$ 中只有与 $n$ 互素的元素有乘法逆。新手常忘记排除。
2. 混淆群的「阶」与「元素的阶」：群阶 $|G|$ 是元素总数；元素阶 $\text{ord}(a)$ 是 $a^k = e$ 的最小 $k$。Lagrange 把二者联系起来。
3. 子群攻击 (small subgroup attack)：DH 中如果对方发的 $A$ 落在小阶子群 $H$，则共享密钥 $g^{ab} \in H$ 容易被穷举。防御：每次乘以 $h$（余因子）或验证 $A^n = e$。
4. 非素数阶群里没有原根：$(\mathbb{Z}/n\mathbb{Z})^$ 仅当 $n \in {1,2,4,p^k,2p^k}$ 时是循环群（Gauss 定理）。例如 $(\mathbb{Z}/8\mathbb{Z})^ = {1,3,5,7}$ 不是循环群。
5. 「加法群」与「乘法群」记号混乱：椭圆曲线群常用加法记 $P + Q$，但其实和 $g \cdot h$ 是同一回事。$kP$ ↔ $g^k$。

---

九、关键速查

公式表

Python 函数签名

def order_of_element(a: int, n: int) -> int  # 在 (Z/nZ)* 中 a 的阶
def euler_phi(n: int) -> int                   # Euler totient
def is_generator(g: int, n: int) -> bool       # 是否原根
def units_mod(n: int) -> list[int]             # 所有可逆元

---

十、面试题

Q1: 为什么 DH 协议必须在循环群中进行？

答：DH 安全性依赖 DLP 在群中难解。循环群 $G = \langle g \rangle$ 保证：

1. 任何元素可表示为 $g^x$（指数空间良定义）
2. 阶 $|G|$ 已知（若为素数则无小子群攻击）
3. 同构于 $(\mathbb{Z}/n\mathbb{Z}, +)$，便于参数化分析

非循环群里 $g^x = h$ 的解集结构复杂，难以做安全证明。

Q2: Lagrange 定理对 ECDSA 安全有何意义？

答：曲线点群阶 $n$ 必须是素数（或大素数 × 小余因子）。因为 Lagrange 推论 $\text{ord}(P) \mid n$，若 $n$ 复合则存在小阶子群，攻击者可把私钥模小阶得到部分信息（small subgroup attack 的根源）。secp256k1 选择 $n$ 为 256-bit 素数，余因子 $h=1$，所以无此问题。

Q3: 解释 $(\mathbb{Z}/12\mathbb{Z})^*$ 的结构。它是循环群吗？

答：$(\mathbb{Z}/12\mathbb{Z})^* = {1, 5, 7, 11}$，4 个元素。

• $\text{ord}(1) = 1$
• $\text{ord}(5) = 2$（$5^2 = 25 \equiv 1$）
• $\text{ord}(7) = 2$
• $\text{ord}(11) = 2$

没有元素阶为 4 → 不是循环群，同构于 Klein 四元群 $\mathbb{Z}/2 \times \mathbb{Z}/2$。这是 Gauss 定理的反例：$12 = 4 \cdot 3$ 不是 $p^k, 2p^k, 1, 2, 4$ 形式。

Q4: 群同态在密码学中有什么用？

答：同态 $\phi: G \to H$ 保留运算，是同态加密 (HE) 的数学基础：

• 加法同态：Paillier，$\text{Enc}(a) \cdot \text{Enc}(b) = \text{Enc}(a+b)$
• 乘法同态：RSA 原始版（不安全），$\text{Enc}(a) \cdot \text{Enc}(b) = \text{Enc}(ab)$
• 全同态 (FHE)：Gentry 2009，基于格

群同态的核 $\ker \phi$ 是 $G$ 的正规子群，$G/\ker\phi \cong \text{Im},\phi$（第一同构定理）——这是商群构造的基础，也是椭圆曲线 isogeny 加密 (CSIDH) 的工具。

Q5: 为什么椭圆曲线密码用「加法」记号而不是「乘法」？

答：纯习惯，但有几何动机。EC 群的运算来自几何（弦切线法），自然写成 $P + Q = R$。抽象上等价：$kP$ 对应 $g^k$，ECDLP 对应 DLP。某些文献也用乘法记号 $P \cdot Q$ 但少见。

---

十一、明日预告

Day 182: 有限域 — 我们今天遇到的 $(\mathbb{Z}/p\mathbb{Z})^*$ 只是冰山一角。明天进入有限域 $\mathbb{F}{p^n}$：扩域如何用不可约多项式构造、$\mathbb{F}{2^8}$ 在 AES S-box 中的应用、扩域是椭圆曲线 pairing 的工作场。

核心问题：为什么不存在 6 元有限域？

参考文献：

• Diffie & Hellman, "New Directions in Cryptography", 1976.
• Lang, Algebra, Ch. 1 (群论).
• Shoup, A Computational Introduction to Number Theory and Algebra, Ch. 6.
• Galbraith, Mathematics of Public Key Cryptography, Ch. 2.