DH密钥交换算法的数学原理与离散对数问题

---

前言

我们都知道在IPsec的技术架构中，IKE（Internet Key Exchange，互联网密钥交换）协议采用DH（Diffie-Hellman）交换技术实现在不安全的网络中安全地传输密钥，并且DH作为IKE最为精髓的安全机制，可以实现在任何时候通讯双方都不需要交换真正的密钥地情况下保证双方密钥的绝对一致，这不得不让人由衷地感叹密码学和数学的魅力。

在意识到DH算法的精妙后，博主决定在此驻足半月，深挖一下DH算法中包含的数学原理，并尝试去理解离散对数问题的本质所在。个人认为，只有明白了DH算法的底层原理，才能对IKE协议和ISAKMP协议框架有更深入的理解。

同时，对密码学的研究也可以让我在愈发枯燥的数通学习进程中起到换换口味，转换心情的作用。

本篇博客主要会涉及到两部分的数学内容：初等数论和抽象代数。其中数论知识可以帮助我们理解DH密钥交换算法中密钥生成的原理，而代数知识可以帮助我们理解离散对数问题，也就是DH算法安全性的来源。文中只会提到对于理解DH算法和离散对数问题所必需具备的数学知识，因为都是纯自学，其中不乏有错误或理解不到位之处，感谢各位大佬在评论区指出。

本篇博客较为硬核，涉及到的数学概念较多，且很多概念之间会互相牵扯，阅读起来可能需要花费些许耐心。

不过本篇博客也可以说是博主的一篇学习笔记，所以包含了很多踩坑和避雷的内容，各节顺序也是由博主按照自己学习时候的理解顺序编排过的，由易到难，不仅能保证自己回顾的时候有清晰的思路，也可以使得读者从上到下按照顺序阅读能起到最好的理解效果。

---

初等数论

要理解DH算法的底层原理，我们首先要了解一些初等数论中的基本概念。而在数论部分如果大家有地方看不懂的话先不用着急，很多概念我们需要结合文章后半段”群论“的知识才能真正参透其中的含义。

数论

数论

数论（number theory），是纯粹数学的分支之一，主要研究整数的性质。整数可以是方程式的解（丢番图方程）。有些解析函数（像黎曼$\zeta$函数）中包括了一些整数、素数的性质，透过这些函数也可以了解一些数论的问题。透过数论也可以建立实数和有理数之间的关系，并且用有理数来逼近实数（丢番图逼近）。

按研究方法来看，数论大致可分为初等数论和高等数论。初等数论是用初等方法研究的数论，它的研究方法本质上说，就是利用整数环的整除性质，主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、计算数论等等。

根据我的理解，数论是数学的一个分支，这个分支主要研究的是整数及其性质。而素数（又名质数）是数论的重要研究目标之一。

数论主要研究的是素数的分布、性质和筛法等，其中有很多与素数有关的理论，例如素数定理、黎曼猜想等。而由于素数在密码学中的广泛应用，使得数论中这些与素数有关的理论可以在我们对密码学的理解过程中可以起到很大的作用。

模运算

一旦涉及到素数的问题，那么模（$\bmod$）运算就是研究素数必须掌握的技能之一。同时，模运算也是密码学中最核心的运算，没有之一。

在传统的四则运算之外，还有一种针对整数的算术系统称为“模运算”。其实在本篇博客中，为了方便理解，我们可以粗俗地把模运算理解为取余（虽然模运算除了求余数外还有很多其他的用处）。

设$a,b \in Z$且$b > 0$，如果$q,r \in Z$满足$a = qb + r$，且$0 \leqslant r < b$，则有$r \coloneqq a \bmod b$。

根据博主查阅的资料来看，这里的符号“$\coloneqq$”是在数学定理或数学书籍中常用的书面符号，意为“定义为”。

举个例子，$p \left(p\in N^+\right)$和$a \left(a\in Z\right)$的运算$a \bmod p$即表示$a$除以$p$的余数。

需要注意的是，模运算通常被应用于程序的编写中。而在绝大多数编程语言里，取余通常会使用%符号，所以在网络上很多博客中，$a \bmod p$被写作$a \% p$。

这里博主需要说一个在网上目前没看到过有人提到，但是却极其重要的点。

在传统的四则运算写法中，符号$/$意味着除以，也就是说我们如果看到表达式$a/b$，一般表示的含义是$\frac ab$。

但是如果我们在模运算的相关文章中看到$a/b$，通常表达的意义为$\left[\frac ab\right]$，也就是商取整。这是因为在模运算中大家通常只讨论整数，所以大家通常会默认表达式$p = a/b$中$p$的值为$\left[\frac ab\right]$。

而且在编程语言中如果出现a/b，在a、b均为整数的情况下，生成的值也必定为$\left[\frac ab\right]$，所以很容易给单纯研究数学，但对编程语言不熟悉的读者带来困扰。这是很多文章作者容易忽略的地方。

运算规则

模运算与基本四则运算有些相似，其规则如下：

• $\left( a + b \right) \bmod p = \left( a \bmod p + b \bmod p \right) \bmod p$
• $\left( a - b \right) \bmod p = \left( a \bmod p - b \bmod p \right) \bmod p$
• $\left( a \times b \right) \bmod p = \left( a \bmod p \times b \bmod p \right) \bmod p$
• $a^b \bmod p = \left( \left( a \bmod p \right)^b \right) \bmod p$

注意这里并没有除法的模运算，因为除法取模的运算方法较为特殊，涉及到费马小定理，这里暂不讨论。

费马小定理

如果$p$是一个素数，而$a \left( a \in Z \right)$不是$p$的倍数，则有$a^{\left(p - 1\right)} ≡ 1 \pmod p$。

结合律

• $\left(\left(a + b\right) \bmod p + c\right) \bmod p = \left(a + \left(b + c\right) \bmod p \right) \bmod p$
• $\left(\left(a \times b\right) \bmod p \times c\right) \bmod p = \left(a \times \left(b \times c\right) \bmod p \right) \bmod p$

交换律

• $\left(a + b\right) \bmod p = \left(b + a\right) \bmod p$
• $\left(a \times b\right) \bmod p = \left(b \times a\right) \bmod p$

分配律

• $\left(a + b\right) \bmod p = \left(a \bmod p + b \bmod p\right) \bmod p$
• $\left(\left(a + b\right) \bmod p \times c\right) \bmod p = \left(\left(a \times c\right)\bmod p + \left(b \times c\right)\bmod p\right) \bmod p$

同余关系

同余是数论的基本概念之一。

同余，顾名思义就是余数相同。模运算引入同余关系的概念，主要是为了方便大家利用这种关系进行相关的运算（包括对模运算的运算法则的推导），相应地我们也需要使用同余式来将这种关系具象化。

若两个数$a \left(a\in N^+\right)$和$b \left(b\in N^+\right)$的差值$a - b$为$n \left(n\in Z\right)$的整数倍，则我们可以说$a$和$b$在模$n$下满足同余关系，简称同余。

数学表达式为$a \equiv b \pmod n$，又称同余式。

根据同余式的定义我们可以知道：

$$a \equiv b \pmod n \Longleftrightarrow \exists q \in Z, a = qn + b$$

如果$a \equiv b \pmod n$且$c\in N^+$，则我们可以得到以下的运算定律：

• $\left(a + c\right) \equiv \left(b + c\right) \pmod n$
• $\left(a - c\right) \equiv \left(b - c\right) \pmod n$
• $\left(a \times c\right) \equiv \left(b \times c\right) \pmod n$
• $a^c \equiv b^c \pmod n$

如果再加上$p \equiv q \pmod n$，则：

• $\left(a + p\right) \equiv \left(b + q\right) \pmod n$
• $\left(a \times p\right) \equiv \left(b \times q\right) \pmod n$

由此可见，同余式的运算规则也涵盖了除除法以外的任何四则运算。

在数论中，符号”$\equiv$“名为“同余符号“，读作“同余相等”，并非数学中传统意义上的”恒等于“。

我们也可以简单将其理解为：

