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

10/23/2020 信息安全

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的逆元: