CTF 密码学基础数学：从群、环到域的抽象代数核心概念与实战应用-平芜编程栈

文档
网络安全
教程

【免费下载链接】ctf-wiki

Come and join us, we need you!

项目地址：https://gitcode.com/gh_mirrors/ct/ctf-wiki

导读：本文聚焦 ctf-wiki 中文仓库中密码学基础数学一文的全部内容，系统梳理抽象代数中支撑现代密码学的地基概念——代数系统、群、半群、幺半群、交换群、环、域、元素的阶与同态。通过掌握这些定义与性质，你将能够理解离散对数、RSA、椭圆曲线加密（ECC）、格密码等 CTF 高频考点背后的数学原理，并能直接在本仓库对应的实战章节中展开攻防练习。

为什么 CTF 密码学要从"基础数学"开始

在密码学简介中已经指出，现代密码学始于 20 世纪中后期的大量理论成果，其核心包括对称加密、非对称加密、哈希函数与数字签名。而这些现代密码体制无一例外都建立在抽象代数（近世代数）的群、环、域结构之上：

RSA依赖整数模 $N$ 的乘法群与欧拉函数（参见 RSA 原理）；
Diffie–Hellman、ElGamal、ECC依赖群上的离散对数问题（参见离散对数与 ECC）；
格密码则使用欧式空间中的格结构（参见格基本介绍与格概述）。

因此，本部分虽然名为"基础数学知识"，却并不见得真的很基础——它是阅读后续全部密码学章节的必备前置。

代数系统与近世代数

在一个集合中，如果有一种或多种代数运算（Algebraic Operation），我们往往笼统地称它为代数系统（Algebraic System），也称代数结构（Algebraic Structure）。

作为一门不断发展的数学分支，代数学的研究范围逐渐扩大：其关注的集合从古典的整数、有理数、实数与复数等常见数集，扩展到矢量、矩阵、线性算子等对象，并着眼于定义在它们之上的代数运算。这些课题共同组成了如今的近世代数（Modern Algebra）学科，或称抽象代数（Abstract Algebra）。

上文提到的代数运算，是定义在集合中元素之间的法则，与集合能否"作成"代数系统有着密切关联，它们扩展自常见的加、减、乘、除这样的运算。经过定义合适的代数运算，集合可以作成群、环、域、格等代数系统，这也是接下来要介绍的核心内容。

群（Group）：现代密码学最核心的代数结构

给定一个集合 $G\neq\varnothing$ 以及其上的二元代数运算「 $\circ$ 」，如果它们满足如下四条性质：

封闭性（Closure）：$\forall v, u \in G, \quad v \circ u \in G;$
结合律（Associativity）：$\forall v, u, w \in G, \quad (v \circ u) \circ w = v \circ (u \circ w);$
单位元（Identity）：$\exists e \in G, \forall v \in G, \quad e \circ v = v;$
逆元（Inverse，亦称反元）：$\forall v \in G, \exists v^{-1} \in G, \quad v^{-1} \circ v = e;$

则称集合 $G$ 对该代数运算作成一个群（Group），记作 $(G,\circ)$。

群的标准例子

整数加法群$(\mathbb{Z},+)$ 是最常见的例子：不难验证它满足加法封闭性与结合律，存在整数 $0$ 作为单位元，并且对于每个整数 $m$ 都有相反数 $-m$ 作为其逆元。

类似地可以验证：

正有理数集 $(\mathbb{Q}_+,\times)$ 对乘法作成群（单位元为 $1$，对于每个元素 $a$ 其逆元为 $\frac{1}{a}$）；
实数域 $\mathbb{R}$ 上的全体 $m$ 阶可逆矩阵对矩阵乘法作成群（单位元为 $m$ 阶单位矩阵 $E_m$，对于每个元素 $A$ 其逆元为逆矩阵 $A^{-1}$），这在近世代数中被称为 $m$ 阶一般线性群$GL_m(\mathbb{R})$；
更简单的例子是定义在集合 ${-1,1}$ 上的乘法群 $({-1,1},\times)$。

