加密流程

背景

1997年7月，借助于互联网上的14000多台计算机，花费了90天时间破解了DES密钥。6个月后，用这种方法破解DES所花费的时间减少了39天。1998年7月，一台特殊构造的计算机（名为Deep Crack）只用了56个小时就破解了一个DES密钥。显然，DES不再是一个可靠的加密系统。为此，美国国家标准局提出了一项取代DES的投标计划，这就是高级加密标准AES（Advanced Encryption Standard）。对于DES算法的改进工作从1997年开始公开进行。
1997年9月12日，发布了征集算法的正式公告和具体细节，其要求如下：
（1）应是对称分组加密，具有可变长度的的密钥（128、192或256位），具有128位的分组长度；
（2）应比三重DES快、至少与三重DES一样安全；
（3）应可应用于公共领域并能够在全世界范围内免费使用；
（4）应至少在30年内是安全的。

AES的评选分三个阶段：

1998年8月12日，在首届AES候选会议上，公布了AES的15个候选算法。
1999年3月，在第2届AES候选会议上，经过对全球各密码机构和个人对候选算法分析结果的讨论，从15个候选算法中选出了5个，分别是：MARS,RC6,Rijndael, Serpent , Twofish。
2000年4月13日至14日，召开了第3届AES候选会议，继续对最后5个候选算法进行讨论。2000年10月2日，NIST宣布Rijndael作为高级加密标准AES。

AES的描述

AES也是一个典型的迭代型分组密码，分组长度：128比特。密钥长度： 128位、192位、256位，分别记为AES-128、AES-192、AES-256。
加密轮数依赖于所选择的子密钥长度：
  • 对于128位的密钥长度，加密的轮数为10；
  • 对于192位的密钥长度，加密的轮数为12；
  • 对于256位的密钥长度，加密的轮数为14。

状态矩阵：将128比特状态数据依次分为16个字节。
数据单元：比特，字节和字。

数学基础

字节的运算：加法、乘法；字的运算：加法、乘法。

字节的运算

字节的运算求有限域的运算。
的表示：
设字节。
的构造：
为系数在上任意次数的多项式，为系数在上的8次不可约多项式，其中：。

字节的加法

加法（“+”）：两个字节对应多项式系数的比特异或。即两个字节逐比特异或。
例：23+64=？ （十六进制表示）

字节的乘法

乘法（“•”） ：两个字节对应多项式的乘积模上二元域上的8次不可约多项式。

字的表示

字节：
，其中。
字：
，其中。

字的加法

加法（“+”）：两个字逐比特异或。
例：D3 64 0F 00+E3 23 81 AB=？（16进制表示）

字的乘法

乘法（“x”） ：两个字对应字多项式的乘积，规定该乘法必须要取模多项式。
多项式形式：

矩阵形式：


单轮加密变换

步骤：输入→行移位→列混合→密钥加→输出。
AES中的操作都是以字节为对象的，操作所用到的变量是由一定数量的字节构成。输入的明文消息长度是128位，将其表示为16个字节，初始化状态矩阵如下：

字节代替

字节代替变换对消息矩阵中的每个元素（每个元素对应每一个字节）进行一个非线性替换，任一个非零元素（即由不可约的8次多项式生成的伽罗瓦域）被下面的变换所代替：。
S盒的数学表达式（上式）也就是：
有限域中两个元素的乘法为模2 元域GF(2)上的一个8次不可约多项式的多项式乘法。对于AES这一8次不可约多项式为：。
这里b为固定的向量值63（用二进制表示）。上述变换的非线性性质来自于逆（即 x 在阶为 8的伽罗瓦域中的逆元），如果将该变换直接作用于变量x ，那么该变换就是一个线性变换！另外，由于常数矩阵A是一个可逆矩阵，所以函数ByteSubs（State）是可逆的。
AES算法的“S-盒”：

查表方式：状态矩阵中一个字节作为S盒的输入，把该字节的高4比特作为行值，低4比特作为列值，以这些行、列值作为索引从S盒的对应位置取出元素作为输出。
所以y=01。这个对应关系如果按书中公式（2-1）计算可得出同样结果。
行移位
行移位在状态矩阵的每行上进行操作。
列混合
列混合对状态矩阵的每一列进行操作。
首先取当前的状态矩阵中的一列，定义为：

把这一列表示成一个三次多项式：。
其中的系数是字节，所以多项式定义在上。
列S(x)上的运算定义为：将多项式S(x)乘以一个固定的3次多项式C(x)，使其与互素，然后和多项式进行取模运算。具体如下：，其中：，的系数也是中的元素。
的矩阵形式：

轮密钥加

密钥加将轮密钥和状态矩阵中的元素逐逐位地进行异或运算。其中轮密钥使用一个固定的密钥扩展方案产生，每一轮的轮密钥是不同的。
AES一***作示例：
假设第i轮消息表示成十六进制：42 6f 62 20 6c 6f 6f 6b 20 61 74 20 74 68 69 73
写成状态矩阵形式为：
42 6c 20 74
6f 6f 61 68
62 6f 74 69
20 6b 20 73
字节代替：在“S－盒”中查找出与每个输入元素对应的元素，从而生成如下的输出矩阵：

行移位：
列混合：对于第一列进行如下的转换

根据以上运算过程，可以计算出消息矩阵与固定矩阵相乘的结果矩阵为：
a6 19 66 4b
45 d1 be 91
9c d0 d0 07
4b 46 23 74
轮密钥加：子密钥为
01 a3 90 12
e1 44 20 11
cc 73 04 a9
59 06 30 b4
与列混合的结果异或得到
a7 ba f3 59
a4 95 9e 80
50 a0 d4 a6
12 40 13 c0
将得到的第一轮输出与初始输入进行比较，转换成二进制，可以发现在全部的128位中有76位发生了改变，而这仅仅是一轮。经过循环迭代加密过程的运算，将得到最终的加密消息。

密钥扩展方案、解密流程

密钥扩展方案分两个阶段，第一阶段：种子密钥生成扩展密钥，第二阶段：轮密钥的获取。
若，则，其中，若则。
解密流程：

单轮解密变换：输入→逆字节代替→逆列移位→逆列混合→逆轮密钥加→输出。
解密算法中的轮密钥：
加密密钥：，
解密密钥：。

简化轮AES的攻击

  • 平方攻击
  • 碰撞攻击
  • 不可能差分攻击
  • 中间相遇攻击（最有效）
针对AES的中间相遇攻击新结果
分组密码 轮数 时间复杂度 来源
AES-128 7 299 2013年欧密会
AES-192
 9 2186.5 2014年FSE
AES-256
 9 2203 2013年欧密会
时间复杂度单位：AES加密次数。

全轮AES的攻击

  • biclique攻击：特殊的穷举搜索
针对AES的biclique攻击新结果

分组密码 轮数 时间复杂度 来源
AES-128 10 2126.18 2011年亚密会
AES-192
 12 2189.4 2011年亚密会
AES-256
 14 2254.42 2011年亚密会
时间复杂度单位：AES加密次数。