$$a \equiv b \pmod n \Longleftrightarrow a \bmod n = b \bmod n$$

互素

互素（Coprime）又称互质，符号为$\perp$，也是初等数论的重要概念之一。

在数论中，如果两个或两个以上的整数的最大公约数是$1$，则称它们互素。

$a\left(a \in Z\right)$和$b\left(b \in Z\right)$互素记为$a \perp b$，或$\gcd \left(a,b\right) = 1$。

由此我们可以得出互素的两个重要例子：

• 如果数域是正整数$N^+$，那么$1$与所有正整数互素。
• 如果数域是整数$Z$，那么$1$和$-1$与所有整数互素，而且它们是仅有与$0$互素的整数。

其中互素还分为整集互素与两两互素，也是十分重要的概念，不过本篇博客就暂不讨论了。

这里提一个小插曲。

博主在研究互素的时候惊讶地发现，互素使用的符号$\perp$，和我们在义务教育阶段学习几何时及其熟悉的垂直符号“$\perp$”一模一样，并且随着我的深入研究，我发现“互素”和“垂直”地符号相同并不是巧合或符号复用，它们表达的竟是相同的意义！

这个观点是由知乎用户jyc在文章“玩数系列——所谓“⊥””中提出的，大家感兴趣的话可以去观看原文，这里博主根据自己的理解简要解释下这个观点。

我们应该还记得，向量中经常会用到一种运算叫点积，比如对于向量$a$和向量$b$，如果$a \perp b$，那么意味着$a \cdot b = 0$。

也就是说，对于空间向量$a = \left(x_1,y_1,z_1\right)$和$b = \left(x_2,y_2,z_2\right)$，我们有：

$$a \perp b \Longleftrightarrow a \cdot b = 0 \Longleftrightarrow x_1x_2 + y_1y_2 + z_1z_2 = 0$$

假如我们括大维度，定义向量$a = \left(x_1,x_2,x_3,\cdots,x_n\right)$和向量$b = \left(y_1,y_2,y_3,\cdots,y_n\right)$，我们同样可得：

$$a \perp b \Longleftrightarrow a \cdot b = 0 \Longleftrightarrow x_1y_2 + x_2y_2 + x_3y_3 + \cdots + x_ny_n= 0$$

这样，我们利用“向量”这种工具，向大家展示了“$\perp$”在几何中的实际意义，接下来我们再看看在素数中，互素意味着什么。

如果我们把整个素数的序列与坐标相对应，例如用$p_1,p_2,p_3,\cdots,p_n$表示，那么根据素数的定义，其中$p_1 = 2,p_2 = 3,p_3 = 5,\cdots$并可以此类推，我们可以把任何一个正整数分解成另一个形式。

定义任意一个正整数$O$，我们都可以对其分解表示为

$$O = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \cdots \times p_n^{a_n}$$

其中$a_1,a_2,a_3,\cdots,a_n$为任意自然数。

如果我们把$a_1,a_2,a_3,\cdots,a_n$提取出来，表示成向量的形式，坐标轴上是素数序列，那么我们可以得到：

$$\begin{aligned} 1 &= 2^0 \times 3^0 \times 5^0 \times 7^0 \times \cdots = \left(0,0,0,0,\cdots,0\right) \\ 2 &= 2^1 \times 3^0 \times 5^0 \times 7^0 \times \cdots = \left(1,0,0,0,\cdots,0\right) \\ 3 &= 2^0 \times 3^1 \times 5^0 \times 7^0 \times \cdots = \left(0,1,0,0,\cdots,0\right) \\ 4 &= 2^2 \times 3^0 \times 5^0 \times 7^0 \times \cdots = \left(2,0,0,0,\cdots,0\right) \\ \vdots \\ 35 &= 2^0 \times 3^0 \times 5^1 \times 7^1 \times \cdots = \left(0,0,1,1,\cdots,0\right) \\ \vdots \end{aligned}$$

这时我们就可以惊讶地发现，假如两个正整数$p_1$和$p_2$互素，例如$p_1 = 4$且$p_2 = 53$，那么此时：

$$\begin{aligned} p_1 &= \left(2,0,0,0,\cdots,0\right) \\ p_2 &= \left(0,0,1,1,\cdots,0\right) \end{aligned}$$

$$\begin{aligned} p_1 \cdot p_2 &= \left(2,0,0,0,\cdots,0\right) \cdot \left(0,0,1,1,\cdots,0\right)\\ &= 2 \times 0 + 0 \times 0 + 0 \times 1 + 0 \times 1 +\cdots+ 0 \times 0 \\ &= 0 \end{aligned}$$

同样可以得出结论$p_1 \cdot p_2 = 0$，记为$p_1 \perp p_2$，意为$p_1$和$p_2$互素。

在这种情况下，符号“$\perp$”，代表的并不是几何中的位置垂直，也不是线性代数中的向量垂直，而是真正意义上的“自然数”的垂直。

不过博主并没有能力严谨地证明出这个观点，也不知道这个是不是某个定理或者可以使用什么公式证明，希望懂数论的大佬们可以在评论区指点一二。

欧拉定理

欧拉定理在不同的数学分支中有不同的定义，这里只讨论数论中的欧拉定理。

在数论中，欧拉定理（Euler Theorem，也称费马-欧拉定理或欧拉$\varphi$函数定理）是一个关于同余的性质。

若$a,n\in N^+$，且满足$\gcd \left(a,n\right) = 1$，则$a^{\varphi\left(n\right)} \equiv 1\pmod n$。

即$a^{\varphi\left(n\right)}$与$1$在模$n$下同余，其中$\varphi\left(n\right)$为欧拉函数。

欧拉函数

欧拉函数以其首名研究者欧拉命名，它又称为$\varphi$函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

在数论中，对于$n \left(n\in N^+\right)$，欧拉函数$\varphi\left(n\right)$表示的是小于等于$n$的正整数中与$n$互素的数的数目。

例如$\varphi\left(8\right) = 4$，因为有$1$、$3$、$5$、$7$这四个数与$8$互素。

欧拉函数的重要结论（也就是费马小定理）：

若$p$为素数，则$\varphi\left(p\right) = p - 1$，此时$a^{p - 1} \equiv 1\pmod p$，称为费马小定理。

需要说明的是，因为欧拉函数的性质和证明涉及到很多其他数论概念和一些抽象代数概念，这些内容会在后文介绍，这里先按下不表，我们只需要暂时记住欧拉函数的概念以及结论即可。

欧拉函数与费马小定理

1736年，欧拉证明了费马小定理：

若$p$为素数，$a$为任意正整数，那么$a^p - a$可被$p$整除。

然后欧拉把费马小定理予以一般化：

若$a$与$n$互素，那么$a^{\varphi\left(n\right)} - 1$可被$n$整除。亦即，$a^{\varphi\left(n\right)} \equiv 1\pmod n$。

其中$\varphi\left(n\right)$即为欧拉总计函数。如果$n$为素数，那么$\varphi\left(n\right) = n - 1$，因此就有了高斯的版本：

若$p$为素数，$a$与$p$互素（$a$不是$p$的倍数），那么$a^{p - 1} \equiv 1\pmod p$。

原根

DH算法原理运用到的数论概念中除了模运算和欧拉定理，还有一个概念叫做原根，到此我们终于接触到了DH算法的核心概念。

原根是DH算法的核心，也是我们要理解离散对数问题必须掌握的基础概念，如果前面我们已经理解了欧拉定理的相关概念，那么原根的概念理解起来就不算困难了。

博主认为，数论中的原根是一个相对复杂的概念，仅从数论的角度可能无法完全理解原根的概念。本节的内容也可能有些“佶屈聱牙”，如果大家理解不了的话只需暂时记住结论就好，文章后半段对于原根的概念还会有更好的阐述。

在数论，特别是整除理论中，原根是一个及其重要的概念，并广泛应用于解决数论问题的算法中。

对于数$a \left(a\in N^+\right)$和数$m \left(m\in N^+\right)$，若$\gcd \left(a,m\right) = 1$，由欧拉定理可知，一定存在$d \left(d\in N^+\right)$在满足$d \leqslant m - 1$时，使得$a^d \equiv 1\pmod m$。

$d$用上面介绍的欧拉函数来表示的话就是$d = \varphi\left(m\right)$，即小于等于$m$的正整数中与$m$互素的正整数个数。

这里博主先贴出原根的标准定义：

在$\gcd \left(a,m\right) = 1$时，定义$a$对模$m$的指数$\delta_m\left(a\right)$为使$a^d \equiv 1\pmod m$成立的最小的正整数$d$，此时

$$\delta_m\left(a\right) \leqslant \varphi\left(m\right)$$

当$\delta_m\left(a\right) = \varphi\left(m\right)$时，则称$a$是模$m$的原根。

为方便起见，原根一般统一使用字母$g$表示。

原根的定义乍一听起来似乎很拗口，但仔细分析一下就会发现不难理解。

通俗地说，如果两个正整数$a$和$m$互素，如果使得$a^d \bmod m = 1$成立的正整数$d$的最小值为$\varphi\left(m\right)$，即可以说$a$是模$m$的原根。

举个例子，我们设$m = 7$，因为$7$是素数，则根据欧拉函数可得：

$$\begin{aligned} \varphi\left(m\right) &= m - 1 \\ &= 7 - 1 \\ &= 6 \end{aligned}$$

也就是说，如果$a$是7的原根，那么$a$需要满足以下几个条件：

1. $a$必须是正整数，即$a\in N^+$。
2. $a$和$7$互素，即$\gcd \left(a,7\right) = 1$。
3. 当正整数$d$满足$a^d \bmod 7 = 1$时，正整数$d$的最小值必须为$6$，不能更小。

假如$a = 2$，依次取$d$值为$1$、$2$、$3$、$4$、$5$、$6$，则有：

$$\begin{aligned} 2^1 \bmod 7 = 2 \\ 2^2 \bmod 7 = 4 \\ 2^3 \bmod 7 = 1 \\ 2^4 \bmod 7 = 2 \\ 2^5 \bmod 7 = 4 \\ 2^6 \bmod 7 = 1 \end{aligned}$$

用同余式表示为：

$$\begin{aligned} 2^1 \equiv 2 \pmod 7 \\ 2^2 \equiv 4 \pmod 7 \\ 2^3 \equiv 1 \pmod 7 \\ 2^4 \equiv 2 \pmod 7 \\ 2^5 \equiv 4 \pmod 7 \\ 2^6 \equiv 1 \pmod 7 \end{aligned}$$

由此可见$d$的最小值为$3$不为$6$，所以$a = 2$的情况下$\delta_m\left(a\right) \not= \varphi\left(m\right)$，即$2$不是$7$的原根。

假如$a = 3$，同样取$d$值为$1$、$2$、$3$、$4$、$5$、$6$，则有：

$$\begin{aligned} 3^1 \bmod 7 = 3 \\ 3^2 \bmod 7 = 2 \\ 3^3 \bmod 7 = 6 \\ 3^4 \bmod 7 = 4 \\ 3^5 \bmod 7 = 5 \\ 3^6 \bmod 7 = 1 \end{aligned}$$

用同余式表示为：

$$\begin{aligned} 3^1 \equiv 3 \pmod 7 \\ 3^2 \equiv 2 \pmod 7 \\ 3^3 \equiv 6 \pmod 7 \\ 3^4 \equiv 4 \pmod 7 \\ 3^5 \equiv 5 \pmod 7 \\ 3^6 \equiv 1 \pmod 7 \end{aligned}$$

由此可见$d$的最小值为$6$，所以$a = 3$的情况下$\delta_m\left(a\right) = \varphi\left(m\right)$，即$3$是$7$的原根。

为什么$2^d \bmod 7$的结果在$1 \leqslant d \leqslant 6$下可以恰好等于$1$至$6$间的所有整数呢？这个现象可以扩展到任意素数和它的原根吗？

博主刚学到这里的时候觉得特别不可思议于是提出了这个疑问。为了搞懂这个问题的底层逻辑，博主又花了大把时间去研究了一些抽象代数的相关知识和重要理论，最终弄懂了这个问题，同时对于数论中的一些概念也有了更深的理解。

在“公钥密码学的数学核心”章节的最后一小节，博主会根据自己的理解去尝试回答下这个问题。

---

DH密钥交换算法

掌握了一些初等数论的基础知识后，我们就能看懂DH密钥交换算法中的密钥生成原理了。

迪菲-赫尔曼密钥交换（Diffie–Hellman key exchange，缩写为D-H） 是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。公钥交换的概念最早由瑞夫·墨克（Ralph C. Merkle）提出，而这个密钥交换方法，由惠特菲尔德·迪菲（Bailey Whitfield Diffie）和马丁·赫尔曼（Martin Edward Hellman）在1976年首次发表。马丁·赫尔曼曾主张这个密钥交换方法，应被称为迪菲-赫尔曼-墨克密钥交换（Diffie–Hellman–Merkle key exchange）。

迪菲－赫尔曼密钥交换的同义词包括:

• 迪菲－赫尔曼密钥协商
• 迪菲－赫尔曼密钥建立
• 指数密钥交换
• 迪菲－赫尔曼协议

虽然迪菲－赫尔曼密钥交换本身是一个匿名（无认证）的密钥交换协议，它却是很多认证协议的基础。

在网络上或者相关论文中我们总是会看到一张类似的图解，不过这里博主不会详细解释DH算法的具体定义与深层原理，这些原理必须要结合群论的相关知识才能理解充分。

这一节博主只用模运算的知识，总结下DH算法中密钥到底是如何生成的，以及为什么通讯两端明明各选了随机数进行模运算，运算结果会惊人地相等。

我们都知道，DH算法的过程就是一个通讯两端协商出相同密钥的过程，这里先说一下具体的协商流程。

密钥协商流程

这里还是用密码学中最为经典的主角——爱丽丝（Alice）和鲍伯（Bob）举例，其实密钥协商的流程很简单，博主总结下来一共就五步：

1. 爱丽丝和鲍伯相互协商两个数：素数$p$和它的原根$g$。
2. 爱丽丝选择一个秘密的整数$a$，计算$A = g^a \bmod p$并发送给鲍伯。
3. 鲍伯选择一个秘密的整数$b$，计算$B = g^b \bmod p$并发送给爱丽丝。
4. 爱丽丝根据自己的$a$和鲍伯的$B$，计算出密钥$s_1 = B^a \bmod p = {\left(g^b \bmod p\right)}^a \bmod p$。
5. 鲍伯根据自己的$b$和爱丽丝的$A$，计算出密钥$s_2 = A^b \bmod p = {\left(g^a \bmod p\right)}^b \bmod p$。

而这里的$s_1$和$s_2$其实是相等的，也即：

$${\left(g^a \bmod p\right)}^b \bmod p = {\left(g^b \bmod p\right)}^a \bmod p$$

所以爱丽丝（Alice）和鲍伯（Bob）通过此轮交换获得了相同的密钥，而泄露出去的数也仅有$p$、$g$、$A$、$B$这四个数。而因为离散对数问题存在，中间人即便截取到了这几个数也无法倒推出$a$和$b$的值，进而也无法知晓$s$的值（也就是真正的密钥值）。

离散对数问题

如果$p$是一个至少300位的素数，并且$a$和$b$至少有100位长，那么即使使用全人类所有的计算资源和当今最好的算法也不可能从$g$、$p$、$g^a \bmod p$中计算出$a$的值。这个问题就是著名的离散对数问题。

这样，通讯双方就以一种相对安全的方式，实现了在公共信道上交换一个私密的信息。

博主使用具体的数字举个例子，从原根开始。

首先通讯双方（R1和R2）协商两个数：素数$p = 11$和$g = 8$，稍微计算一下可得：

$$\begin{aligned} 8^1 \bmod 11 &= 8 \\ 8^2 \bmod 11 &= 9 \\ 8^3 \bmod 11 &= 6 \\ 8^4 \bmod 11 &= 4 \\ 8^5 \bmod 11 &= 10 \\ 8^6 \bmod 11 &= 3 \\ 8^7 \bmod 11 &= 2 \\ 8^8 \bmod 11 &= 5 \\ 8^9 \bmod 11 &= 7 \\ 8^{10} \bmod 11 &= 1 \end{aligned}$$

