AES算法

简介

AES,高级加密标准（英语：Advanced Encryption Standard，缩写：AES），在密码学中又称Rijndael加密法，是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。严格地说，AES和Rijndael加密法并不完全一样（虽然在实际应用中二者可以互换），因为Rijndael加密法可以支持更大范围的区块和密钥长度：AES的区块长度固定为128 比特，密钥长度则可以是128，192或256比特；而Rijndael使用的密钥和区块长度可以是32位的整数倍，以128位为下限，256比特为上限。

原理

基本术语

字节

AES基本处理单位为字节，在AES中字节可以以有限域上的多项式表示
$b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x+b_0$
例：字节 01100011（0x63）：$x^6+x^5+x+1$

状态

AES的操作在称为状态(state)的二维字节数组上进行。状态由4行字节组成，每行长度为(分组长度/32)个字节。在实际实现中将每一列的4个字节作为32位字。
例：长度为128位的分组数据块
F6 14 46 C1 A6 8C EA 53 82 48 26 A7 A4 7F 19 14
| F6 | A6 | 82 | A4 |
| :—–:| :—-: | :—-: | :—-: |
| 14 | 8C | 48 | 7F |
| 46 | EA | 26 | 19 |
| C1 | 53 | A7 | 14 |

数学基础

加减法

有限域上加减法是通过对应多项式中相同次幂系数相加减后模2来实现的，加法也可以看作异或操作。

乘法

对应多项式相乘再模$x^8+x^4+x^3+x+1$

乘x

多项式乘x得到$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x$
模$x^8+x^4+x^3+x+1$约简，$b_7=0$则为最简，不为零则减去$x^8+x^4+x^3+x+1$。
这种乘法在AES中称作xtime()

算法描述

AES输入、输出分组及状态数组的长度都是128位，即Nb(分组长度/32)=4，密钥K长度为128/192/256位，即Nk=4/6/8。轮数用Nr表示，Nk=4时，Nr=10，Nk=6时，Nr=12，Nk=10时，Nr=14。

加密过程

将输入复制到状态数组。进行一个初始轮密钥加，然后执行轮函数Nr次，其中最后一轮不同于前Nr-1轮。最后得到密文。
轮函数有四个组成部分：SubBytes(),ShiftRows(),MixColumns(),AddRoundKey()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
cipher(byte in[4][Nb],byte out[4][Nb],dword dw[Nb][Nr+1])
{
    byte state[4][Nb]
    state=in
    AddRoundKey(state,dw[0][Nb-1]) //初始轮密钥加
    for(i=0;i<Nr-1;i++) //Nr-1轮轮函数
    {
        SubBytes(state)
        ShiftRows(state)
        MixColumns(state)
        AddRoundKey(state,dw[i*Nb,(i+1)*Nb-1])
    }
    SubBytes(state)
    ShiftRows(state)
    AddRoundKey(state,dw[Nr*Nb,(Nr+1)*Nb-1])
    out=state
}

SubBytes()

字节代换，AES定义了一个16x16的S-box。
在这里插入图片描述
以状态数组每个元素高4位作行标，低4位作列标，取出S-box中元素作为操作结果。

ShiftRows()

状态数组第一行保持不变，第二行循环左移一个字节，第三行循环左移两个字节，第四行循环左移三个字节。

MixColumns()

以列为单位作变换
$\begin{bmatrix}s_{0,c}\s_{1,c}\s_{2,c}\s_{3,c}\\end{bmatrix}=\begin{bmatrix}02&03&01&01\01&02&03&01\01&01&02&03\03&01&01&02\end{bmatrix}\begin{bmatrix}s_{0,c}\s_{1,c}\s_{2,c}\s_{3,c}\\end{bmatrix}$

AddRoundKey()

将状态中元素同轮密钥通过简单的异或运算相加。轮密钥是由密钥通过密钥扩展生成的，也可看做一个状态数组。
密钥扩展：
将密钥进行处理，生成Nb(Nr+1)个32位双字，为轮函数提供密钥。
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

解密过程

加密算法的逆过程，解密轮函数也有四部分：
InvShiftRows(ShiftRows的逆过程):执行相应的向右位移
InvSubBytes(SubBytes的逆过程):在Inverse S-box中查表操作
InvMixColumns(MixColumns的逆过程):乘矩阵$\begin{bmatrix}0e&0b&0d&09\09&0e&0b&0d\0d&09&0e&0b\0b&0d&09&0e\end{bmatrix}$
AddRoundKey为异或操作，逆过程是其本身。

具体实现

实际软件实现采用了空间换时间的方法，与上述过程不同,常常将轮函数的几个步骤合并为一组查表操作。
实现过程中定义了4个T表，每个T表都有256个4字节的32位双字（共4KB），以此将SubBytes，ShiftRows，MixColumns合并为简单的查表操作。AddRoundKey可以通过在每一列上执行一个32位异或来实现。