AES算法详解及欧几里得算法简介

AES 算法简介

AES 的全称是 Advanced Encryption Standard，意思是高级加密标准。AES 密码分组大小和密钥大小可以为 128 位、192 位和 256 位。然而 AES 只要求分组大小为 128 位。本文只对分组大小 128 位，密钥长度也为 128 位的 Rijndael 算法进行分析。密钥长度为 192 位和 256 位的处理方式和 128 位的处理方式类似，只不过密钥长度每增加 64 位，算法的循环次数就增加 2 轮，128 位循环 10 轮、192 位循环 12 轮、256 位循环 14 轮。

AES 算法使用逻辑就是：发送方将要发送的明文数据 X 使用秘钥 K 进行 AES 加密后会得到密文 Y，将密文进行网络传输，接受方在收到密文 Y 后使用秘钥 K 进行 AES 解密后技能得到明文 X, 这样即使密文 Y 在网络上传输时被截获了，没有秘钥也难以破解其真实意思。

AES 算法相关数学知识

在 AES 算法中的 MixColumn 层中会用到伽罗瓦域中的乘法运算，而伽罗瓦域的运算涉及一些数学知识如下：

素域：

有限域有时也称伽罗瓦域，它指的是由有限个元素组成的集合，在这个集合内可以执行加、减、乘和逆运算。而在密码编码学中，我们只研究拥有有限个元素的域，也就是有限域。域中包含元素的个数称为域的阶。只有当 m 是一个素数幂时，即 m =pⁿ(其中 n 为正整数是 p 的次数，p 为素数)，阶为 m 的域才存在。p 称为这个有限域的特征。也就是说，有限域中元素的个数可以是 11(p=11 是一个素数,n=1)、可以是 81(p= 3 是一个素数，n=4)、也可以是 256(p= 2 是一个素数，n=8)….. 但有限域的中不可能拥有 12 个元素，因为 12=2·2·3，因此 12 也不是一个素数幂。有限域中最直观的例子就是阶为素数的域，即 n = 1 的域。的元素可以用整数 0、1、…、p-1l 来表示。域的两种操作就是 模整数加法 和整数乘法模 p 。加上 p 是一个素数，整数环 Z 表示为 GF(p)，也成为拥有素数个元素的素数域或者伽罗瓦域。GF(p)中所有的非零元素都存在逆元，GF(p)内所有的运算都是模 p 实现的。

素域内的算数运算规则如下：

(1)加法和乘法都是通过模 p 实现的；

(2)任何一个元素 a 的加法逆元都是由 a +(a 的逆元)=0 mod p 得到的；

(3)任何一个非零元素 a 的乘法逆元定义为 a·a 的逆元 =1。

例：在素域 GF(5)={0、1、2、3、4}中，2 的加法逆元为 3，这是因为 2 +(3)=5，5mod5=0, 所以 2 +3=5mod5=0。2 的乘法逆元为 3，这是因为 2·3=6，6mod5=1，所以 2·3=6mod5=1。(在很多地方 a 的加法逆元用 - a 表示，a 的乘法逆元用 1 / a 表示)

注：GF(2)是一个非常重要的素域，也是存在的最小的有限域，由于 GF(2)的加法，即模 2 加法与异或 (XOR) 门等价，GF(2)的乘法与逻辑与 (AND) 门等价，所以 GF(2)对 AES 非常重要。

扩展域：

如果有限域的阶不是素数，则这样的有限域内的加法和乘法运算就不能用 模整数加法 和整数乘法模 p 表示。而且 m >1 的域被称为扩展域，为了处理扩展域，我们就要使用不同的符号表示扩展域内的元素，使用不同的规则执行扩展域内元素的算术运算。

在扩展域 GF(2^m)中，元素并不是用整数表示的，而是用系数为域 GF(2)中元素的多项式表示。这个多项式最大的度 (幂) 为 m -1，所以每个元素共有 m 个系数，在 AES 算法使用的域 GF(2^8)中，每个元素 A∈GF(2⁸)都可以表示为：

注意：在域 GF(2⁸)中这样的多项式共有 256 个，这 256 个多项式组成的集合就是扩展域 GF(2⁸)。每个多项式都可以按一个 8 位项链的数值形式存储：

像 x ⁷、x⁶等因子都无需存储，因为从位的位置就可以清楚地判断出每个系数对应的幂。

