AES算法分析

1 AES加密框架

1.1使用多个子密钥---引出扩展子密钥与明文大小有关

1.1.1明文块的划分和大小

1.1.2不同长度子密钥的各个信息

1.1.3扩展子密钥算法---不同子密钥长度有不同算法

1.2把结构分解成函数调用---加密框架

2扩展子密钥

3 S盒替换

4行循环左移

5列混合操作

6 子密钥执行XOR运算

7 AES解密框架

7.1逆S盒

7.2逆列混合矩阵因子

更具体的讲述可以参考《经典密码学与现代密码学》

但是，在该文章中P158介绍 AES加密中的列混合矩阵因子是：

02 03 01 01

01 02 03 01

01 01 01 03  //这一行应该是01 01 02 03

03 01 01 02

其实第三行是错误的，可以推论出这个矩阵因子应该是有规律的，它的规律就是，从第二行开始，它是02 03 01 01需要循环右移一位，后面的规律是，下一行是前一行循环右移一位。

还有，在扩展子密钥的算法中，应当是 i 是4个倍数是，才进行特殊处理。

而且，扩展子密钥的时候，改书只讲了128Bit的子密钥，其实，对于256Bit的子密钥，有不同的扩展算法。

1 AES加密框架

如下是整个ASE加密结构：

从这个ASE加密的框架可以看出，我们只需要：子密钥 和 明文，就可以经过AES算法加密，得到密文。

那么，在整个加密过程中，有4个执行加密过程：

1 KeyAdd  2 Substition  3 ShiftRow  4 MixColumn

其中，在循环轮加密的时候，执行步骤是：

1 Substition  2 ShiftRow  3 MixColumn  4 KeyAdd

就是循环执行这4个过程。

而最后一次加密的时候，就执行如下三个步骤：

1 Substition  2 ShiftRow  3 KeyAdd

所以，最后一轮加密，比在轮密钥中，少了 MixColumn 这个步骤。

1.1使用多个子密钥---引出扩展子密钥与明文大小有关

从上面的结构中，可以看出，每次执行KeyAdd运算的时候，都需要一个子密钥，那么，就需要多个子密钥。

但是，我只提供了一个初始的密钥，那么，AES加密中，就提供了一个算法来生成子密钥。

所以，在执行一切运算之前，就要根据一定的算法来生成子密钥。

就是所谓的扩展子密钥。

那么，要扩展多少个子密钥，就看要执行多少次KeyAdd运算。

从上面图中，可以看出，如果只执行一次循环，就要执行3次KeyAdd运算，所以，就需要3个子密钥。

那么，如果执行N次需要，就需要N+2个子密钥，如果除掉初始提供的1个子密钥，就需要生产N+1个子密钥。

那么，N等于多少？这个，就根据我们要执行加密的密钥长度来决定。

在AES加密中，密钥可以是128Bit, 192Bit, 256Bit.

下面先讲解每次加密，使用明文的大小，就可以知道扩展子密钥的长度。因为，并不是每次扩展的子密钥的长度，都是跟当前初始密钥的长度一样。

因为，密钥是用来对明文加密，而AES加密算法中，使用子密钥，就是明文中每一个字节与密钥中每一个字节执行XOR（异或）运算。有如下的操作：

所以，每次使用的密钥，都有明文块大小一样。

那么，下面介绍明文块的大小，就可以知道，为什么，在扩展子密钥的时候，扩展的子密钥，并不是与本身的长度一样。

1.1.1明文块的划分和大小

AES首先是将明文按字节分成“列”，其中，前4个字节为第一列，然后，接下去的4个字节作为第二列，一个块是128位，那么可以组成4 x 4 的矩阵，如下图：

假设，明文只有abcde这5个字节，那么，可以在abcde在5个字节后面扩展0，成为16个字节，这样，得到一个明文块，使用这个明文块来解密。

其实，可以推论，如果明文是5个字节，如果，加密之后，得到5个密文，那么，破解方就可以假设明文是5个字节，这样会加大破解成功概率。

如果明文是5个字节，经过加密之后，得到16个密文，同样的10个明文，加密，得到16个密文，那么，就加大破解难道。

如果明文是1024个字节，那么，可以每次读取明文的16个字节来加密，最后，把密文在合并起来。例如有要加密的数据如下：

Input = 61 62 63 64 65 66 69 67 68

那么，转换成每4个字节一列，存放到 State 数组中如下：

61 65 68 0

62 66 0  0

63 69 0  0

64 67 0  0

所以，可以知道，每次要加密的明文是16个字节。那么，在执行AddKey的时候，算法如下：

所以，每次使用16个字节的密钥来与明文执行XOR操作。

那么，在扩展子密钥的时候，每次扩展16个子密钥就可以了，但是，为什么会有128bit, 192bit, 256bit这样的密钥，这是在扩展子密钥的时候，是在基于初始化密钥的基础上扩充的，那么，在根据如下的扩充子密钥算法来生产子密钥：

其中，i 是要扩充的第几个密钥数组，例如 128Bit的子密钥，是16个字节，每个4个字节分成一个组，有w(0), w(1), w(2), w(3)，那么，开始扩展的时候，第一个w(i) 就是 i = 4

如果是192Bit的子密钥，就是24个字节，每4个字节分成一组，就有w(0), w(1), w(2), w(3), w(4), w(5) 这样，在扩展子密钥的时候，第一个w(i) 就是 i = 6.

所以，可以看出，对于不同长度的子密钥，其扩展子密钥的时候，会有不同的计算方式，但是，无论是128Bit，192Bit 还是256Bit，每次只扩展16个字节子密钥，因为，要加密的明文块是16个字节，我们需要的操作，只是明文的每个字节与子密钥对应执行XOR运算，如下图：

1.1.2不同长度子密钥的各个信息

下面整理对不同长度子密钥的各个信息：

1 各种长度子密钥，其对于的明文，都是以16个字节的明文为单位进行加密。

2 扩展子密钥的时候，各种长度的初始子密钥，其每次都扩展16个字节子密钥，可以参考上面1.1.1，因为，要与明文块大小一样。

3 执行轮循环加密的轮数：128Bit 执行10轮，192Bit执行12轮，256执行14轮。

4 扩展子密钥长度：从AES加密框架，可以看出，如果有N次轮加密，那么，需要执行N+2次KeyAdd操作，除了提供的一次初始密钥之外，还使用N+1次。

4.1对于128Bit，执行10轮密钥，所以要扩展10+1 = 11 次，每次扩展16个字节，所以扩展11*16 = 176个字节。那么，总的密钥长度是加上初始提供的16个字节，就有192个字节。

4.2对于192Bit，执行12轮加密，所以要扩展12+1 = 13 次，每次扩展16个字节，所以扩展 13*16 = 208 个字节，那么，总的密钥长度是加上初始提供的24个字节，就有232个字节。

4.3对于256Bit，执行14轮加密，所以要扩展14+1 = 15次，每次扩展16个字节，所以，扩展15*16=240个字节，那么，总的密钥长度是加上初始提供的32个字节，就有272个字节。

可以总结成如下表：

初始密钥长度，单位Bit	128	192	256
明文分组块长度，单位Bit	128(16个字节)	128	128
轮密钥的轮数	10	12	14
每轮生产密钥的长度	16个字节	16个字节	16个字节
扩展子密钥长度	176个字节	298个字节	240个字节
总密钥长度	192个字节	232个字节	272个字节

1.1.3扩展子密钥算法---不同子密钥长度有不同算法

在《经典密码学与现代密码学》中介绍的扩展子密钥，只是128Bit的子密钥扩展算法，该算法还使用与192Bit的子密钥，如果是256Bit的子密钥，就有一点变化。

具体可以参考收集的文档《AES全面介绍》

1.2把结构分解成函数调用---加密框架

根据上面的分解，我们知道了整个加密过程中，在看AES的整体结构：

我们可以把要执行的功能抽象成函数，那么有如下的函数：

1 KeyExpansion(); 用于扩展子密钥

2 Subsition(); S盒替换

3 ShiftRow(); 行循环左移

4 Mixcolumb(); 列混合操作

5 KeyAdd(); 子密钥执行XOR操作

8 Round(); 轮循环加密操作

9 FinalRound(); 最后一轮加密操作

所以，有如下的结果：

AES()

{

   KeyExpansion(); //扩展子密钥

   For(int i = 0;  i < 轮数;  i++)

   {

       Round(); //轮循环加密

   }

   FinalRound();  //最后一次加密

}

Round()

{

   Subsition(); //S盒替换

   ShiftRow(); //行循环左移

   Mixcolumn(); //列混合操作

   KeyAdd(); //与子密钥执行XOR操作

}

FindRound()

{

   Subsition(); //S盒替换

   ShiftRow(); //行循环左移

   KeyAdd(); //与子密钥执行XOR操作

}

如下是一个截图：

2扩展子密钥

因为，在每一步中都需要执行KeyAdd(); 操作，每一次都使用不同的一个密钥，所以，在一起加密之前，先使用初始密钥，扩展子密钥。

根据如下的扩充子密钥算法来生产子密钥，注意，改算法只是适用于128Bit和192Bit位密钥的加密，对于256Bit密钥的加密，有一些改变，具体可以参考收集的《AES全面介绍》：

其中，i 是要扩充的第几个密钥数组，例如 128Bit的子密钥，是16个字节，每个4个字节分成一个组，有w(0), w(1), w(2), w(3)，那么，开始扩展的时候，第一个w(i) 就是 i = 4

如果是192Bit的子密钥，就是24个字节，每4个字节分成一组，就有w(0), w(1), w(2), w(3), w(4), w(5) 这样，在扩展子密钥的时候，第一个w(i) 就是 i = 6.

注意：在第4步的时候，只有第一个字节e与r(i)执行XOR操作，其它三个字节不执行。

3 S盒替换

S盒是一个16x16的矩阵，我需要执行的S盒替换操作如下：

例如上图，就是，把明文中的A1.2在S盒中找到一个对应的元素B1.2，然后，就使用这个B1.2来代替A1.2这个元素。

那么，S盒它具有一个构造的过程，具体可以参考《AES密码盒算法的详细实现过程及其应用》，最终构造得出的S盒如下：

可以看到，他是一个16行16列的矩阵。

那么替换的算法，是：

假设有一个字节的数据是0X6A，那么，把这个数据的高4位和低4位拆开，得到：

高4为为0X06，低4位为0X0A，那么，就以高4位为行，低4位为列，在S盒中找到相应的元素，就是在0X06行0X0A列中找到0X02这个数据。

这样，就可以使用0X02这个数据来代替0X0A这个数据，以这样的算法，把16个字节的明文替换完。

4行循环左移

经过上面的S盒替换之后，需要对每一行的数据执行左循环移动，移动的规律是：

第一行左循环移动0位

第二行左循环移动1位

第三行左循环移动2位

第四行左循环移动3位

有如下的操作：

5列混合操作

在轮循环操作中，需要在执行行循环左移之后，就执行列混合操作，有如下的介绍：

所以，可以看到，并不是执行真正的两个矩阵相乘的操作，只是，按矩阵相乘的规则，对应元素相乘，但是，最后，不是相加，而是相异或操作。

6 子密钥执行XOR运算

最后一个阶段，就是把经过上面处理的数据，与子密钥执行XOR运算，执行元素的规则是如同两个矩阵相加一样，对应矩阵元素执行XOR元素，有如下图：

7 AES解密框架

从上面加密过程中，我们可以知道，在S盒替换和列混合操作中，使用一个矩阵因子来执行“替换”操作，其它的步骤，都只是执行一些换上变化。

例如，行循环左移操作，在解密的时候，执行对应的行循环右移操作就可以了。还有，异或操作，假设有：Var = 0111 1100  Mix = 1111 0011 ，那么执行 Var XOR Mix ，是使用Mix来加密Var：

0111 1100

 1111 0011

 1000 1111

那么， 解密Var 的时候，只需要把结果与Mix在执行XOR就可以了，有如下：

 1000 1111

 1111 0011

 0111 1100

所以，执行XOR操作有可逆的运算。但是，对于替换操作中使用到的矩阵因子，就有不同，那么：在加密中使用到的S盒和解密中使用的S盒不同，而且，执行列混加密的时候，只有矩阵因子和解密的时候不同。下面有介绍。

7.1逆S盒

7.2逆列混合矩阵因子

那么，矩阵因子如下：

0e  0b  0d  09

1. 0e  0b  0d

0d  09  0e  0b

0b  0d  09  0e

使用这个矩阵因子，与密文执行加密的时候，相应的操作就可以了。

韦凯峰Linux编程学堂，一瓶啤酒的价格，零基础入门，掌握Linux C/C++编程，Linux系统编程，用技术改变生活，改变自己，改变世界！