所以根据上文中原根在数论中的定义可知，$g = 8$满足以下三个条件：

1. $g = 8$是正整数。
2. $g = 8$和$p = 11$互素。（这条其实不用证明和计算，因为$p$为素数）
3. $g = 8$满足$8^d \bmod 11 = 1$时，正整数$d$的最小值为$\varphi\left(11\right) = 10$。

所以$g$为素数$p$的一个原根。

随后通讯端R1内部生成一个随机数$a = 28$，计算$A = g^a \bmod p$的值并发送给通讯端R2。

$$\begin{aligned} A &= g^a \bmod p \\ &= 8^{28} \bmod 11 \\ &= 5 \end{aligned}$$

同样的，通讯端R2内部也生成一个随机数$b = 17$，计算$B = g^b \bmod p$的值并发送给通讯端R1。

$$\begin{aligned} B &= g^b \bmod p \\ &= 8^{17} \bmod 11 \\ &= 2 \end{aligned}$$

通讯端R1收到$B = 2$后，与$a$做运算后得出密钥$s$的值：

$$\begin{aligned} s&= B^a \bmod p \\ &= 2^{28} \bmod 11 \\ &= 3 \end{aligned}$$

通讯端R2收到$A = 5$后，与$b$做运算后得出密钥$s$的值：

$$\begin{aligned} s&= A^b \bmod p \\ &= 5^{17} \bmod 11 \\ &= 3 \end{aligned}$$

至此，双方生成了相同的密钥（值为$3$），完成了密钥的交换。

而关于离散对数问题，我们还需要一些群论相关的数学概念才能一窥它的原理，这里先暂且按下不表。

数学证明

在密钥协商流程中，我们提到了一个结论：

$${\left(g^a \bmod p\right)}^b \bmod p = {\left(g^b \bmod p\right)}^a \bmod p$$

这个结论本身是很好证明的，博主在前面讲模运算时候提到了模运算的运算规则之一：

$$a^b \bmod p = \left( \left( a \bmod p \right)^b \right) \bmod p$$

于是利用这个运算规则我们就可以得到：

$$\begin{aligned} {\left(g^a \bmod p\right)}^b \bmod p &= {\left(g^a\right)}^b \bmod p \\ &= g^{ab} \bmod p \\ &= {\left(g^b\right)}^a \bmod p \\ &= {\left(g^b \bmod p\right)}^a \bmod p \end{aligned}$$

而在研究过程中，博主在网络上看到有很多针对模运算规则的证明，并从中获得了些许灵感，决定也尝试使用传统的加减乘除四则运算来代替模运算，并且证明成功了。

这里简单提一下博主的证明过程，说不定大家还会有新的思路。

我们设$r = g^a \bmod p$，这里根据模运算和原根的定义可得：

$$\exists q,r \in N,g^a = qp + r$$

用传统除法的定义就是：$g^a$是被除数，$p$是除数，$q$是商，$r$是余数。

将$r = g^a \bmod p = g^a - qp$带入到${\left(g^a \bmod p\right)}^b \bmod p$中即可得到：

$$\begin{aligned} {\left(g^a \bmod p\right)}^b \bmod p &= r^b \bmod p \\ &= \left(g^a - qp\right)^b \bmod p \\ &= \left(\sum_{i=0}^b C_b^i\left(g^a\right)^{b - i}\left(-qp\right)^i\right) \bmod p \\ &= \left(C_b^0\left(g^a\right)^b\left(-qp\right)^0 + C_b^1\left(g^a\right)^{b-1}\left(-qp\right)^1 + C_b^2\left(g^a\right)^{b-2}\left(-qp\right)^2 + \cdots + C_b^b\left(g^a\right)^0\left(-qp\right)^b\right) \bmod p \\ &= \left(\left(C_b^0\left(g^a\right)^b\left(-qp\right)^0\right) \bmod p + \left(C_b^1\left(g^a\right)^{b-1}\left(-qp\right)^1\right) \bmod p + \left(C_b^2\left(g^a\right)^{b-2}\left(-qp\right)^2\right) \bmod p + \cdots + \left(C_b^b\left(g^a\right)^0\left(-qp\right)^b\right) \bmod p\right) \bmod p \end{aligned}$$

在二项式展开后，除了第一项$C_b^0\left(g^a\right)^b\left(-qp\right)^0$，后面的每一项都含有$p$的非零次方（即为$p$的倍数），所以这些项模$p$的值均为$0$，于是可得：

$$\begin{aligned} {\left(g^a \bmod p\right)}^b \bmod p &= \left(\left(C_b^0\left(g^a\right)^b\left(-qp\right)^0\right) \bmod p + 0 + 0 + \cdots + 0\right) \bmod p \\ &= \left(\left(\left(\frac{b!}{0!\left(b - 0\right)!}\right)\left(g^a\right)^b\left(-qp\right)^0\right) \bmod p\right) \bmod p \\ &= \left(g^{ab} \bmod p\right) \bmod p \\ &= g^{ab} \bmod p \end{aligned}$$

同理可得：

$${\left(g^b \bmod p\right)}^a \bmod p = g^{ab} \bmod p$$

于是就有：

$${\left(g^a \bmod p\right)}^b \bmod p = g^{ab} \bmod p = {\left(g^b \bmod p\right)}^a \bmod p$$

得证。

这里博主提一下，虽然有离散对数问题作为保障使得密码基本不可能被破解，但这并不意味着DH密钥交换算法是一个安全机制完备的算法。DH密钥交换的过程本身并没有提供通讯双方的身份验证服务，因此它很容易受到中间人攻击。

关于DH密钥交换算法的安全问题，本篇文章暂不讨论。

---

抽象代数

至此，我们已经了解了初等数论中诸多重要概念和DH算法的密钥生成原理，但这些内容仅仅是接下来内容的基础。

要想看懂这些概念的本质，并且理解离散对数问题的原理，光靠初等数论的知识是远远不够的，我们还需要了解一点抽象代数相关的知识。

其实在密码学中，大家对各类算法的研究会更倾向于使用抽象代数中的相关理论。而且很多初等数论中的概念（例如：原根），在抽象代数中会有完全不同的定义，并且这些概念在抽象代数中的定义也更符合密码学中的各种应用。

所以下面我们再来了解一些抽象代数中的概念，理解了这部分，咱们不仅能理解密码学中很多算法的底层数学原理，甚至能一窥公钥密码学中的数学核心。

代数

代数

代数（algebra）是一个较为基础的数学分支。它的研究对象有许多。诸如数、数量、代数式、关系、方程理论、代数结构等等都是代数学的研究对象。

初等代数一般在中学时讲授，介绍代数的基本思想：研究当我们对数字作加法或乘法时会发生什么，以及了解变量的概念和如何建立多项式并找出它们的根。

代数的研究对象不仅是数字，还有各种抽象化的结构。例如整数集作为一个带有加法、乘法和序关系的集合就是一个代数结构。在其中我们只关心各种关系及其性质，而对于“数本身是什么”这样的问题并不关心。常见的代数结构类型有群、环、域、模、线性空间等。

和数论一样，代数也是数学的一个分支之一，不同于数论有较为明确的研究对象，代数的研究对象可谓千奇百怪，尤其是广泛应用于密码学中的“抽象代数”分支，研究的对象甚至是各种抽象化的结构，比如上一章节讨论的“模”，以及接下来要讨论的“群”。

抽象代数是代数学的一个分支，同时也是数学中一门很重要的学科，主要研究对象是代数结构，比如群、环、域、模、向量空间、格等等。

代数的分类

• 初等代数：学习以位置标志符(place holders)标记常数和变量的符号，与掌控包含这些符号的表示式及方程式的法则，来记录实数的运算性质。（通常也会涉及到中等代数和大学代数的部分范围。）
• 抽象代数：讨论代数结构的性质，例如群、环、域等。这些代数结构是在集合上定义运算而来，而集合上的运算则适合某些公理。
• 线性代数：专门讨论矢量空间，包括矩阵的理论。
• 泛代数：讨论所有代数结构的共有性质。
• 计算代数：讨论在电脑上进行数学的符号运算的算法。

