第六讲 高级加密标准(AES)

1997年1月2日，美国国家标准与技术研究所(NIST)宣布启动设计新的对称分组加密算法作为新一代加密标准替代DES。新的加密标准将被命名为高级加密标准(AES)。不同于暗箱设计过程的DES，AES的设计方案于1997年9月12日向全世界公开征集。

AES需要满足下列要求 (1) 必须详细和公开说明对称加密算法的设计原理。 (2) 算法必须支持最小128比特的消息分组，密钥长度可以为128，192，256比特，而安全强度至少达到三重DES但效率应该高于三重DES。 (3) 算法适合于在各种硬件设备上执行。 (4) 如果算法被选中，不应该存在专利问题并可以在世界范围内使用。

1998年8月20日，NIST公布了15个AES侯选算法，这些算法由遍步世界的密码团体的成员提交。公众对这15个算法的评论被当作初始评论(公众的初始评论也被称为第一轮)。第一轮于1999年4月15日截止。根据收到的分析和评论，NIST从15个算法中选出5个算法。

5个参加决赛的AES侯选算法是MARS(来自IBM)，RC6(来自RSA Laboratories)， Rijndael(来自Joan Daemen和Vincent Rijmen)，Serpent(来自Ross Anderson， Eli Biham，和Lars Knudsen)，和Twofish(来自Bruce Schneier，John Kelsey，Doug Whiting，David Wagner，Chris Hall，和Niels Ferguson)。这些参加决赛的算法在又一次更深入的评论期(第二轮)得到进一步的分析。

在第二轮中，要征询对候选算法的各方面的评论和分析，这些方面包括但不限于下面的内容：密码分析、知识产权、所有AES决赛候选算法的剖析、综合评价以及有关实现问题。在2000年5月15日第二轮公众分析结束后，NIST汇集和研究了所有得到的信息，为最终选择提供依据。2000年10月2日，NIST宣布它选中了 Rijndael作为AES。

本讲提要 有限域GF(pn)的知识 基本算法 层 解密 设计思考 执行考虑 AES的积极意义 加密模式 消息认证码(MAC)

1 有限域GF(pn)的知识

1.1 建立有限域 GF(pn)

1.2 关于除法

1.3 GF(28)

2 基本算法 为使论述简单，我们以使用128比特密钥加密128比特消息为例说明，并且先对算法的整体架构予以说明。算法由10轮组成。每一轮使用一个由原始密钥产生的密钥。第0轮使用原始的128比特密钥。每一轮都是128比特输入128比特输出。

每一轮由四个基本步骤称为层(layers)组成： (1) 字节转换(The ByteSub Transformation)： 这是一个非线性层主要用于防止差分和线性分析攻击。 (2) 移动行变换(The ShiftRow Transformation)：这是一个线性层，可以导致多轮之间各个比特位间的扩散。 (3) 混合列变换(The MixColumn Transformation)： 这一层的目的与移动行变换相同。 (4) 轮密钥加密变换(AddRoundKey)：轮密钥与上一层的结果进行异或操作。

# 注意最后一轮忽略了混合列变换(MC)层。 一轮的过程 ByteSub (BS) ShiftRow (SR) MixColumn (MC) AddRoundKey (ARK) Rijndael加密 (1) 使用第0轮密钥执行ARK操作。 (2) 依次使用第1轮到9轮密钥按顺序执行BS， SR， MC，和ARK操作。 (3) 使用第10轮密钥按顺序执行BS， SR，和ARK操作。 # 注意最后一轮忽略了混合列变换(MC)层。

3 层

3.1字节转换

3.1字节转换 (续)

3.2 移动行变换

3.3混合列变换

3.4 轮密钥加密变换

3.5 轮密钥产生方法

3.6 S-盒原理

3.6 S-盒原理(续)

4 解密 字节转换、移动行变换、混合列变换、轮密钥加密变换都存在相应的逆变换： (1) 字节转换的逆变换可以通过查另一个表来完成，我们称之为逆字节转换(IBS)。 (2) 移动行变换的逆变换可以通过字节右移来实现，我们称之为逆移动行变换(ISR)。

(3) 逆混合列变换 (IMC) 通过乘上另一个矩阵 实现。 (4) 轮密钥加密变换实际上是自身的逆。

Rijndael 解密 (1) 使用第10轮密钥执行ARK操作。 (2) 依次使用第9轮到1轮密钥按顺序执行IBS，ISR， IMC，和IARK操作。 (3) 使用第0轮密钥按顺序执行IBS， ISR，和ARK操作。 # 为了保持结构的一致性，在最后一轮加密中忽略了 MC操作。

5 设计思考 (1) 由于加密和解密过程不一致，相比DES(全1密钥，加密两次恢复为本身)，相信AES不存在任何弱密钥。 (2) 不同于Feistel系统，AES对输入所有比特的处理相同。这使得输入的扩展速度很快。实践表明两轮计算就能得到充分扩展，也就是说，所有的128比特输出完全依赖于所有128比特输入。 (3) AES的S-盒的建立有明晰而简单的代数意义，这样可以避免任何建立在算法上的陷门，较好避免存在于DES的S-盒上的神秘色彩。AES的S-盒具有良好的非线性特性，它可以很好的用来阻止差分和线性分析。

(4) 移动行这一层可以很好的阻止新发现的截断攻击和平方攻击。 (5) 混合列可以达到字节扩散的目的。这步1个输入字节的改变导致所有4个输出字节改变。 (6) 轮密钥产生方法使用了密钥位的非线性组合，因为它使用了S-盒，这种非线性组合用来对付当解密者知道了部分密钥并以此推测余下部分的攻击。循环常量(10)(i-4)/4是用来消除在循环过程中生成每个循环差别的对称性。

(7) 轮次之所以选择10，是因为在6轮情况下存在比强力搜索攻击更好的算法。已知的纯数学密码分析结果在7轮以上还没有比强力搜索攻击更好的办法。多出4轮能够让人更有安全感。当然，轮次还可以根据需要增加。

6 执行考虑 我们已经看到Rijndael内部的层是非常简单的，它在很小的代数空间上即可完成，因此，可以高效完成这些层。从前面对Rijndael的内部层描述可以看到，仅有SB/ISB和MC/IMC值得考虑它们的快速实现问题。

(1) 对于SB/ISB，我们建议使用S-盒查表方法：可以一次建立一个有28=256个字节的小表，长期使用(就是说，这个表可以“固化”在硬件或者是软件中实现)。“查表法”不仅非常有效，还能阻止定时分析攻击，这种攻击根据不同数据的运算时间差异，来推断运算是在比特0还是在比特1上运行。

(2) 在MC操作中，有限域GF(28)上的两个元的乘法操作也可以用“查表法”来实现：z = xy(有限域乘法)，这里x{01，10，11}和yGF(28)。我们进一步注意到字节01为有限域乘法单位元，也就是，01y=y。因而无论用软件还是硬件执行“查表法”时只需要存储2256=512项，这个表是非常小的。这样实现不仅速度很快，而且还能够减少定时分析攻击的危险。

(3) 执行IMC操作就不像执行MC操作那么快。这是因为IMC操作的44矩阵比MC操作的矩阵复杂的多，一般执行IMC操作比MC操作需要多花费30%的处理时间。然而，幸运地是在一些应用中解密是不需要的。

7 AES的积极意义 (1) 首先，多重加密，例如，三重DES加密，随着AES的出现而成为不必要的选择。可以加长的密钥以及128、192、256比特的数据分组长度为各种应用需求提供了大范围的安全强度。由于多重加密多次使用多个密钥，那么避免使用多重加密就意味着实用中必须使用的密钥数目减少，因此，可以简化安全协议和系统设计。

(2) 其次，AES的广泛使用将促进同样强度的Hash函数的出现。在某些情况下，分组加密算法与Hash函数密切相关。分组加密算法经常被用来作为Hash函数，这已经成为一种标准应用。UNIX操作系统的登录认证协议就是一个著名的例子。我们也看到上一讲的UNIX口令方案的实现中DES的“单向变换”用法。前面看到Hash函数应该是分组加密算法数据分组的2倍，因此，将需要与128、192、256比特AES长度相匹配的256、384、512比特的新Hash函数。各大标准化组织也正在积极从事这方面的工作。

(3) 最后，像DES标准吸引了许多试图攻破该算法的密码分析家的注意，随之促进了分组密码分析的认识水平的发展一样，作为新的分组密码标准的AES也可望引起分组密码分析中高水平研究的再次兴起，这必将使得该领域的认识水平得到进一步提高。

8 加密模式 通常大多数消息的长度大于分组密码的消息分组长度，长的消息被分成一系列连续排列的消息分组，密码一次处理一个分组。在分组密码的上层不同的加密模式被开发出来，这些加密模式可以为整体消息加密提供一些希望得到的性质，如：分组密码的不确定性(随机性)，将明文消息添加到任意长度(使得密文长度不必与相应的明文长度相关)，错误传播控制，流密码的密钥流生成，等等。

8.1 电码本(ECB)模式

8.1电码本(ECB)模式 (续)

8.2 密码分组链接(CBC)模式 C0 P1 EK C1 P2 C2 …

8.2 密码分组链接(CBC)模式 (续)

8.3 密码反馈 (CFB)模式

8.3 密码反馈 (CFB)模式 (续)

8.3 密码反馈 (CFB)模式 (续)

9 消息认证码(MAC) 定义 1 消息认证码(MAC)算法是带有密钥k 的函数族hk，其具有如下性质： (1) 易于计算：对于任何已知函数hk，给定值k和输入x，值hk(x)容易计算出来。这个值被称做MAC-值或MAC。

(2) 压缩：函数hk可以将任意有限比特长度的输入x映射为固定n比特长度的位串。进一步，给出函数族h的算法描述，对于任何一个固定符合要求的密钥值k(攻击者不知其值)，需要满足如下性质： (3) 计算抵抗：给定0个或多个消息-MAC值对(xi，hk(xi))，找到任意消息-MAC值对(x，hk(x))满足xxi在计算上不可能(当然也包括某些i满足hk(x)=hk(xi)的可能性) 。

9.1 攻击者攻击MAC的目标 目标：在不知道密钥k的情况下，给定一个或多个消息-MAC值对(xi，hk(xi))，计算出一个或多个新消息-MAC值对(x，hk(x))，满足xxi。 攻击者潜在的能力： (1) 已知消息攻击。 (2) 选择消息攻击：掌握一个或多个由攻击者选择的xi对应的消息-MAC值对 (xi，hk(xi)) 。 (3) 适应性选择消息攻击：允许根据前面的询问结果连续做出选择。

9.2 伪造种类 在实际中造成的破坏程度取决于攻击者控制消息x并伪造其MAC值的程度，依此可以做如下分类。 (1) 选择性伪造攻击：攻击者可以根据选择，控制消息的内容伪造出消息-MAC值对(或者至少为部分控制消息内容)。 (2) 存在性伪造攻击：攻击者虽然可以伪造出消息-MAC值，但无法控制消息的内容。

9.3 实例 – 基于CBC的MAC

9.3 实例 – 基于CBC的MAC (续) M1 Ek H1 M2 H2 … Ht-1 Mt Ht Dk' 可选

9.3 实例 – 基于CBC的MAC (续) 评论. (1) 很明显，在生成CBC-MAC值(由运行CBC模式的分组密码构造的MAC)的计算中包括了不可求逆的数据压缩(本质上，CBC-MAC是整个消息的“短摘要”)，因此CBC-MAC是一个单向变换。 (2) 所有的分组密码加密算法的混合变换性质为这个单向函数变换增加了一个杂凑特点(也就是说，将MAC分布到MAC空间与分组密码加密算法将密文分布到密文空间同样均匀)。

(3) 根据以上，我们可以设想为了生成一个有效的CBC-MAC，该实体必须知道控制分组密码算法的密钥k。与发送者共享密钥k的接收者可由所接收的消息重新计算出MAC值，并检查与所收到的MAC值是否一致。如果一致，就可以相信消息来自所声称的发送者。

谢谢 !