密码学笔记——AES算法
现在仔细学习整理一下对称加密算法的典型代表——AES算法，并进行C++实现。
算法结构
这里我们只考虑AES-128，即密钥是128bit 的具体算法。
对于输入的明文，首先经过某种扩充处理，保证长度是128bit 的整数倍，然后对明文进行分组，每一组128bit 即16个字节的数据，在具体算法描述中通常会按列拼接为一个$4\times 4$的字节矩阵，并称为状态矩阵。
对于每一个分组执行相同的加密处理得到密文，将每一组的密文拼接即可得到最终的密文。
我们主要考虑单个分组的处理，下面的明文以及密钥均为16个字节的数据，
记明文为$P$，密钥为$K$，密文为$C$。
首先我们要进行密钥的扩展，从16字节的原始密钥$K$经过某种扩展算法得到10个辅助密钥$K_1,\dots,K_{10}$，每一个$K_i$均是16字节的，对应一个状态矩阵，记$K_0 = K$。
加密算法大致分成10轮（9轮是完整的，还有1轮不完整，以及额外的初始步），输入明文$M=P$、密钥$K$以及扩展密钥${K_1,\dots,K_{10}}$，具体计算为：
- 初始：（只含轮密相加）
- 轮密相加：将$M$和原始密钥$W_0 = K$异或加密，得到$M=\text{XOR}(K,M)$
- 重复9轮相同操作：$i=1,\dots,9$
- 字节代换：$M=f(M)$
- 行移位：$M=g(M)$
- 列混淆：$M=h(M)$
- 轮密相加：$M=\text{XOR}(K_i,M)$
- 第10轮：（不含列混淆）
- 字节代换：$M=f(M)$
- 行移位：$M=g(M)$
- 轮密相加：$M=\text{XOR}(K_{10},M)$
最终得到当前分组的密文，整体记作$C = M = E(K,P)$。
加密过程如下图所示
解密操作是完全反过来的，输入密文$M=C$、密钥$K$以及扩展密钥${K_1,\dots,K_{10}}$，具体计算为：
- 初始：（不含列混淆）
- 轮密相加：$M=\text{XOR}(K_{10},M)$
- 逆行移位：$M=g^{-1}(M)$
- 逆字节代换：$M=f^{-1}(M)$
- 重复9轮相同操作：$i=9,\dots,1$（注意指标是逆序的）
- 轮密相加：$M=\text{XOR}(K_i,M)$
- 逆列混淆：$M=h^{-1}(M)$
- 逆行移位：$M=g^{-1}(M)$
- 逆字节代换：$M=f^{-1}(M)$
- 第10轮：（只含轮密相加）
- 轮密相加：将$M$和原始密钥$W_0 = K$异或加密，得到$M=\text{XOR}(K,M)$
最终得到当前分组的原文，整体记作$P = M = D(K,C)$。
解密过程如下图所示
AES算法主要由下面的基本操作组成：
- 轮密相加 (Add Round Key)
- 字节代换及其逆运算 (SubByte)
- 行移位及其逆运算 (Shift Rows)
- 列混淆及其逆运算 (Mix Column)
由于轮密相加操作非常简单，只是简单的异或，它的逆运算就是自身，我们只需要关注剩下的三类基础操作及其逆运算的实现。
算法细节
字节代换及其逆运算
AES算法的字节代换及其逆运算在程序实现中就是两个简单的查表操作，程序中通过硬编码定义了一个S盒和一个逆S盒，均为$16\times 16$的字节矩阵。
在字节代换或逆运算时，对每一个字节的原始数据，取字节的高4位作为行索引，低4位作为列索引，取出S盒或者逆S盒中对应索引的元素作为输出。
S盒和逆S盒具体为
1 | // S盒 |
行移位及其逆运算
行移位是一个简单的循环向左移位操作，主要是为了数据的扩散。
当前我们的密钥长度为128bit ，将16字节的数据$M$按列拼接为4阶状态矩阵的形式，行移位的具体操作为：
- 第1行左移0个字节
- 第2行左移1个字节
- 第3行左移2个字节
- 第4行左移3个字节
逆运算也是显然的：
- 第1行右移0个字节
- 第2行右移1个字节
- 第3行右移2个字节
- 第4行右移3个字节
列混淆及其逆运算
AES算法的列混淆及其逆运算在数学中是两个有限域意义上的矩阵乘法，不妨将矩阵记作$C,C^{-1}$，均为$4\times 4$的字节矩阵。
在列混淆或逆运算时，通过$C$或$C^{-1}$左乘原始数据的$4\times 4$状态矩阵，得到的$4\times 4$矩阵作为结果。
这里的乘法涉及到有限域$GF(2^8)$上的乘法运算，首先将一个字节的二进制编码$(a_7,a_6,a_5,a_4,a_3,a_2,a_1,a_0)$对应为一个$F_2$上的多项式
$$
a_0 + a_1 x + a_2 x^2 + \dots + a_7 x^7
$$
加减法运算就是每一个多项式系数在模2的意义下进行的
$$
\begin{aligned}
A &= a_0 + a_1 x + a_2 x^2 + \dots + a_7 x^7 \
B &= b_0 + b_1 x + b_2 x^2 + \dots + b_7 x^7 \
C &= A + B = c_0 + c_1 x + c_2 x^2 + \dots + c_7 x^7
\end{aligned}
$$
其中 $c_i = a_i + b_i \pmod 2$。
乘法比较复杂，首先对多项式进行乘法得到
$$
C = A \times B = c_0 + c_1 x + c_2 x^2 + \dots + c_{14} x^{14}
$$
其中
$$
c_0 = a_0 b_0 \pmod 2, \dots, c_{14} = a_7 b_7 \pmod 2
$$
这里乘积的次数超过了$x^7$，因此还要对一个八次的本原多项式取模，AES算法使用的本原多项式为
$$
1 + x + x^3 + x^4 + x^8
$$
具体的细节略。
密钥扩充算法
现在我们关注如何从16字节的原始密钥$K=K_0$扩展得到10个辅助密钥$K_1,\dots,K_{10}$，每一个$K_i$均是16字节的一个状态矩阵。
首先生成一个4行44列的字节矩阵$W$，下面主要对$W$以列为单位进行操作，下面的+表示按位异或，实际上就是有限域的加法。
- 用原始矩阵填充前4列，
W(:,0:3)=K - 循环生成
W(:,4i:4i+3)，针对第$4i$列有额外的运算
1 | w(:,4i) = w(:,4i-4) + T_i(W(:4i-1)) |
- 取扩展密钥
K_i = W(:4i:4i+3)
其中针对第$4i$列加上了额外的$T_i$运算，这依赖于一组直接提供的4字节常量：$Rcon_1,Rcon_2,\dots,Rcon_{10}$，具体为
1 | static const int Rcon[10] = { |
$T_i$运算由以下3部分组成：
- 字循环：将4个字节的列向量循环上移1个字节，即把
[b0, b1, b2, b3]'变换成[b1,b2,b3,b0]' - 字节代换：使用S盒进行字节代换
- 轮常量异或：与轮常量$Rcon_i$进行异或
密钥扩充算法的示意图如下
内容填充处理
AES 算法在对明文加密的时候，如果总长度不是128bit的整数倍，最后一个长度不足的块会根据不同的填充模式进行填充，然后再进行加密。
常见的策略有三种：
- 不做任何填充，严格要求明文必须是16字节的整数倍；
- 在块的末尾补足相应数量的字符，并且每个字节的值等于缺少的字符数；
- 在块的末尾补足相应数量的字符，但是只有最后一个字节的值等于缺少的字符数，其它字符填充随机数。
工作模式
前面提到的AES算法描述是对每一个块进行单独加密解密处理的，不同的块之间完全没有联系，这种工作模式称为 ECB 模式，优势是实现简单，利于并行，劣势是安全性较差。
除此之外，还有一种常见的 CBC 模式，它在加密每一个块之前，将当前块的明文和前一个块的密文进行一次异或加密，在不同的块之间建立联系，
对于第一个块的处理则引入一个随机的块（又称作初始向量IV）与之异或。实践中可以将IV与密文一起通过不安全的信道直接传输。
IV起到的作用与哈希算法中的加盐类似，目的是防止同样的明文块始终加密成相同的密文块。
CBC模式的优点是安全性更高，缺点是引入了额外的初值向量IV，增加了复杂度。