扩展域 GF(2^m)内的加减法：

在 AES 算法中的密钥加法层中就使用了这部分的知识，但是不是很明显，因为我们通常把扩展域中的加法当作异或运算进行处理了，因为在扩展域中的加减法处理都是在底层域 GF(2)内完成的，与按位异或运算等价。假设 A(x)、B(x)∈GF(2^m)，计算两个元素之和的方法就是：

而两个元素之差的计算公式就是：

注：在减法运算中减号之所以变成加号，这就和二进制减法的性质有关了。从上述两个公式中我们发现在扩展域中加法和减法等价，并且与 XOR 等价(异或运算也被称作二进制加法)。

扩展域 GF(2^m)内的乘法

扩展域的乘法主要运用在 AES 算法的列混淆层 (Mix Column) 中，也是列混淆层中最重要的操作。我们项要将扩展域中的两个元素用多项式形式展开，然后使用标准的多项式乘法规则将两个多项式相乘：

注：通常在多项式乘法中 C(x)的度会大于 m -1，因此需要对此进行化简，而化简的基本思想与素域内乘法情况相似：在素域 GF(p)中，将两个整数相乘得到的结果除以一个素数，化简后的结果就是最后的余数。而在扩展域中进行的操作就是：将两个多项式相乘的结果除以一个不可约多项式，最后的结果就是最后的余数。(这里的不可约多项式大致可以看作一个素数)

例：

AES 算法原理

AES 算法主要有四种操作处理，分别是 密钥加法层 (也叫轮密钥加，英文 Add Round Key)、 字节代换层 (SubByte)、 行位移层 (Shift Rows)、 列混淆层 (Mix Column)。而明文 x 和密钥 k 都是由 16 个字节组成的数据(当然密钥还支持 192 位和 256 位的长度，暂时不考虑)，它是按照字节的先后顺序从上到下、从左到右进行排列的。而加密出的密文读取顺序也是按照这个顺序读取的，相当于将数组还原成字符串的模样了，然后再解密的时候又是按照 4·4 数组处理的。AES 算法在处理的轮数上只有最后一轮操作与前面的轮处理上有些许不同(最后一轮只是少了 列混淆 处理)，在轮处理开始前还单独进行了一次轮密钥加的处理。在处理轮数上，我们只考虑 128 位密钥的 10 轮处理。接下来，就开始一步步的介绍 AES 算法的处理流程了。

AES 算法流程图:

密钥加法层

在密钥加法层中有两个输入的参数，分别是明文和子密钥 k[0]，而且这两个输入都是 128 位的。k[0]实际上就等同于密钥 k，具体原因在密钥扩展生成中进行介绍。我们前面在介绍扩展域加减法中提到过，在扩展域中加减法操作和异或运算等价，所以这里的处理也就异常的简单了，只需要将两个输入的数据进行按字节异或操作就会得到运算的结果。

图示：

字节代换层

字节代换层的主要功能就是让输入的数据通过 S_box 表完成从一个字节到另一个字节的映射，这里的 S_box 表是通过某种方法计算出来的，具体的计算方法在此不做详述，我们主需要知道如何使用 S_box 结果即可。S_box 表是一个拥有 256 个字节元素的数组，可以将其定义为一维数组，也可以将其定义为 16·16 的二维数组，如果将其定义为二维数组，读取 S_box 数据的方法就是要将输入数据的每个字节的高四位作为第一个下标，第四位作为第二个下标，略有点麻烦。这里建议将其视作一维数组即可。逆 S 盒与 S 盒对应，用于解密时对数据处理，我们对解密时的程序处理称作逆字节代换，只是使用的代换表盒加密时不同而已。

S 盒

逆 S 盒

加密图示：

行位移——ShiftRows

行位移操作最为简单，它是用来将输入数据作为一个 4·4 的字节矩阵进行处理的，然后将这个矩阵的字节进行位置上的置换。ShiftRows 子层属于 AES 手动的扩散层，目的是将单个位上的变换扩散到影响整个状态当，从而达到雪崩效应。在加密时行位移处理与解密时的处理相反，我们这里将解密时的处理称作逆行位移。它之所以称作行位移，是因为它只在 4·4 矩阵的行间进行操作，每行 4 字节的数据。

