对称密码-AES

模板引擎对LaTeX支持不太好，可以查看静态页面:链接
 个人主页

引言：从DES到AES

AES（ Advanced Encryption Standard ）分组密码广泛使用的一种对称密码。AES提出是为了替代DES，DES存在的问题在业内饱受诟病：

DES不能够抵抗蛮力攻击，在1999年NIST(National Institute of Standards and Technology)就明确要求使用3DES抵抗蛮力攻击。但是DES的软件实现并不十分高效，而3DES的耗时是DES的三倍多。
DES的分组大小相对较小，每个分组一般为64 bits。
当时的NIST认为抵抗量子计算机攻击，密钥长度应该接近256 bits，而DES的密钥实际为48 bits。不过在现在看来在量子霸权下，256 bits的密钥依然不够看。

所以就上述问题，NIST公开征集的密码标准，所提交的候选方案需要满足以下要求：

分组大小为 128位的分组密码
必须支持三种密码长度: 128位，192位和256位
比提交的其他算法更安全
在软件和硬件实现上都很高效

AES算法概述

DES加密使用Feistel结构，在Feistel网络中每一轮只加密了半个分组：32 bits 的数据。而在AES中，每一轮加密是对整个分组进行加密，所以AES需要的加密轮数 $n_r$ 比DES少的原因。并且 $n_r$ 不是固定的，同秘钥长度有关，下表为AES秘钥长度和 $n_r$ 的关系。

秘钥长度	轮数 $n_r$
128	10
192	12
256	14

首先需要知道，每一轮加密分为三层：字节代换层（Byte Substitution Layer，SubBytes）， 扩散层、秘钥加法层（AddRoundKey ）

image

每一层的作用的作用如下：

秘钥加法层 128位子秘钥和每一轮的输入进行异或运算。

字节代换层 通过提前设置好的S-Box，将16字节（128 bits）映射为4x4的矩阵

扩散层 由两个子层组成，每个子层都是线性操作：

ShiftRows 行移位变化
MixColumn 列混淆变换，将4x4的矩阵合并为16字节

AES同样采用了秘钥编排为每一轮加密生成子秘钥( $k_0, k_1, \dots, k_{n_r}$ )。之后将每一层加密和秘钥编排组合起来，就是AES算法的框架。

image

AES内部结构

加密轮

和DES不同的是AES是面向字节（Byte）的，而DES是面向（Bits）的，即AES处理的最小单位是字节。单轮AES的详细结构如下。定义16字节输入为 $A_0, A_1, A_2, \dots, A_{15}$ 。

image

(1)首先字节会经过一个S-Box。假设 $A_0 = (1000 \, 0100)_2$ ，经过S-Box之后得到的 $B_0$ 为 $A_0$ 在有限域GF( $2^8$ )上的逆元。即在有限域GF( $2^8$ )上， $A_0B_0 = (x^7+x^2)B_0 = 1 mod P(x)$ 其中 $P(x)$ 为GF( $2^8$ )上的不可约多项式。S-Box是事先计算好的，和 $P(x)$ 有关。以下为S-Box示例，对应的 $P(x)=x^8+x^4+x^3+x+1$ 。因为 $A_0 = (1000 \, 0100)_2 = (84)_{hex} \rightarrow x = 8, y=4$ ，所以查表可得 $B_0 = (96)_{hex} = (1001 \, 0110)_2$ 。

image

(2) 对于AES中S-Box每一轮都是相同的，S-Box式一个非线性映射即 $S(a) + S(b) \neq S(a+b)$ 。并且S是双向映射的，即输入和输出一一对应，确保能够解密。

(3) 在SubByte层除了S-Box求逆操作外，有的还会进行一个防射步骤，进而破话有限域的代数结构，能够抵抗针对有限域逆元的攻击。放射即将逆元(8 bits)和一个(8x8)的常量矩阵相乘，在和一个8位的常向量相加。

（1）-（3）就是字节替换层的过程，接下来回进行扩展时层。

(4) ShiftRows 子层 通过上一层之后，我们可以得到状态矩阵（Status Matrix） $B = (B_0, B_1, \dots, B_{15})$ , ShiftRows 子层的操作很简单，只需要按照一定的规则对举证每一行的进行循环移动集合，目的是为了增加AES的扩散属性。如下图所示

image

（5）MixColumn子层 会进行列混淆，以矩阵 $B$ 每一列的4个字节作为一个向量右乘上一个4X4的常量举证，结果作为新矩阵 $C$ 的行，以下面的式子为例：

$\begin{gathered} \begin{pmatrix} C_0 \\ C_1 \\ C_2 \\C_3 \end{pmatrix} \end{gathered} \leftarrow \begin{gathered} \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 &02 &03 \\ 03& 01 &01& 02 \end{pmatrix} \end{gathered} \begin{gathered} \begin{pmatrix} B_0 \\ B_1 \\ B_2 \\B_3 \end{pmatrix} \end{gathered}$

假设经过ShiftRows 子层得到的状态矩阵$B = {25, 25, \dots, 25}，则我们只需要计算：

$02 \cdot 25 = (00000010)\cdot(00100101)=x \cdot (x^5+x^2+1) =\\x^6+x^3+x\\ 03 \cdot 25 = (00000011)\cdot(00100101)=(x+1) \cdot (x^5+x^2+1)=\\x^6++x^5+x^3+x^2+x+1$

由于上述中间值没有大于 $2^8$ 所以不需要mod不可约多项式。所以我们可得到 $C_i$ 为：
$\begin{aligned} &01 \cdot 25=x^{5}+x^{2}+1\\ &01 \cdot 25=x^{5}+\quad x^{2}+1\\ &02 \cdot 25=x^{6}+\quad x^{3}+x\\ &\frac{03 \cdot 25=x^{6}+x^{5}+x^{3}+x^{2}+x+1}{C_{i}=x^{5}+x^{2}+1} \end{aligned}$
所以 $C_i = (0010\,0101)_2=(25)_{hex}$ 。

(6)秘钥加法层 16字节的 $C$ 和16字节的每一轮的子秘钥 $K_i$ 进行异或运算，和GF（2）的加法运算相同。

秘钥编排

128 位秘钥编排

128 位秘钥编排如图所示，初始秘钥 $K=\{K_0, K_1, \dots, K_{15}\}$ ，其中 $K_i$ 的大小为1 byte = 8 bits。整个秘钥编排过程还是比较简单只需要进行异或操作一个g函数。g函数的内部其实进行了一次循环移动和求逆运算。

函数g()的目的有两个:第一，增加密钥编排中的非线性:第二，消除AES中的对称性。这两种属性都是抵抗某些分组密码攻击必要的。

image

从上面的流程图可以得出子秘钥的第一个子分组 $W[4_i](i \in \{1,2,3,\dots,10\})$ 的递推公式为：
$W[4 i]=W[4(i-1)]+g(W[4 i-1])$
其余三个分组的递推公式为：
$W[4 i+j]=W[4 i+j-1]+W[4(i-1)+j]$
在非线性函数g()中，首先将四个字节进行翻转，然后进行S-Box代换，最后和轮系数 $RC[i](i \in \{1,2,3,\dots,10\})$ 相加， $RC$ 的生成规则如下:
$\begin{aligned} R C[1] &=x^{0}=(00000001)_{2} \\ R C[2] &=x^{1}=(00000010)_{2} \\ R C[3] &=x^{2}=(00000100)_{2} \\ \, & \vdots \\ R C[10] &=x^{9}=(00110110)_{2} \end{aligned}$