密码学基础之抽象代数基础

上一篇我们聊了聊进制与编码，那么关于如何将数据转化为数字已经不成问题了，这帮助初入密码学的朋友解决了心里的第一个槛。于是接下来，我们就聊一聊这些由数据转化而来的数字上的一些相关学问，没错，数学来了。相信这可能是很多没有数理基础的又想在 CTF 里玩密码学的朋友会遇到的第二个槛：嗨嗨嗨，我搞了一堆python 脚本对那个叫 RSA 的东西一顿梭梭梭，但是有一天，题目的式子稍微变了变，哎，一下给整懵逼了。

但这里我们先不讲高中数学，也不聊高等数学，这里想给大家介绍的，是抽象代数。虽然我也只是懂得其中的一些皮毛，但也希望能将这些浅显的东西分享出来，也算是为后续在一些式子上的推导打个基础吧。

另外知乎上刘巍然一篇科普向的书籍《质数了不起》，和 b 站上的一个学习视频《某群清华大佬讲解“形象”代数》 中的群论基础部分，推荐大家在某个失眠的夜去浅读（看）一下子。

群的定义

相信大家对群是既熟悉又陌生吧，可能在很多地方都有听过它的名号，但是让具体去描述它是个什么东西，可能又说不出个所以然。在介绍群的定义之前，我们需要先了解一些更加基础的概念。

集合与元素，大家第一次听到这两个概念应该是可以一直向前追溯的小学的。集合是“确定的一堆东西”，而集合里的“东西”则称之为元素，并且集合里面的东西可以是任意的东西。

第一颗?：我们定义一个集合 ，并且其中的元素都是 10 的倍数，于是这个集合为 ，里面会有无限多个元素，这样的集合也叫做无限集合。

我们对 中的元素加一个限制，比如还要求绝对值小于等于 10，于是我们就有了一个具有三个元素的有限集合

最后我们再定义一个集合 ，这个集合会相对抽象些，我们观察如下图形

我们设定集合 中的元素是能够使得图片（表面上）不发生任何变化的等距变换（旋转、平移），于是这个集合为 其中正号表示顺时针旋转、符号表示逆时针旋转。同样的，这也是一个无限集合。

运算，这个概念大家接触的就更早了，想必各位在幼儿园之前就已经被爸妈教育 一加一等于二 了，这里加，就是一种运算。上面元素可以是任意的东西，那么这里的运算也可以是任意的“法则”。例如大家肯定在数学试卷中见到过 “定义一种运算 ”  叭，下面肯定还接着给出了运算 的一些运算规则，然后让你去推导一些东西什么的巴拉巴拉。（所以其实我们或多或少的早都接触过群论了）

第二颗?：沿用上述三个集合 ，我们为集合 赋予一个加法运算，组成一个代数结构 ，那么对于其中的任意两个元素 ，我们可以进行计算 ，并且不难验证的是， 的运算结果也是 中的一个元素，于是我们称这个代数结构中的运算，也就是加法，具有封闭性。

如果我们对 也赋予一个加法运算，组成代数结构 ，那么我们很容易发现，这里的加法是不具有封闭性的，因为 ，而 这个元素是不在 中的。

对于集合 ，我们赋予一个运算叫复合变换 ，构成 ，直观上来说该变换在这里就是将两个旋转的角度相加（所以要理解成角度的加法也没有关系），容易验证，这个复合变换也是具有有封闭性的。

在了解相关”基础设施“之后，我们开始定义群：

首先我们需要有一个非空集合 ，和一个具有封闭性的二元运算 ，即满足 （S 中的元素和 S 中的元素运算后还在 S 中）组成代数结构 < S,★ > 。

1. 如果这个代数结构满足 结合律，即对于所有元素  均满足 ，则称该代数结构为 半群。
2. 如果这个半群存在 恒等元 （也称幺元），即对于所有元素 ，均满足 ，则称该代数结构为幺半群。
3. 如果这个幺半群中所有的元素都存在 逆元，即对于所有元素 ，均存在元素 满足 ，则称该代数结构为群。
4. 如果群中的运算具有交换律，即对于所有元素  均满足 ，则称该代数结构为 阿贝尔群。

老规矩，开始举例。