加密时：保持矩阵的第一行不变，第二行向左移动 8Bit(一个字节)、第三行向左移动 2 个字节、第四行向左移动 3 个字节。

解密时：保持矩阵的第一行不变，第二行向右移动 8Bit(一个字节)、第三行向右移动 2 个字节、第四行向右移动 3 个字节。

正向行位移图解:

逆向行位移图解:

列混淆——MixColumn

列混淆子层是 AES 算法中最为复杂的部分，属于扩散层，列混淆操作是 AES 算法中主要的扩散元素，它混淆了输入矩阵的每一列，使输入的每个字节都会影响到 4 个输出字节。行位移子层和列混淆子层的组合使得经过三轮处理以后，矩阵的每个字节都依赖于 16 个明文字节成可能。其中包含了矩阵乘法、伽罗瓦域内加法和乘法的相关知识。

在加密的正向列混淆中，我们要将输入的 4·4 矩阵左乘一个给定的 4·4 矩阵。而它们之间的加法、乘法都在扩展域 GF(2⁸)中进行，所以也就可以将这一个步骤分成两个部分进行讲解：

1) 正向列混淆

正向列混淆的原理图如下：

根据矩阵的乘法可知，在列混淆的过程中，每个字节对应的值只与该列的 4 个值有关系。此处的乘法和加法都是定义在 GF(2⁸)上的，需要注意如下几点：

1) 将某个字节所对应的值乘以 2，其结果就是将该值的二进制位左移一位，如果原始值的最高位为 1，则还需要将移位后的结果异或 00011011；

2) 乘法对加法满足分配率，例如：07·S0,0=(01⊕02⊕04)·S0,0= S0,0⊕(02·S0,0)(04·S0,0)

3) 此处的矩阵乘法与一般意义上矩阵的乘法有所不同，各个值在相加时使用的是模 2 ⁸加法（异或运算）。

下面举一个例子，假设某一列的值如下图，运算过程如下：

在计算 02 与 C9 的乘积时，由于 C9 对应最左边的比特为 1，因此需要将 C9 左移一位后的值与 (0001 1011) 求异或。同理可以求出另外几个值。

2) 逆向列混淆

逆向列混淆的原理图如下：

由于：

说明两个矩阵互逆，经过一次逆向列混淆后即可恢复原文。

我们发现在矩阵乘法中，出现了加法和乘法运算，我们前面也提到过在扩展域中加法操作等同于异或运算，而乘法操作需要一个特殊的方式进行处理，于是我们就先把代码中的加号换成异或符号，然后将伽罗瓦域的乘法定义成一个有两个参数的函数，并让他返回最后计算结果。于是列混淆的代码就会变成下面的样子：

接下来我们就只用处理伽罗瓦域乘法相关处理了，由于前面介绍过相关概念，所以代码就不在此进行讲解了，大家可以参考下方的代码注释进行理解：

在解密的逆向列混淆中与正向列混淆的不同之处在于使用的左乘矩阵不同，它与正向列混淆的左乘矩阵互为逆矩阵，也就是说，数据矩阵同时左乘这两个矩阵后，数据矩阵不会发生任何变化。

正向列混淆处理

逆向列混淆

加解密验证

加密部分讲解完毕，最后应该注意要将密文结果从矩阵形式还原成字符串形式输出！

AES密钥扩展

子密钥的生成是以列为单位进行的，一列是 32Bit，四列组成子密钥共 128Bit。生成子密钥的数量比 AES 算法的轮数多一个，因为第一个密钥加法层进行密钥漂白时也需要子密钥。密钥漂白是指在 AES 的输入盒输出中都使用的子密钥的 XOR 加法。子密钥在图中都存储在 W[0]、W[1]、…、W[43]的扩展密钥数组之中。k1-k16 表示原始密钥对应的字节，而图中子密钥 k0 与原始子密钥相同。在生成的扩展密钥中 W 的下标如果是 4 的倍数时 (从零开始) 需要对异或的参数进行 G 函数处理。扩展密钥生成有关公式如下：

函数 G()首先将 4 个输入字节进行翻转，并执行一个按字节的 S 盒代换，最后用第一个字节与轮系数 Rcon 进行异或运算。轮系数是一个有 10 个元素的一维数组，一个元素 1 个字节。G()函数存在的目的有两个，一是增加密钥编排中的非线性；二是消除 AES 中的对称性。这两种属性都是抵抗某些分组密码攻击必要的。