在近世代数中，研究群的分支被称为群论（Group Theory）。值得注意的是，密码学中使用最多的并非普通整数群，而是有限循环群：例如离散对数中定义的"生成元 $g$ 使得群 $G$ 中每一个元素都可以写成 $y=g^k$"，这里的 $k$ 就是 $y$ 在群 $G$ 中的对数——这正是群论概念在密码学中的直接落地。

半群和幺半群

有些代数系统只具有环的部分性质，虽不在主要讨论范围内，但也具有广泛的应用场景与不可忽视的研究价值：

对于其上二元代数运算封闭的非空集合：

如果仅满足结合律，那么该集合对该代数运算作成半群（Semigroup）；
如果除封闭性、结合律外还具有单位元，则该集合对该运算作成幺半群（Monoid）。

由此可以认为：

幺半群是含有单位元的半群；
群是每个元素皆有逆元的幺半群。

举例来说，正整数对整数加法作成半群（无单位元 0 不在集合内）；而非负整数对整数加法作成幺半群，因为 0 可以视为整数加法的单位元。

交换群（阿贝尔群）

给定一个群 $(G,\circ)$，如果它满足交换律（Commutativity），即 $\forall v, u \in G,\ v \circ u = u \circ v,$ 则称这个群是交换群或 Abel（阿贝尔）群（Abelian Group）。

显然，上文提到的整数加法群 $(\mathbb{Z},+)$ 是交换群，但 $m$ 阶一般线性群 $GL_m(\mathbb{R})$ 不是交换群（矩阵乘法不满足交换律）。

这一概念在 ECC 中有着直接应用：椭圆曲线上的点集 $E(F_p)$ 连同点的运算 $\oplus$ 形成一个 Abel 群（交换群），即满足封闭性、逆元存在、交换律等性质，这正是椭圆曲线密码能够成立的代数前提。

环和域：承载 RSA 等公钥体制的代数结构

给定一个集合 $R\neq\varnothing$ 以及其上的两个二元代数运算「 $+$ 」和「 $\circ$ 」，如果它们满足如下性质：

$(R,+)$ 作成交换群；
$R$ 对运算「 $\circ$ 」满足结合律：$\forall v, u, w \in R,$ 皆有 $(v \circ w) \circ u = v \circ (w \circ u);$
分配律（Distributivity）：$\forall v, u, w \in R,$ 皆有 $w \circ (v + u) = w \circ v + w \circ u$ 与 $(v + u) \circ w = v \circ w + u \circ w$ 成立；

则称集合 $R$ 对此二代数运算作成一个环（Ring），记作 $(R,+,\circ)$，并常分别称运算「 $+$ 」和「 $\circ$ 」为加法和乘法。

环的四种特殊形态

如果环 $R$ 上的乘法存在单位元 $e$，即 $\exists e \in G, \forall v \in G,$ 皆有 $e \circ v = v,$ 则称环 $R$ 为幺环（Ring with identity）；
如果环 $R$ 上的乘法满足交换律，则称其为交换环（Commutative Ring）；
如果环 $R$ 中对除加法单位元外任意元素 $a \neq 0$ 皆存在乘法逆元 $a^{-1}$，则称 $R$ 为除环（Division Ring）；
如果环 $R$ 既是交换环又是除环，那么环 $R$ 是一个域（Field）。

在部分书籍中，默认环含有乘法单位元，并称不含有乘法单位元的环为伪环（Pseudo Ring）。在部分繁体中文语境下，域和域论常被称为体和体论（繁体中文分别写作「體」和「體論」）。

在近世代数中，研究环和域的分支分别被称为环论（Ring Theory）和域论（Field Theory）。

域的实战意义：RSA 的整个运算都发生在模 $p$ 或模 $pq$ 的整数环中。比如 RSA 原理中公钥 $(N,e)$ 与私钥 $(N,d)$ 的关系 $ed\equiv 1 \pmod{\varphi(N)}$，正是基于整数模 $N$ 乘法群中求逆元的运算；而 ECC 中所用的有限域 $GF(p)$（以素数为模的整数域）和特征为 2 的伽罗华域 $GF(2^m)$ 则是"域"概念在椭圆曲线上的直接实例。掌握环与域的公理化定义，是理解这些体制安全性的前提。

元素的阶与指数

指数：仿照数的指数，我们定义群中元素的指数，对于 $v \in G, m$ 为正整数：

$v^0 = e;$
$v^m = v \circ v \circ \cdots \circ v,$ 其中共有 $m$ 个 $v$ 参与代数运算；
$v^{-m} = \left(v^{-1}\right)^m;$

元素的阶：对于任意给定的元素 $v \in G,$ 如果正整数 $m$ 满足 $v^m = e,$ 则称元素 $v$ 的阶数为 $m$；如果这样的正整数不存在，则称该元素的阶为无限。

例如，在群 $\left({1,-1,+\mathrm{j},-\mathrm{j}},\times\right)$ 中，各元素的阶如下：

元素	阶
1	1
-1	2
$+\mathrm{j}$	4
$-\mathrm{j}$	4

阶在 CTF 密码题中的应用：离散对数问题（DLP）的难度与群中元素的阶密切相关。离散对数中定义"使得 $a^d \equiv 1 \pmod m$ 成立的最小正整数 $d$ 称为 $a$ 对模 $m$ 的指数或阶，记为 $\delta_m(a)$"，并指出当 $\delta_m(a)=\varphi(m)$ 时 $a$ 是模 $m$ 的原根。当群的阶是光滑数（即可以分解为许多小素数幂的乘积）时，可以使用 Pohlig-Hellman 算法将大离散对数问题化整为零求解——这正是"阶"这一概念决定攻击可行性的经典案例。相应地，在 ECC 中，生成元 $G$ 的阶被定义为满足 $nG=O$ 的最小正整数 $n$，它直接刻画了椭圆曲线群的大小与安全强度。

同态：代数系统之间保持运算的映射

代数系统间的同态（Homomorphism）指在不同代数系统之间能够保持代数运算的映射。

具体来讲，对于群 $(G,\circ)$ 和 $(H,\ast)$ 而言，如果映射 $\psi: G \to H$ 满足 $\forall v, u \in G,$

$$ \psi(v \circ u) = \psi(v) \ast \psi(u), $$

那么映射 $\psi$ 便可以称为从 $G$ 到 $H$ 的一个群同态。

同态的意义在于：它揭示了两个看似不同的代数系统在运算结构上的一致性。在密码学中，许多攻击与构造实际上就是在寻找合适的同态映射——例如 Pohlig-Hellman 算法正是把原群中的离散对数问题同态地"投影"到若干小阶子群上分别求解，再通过中国剩余定理（CRT）组合回原解（参见离散对数的求解方式小节）。

抽象代数知识在仓库中的实战串联

上文的所有概念都可以在本仓库的密码学章节中找到对应的实战出口：

群与阶→ 离散对数：生成元、原根、群的阶与光滑数，以及 BSGS、Pollard's rho、Pollard's kangaroo、Pohlig-Hellman 等求解算法；
交换群与有限域→ ECC：椭圆曲线点集作成 Abel 群，密钥生成、加密、解密全流程与 SECCON CTF 实战例题；
环与欧拉函数→ RSA 原理：公钥/私钥生成、加解密公式、正确性证明（含 $m^{k\phi(N)+1}\equiv m \bmod N$ 的两种情形），以及 veryeasyRSA、CodeGate、国家安全周、Pwnhub 等实战题目；
格→ 格基本介绍与格概述：格是 $R^m$ 中 $n$ 个线性无关向量所有整数线性组合构成的群结构，SVP、CVP 等困难问题支撑了后量子密码方向。

建议按"先本文（代数结构）→ 再离散对数 → 再 RSA / ECC → 最后格"的顺序阅读，即可建立从抽象代数到现代密码攻防的完整知识链路。