运算

在详细地介绍抽象代数的各个概念之前，我们需要先了解一个概念：运算。

可能很多人会问：“运算”还用介绍？难道又是另一种让人看不懂的同名新概念吗？其实不是的，这里的运算就是我们理解的那个运算，只不过我们需要了解一下运算的本质是什么。

在数学上，运算（operation）是一种行为，通过已知量的可能的组合，获得新的量。运算的本质是集合之间的映射。

举个例子，对于算术中的加法$7+14=21$，$7$和$14$表示的是输入，$21$表示的是结果，而加号“$+$”表明这是一个加法运算。

笛卡尔积

从运算的本质出发，其实$7+14=21$是一个常见的二元运算，本质上是$A \times B \mapsto C$形式的映射。集合$A$有一个元素$\{7\}$，集合$B$有一个元素$\{14\}$，然后集合$C$有一个元素$\{7+14\}$，对集合$A$和$B$执行加法运算的话，就形成了这种映射关系。

需要注意的是，式子$A \times B \mapsto C$中的“$\times$”不是“乘”的意思，而是指笛卡尔乘积。

笛卡尔乘积

在数学中，笛卡尔乘积指的是两个集合$X$和$Y$的笛卡尔积（Cartesian product），又称直积，表示为$X \times Y$，第一个对象是$X$的成员而第二个对象是$Y$的所有可能有序对的其中一个成员。

假设集合$A=\{a,b\}$，集合$B=\{0,1,2\}$，则两个集合的笛卡尔积为$\{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)\}$。

博主这里把运算的本质单独拎出来是因为，这个集合的映射关系对我们之后理解“群”的概念至关重要，因为“群”中几乎都是二元运算。

一元运算

一元运算本质上是$A \mapsto B$形式的映射，包括但不限于：

• 绝对值
• 三角函数
• 反三角函数
• 逻辑非

二元运算

二元运算本质上是$A \times B \mapsto C$形式的映射，包括但不限于：

• 数与数之间：加、减、乘、除、乘方、开方、对数
• 集合与集合之间：交、并、补、差、笛卡尔积
• 逻辑：逻辑且、逻辑或

代数运算都是二元运算。

代数结构

代数结构是抽象代数中的主角，抽象代数的内容基本就是研究各种各样的代数结构。

在抽象代数里，代数结构（algebraic structure）是指在一个或多个运算下封闭的非空集合。

作为抽象代数的主角，代数结构的定义确实过于“抽象”了，这里博主就用例子说说自己理解的代数结构。