AES 解密流程图

至此，AES 算法基础部分介绍完毕！

欧几里得算法：

两个正整数 r0 和 r1 的 gcd 表示为 gcd(r0, r1)，它指的是可以被 r0 和 r1 同时整除的最大正整数，例如 gcd(21, 6)=3。对与较小的整数而言 gcd 就是将两个整数进行因式分解，并找出最大的公因子。
例：r0=84,r1=30，因式分解：r0=2·2·3·7；r1=2·3·5；gcd 的结果就是：gcd(30,84)=2·3=6。
gcd(r0,r1)=gcd(r0-r1,r1)其中假设 r0>r1，并且两个数均是正整数。证明：gcd(r0,r1)=g，由于 g 可以同时被 r0、r1 整除，则可以记作 r0=g·x、r1=g·y，其中 x >y，并且 x 和 y 互为素数。所以得到：gcd(r0,r1)=gcd(r0-r1,r1)=gcd(g·(x-y),g·y)=g=gcd(ri,0)。
例：r0=973,r1=301,gcd 的计算方式为：

欧几里得算法代码

扩展欧几里得算法：

扩展欧几里得算法主要的应用不是为例计算最大公因子，它的在密码学中主要的作用是为了计算乘法逆元，乘法逆元在公钥密码学中占有着举足轻重的地位。当然，除了扩展欧几里得算法 (EEA) 除了可以计算 gcd，它还可以计算以下形式的线性组合：

其中 s 和 t 都表示整型系数。关于如何计算这两个系数的推到过程这里就不介绍了，我们只给出最后的公式结论:

介绍完这些公式，我们来看看乘法的逆元是怎么计算的吧。假设我们要计算 r1 mod r0 的逆元，其中 r1 < r0。我们前面提到过乘法的逆元计算公式为 a *b=1 mod p，b 就是 a mod p 的乘法逆元，也就是 gcd(p, a)= 1 的情况。下才存在乘法逆元。则 s·r0+t·r1=1=gcd(r0,r1)，将这个等式执行模 r0 计算可得：
例：计算 12 mod 67，12 的逆元，即 gcd(67,12)=1

注：通常情况下不需要计算系数 S, 而且实际中一般也用不上它，另外结果 t 可能是一个负数，这种情况下就必须把 t 加是 r0 让人的结果为正，因为 t =(t+r0) mod r0。

扩展欧几里得算法代码

如果要想计算伽罗瓦域内乘法的逆元，函数的输入 r0 就是 GF(2^8)的不可约多项式 p(x)，r1 就是域元素 a(x)，然后通过 EEA 计算多项式 t(x)得到 a(x)的乘法逆元。只不过在上方给出的 EEA 代码略有不同，因为在伽罗瓦域中多项式都是在 GF(2)上进行加减运算的，也就是说上面的加号和减号都要换成异或运算符，同时乘法和除法也有要进行适当的调整，转变成多项式乘法和除法。否则结果会出现偏差。

伽罗瓦域的扩展欧几里得算法：

伽罗瓦域的扩展欧几里得算法

生成 S 盒的过程：

AES 的 S 盒具有非常强的代数结构，它是经过两个步骤计算而来的：

我们已经了解的逆元的计算过程，接下来只剩下了仿射映射过程了。

S 盒的仿射映射:

仿射映射这个名词听起来有点高深莫测的感觉，不过在我的理解上，它就是一个计算过程。S 盒的仿射映射也比较简单，主要就是运用到了矩阵乘法，不过这个矩阵是 Bit 矩阵。先上一下计算方法：

注意仿射映射所有的计算都是基于 GF(2)上的。我们从计算过程上发现，输入数据 A 的逆元 B 在仿射映射中被展开成了一个 8·1 的矩阵，最上方是 LSB，然后左乘了一个 8·8 的 Bit 矩阵，后加上了 0x63 展开的 8·1 矩阵，由于是基于 GF(2)的，所以需要进行 mod 2 操作，最终的结果才是输出数据 C。可能有些同学还是看不懂这张图，那我们就以输入数据为 A =0x7 为例，手动计算一下这个结果 C:

1、计算乘法逆元：
将以下两个参数带入 EEA_V2()函数可以得到 A 的逆元: