高级加密标准AES

鉴于DES可以被破解和加密效率不高的缺陷，NIST于1997年开始公开征集新的高级加密标准AES
选拔标准是分组长度为128位的分组密码、支持128/192/256三种长度的密钥、软硬件效率高
2000年Rijmen提出的Rijndael算法被NIST选为高级加密标准AES，并于2001年正式发布

AES的基础是有限域$GF(2^8)$上的运算，其中选择的素多项式是$m(x)=x^8+x^4+x^3+x+1$
有关有限域的基本概念可以参考密码学的近世代数基础

AES总体结构

如图所示AES共有N轮迭代，除最后一轮迭代外，每一轮迭代包含字节代替、行位移、列混淆和轮密钥加4个部分，而最后一轮则不包含列混淆，此外第1轮迭代前有一次轮密钥加

密钥经过密钥扩展算法后，按顺序每4个字（16字节）作为一次迭代的密钥

AES的迭代轮数N是于密钥长度相关的，若密钥为128位（4个字），则扩展为44字，对应10轮；若密钥为192位则对应12轮；若为256位则对应14轮

aes_structure

此外加密过程中消息和密钥是矩阵形式，明文/密钥的16字节将按列存储到一个4×4矩阵中，上述轮密钥加就是用消息矩阵和密钥矩阵按对应位置直接异或

AES的一个显著特征就是它不是Feistel结构
而是每一轮都用代替和混淆将整个数据分组作为单一矩阵处理

aes_mat

字节代替

字节代替定义了一个16×16的字节表格，称为S盒
该操作对消息矩阵的每一个字节，以高4位作为行号，低4位作为列号，查找S盒替换即可

S盒的构造是字节代替的重点

第一步，按从左到右从上到下的顺序升序初始化S盒，也即第y行x列处初始化为{yx}
例如第一行依次为00, 01, …, 0F，第二行依次为10, 11, …, 1F，依此类推

第二步，把S盒中每个字节映射为它在有限域$GF(2^8)$中的逆

第三步，对S盒中每个字节(记为$b=b7b_6…b_0$)做如图矩阵乘法所示的变换
其中乘法为逻辑与，加法为异或，该变换也可以表示为
$b_i’=b_i\oplus b{(i+4)\mod 8}\oplus b{(i+5)\mod 8}\oplus b{(i+6)\mod 8}\oplus b_{(i+7)\mod 8}\oplus c_i$，其中$c=0x63$

为了解密，我们还需要计算逆字节代替所需要的逆S盒
逆S盒的构造方法是初始化后先做上述第三步的逆变换，然后再对每个字节求其$GF(2^8)$中的逆

aes_sbox

行移位

行移位操作很简单，消息矩阵第1行不变，第2、3、4行分别循环左移1、2、3位，逆行移位则是右移
该操作确保某一列的4个字节被分别移到4个不同列

aes_rowshift

列混淆

列混淆使用固定的变换矩阵对消息做如下变换

其中运算遵循$GF(2^8)$上的运算，即每个字节转换为一个8次多项式进行运算，结果再转换回8位字节
素多项式为上文中提到的 $m(x)=x^8+x^4+x^3+x+1$

以下图的变换结果中第一行第一列为例

$\begin{aligned} &0x87\cdot 0x2=(x^7+x^2+x+1)x=(x^8+x^3+x^2+x)\mod m(x)=x^4+x^2+1=0x15 \\ &0x6E\cdot 0x3=(x^6+x^5+x^3+x^2+x)(x+1)\mod m(x)=x^7+x^5+x^4+x=0xB2 \\ &0x46\cdot 0x1=(x^6+x^2+x)1\mod m(x)=x^6+x^2+x=0x46 \\ &0xA6\cdot 0x1=(x^7+x^5+x^2+x)1\mod m(x)=x^7+x^5+x^2+x=0xA6 \\ \end{aligned}$

因此$0x15\oplus0xB2\oplus0x46\oplus0xA6=0x47$

aes_mixcol_samples

对于逆列混淆，则有如下变换，不难验证在有限域$GF(2^8)$上两变换矩阵互为逆

aes_demixcol

密钥扩展

此处以128位密钥为例说明扩展，其伪码如下图所示
算法输入为4字密钥，输出为44字的密钥序列，保存于字数组w[44]中

128位密钥首先被按列转换为密钥矩阵，并将密钥矩阵1~4列的4个字分别填入w[0]~w[3]
之后对于$w[i]$，若$i\mod 4\neq0$，则$w[i]=w[i-4]\oplus w[i-1]$
若$i\mod 4=0$，则$w[i]=w[i-4]\oplus S(R(w[i-1]))\oplus Rcon[i/4]$

其中$R$表示字循环，使一个字的四个字节循环左移一个字节，即若输入字$[b_0b_1b_2b_3]$，则输出$[b_1b_2b_3b_0]$
$S$表示用$S$盒进行字节代替，此处的S盒与上述加密过程的S盒相同
$Rcon$为轮常量，每轮的轮常量均不同，其定义如下，其中乘法定义在域$GF(2^8)$上

$\begin{aligned} & Rcon[j]=(Rc[j],0,0,0)\\ & RC[1]=1\\ & RC[j]=2\cdot RC[j-1] \end{aligned}$

由该公式可以得出$RC[10]={0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,0x1B,0x36}$

aes_keyextend