我们定义一个结构$\left(G,*,\#,\cdots\right)$，其中$G$表示一个非空集合，$*$和$\#$表示各种各样的运算，如果这个结构满足封闭性，那么这个结构就称为一个代数结构。

而代数结构中的封闭性是指，集合中任意元素的运算结果都属于集合，也就是说对于任意$a,b \in G$，都有：

$$\begin{aligned} &a * b \in G \\ &a \# b \in G \\ &\vdots \end{aligned}$$

例如，由整数集合$Z$构成的结构$\left(Z,\div\right)$就不是一个代数结构，有两个原因：

1. 结构不封闭：例如$7,2 \in Z$，但$7 \div 2 \notin Z$。
2. 运算不适用于所有元素：集合中元素$\{0\}$不能参与部分运算，因为0不能做除数。

相对应的，结构$\left(Z,\times\right)$就是一个代数结构，甚至是一个“群”。

群论

群论

在数学和抽象代数中，群论（Group theory）研究名为群的代数结构。

群

群是代数结构的一种，在抽象代数中具有极其重要的地位，许多代数结构，包括环、域和向量空间等可以看作是在群的基础上添加新的运算和公理而形成的。

群的概念在数学的许多分支都有出现，而且群论的研究方法也对抽象代数的其它分支有重要影响。

我们在现代密码学许多算法中都能看到对群（尤其是有限循环群）的研究，不仅如此，群论的重要性还体现在物理学和化学的研究中。许多不同的物理结构，如晶体结构和氢原子结构可以用群论方法来进行建模。

如果一个集合$G \ne \varnothing$，与在$G$上的一个二元运算$*$构成的代数结构$\left(G,*\right)$，满足：

1. 封闭性：对于$\forall a,b \in G$，都有$a*b \in G$
2. 结合律：对于$\forall a,b,c \in G$，都有$\left(a*b\right)*c = a*\left(b*c\right)$
3. 存在“单位元”：$\exists e \in G$，使得$\forall a \in G$ ，都有$e*a = a*e = a$
4. 所有元素都具有“逆元”：对于$\forall a \in G$，都$\exists b \in G$，使得$a*b = b*a = e$

这四个条件，则称$\left(G,*\right)$为一个群，简记作$G$。

仔细分析一下群的定义不难看出，作为代数结构的一种，群的定义其实就是在代数结构的基础上加了几个限制条件。

首先群是一种只包含一个非空集合和一个二元运算的代数结构，群的定义在代数结构“封闭性”的基础上，增加了三个必须具备的性质。

结合律很好理解，下面主要说一下单位元和逆元的概念。

需要注意的是，我们在很多“群”的定义中（比如百度百科）都能看到类似这样的描述：

群$(G,*)$又称为乘法群，简记为$G$，代表的是$G \times G \mapsto G$形式的映射关系。若$a,b \in G$，在无歧义时，可将$a*b$写成$ab$。

这个地方有点绕，这里说下博主个人的两种不同理解。

理解一

此处的“乘法”是指群的乘法，并不是传统意义上的数的乘法，群的乘法得出的结果称为积，可以参考上文“笛卡尔积”的概念。

同样的，$ab$也不是指两个数做乘法运算，而是指两个集合中的元素做二元运算（即群的乘法）的结果。

总结下来就是，$(G,*)$虽然可称为乘法群，但$(G,*)$不等同于$(G,\times)$，$ab$也不等同于$a \times b$。

当我们理解了这个之后，我们就能大概明白，为什么群的简记方法都是模仿乘法的形式定义的了。这里博主对群的常用简记符号做一个总结：

• $G$是$(G,*)$的简记，意为名为$G$的群（或乘法群）。
• $ab$是$a*b$的简记，意为元素$a$和元素$b$做一次运算。
• $a^t$是$\underbrace{a*a*a*\cdots*a}_{\text{t}}$的简记，意为$t$个元素$a$一起运算。

理解二

此处的“乘法”就是指传统意义上的乘法，“乘法群”即意为群中的二元运算为乘法。

在这种情况下，乘法群和加法群就有更为明确的定义了：

• 一个群$(G,*)$如果被称之为“乘法群”，此时$(G,*)$就是$(G, \times )$
• 一个群$(G,*)$如果被称之为“加法群”，此时$(G,*)$就是$(G,+)$

只不过在大多数情况下，群论都是在研究乘法群，所以一般在无特别说明的情况下，“群”就是指“乘法群”，即二元运算为乘法的群。

所以对于群的各简记符号，在不特别说明群是加法群的情况下，用“$\times$”替换掉"$*$"即可。

总结下来，博主认为第二种理解正确的可能性更大些，后面的内容也会按照第二种理解进行推导。

其实到这里我们可以回顾下数论中原根的定义，为什么$a^d \equiv 1\pmod m$中的$d$必须是正整数呢？这里就不得不提到抽象代数对于“原根”的定义了。

我们后面会提到，数论中原根定义中的$a$在抽象代数的定义中，其实是某种群的一个元素，而既然已经涉及到群的概念了，那$a^d$必然是个简记法，也就意味着$d$和$a$不是一个维度的概念，代表$a$个数的$d$也必定是正整数。

关于原根在抽象代数中的具体定义后文会有详细的表述，这里先按下不表。

单位元

单位元又称幺元，一般用$e$表示。

如果群里存在一个元素$e$，任何元素与$e$的运算都是元素本身，就称$e$是群中的一个单位元。

需要注意的是，每个群只有唯一的单位元。

举个简单的例子，在群$\left(Z,+\right)$中，很明显$0$就是一个单位元，因为$0$与任何整数相加都等于这个数本身。

而对于单位元的唯一性很好理解。假设群$(G,*)$中有两个不相等的单位元$e$和$e'$，那么根据单位元定义，任何元素与单位元运算都是它本身，所以通过$e$是单位元可以得到

$$e*e' = e'$$

通过$e'$是单位元也可以得到

$$e*e' = e$$

就有

$$e = e'$$

与假设条件冲突。

因为群不一定满足交换律，所以若$a,e \in G$，只有当且仅当$e*a = a*e = a$时才能说$e$是群$G$的单位元，否则只能把满足$e*a = a$的$e$称作左单位元，把满足$a*e = a$的$e$称作右单位元。但又因为一个群中只有一个单位元，所以博主也不知道这个左右单位元的区分有何意义，估计是用在集合上的，或者是别的代数结构里的。

逆元

有了单位元的概念，我们就可以讨论逆元了。

如果对于群里每一个元素，都存在一个元素与它的运算结果等同于单位元$e$，这两个元素就互为逆元。

同样需要注意的是，群里的每个元素只有唯一的逆元。

元素$a$的逆元一般表示为$a^{-1}$，有的元素的逆元是它自己，比如单位元$e$。

需要注意的是，群的定义中，必须每一个元素都能找到自己的逆元才能称作是群。所以代数结构$\left(Q,\times \right)$就不是一个群，虽然具有单位元$1$（因为$1$与任何有理数相乘也等于它本身），但是元素$0$找不到逆元，因为$0$没有倒数。

类似单位元，逆元也有左逆元和右逆元的概念，但我们可以利用单位元的唯一性证明左右逆元是相等的：

假如群$(G,*)$中的元素$a$有一个左逆元$a^{-1}_l$和一个右逆元$a^{-1}_r$，则根据单位元的定义和唯一性我们可以得到：

$$\begin{aligned} a^{-1}_l*a &= e \\ a*a^{-1}_r &= e \end{aligned}$$

$$\begin{aligned} a^{-1}_l &= a^{-1}_l*e = e*a^{-1}_l \\ a^{-1}_r &= a^{-1}_r*e = e*a^{-1}_r \end{aligned}$$

根据群的结合律，就有：

$$\begin{aligned} a^{-1}_l &= a^{-1}_l*e \\ &= a^{-1}_l*\left(a*a^{-1}_r\right) \\ &=\left(a^{-1}_l*a\right)*a^{-1}_r \\ &= e*a^{-1}_r \\ &= a^{-1}_r \end{aligned}$$

由此可证：

$$a^{-1}_l = a^{-1}_r$$

即左右逆元是相等的，也即：

$$a*a^{-1} = a^{-1}*a = e$$

有了左右逆元相等的性质后，逆元的唯一性也可以用类似的方法证明出来了：

假如群$(G,*)$中的元素$a$有两个逆元$b$和$c$，则有：

$$\begin{aligned} a*b &= b*a = e \\ a*c &= c*a = e \end{aligned}$$

此时根据单位元的定义和单位元的唯一性我们可以得到：

$$\begin{aligned} b &= b*e = e*b \\ c &= c*e = e*c \end{aligned}$$

根据群的结合律，就有：

$$\begin{aligned} b &= b*e \\ &= b*\left(a*c\right) \\ &=\left(b*a\right)*c \\ &= e*c \\ &= c \end{aligned}$$

由此可证：

$$b = c$$

即元素$a$只有一个逆元。

逆元的概念可能远比我们想象中的重要，因为逆元主要是用来做逆运算的，而逆运算的复杂度，就与后文要讨论的加密算法的安全性息息相关了。

对于二元运算"$+$"来说，因为有了“相反数”的概念，我们可以通过加法来实现减法，也就是使用$a + \left(-b\right)$来表示$a - b$。

对于二元运算"$\times$"来说，因为有了“倒数”的概念，我们可以通过乘法来实现除法，也就是使用$a \times \frac 1 b$来表示$a \div b$。

而对于群来说，群虽然只定义了一种运算，但我们可以借助“逆元”，来实现另一种运算，也就是群所定义的运算的逆运算。

博主认为，这才是逆元最大的用处。

群的阶

"阶"这个概念在数学中需要指定定语，在不同的定语下阶的意义完全不同（可以类比上文中的欧拉函数），这里先提一下“群的阶”的概念，后面还会提到“元素的阶”。

每个群都关联了一个集合，集合可以分为有限集和无限集两种，而与之相对应的，群也分为有限群和无限群。

若群$\left(G,*\right)$中集合$G$为有限集，则称集合$G$里的元素个数为群$G$的阶，记为$|G|$。

若群$\left(G,*\right)$中集合$G$为无限集，则称群$G$的阶为无限阶。

子群

因为群的定义和构造都与集合有关，而集合有子集的概念，并且甚至有相应的运算规律，那群也不例外。

设$\left(G,*\right)$是群，$H$是$G$的非空子集，如果$\left(H,*\right)$是一个群，则称$\left(H,*\right)$是$\left(G,*\right)$的子群。

由此可见，子群的定义并不复杂，因为基本是完全对标的子集的定义。

沿用定义中的例子，$G$的子群主要分以下两种：

• 平凡子群：$\left(\{e\},*\right)$、$\left(G,*\right)$。
• 非平凡子群（又称真子群）：$\left(H,*\right)$且$H \not = \{e\},G$。

平凡子群其实就两个，一个就是仅有单位元一个元素的群，另一个就是群$G$本身，除此之外都是真子群。

阿贝尔群

阿贝尔群又称交换群，意思是满足交换律的群。

如果对于群$G$中$\forall a,b \in G$，都有

$$a*b = b*a$$

则称群$G$为阿贝尔群。

阿贝尔群是非常重要的一种群，因为它的运算同时满足交换律和结合律。

我们都知道，在数的运算中，一旦一种运算同时满足交换律和结合律，那么这种运算往往通过交换律和结合律推导出各种各样的性质，比如幂的交换律等等。群的运算也不意外，一旦一个群是阿贝尔群，那么它将满足以下定律：

• $\left(a^t\right)^m = a^{tm}$
• $a^t*a^m = a^{t+m}$
• $\left(a^{-1}\right)^t = \left(a^t\right)^{-1} = a^{-t}$
• $\left(a*b\right)^t = a^t*b^t$

其中的$t$和$m$均为整数。

循环群

在密码学涉及的群论内容里，循环群是毫无疑问的核心，因为有大量的公钥密码算法和安全协议是以循环群为基础的。

对于任意群，有一种构造子群很简单的方法。我们都知道在一个群中，群具有封闭性（即群里的每个元素各自运算后的结果都会属于这个群），于是就有：

设$\left(G,*\right)$是群，$a \in G$，则群$\left(\{a^i | i \in Z\},*\right)$必定是$G$的子群，这种群也叫做“由$a$生成的循环子群”，通常使用$<a>$表示（即$<a> \coloneqq \{a^i | i \in Z\}$，意为由$a$生成的$G$的子群）。

至此，我们可以引出循环群的定义了：

设$\left(G,*\right)$是群，若$\exists a \in G$，使得

$$G = <a> = \{a^i | i \in Z\}$$

则称$\left(G,*\right)$是由$a$生成的循环子群（简称G是循环群），称$a$是循环群$\left(G,*\right)$的生成元。

也就是说，循环群中所有的元素都可以通过$a$自运算出来，都具有以$a$为底的格式。

举个简单的例子，整数加法群$\left(Z,+\right)$就是一个循环群，并且这个循环群有两个生成元：$1$和$-1$。

元素的阶

群的阶的概念十分简单（其实就是群中的元素个数），但是元素也有阶的概念，并且定义完全不同。

设$\left(G,*\right)$是群且$a \in G$，如果$n$是满足$a^n = e$的最小正整数，则称$n$是元素$a$的阶。

其实，这个元素的阶的概念非常有意思，换一种角度思考，它描述的是一个元素到单位元$e$的距离。有的元素可能自己运算仅两次就等于单位元$e$，就说明这个元素到达单位元$e$距离很短（元素的阶仅为$2$），但是有的元素可能运算无限多次也无法到达单位元$e$，这种阶就成为无限阶。

元素的阶有一个很重要的性质：

• 对于一个有限循环群，如果它的阶是$n$，则生成元$g$的阶也是$n$。

如果一个群是有限循环群，则生成元$g$的“产量”即决定了群的大小。当$g$进行了大于$n$次的运算后，得出的结果必然是群中已有的元素，所以群的阶和$g$的阶必定都是$n$。

---

公钥密码学的数学核心

在我们理解了抽象代数中的一些基本概念之后，我们才有能力去理解接下来的概念。因为本章节的概念都是需要同时利用数论和抽象代数的知识才能理解透彻的，而本章节的概念才是公钥密码学，甚至是整个密码学的核心。

乘法逆元

在对群中的“逆元”概念有充分理解后，博主终于可以引出模运算中非常重要的概念——“乘法逆元”了。

设$a \in Z$，$n \in N$，如果存在$z$使得$az \equiv 1 \pmod n$，则称$z$是模$n$下$a$的乘法逆元，记作$a^{-1} = z$。

没错，“乘法逆元”虽然称为逆元，但其实是模运算的概念之一。

当我们理解了逆元以后，乘法逆元的定义就变得通俗易懂了，我们甚至可以简单理解为：乘法逆元就是乘法群中的逆元。

不过既然乘法逆元是模运算的概念，那我们在使用这个概念的时候，就有一个需要注意的点。

在群中，我们一般会称“两个元素互为逆元”，因为逆元就类似倒数，是一个相对的概念，比如我们只能说$2$是$\frac 1 2$的倒数，而不会有"$2$是一个倒数"这样的说法。

而对于乘法逆元，因为是模运算中的概念，所以我们在使用时这个概念时不仅要指出“相互”的关系，还要指定模。

举个例子，对于$2 \times 3 \equiv 1 \pmod 5$，我们可以这样描述：

• 错误说法：$2$的乘法逆元是$3$，$2$和$3$互为乘法逆元
• 正确说法：在模$5$下，$2$的乘法逆元是$3$，$2$和$3$互为乘法逆元

同余类

同余类

同余类又称剩余类，是数论的基本概念之一，指全体整数按照对一个正整数的同余关系而分成的类。

举个例子，对于整个整数集合$Z$，所有元素在模$5$下只会产生5种结果，我们把整数大集合$Z$以这个结果为依据划分为5个不相交的子集：

• 余数为$0$时，$Z_0 = \{\cdots ,-5,0,5,10,15, \cdots\}$
• 余数为$1$时，$Z_1 = \{\cdots ,-4,1,6,11,16, \cdots\}$
• 余数为$2$时，$Z_2 = \{\cdots ,-3,2,7,12,17, \cdots\}$
• 余数为$3$时，$Z_3 = \{\cdots ,-2,3,8,13,18, \cdots\}$
• 余数为$4$时，$Z_4 = \{\cdots ,-1,4,9,14,19, \cdots\}$

同理可得，对于任意模数$n$，我们都可以把整数集合$Z$做如此划分，这些子集就称为模$n$的同余类。

设$a \in Z,n \in N^+$，如果集合$X$满足

$$X = \{x \in Z | x \equiv a \pmod n\}$$

则称集合$X$为模$n$下的同余类，意为在模$n$下同余的所有整数组成的集合。

代表元

同余类中每个整数都称作这个同余类的代表元（representative），例如在上面的例子中，$-5$、$0$、$5$、$10$、$15$等都是同余类$[0]$的代表元。

有了代表元以后，我们可以用代表元来表示一个同余类。模$n$下的同余类，通常取各同余类$0$到$n-1$之间最小的代表元$a$来作为相应同余类的记号，记作$[a]_n$，在不引起歧义时简记为$[a]$。

由此，前面列举的模$5$下的5个同余类就可以记为：

$$\begin{aligned} &[0]_5 = \{\cdots,-5,0,5,10,15,\cdots\} \\ &[1]_5 = \{\cdots,-4,1,6,11,16,\cdots\} \\ &[2]_5 = \{\cdots,-3,2,7,12,17,\cdots\} \\ &[3]_5 = \{\cdots,-2,3,8,13,18,\cdots\} \\ &[4]_5 = \{\cdots,-1,4,9,14,19,\cdots\} \end{aligned}$$

其实在同余类的定义中，在不引起歧义的情况下，$[a]$形式的简写手法还能再简写为$a$。

例如$[0]$、$[1]$、$[2]$可简写为0、1、2，$[a] \in Z_n$可简写成$a \in Z_n$。

同时由于同余类的运算法则和模运算完全一致，所以下面的三种写法都是完全等价的：

• $[a]_n \in Z_n,\left([a]_n + [1]_n\right) \times \left([a]_n - [1]_n\right) = [a]_n^2 - [1]_n$
• $[a] \in Z_n,\left([a] + [1]\right) \times \left([a] - [1]\right) = [a]^2 - [1]$
• $a \in Z_n,\left(a + 1\right) \times \left(a - 1\right) = a^2 - 1$

为了表达的直观与方便，网络上的资料大多数都采用了最后一种写法。我们在看到这这种写法时头脑一定要清楚，这里的$a$和$1$本质上都是同余类，而不是单纯的整数。

不过在本篇博客中，博主还是尽量选择标准写法，简写有时候自己都能看晕，实在是不利于梳理。

同余类运算

刚刚博主提到了同余类的运算法则。没错，同余类之间是可以进行运算的，虽然每个同余类都是一个集合，但是同余类之间的运算却有一套简单又独特的定义，并不用集合运算“交并差补”那一套。

同余类之间的加法和乘法运算定义如下：

• $[a]+[b] \coloneqq [a+b]$
• $[a] \times [b] \coloneqq [a \times b]$

其中$a$和$b$必定为整数。

注意博主这里的符号使用的是”$\coloneqq$“而不是”=“，因为根据博主查阅到的资料，一般来说同余类之间的运算都是被定义出来的，这可能是因为并不能简单的使用”二元运算“的概念来给两个集合之间的四则运算强加运算法则，也可能有一些博主所不知道的其他的定义或者证明，也请有所了解的大佬在评论区指点一下。

总之，对于同余类运算的具体描述应为：

• 模$n$下的同余类加法：把$[a]+[b]$定义为整数$a+b$所代表的模$n$下的同余类。
• 模$n$下的同余类乘法：把$[a]\times[b]$定义为整数$a \times b$所代表的模$n$下的同余类。

在实际运算时，可以先忽略“$[]$”，先计算内部整数之间的运算，最后再取模并添加上同余类符号。

举个例子，在模$6$下，$\left([3]+[4]\right) \times [5] = [5]$，计算过程如下：

$$\begin{aligned} \left([3]_6+[4]_6\right) \times [5]_6 &= [\left(3+4\right) \times 5]_6 \\ &= [7 \times 5]_6 \\ &= [35]_6 \\ &= [35 \bmod 6]_6 \\ &= [5]_6 \end{aligned}$$

同余类集合

如果我们把每个同余类看作一个元素，那么组成的集合就叫做同余类集合。

模$n$下的同余类集合一般用$Z_n$表示，那么就有

$$Z_n = \{[0],[1],[2],\cdots,[n-1]\}$$

根据博主的理解，虽然集合$Z_n$和集合$Z$看似好像内容都是所有整数，但是两个集合是完全不同的两个东西。对于$Z$来说，集合的构成元素为单个的数，而$Z_n$中构成集合的基本元素为同余类，理解的时候不能再把同余类中的元素拆开讨论，同余类中所有元素既是一个整体。

这个涉及到后面的运算性质，所以需要注意一下把概念区分开。

如果我们这时候在$Z_n$中选择两个元素$[a]$和$[b]$，并设：

$$\begin{aligned} u &= [a] \\ v &= [b] \end{aligned}$$

根据模运算中乘法逆元的定义我们可以得知，当$a \times b \equiv 1 \pmod n$时，$a$和$b$即在模$n$下互为乘法逆元。

而根据同余类的运算定理我们知道：

$$a \times b = [a] \times [b] = u \times v$$

由此我们可以得出同余类集合中乘法逆元的定义：

对于同余类集合$Z_n = \{[0],[1],[2],\cdots,[n-1]\}$，设$u,v \in Z_n$，若$uv = [1]$，则称$u$和$v$互为乘法逆元。

由此我们可以得出结论：

• 模$n$下的$u$和$v$互为乘法逆元$\Longleftrightarrow a \times b \equiv 1 \pmod n$

翻译过来就是：

• 模$n$下的$u$（和$v$）有乘法逆元$\Longleftrightarrow a$（和$b$）与$n$互素

也就是说，并不是所有的同余类都有乘法逆元的。只有那些代表元与模$n$互素的同余类在$Z_n$中才有乘法逆元。

这个结论非常重要，一定要理解并牢牢记下，马上就会用到。

数论的基石

如果我们去查阅密码学的相关论文，或是网络上的相关资料，经常会看到一个符号"$Z_n^*$"。它就是密码学中大名鼎鼎的”整数模$n$乘法群“（又称模$n$既约同余类），它不仅是数论的基石，同时也是公钥密码学的核心概念之一。

现在我们终于具备了能看懂它的基础知识，可以去尝试理解它的性质与神奇之处了。

模n既约同余类

如果我们在同余类中定义符号$Z_n^*$，它并不是一个群，而是一个集合。

模n既约同余类是同余类集合的一种，包含集合$Z_n$中所有具有乘法逆元的同余类，记为：

$$Z_n^* = \{[a]|a \in Z,1 \leqslant a \leqslant n-1,\gcd \left(a,n\right) = 1\}$$

很明显，由之前同余类乘法逆元的定义我们可以知道，$Z_n^*$中的每个同余类，它们的所有代表元都与模$n$互素。

例如，在模$6$下我们可以得到：

$$\begin{aligned} Z_6 &= \{[0],[1],[2],[3],[4],[5]\} \\ Z_6^* &= \{[1],[5]\} \end{aligned}$$

其中$Z_6^* = \{[1],[5]\}$的含义是：在模$6$下，有且只有$[1]$和$[5]$这两个同余类中所有的元素与$6$互素。

$Z_n$和$Z_n^*$之间的关系如下，分为两种情况：

• $n$为素数时，$Z_n^* = Z_n \setminus \{[0]\}$。
• $n$为合数时，$Z_n^* \subsetneq Z_n \setminus \{[0]\}$。

因为一旦模$n$为素数，那么对于任意非零整数$a$必然满足$\gcd \left(a,n\right)$，此时

$$Z_n^* = \{[1],[2],[3],\cdots,[n-1]\}$$

此时在$Z_n^*$定义里，$[a]$的取值为$1$到$n-1$之间的所有整数。

关于模$n$为素数的情况，后面会单独介绍。

再回头看欧拉函数，因为欧拉函数$\varphi\left(n\right)$表示的是小于等于$n$的正整数中与$n$互素的数的数目，结合$Z_n^* = \{[a]|a \in Z,1 \leqslant a \leqslant n-1,\gcd \left(a,n\right) = 1\}$我们就可以惊讶地发现：欧拉函数定义中“小于等于$n$的正整数中与$n$互素的数”其实指的就是$Z_n^*$中的$[a]_n$。

换句话说就是：$Z_n^*$的阶为$\varphi\left(n\right)$。

我们如果用$Z_n^*$来表示欧拉函数，$\varphi\left(n\right)$则可定义为：

对于$\forall n \in N^+$，$\varphi\left(n\right) \coloneqq |Z_n^*|$，且令$\varphi\left(1\right) = 1$。

在这种情况下，我们就能理解为什么当$n$取值为素数$p$时，$\varphi\left(p\right) = p-1$了。因为当模$n$为素数时，$Z_n^*$定义中$[a]$的取值为$1$到$n-1$之间的所有整数，这个整数个数即为$n-1$个。

整数模n乘法群

接下来我们再来看看，$Z_n^*$在数论中的定义——整数模$n$乘法群。其实这个定义才是用的更为广泛，更加标准的定义。

模$n$的互素同余类组成一个乘法群，称为整数模$n$乘法群，记为$Z_n^*$。

其实数论中的这个定义与同余类中的定义并无多少差别，但是唯一的不同是，一个是“同余类”（也就是集合），一个是“群”。也就是说根据群的定义，此处的$Z_n^*$其实是$\left(Z_n^*,\times \right)$的简写，也可以直接写成$Z_n^\times$。

既然把$Z_n^*$定义为群，我们可以顺便讨论下它的一些性质：

• $Z_n^*$是一个有限群
• $Z_n^*$中的元素都不是单一整数，而是一个个模$n$下的同余类（即$[a]_n$）
• $Z_n^*$的单位元是同余类$[1]_n$
• $Z_n^*$的阶是$\varphi\left(n\right)$

需要注意的是，$Z_n^*$不一定为循环群，所以不一定有生成元。

$Z_n^*$是循环群的条件为：$n = 1,2,4,p^k,2p^k$（其中$p$为奇素数，$k$为正整数）。

这个条件非常重要，后面会用到。

最小简约余数系

如果$a \equiv b \pmod n$，那么$\gcd\left(a,n\right) = \gcd\left(b,n\right)$。也就是说一个数$a$如果与$n$互质，那么$[a]_n$里面所有的数都与$n$互质。因此我们可以从$Z_n^*$中的每个同余类里面抽出一个数来代表对应的同余类。

例如$n = 8$，我们可以将$Z_n^*$写成下面任意一种形式：

• $Z_8^* = \{1,3,5,7\}$
• $Z_8^* = \{9,11,13,15\}$
• $Z_8^* = \{1,3,29,87\}$

通常我们用每个同余类中最小的正整数来表示那个类，这样形成的集合也叫做最小简约余数系。上面提到的$Z_8^* = \{1,3,5,7\}$就是这样一个例子。

一般我们都用模$n$的最小简约余数系来代表群$Z_n^*$的集合。

群与模运算

在模运算中，原根就是生成元，乘法阶就是元素的阶，原根和乘法阶的性质既可以用模运算的知识来理解，也可以用群论的知识来理解。

乘法阶

乘法阶是模运算中一个很重要的概念。

在模运算中，乘法阶的定义如下：

设$a \in Z,\gcd \left(a,n\right) = 1$，如果$k$是满足$a^k \equiv 1 \pmod n$的最小正整数，则称$k$是$a$在模$n$下的乘法阶，记为$ord_n\left(a\right)$。

博主之所以在这里才提出“乘法阶”这个重要概念，因为用$Z_n^*$来定义乘法阶会更容易理解：

设$a \in Z_n^*$，$a$的乘法阶$ord_n\left(a\right)$是满足$a^{ord_n\left(a\right)} \equiv 1 \pmod n$的最小正整数。

在这个定义中，元素$a$不再是一个整数，而是一个同余类。由此我们可以得出这样的结论：

$$a^{ord_n\left(a\right)} \equiv 1 \pmod n \Longleftrightarrow \gcd \left(a^{ord_n\left(a\right)},n\right) = 1 \Longleftrightarrow a^{ord_n\left(a\right)} = [1]_n$$

因为$[1]_n$是$Z_n^*$的单位元，结合上文中“元素的阶”的定义我们就会得到一个重要的结论：

• 在$Z_n^*$中，元素的阶就是这个元素的乘法阶。

原根与生成元

既然乘法阶、$Z_n^*$等模运算概念都可以用群论的知识去理解，那么原根也不例外。

相比于前文中原根那晦涩难懂的标准定义，如果我们用乘法阶来定义原根就会通俗很多：

设$g \in Z$，$\gcd \left(g,n\right) = 1$，如果

$$ord_n\left(g\right) = \varphi\left(n\right)$$