现在仔细学习整理一下对称加密算法的典型代表——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}\}\)，具体计算为：

  1. 初始：（只含轮密相加）
    • 轮密相加：将\(M\)和原始密钥\(W_0 = K\)异或加密，得到\(M=\text{XOR}(K,M)\)
  2. 重复9轮相同操作：\(i=1,\dots,9\)
    • 字节代换：\(M=f(M)\)
    • 行移位：\(M=g(M)\)
    • 列混淆：\(M=h(M)\)
    • 轮密相加：\(M=\text{XOR}(K_i,M)\)
  3. 第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}\}\)，具体计算为：

  1. 初始：（不含列混淆）
    • 轮密相加：\(M=\text{XOR}(K_{10},M)\)
    • 逆行移位：\(M=g^{-1}(M)\)
    • 逆字节代换：\(M=f^{-1}(M)\)
  2. 重复9轮相同操作：\(i=9,\dots,1\)（注意指标是逆序的）
    • 轮密相加：\(M=\text{XOR}(K_i,M)\)
    • 逆列混淆：\(M=h^{-1}(M)\)
    • 逆行移位：\(M=g^{-1}(M)\)
    • 逆字节代换：\(M=f^{-1}(M)\)
  3. 第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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// S盒
static const int S[16][16] = {
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 };

// 逆S盒
static const int S2[16][16] = {
    0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
    0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
    0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
    0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
    0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
    0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
    0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
    0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
    0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
    0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
    0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
    0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
    0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
    0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
    0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d };

行移位及其逆运算

行移位是一个简单的循环向左移位操作，主要是为了数据的扩散。 当前我们的密钥长度为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\)以列为单位进行操作，下面的+表示按位异或，实际上就是有限域的加法。

  1. 用原始矩阵填充前4列，W(:,0:3)=K

  2. 循环生成W(:,4i:4i+3)，针对第\(4i\)列有额外的运算 

    1
    2
    3
    4
    w(:,4i) = w(:,4i-4) + T_i(W(:4i-1))
    w(:,4i+1) = w(:,4i-3) + W(:4i)
    w(:,4i+2) = w(:,4i-2) + W(:4i+1)
    w(:,4i+3) = w(:,4i-1) + W(:4i+2)

  3. 取扩展密钥K_i = W(:4i:4i+3)

其中针对第\(4i\)列加上了额外的\(T_i\)运算，这依赖于一组直接提供的4字节常量：\(Rcon_1,Rcon_2,\dots,Rcon_{10}\)，具体为 

1
2
3
4
5
6
static const int Rcon[10] = {
    0x01000000, 0x02000000,
    0x04000000, 0x08000000,
    0x10000000, 0x20000000,
    0x40000000, 0x80000000,
    0x1b000000, 0x36000000 };

\(T_i\)运算由以下3部分组成：

  • 字循环：将4个字节的列向量循环上移1个字节，即把 [b0, b1, b2, b3]' 变换成 [b1,b2,b3,b0]'
  • 字节代换：使用S盒进行字节代换
  • 轮常量异或：与轮常量\(Rcon_i\)进行异或

密钥扩充算法的示意图如下

内容填充处理

AES 算法在对明文加密的时候，如果总长度不是128bit的整数倍，最后一个长度不足的块会根据不同的填充模式进行填充，然后再进行加密。

常见的策略有三种：

  1. 不做任何填充，严格要求明文必须是16字节的整数倍；
  2. 在块的末尾补足相应数量的字符，并且每个字节的值等于缺少的字符数；
  3. 在块的末尾补足相应数量的字符，但是只有最后一个字节的值等于缺少的字符数，其它字符填充随机数。

工作模式

前面提到的AES算法描述是对每一个块进行单独加密解密处理的，不同的块之间完全没有联系，这种工作模式称为 ECB 模式，优势是实现简单，利于并行，劣势是安全性较差。

除此之外，还有一种常见的 CBC 模式，它在加密每一个块之前，将当前块的明文和前一个块的密文进行一次异或加密，在不同的块之间建立联系， 对于第一个块的处理则引入一个随机的块（又称作初始向量IV）与之异或。实践中可以将IV与密文一起通过不安全的信道直接传输。

IV起到的作用与哈希算法中的加盐类似，目的是防止同样的明文块始终加密成相同的密文块。

CBC模式的优点是安全性更高，缺点是引入了额外的初值向量IV，增加了复杂度。