第三颗?：

1. 沿用前面的集合 ，显然我们所熟知的加法运算是具有结合律的（在很多情况下结合律其实很难证明，所以这里我挑了一个简单的运算来略过这一步），于是可以称 为半群。
2. 然后 中存在恒等元 ，因为对于任何元素 ，都有 ，于是可以称 为幺半群。
3. 对于 中的任意元素 ，都有对应的逆元 满足 ，于是可以称 为群。
4. 另外加法运算是满足交换律的，即对于任何元素 ，都有 ，于是可以称 为阿贝尔群。

另外我们可以再新定义一个代数结构，其中 是包含所有 的矩阵的集合，运算为矩阵乘法。回想一下还残存不多的线性代数的知识，我们知道矩阵乘法具有结合律；有单位矩阵 ，但只有行列式不为 0 的矩阵存在逆矩阵。因此该代数结构仅仅是一个幺半群。若想要让它”升级“为群，则需要给元素加一个行列式不为 0 的限定。另外我们知道矩阵乘法不具有交换律，所以即使所有元素的行列式都不为 0 ，该代数结构也不构成阿贝尔群。

所以在我们了解了群的定义，然后呢？群有什么用呢？具体来说其实没有什么功能上的作用，不过它能够帮助我们更好的理解后续的很多更”高级“的概念。接下来就是第一个概念，剩余系。

剩余系

又从一个我们小学就接触过的概念起手（所以这篇内容介绍的东西真的很基础）：带余除法。例如 ，一般我们需要的是这个商 ，但这里我们关注的是这个余数 ，甚至我们还给他一个专门的符号 ，有 。

于是现在我们又定义一个集合 ，其中的元素是任意整数除 3 后所有可能的余数，于是我们有 。余数就是剩余的数，所以除数 3 的所有可能余数组成的集合，就是 的剩余系。同理我们能知道 2 的剩余系就是 ，这就是二进制中的两个元素；5 的剩余系就是 ;   10 的剩余系就是 。

前面我们有 ，现在我们换个符号: ，有 。原来 3 叫做除数，这里我们也换个名字，叫做模数。所以上式就表示为模 3 下 5 和 2 同余。即在模数为 3 的情况下，5 和 2 具有相同的余数（5 的余数是 2，2 的余数也是 2）。除了 5 和 2 同余，，5 还和 8 同余；，8 也和 11 同余；不难得出：2 + 3的任意整数倍的值都互相同余 （注意这个整数倍也可以是负数）。这样的数也可以组成一个集合 ，叫做模 3 的一个剩余类（因为它们会有一些相同的性质，所以是一类）。

剩余系只是一个集合，跟前面我们提到的群还差了一个运算，于是这里我们就赋予一个运算给剩余系：模加。

模加其实就是剩余系中的一个满足封闭性的普通加法。为什么不直接用加法呢？以 举例，如果是加法，在计算 1+1 的时候就等于 2，而 2 并不在 中，因此加法在这里不满足封闭性，就更别说用来构成一个群了。那么模加的运算法则是怎样的呢？沿用上面的例子，在 1+1 = 2 即将破坏封闭性的时候，我们对 2 进行一个模 2 的运算，即 ，所以有 。可以发现， 长得跟等号 很像，其实功能也和等号差不多：一个表示同余，一个表示相等；模加的时候用同余，加法的时候用相等。

第四颗?：我们说明 是一个阿贝尔（交换）群（这里的加法是模加）

1. 首先我们有非空子集 ，和具有封闭性的二元运算 模加
2. 结合律成立：
3. 有单位元 ：
4. 任意元素均有逆元：，我们直接枚举：
5. 模加具有交换律：

既然加法有对应的模加，那么我们熟悉的乘法有对应的模乘么？有的，和普通乘法运算法则也是一致，只需要对最后计算的结果，也就是积，取余数就好。那么  构成群么？不构成，虽然其满足结合律，有单位元 1，但是元素 0 没有逆元，所以其仅仅算是个幺半群。另外如果是  < S10, · > ，除了 0 以外，元素 2,4,5,6,8 均没有逆元（可以用 2 乘以 0,1,……9 来验证）。这里直接给出一个结论，当且仅当元素和模数互素时，该元素存在对应的乘法逆元。（互素这个概念应该都知道叭，就是两个元素除了 1 没有其他公因子，至少公因子这个概念是知道的叭。。。）

第五颗?：以 为例，其中 1,3,7,9 和模数10互素，它们均有逆元：；因此 1 的逆元是它自己；，因此 3,7 互为逆元；，因此 9 的逆元也是它自己。而其它元素则找不到逆元。

于是，这些有逆元的元素（也就是和模数互素的元素）也组成了一个系，叫做简化剩余系。这样，简化剩余系再附加一个模乘运算，就能够构成一个阿贝尔群；一般情况下我们会以运算作为标签，模乘的叫做乘法群，模加的叫做加法群。

然后这里提一下，我们在密码学中经常会提到有限域（也就是伽罗华域），这个域相比于群就是具有两个运算的代数结构，如加法和乘法，其中要求每个元素都要有自己的加法逆元和乘法逆元，不过不要求 0 有自己的乘法逆元。所以问大家一个问题，我们在 RSA 中的计算都是在模 下的，其中 是两个大素数。那么模 下的剩余系和加法、乘法能构成一个有限域么？

关于乘法群中的离散对数问题

我们知道乘法是二元运算，是两个元素之间的运算；但是我们可以将乘法运算进行叠加，这样就可以做到三个，甚至更多个元素的运算。当我们将一个元素不断的和自己进行乘法运算时，也就变成我们熟知的幂次运算。例如我们在模 下将 个 相乘得到 , 可记为 。

需要明确的是，幂次运算是乘法运算的叠加，所以严格意义上它在乘法群中不是一个运算，既没有结合律，也没有幺元，更不存在逆元。

当我们有式子 ，其中仅知道 ，需要计算出 ，这样一个问题就是解乘法群下的离散对数问题。之所以离散，是因为我们的元素是模 p 剩余系中的整数，这在数轴，亦或是坐标系中，是一系列离散的点。之所以对数，是因为这是一个已知底数和幂求指数的计算。

离散对数问题是数学困难问题之一，尚没有应对所有离散对数问题的高效算法。后续应该会介绍目前已知的解某些特殊情况下离散对数问题的算法。

椭圆曲线

椭圆曲线也是现代密码学中的常客了，不过对于初学者来说它可能比较陌生，又相对复杂，所以就会让人感到孩怕（事实上也确实挺难的）。但这里暂且不介绍椭圆曲线上很复杂的理论，只是想简单介绍一下这个代数结构。

我们常听到椭圆曲线加法群，所以它其实也是一个由元素和运算结合起来的一个代数结构 ，集合中的元素是一系列满足同余式 的坐标 ，其中 是素数， 是模 下的整数。为了让这个代数结构构成一个群，还往集合中”硬塞“了一个点 ，也就是后面关于运算 的单位元。

而这里的运算法则 + 并不是普通的加法，具体规则为：设相加的两个点为 ：

1. 如果 ，则
2. 如果 ，则
3. 否则设
1. 其中如果 ，则
2. 如果 ，则
3. 如果 ，则
4. 否则设

椭圆曲线的加法具有结合律，即

椭圆曲线的单位元是 ，即

椭圆曲线中每个元素都存在逆元，即 ，一般我们记 ，设 ，则

椭圆曲线的加法具有交换律，即

所以这也是一个阿贝尔群。（证明挺复杂的，感兴趣的朋友可以去翻翻椭圆曲线的相关书籍）

椭圆曲线下的离散对数问题

椭圆曲线的加法同样可以叠加，例如我们将 个 相加得到 , 可记为 ，虽然这看起来像是数乘，但可没办法通过 来计算得到 。所以类比上面乘法群下的离散对数问题，已知 解出 这样的问题就称为椭圆曲线下的离散对数问题。所以其实可以把所有离散对数问题抽象成一种求运算叠加次数的问题。而各个离散对数问题有难有易，椭圆曲线下的离散对数问题就比乘法群下的离散对数问题困难，但加法群下的离散对数问题就比较简单。

那么这就是这周基础系列文章的全部内容了，下周准备以今天的内容为基础，简单介绍一下数论四大定理。