《现代密码学》第4章(6) 分组密码： AES算法.

Presentation on theme: "《现代密码学》第4章(6) 分组密码： AES算法."— Presentation transcript:

1 《现代密码学》第4章(6) 分组密码： AES算法

2 本节主要内容 1、AES候选算法产生过程 2、Rijndael的数学基础和设计思想 3、Rijndael的算法说明 4、习题

3 1. AES候选算法产生过程 背景 从各方面来看，DES已走到了它生命的尽头。其56比特密钥实在太小，虽然三重DES可以解决密钥长度的问题，但是DES的设计主要针对硬件实现，而今在许多领域，需要用软件方法来实现它，在这种情况下，它的效率相对较低。鉴于此，1997年4月15日美国国家标准和技术研究所（NIST）发起征集AES（AES—Advanced Encryption Standard）算法的活动，并成立了AES工作组。目的是为了确定一个非保密的、公开披露的、全球免费使用的加密算法，用于保护下一世纪政府的敏感信息。也希望能够成为保密和非保密部门公用的数据加密标准（DES）。

4 1. AES候选算法产生过程 1997年4月15日，美国ANSI发起征集AES（advanced encryption standard）的活动，并为此成立了AES工作小组。此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。对AES的基本要求是： 比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。

5 1. AES候选算法产生过程 评选过程中采用的方法 1.用量化的或定性的尺度作为选择的标准； 2.选择一种以上的算法；
3.选择一个备用算法； 4.考虑公众的建议以改进算法。

6 1. AES候选算法产生过程 1998年8月12日，在首届AES候选会议（first AES candidate conference）上公布了AES的15个候选算法，任由全世界各机构和个人攻击和评论，这15个候选算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。1999年3月，在第2届AES候选会议（second AES candidate conference）上经过对全球各密码机构和个人对候选算法分析结果的讨论，从15个候选算法中选出了5个。

7 1. AES候选算法产生过程 这5个是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日，召开了第3届AES候选会议（third AES candidate conference），继续对最后5个候选算法进行讨论。2000年10月2日，NIST宣布Rijndael作为新的AES。至此，经过3年多的讨论，Rijndael终于脱颖而出。

8 1. AES候选算法产生过程 Rijndael 由比利时的Joan Daemen和Vincent Rijmen设计，算法的原型是Square算法，它的设计策略是宽轨迹策略（wide trail strategy）。宽轨迹策略是针对差分分析和线性分析提出的，它的最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界；由此，可以分析算法抵抗差分密码分析及线性密码分析的能力。

9 1. AES候选算法产生过程 在宣布最后的5个候选算法后，NIST再次恳请公众参与对这些算法的评论。公众对这五种候选算法的评阅期于2000年5月15日结束。NIST发布的AES主页[2]提供了大量的关于算法描述、源程序、有关AES3的论文以及其他公众评论的信息。2000年4月开始进行第三阶段（AES3）的评选，AES3共收到37篇提交给NIST的论文，并采用了其中的24篇。在这一阶段的讨论中，这些算法得到了非常深入的分析。NIST的AES小组综合所有公众对候选算法的评价和分析作了一个非常彻底的评论。

10 1. AES候选算法产生过程 经过长时间的评审和讨论之后，NIST在2000年5月宣布选择Rijndael作为AES的算法。该算法的开发者提出以下几种发音供选择"Reign Dah1"，"Rain doll"和 "Rhine Dah1"。

11 1. AES候选算法产生过程 结果 NIST最终选择了Rijndael作为AES的标准，因为全面地考虑，Rijndael汇聚了安全，性能好，效率高，易用和灵活等优点。 Rijndael使用非线性结构的S-boxes，表现出足够的安全余地；Rijndael在无论有无反馈模式的计算环境下的硬，软件中都能显示出其非常好的性能；它的密钥安装的时间很好，也具有很高的灵活性；Rijndael的非常低的内存需求也使它很适合用于受限的环境；

12 1. AES候选算法产生过程 Rijndael的操作简单，并可抵御时间和能量攻击，此外，它还有许多未被特别强调的防御性能；Rijndael在分组长度和密钥长度的设计上也很灵活，算法可根据分组长度和密钥长度的不同组合提供不同的迭代次数，虽然这些特征还需更深入地研究，短期内不可能被利用，但最终，Rijndael内在的迭代结构会显示良好的潜能来防御入侵行为。

13

14 Rijndael 特点 不属于Feistel结构 加密、解密相似但不对称 支持128/32=Nb数据块大小
支持128/192/256(/32=Nk)密钥长度 有较好的数学理论作为基础 结构简单、速度快

15 AES参数 AES-128 4 10 AES-192 6 12 AES-256 8 14 Key Length (Nk words)
Block Size (Nb words) Number of Rounds (Nr) AES-128 4 10 AES-192 6 12 AES-256 8 14

16 2. Rijndael的数学基础和设计思想 域的概念：一个field 是一个group并且满足下面的性质
（1）乘法封闭性：如果a,b属于G，则ab属于G. （2）乘法结合律：如果a,b,c 属于G，则有a(bc)=(ab)c恒成立。 （3）分配律：如果a,b,c 属于G,则有a(b+c)=ab+ac。 （4）乘法交换律：如果a,b属于G,则有ab=ba。 （5）没有0的除法：如果a,b属于G,并且ab=0,不能得出a=0 or b=0 （6）存在乘法单位元：aI=Ia=a. （7）存在乘法逆元：如果a属于G,且a不等于0,则有ba=ab=I. 给定一个素数，则必存在一个有限域，域中的元素个数为： 这类有限域用 来表示。

17 2.1 Rijndael的数学基础 1. 有限域GF(28)
有限域中的元素可以用多种不同的方式表示。对于任意素数的方幂，都有惟一的一个有限域，因此GF(28)的所有表示是同构的，但不同的表示方法会影响到GF(28)上运算的复杂度，本算法采用传统的多项式表示法。

18 2.1 Rijndael的数学基础 将b7b6b5b4b3b2b1b0构成的字节b看成系数在{0,1}中的多项式
b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 例如： 十六进制数‘57’对应的二进制为 ，看成一个字节，对应的多项式为x6+x4+x2+x+1。 AES的理论基础定义在GF(28) ,其基本的运算有三种，分别为加法，乘法和乘x。

19 2.1 Rijndael的数学基础 （1）加法 在AES算法中，若两个多项式进行加法运算（加法运算的
符号定义为 ）运算的方法为两个多项式对应的系数相 加后，在取模2运算。 此加法运算可以有XOR运算进行处理，即相加的两个 数进行异或运算。

20 2.1 Rijndael的数学基础 在多项式表示中，GF(28)上两个元素的和仍然是一个次数不超过7的多项式，其系数等于两个元素对应系数的模2加（比特异或）。 例如： ‘57’+‘83’=‘D4’，用多项式表示为 (x6+x4+x2+x+1)+(x7+x+1)=x7+x6+ x4+ x2 (mod m(x)) 用二进制表示为 = 由于每个元素的加法逆元等于自己，所以减法和加法相同。

21 2.1 Rijndael的数学基础 （2）乘法 在AES算法中，若两个多项式进行乘法运算（乘法运算的
符号定义为 ）运算的方法为两个多项式相乘。若运算 的结果超过8次方，则必须对此结果对一个多项式m(x)进行 模运算。AES算法中定义m(x)多项式为： 例如： 运算过程如下：

22 2.1 Rijndael的数学基础

23 2.1 Rijndael的数学基础 要计算GF(28)上的乘法，必须先确定一个GF(2)上的8次不可约多项式；GF(28)上两个元素的乘积就是这两个多项式的模乘（以这个8次不可约多项式为模）。 在Rijndael密码中，这个8次不可约多项式确定为 m(x)= x8+x4+x3+x+1 它的十六进制表示为‘11B’。

24 2.1 Rijndael的数学基础 例如，‘57’·‘83’=‘C1’可表示为以下的多项式乘法：
(x6+x4+x2+x+1)·(x7+x+1)=x7+x6+1(mod m(x)) 乘法运算虽然不是标准的按字节的运算，但也是比较简单的计算部件。

25 2.1 Rijndael的数学基础 以上定义的乘法满足交换律，且有单位元‘01’。另外，对任何次数小于8的多项式b(x)，可用推广的欧几里得算法得 b(x)a(x)+m(x)c(x)=1 即a(x)·b(x)=1 mod m(x)，因此a(x)是b(x)的乘法逆元。 再者，乘法还满足分配律： a(x)·(b(x)+c(x))= a(x)·b(x)+a(x)·c(x) 所以，256个字节值构成的集合，在以上定义的加法和乘法运算下，有有限域GF(28)的结构。

26 X的幂乘运算可以重复应用xtime来实现。对任意常数
2.1 Rijndael的数学基础 （3）乘X运算 在AES算法中，若一最高项指数不大于7的多项式b(x)乘上x 的乘法运算，称为xtime运算。例如： 如果 ，求模结果不变，否则要对乘积结果对m(x)求模 。 求模过程可以用乘积结果减去m(x).在具体运算时可以用下 面的方法：x乘b(x)可以先对b(x)在字节内左移一位，若 ，则再与‘1b’做逐比特的异或运算来实现。该运算记为 b=xtime(a)。在专用的芯片中只需4个异或。 注意： X的幂乘运算可以重复应用xtime来实现。对任意常数 的乘法可以通过对中间结果相加来实现。

27 2.1 Rijndael的数学基础 例如：

28 2.1 Rijndael的数学基础 GF(28)上还定义了一个运算，称之为x乘法，其定义为x·b(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x(mod m(x)) 如果b7=0，求模结果不变，否则为乘积结果减去m(x)，即求乘积结果与m(x)的异或。

29 2.1 Rijndael的数学基础 由此得出x（十六进制数‘02’）乘b(x)可以先对b(x)在字节内左移一位（最后一位补0），若b7=1，则再与‘1B’（其二进制为 ）做逐比特异或来实现，该运算记为b=xtime(a)。 在专用芯片中，xtime只需4个异或。x的幂乘运算可以重复应用xtime来实现。而任意常数乘法可以通过对中间结果相加实现。

30 2.1 Rijndael的数学基础 例如，‘57’·‘13’可按如下方式实现： ‘57’·‘02’=xtime(57)=‘AE’；
‘57’·‘08’=xtime(47)=‘8E’； ‘57’·‘10’=xtime(8E)=‘07’； ‘57’·‘13’=‘57’·(‘01’‘02’‘10’) =‘57’‘AE’‘07’=‘FE’。

31 2.1 Rijndael的数学基础 2. 系数在GF(28)上的多项式
多项式的加法就是对应系数相加；换句话说，多项式的加法就是4字节向量的逐比特异或。

32 2.1 Rijndael的数学基础 规定多项式的乘法运算必须要取模M(x)=x4+1，这样使得次数小于4的多项式的乘积仍然是一个次数小于4的多项式，将多项式的模乘运算记为， 设 a(x)= a3x3+a2x2+a1x+a0， b(x)= b3x3+b2x2+b1x+b0， c(x)= a(x)b(x)=c3x3+c2x2+c1x+c0。

33 2.1 Rijndael的数学基础 由于xj mod (x4+1)= x j mod 4，所以
c0=a0b0a3b1a2b2a1b3； c1= a1b0a0b1a3b2a2b3； c2= a2b0a1b1a0b2a3b3； c3= a3b0a2b1a1b2a0b3。

34 2.1 Rijndael的数学基础 可将上述计算表示为

35 2.1 Rijndael的数学基础 注意到M(x)不是GF(28)上的不可约多项式（甚至也不是GF(2)上的不可约多项式），因此非0多项式的这种乘法不是群运算。 不过在Rijndael密码中，对多项式b(x)，这种乘法运算只限于乘一个固定的有逆元的多项式a(x)= a3x3+a2x2+a1x+a0。

36 定理1 系数在GF(28)上的多项式a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当矩阵 在GF(28)上可逆。
2.1 Rijndael的数学基础 定理1 系数在GF(28)上的多项式a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当矩阵 在GF(28)上可逆。

37 2.1 Rijndael的数学基础 证明： a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当存在多项式h3x3+h2x2+h1x+h0， (a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1 mod(x4+1) 因此有 (a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0x+h3)=x mod (x4+1) (a3x3+a2x2+a1x+a0)(h1x3+h0x2+h3x+h2)=x2 mod (x4+1) (a3x3+a2x2+a1x+a0)(h0x3+h3x2+h2x+h1)=x3 mod(x4+1)；

38 2.1 Rijndael的数学基础 将以上关系写成矩阵形式即得 （证毕）

39 2.1 Rijndael的数学基础 c(x)=xb(x)定义为x与b(x)的模x4+1乘法，即c(x)= xb(x)= b2x3+b1x2+b0x+b3。其矩阵表示中，除a1=‘01’外，其他所有ai= ‘00’，即 因此，x（或x的幂）模乘多项式相当于对字节构成的向量进行字节循环移位。

40 Rijndael密码的设计力求满足以下3条标准： ① 抵抗所有已知的攻击。 ② 在多个平台上速度快，编码紧凑。 ③ 设计简单。

41 2.2 Rijndael的设计思想 当前的大多数分组密码，其轮函数是Feistel结构，即将中间状态的部分比特不加改变地简单放置到其他位置。Rijndael没有这种结构，其轮函数是由3个不同的可逆均匀变换组成的，称它们为3个“层”。所谓“均匀变换”是指状态的每个比特都是用类似的方法进行处理的。不同层的特定选择大部分是建立在“宽轨迹策略”的应用基础上的。简单地说，“宽轨迹策略”就是提供抗线性密码分析和差分密码分析能力的一种设计。

42 2.2 Rijndael的设计思想 为实现宽轨迹策略，轮函数3个层中的每一层都有它自己的功能： 线性混合层 确保多轮之上的高度扩散；
线性混合层 确保多轮之上的高度扩散； 非线性层 将具有最优的“最坏情况非线性特性”的S盒并行使用； 密钥加层 单轮子密钥简单地异或到中间状态上，实现一次性掩盖。

43 2.2 Rijndael的设计思想 在第一轮之前，用了一个初始密钥加层，其目的是在不知道密钥的情况下，对最后一个密钥加层以后的任一层（或者是当进行已知明文攻击时，对第一个密钥加层以前的任一层）可简单地剥去，因此初始密钥加层对密码的安全性无任何意义。许多密码的设计中都在轮变换之前和之后用了密钥加层，如IDEA、SAFER和Blowfish。

44 2.2 Rijndael的设计思想 为了使加密算法和解密算法在结构上更加接近，最后一轮的线性混合层与前面各轮的线性混合层不同，这类似于DES的最后一轮不做左右交换。可以证明这种设计不以任何方式提高或降低该密码的安全性。

45 Rijndael是一个迭代型分组密码，其分组长度和密钥长度都可变，各自可以独立地指定为128比特、192比特、256比特。

46 3.1 状态、种子密钥和轮数 类似于明文分组和密文分组，算法的中间结果也须分组，称算法中间结果的分组为状态，所有的操作都在状态上进行。状态可以用以字节为元素的矩阵阵列表示，该阵列有4行，列数记为Nb，Nb等于分组长度除以32。 例如用128比特密钥加密192比特的明文，则明文和密钥被表示成下面的状态：

47 明文状态 密钥状态

48 3.1 状态、种子密钥和轮数 种子密钥类似地用一个以字节为元素的矩阵阵列表示，该阵列有4行，列数记为Nk，Nk等于分组长度除以32。表3.8是Nb=6的状态和Nk=4的种子密钥的矩阵阵列表示。（见65页表3.8） 有时可将这些分组当作一维数组，其每一元素是上述阵列表示中的4字节元素构成的列向量，数组长度可为4、6、8，数组元素下标的范围分别是0~3、0~5和0~7。4字节元素构成的列向量有时也称为字。

49 3.1 状态、种子密钥和轮数 算法的输入和输出被看成是由8比特字节构成的一维数组，其元素下标的范围是0~(4Nb –1)，因此输入和输出以字节为单位的分组长度分别是16、24和32，其元素下标的范围分别是0~15、0~23和0~31。输入的种子密钥也看成是由8比特字节构成的一维数组，其元素下标的范围是0~(4Nk –1)，因此种子密钥以字节为单位的分组长度也分别是16、24和32，其元素下标的范围分别是0~15、0~23和0~31。

50 3.1 状态、种子密钥和轮数 算法的输入（包括最初的明文输入和中间过程的轮输入）以字节为单位按a00a10a20a30a01a11a21a31…的顺序放置到状态阵列中。 同理，种子密钥以字节为单位按k00k10k20k30k01k11k21k31…的顺序放置到种子密钥阵列中。 而输出（包括中间过程的轮输出和最后的密文输出）也是以字节为单位按相同的顺序从状态阵列中取出。

51 3.1 状态、种子密钥和轮数 若输入（或输出）分组中第n个元素对应于状态阵列的第(i, j)位置上的元素，则n和(i, j)有以下关系：i=n mod 4; j= ;n=i+4j 迭代的轮数记为Nr，Nr与Nb和Nk有关，表给出了Nr与Nb和Nk的关系。 14 12 10

52 3.2 轮函数 Rijndael的轮函数由4个不同的计算部件组成，分别是： 字节代换（ByteSub）、 行移位（ShiftRow）、
列混合（MixColumn）、 密钥加（AddRoundKey）。

53 3.2 轮函数 (1) 字节代换（ByteSub） 字节代换是非线形变换，独立地对状态的每个字节进行。代换表（即S-盒）是可逆的，由以下两个变换的合成得到： ① 首先，将字节看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。 ② 其次，对字节做如下的（GF(2)上的，可逆的）仿射变换：

54 3.2 轮函数

55 上述S-盒对状态的所有字节所做的变换记为ByteSub (State) 图3.19是字节代换示意图。
3.2 轮函数 上述S-盒对状态的所有字节所做的变换记为ByteSub (State) 图3.19是字节代换示意图。 图3.19 字节代换示意图

56 ByteSub的逆变换由代换表的逆表做字节代换，可通过如下两步实现: 首先进行仿射变换的逆变换，再求每一字节在GF(28)上逆元。
3.2 轮函数 ByteSub的逆变换由代换表的逆表做字节代换，可通过如下两步实现: 首先进行仿射变换的逆变换，再求每一字节在GF(28)上逆元。

57

58 S盒对状态的所有字节所做的变换记为： ByteSub(State)

59 3.2 轮函数 (2) 行移位（ShiftRow） 行移位是将状态阵列的各行进行循环移位，不同状态行的位移量不同。第0行不移动，第1行循环左移C1个字节，第2行循环左移C2个字节，第3行循环左移C3个字节。位移量C1、C2、C3的取值与Nb有关，由表3.10给出。（见66页表3.10） 按指定的位移量对状态的行进行的行移位运算记为ShiftRow (State)图3.20是行移位示意图。

60 3.2 轮函数 图3.20 行移位示意图

61 行移位（ShiftRow） 例如当Nb=4时，具体的操作如下： 按指定的位移量对状态的行
进行的行移位运算记为： ShiftRow(state)

62 3.2 轮函数 ShiftRow的逆变换是对状态阵列的后3列分别以位移量Nb-C1、Nb-C2、Nb-C3进行循环移位，使得第i行第j列的字节移位到(j+Nb-Ci) mod Nb。

63 3.2 轮函数 （3） 列混合（MixColumn） 在列混合变换中，将状态阵列的每个列视为GF(28)上的多项式，再与一个固定的多项式c(x)进行模x4+1乘法。当然要求c(x)是模x4+1可逆的多项式，否则列混合变换就是不可逆的，因而会使不同的输入分组对应的输出分组可能相同。Rijndael的设计者给出的c(x)为（系数用十六进制数表示）： c(x)=‘03’x3+‘01’x2+‘01’x+‘02’

64 c(x)是与x4+1互素的，因此是模x4+1可逆的。列混合运算也可写为矩阵乘法。设b(x)= c(x)a(x)，则
3.2 轮函数 c(x)是与x4+1互素的，因此是模x4+1可逆的。列混合运算也可写为矩阵乘法。设b(x)= c(x)a(x)，则

65 3.2 轮函数 这个运算需要做GF(28)上的乘法，但由于所乘的因子是3个固定的元素02、03、01，所以这些乘法运算仍然是比较简单的。
对状态State的所有列所做的列混合运算记为MixColumn（State） 图3.21是列混合运算示意图。

66 3.2 轮函数 图3.21 列混合运算示意图

67 列混合运算

68 列混合运算

69 列混合运算

70 3.2 轮函数 列混合运算的逆运算是类似的，即每列都用一个特定的多项式d(x)相乘。 d(x)满足
(‘03’x3+‘01’x2+‘01’x+‘02’)d(x)=‘01’ 由此可得 d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’

71 3.2 轮函数 (4) 密钥加（AddRoundKey）
密钥加是将轮密钥简单地与状态进行逐比特异或。轮密钥由种子密钥通过密钥编排算法得到，轮密钥长度等于分组长度Nb。 状态State与轮密钥RoundKey的密钥加运算表示为 AddRoundKey (State, RoundKey) 图3.22是密钥加运算示意图。

72 3.2 轮函数 图3.22 密钥加运算示意图

73 3.2 轮函数 密钥加运算的逆运算是其自身。 综上所述，组成Rijndael轮函数的计算部件简捷快速，功能互补。轮函数的伪C代码如下：
Round (State, RoundKey) { ByteSub (State); ShiftRow (State); MixColumn (State); AddRoundKey (State, RoundKey) }

74 3.2 轮函数 结尾轮的轮函数与前面各轮不同，将MixColumn这一步去掉。 其伪C代码如下：
FinalRound (State, RoundKey) { ByteSub (State); ShiftRow (State); AddRoundKey (State, RoundKey) }

75 3.2 轮函数 在以上伪C代码记法中，State、RoundKey 可用指针类型，函数Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey都在指针State、RoundKey所指向的阵列上进行运算。

76 3.3 密钥编排 密钥编排指从种子密钥得到轮密钥的过程，它由密钥扩展和轮密钥选取两部分组成。其基本原则如下：
（1）轮密钥的比特数等于分组长度乘以轮数加1；例如要将128比特的明文经过10轮的加密，则总共需要（10+1）*128=1408比特的密钥。 （2）种子密钥被扩展成为扩展密钥； （3）轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，如此下去。

77 3.3 密钥编排 (1) 密钥扩展 扩展密钥是以4字节字为元素的一维阵列，表示为W[Nb* (Nr+1)]，其中前Nk个字取为种子密钥，以后每个字按递归方式定义。扩展算法根据Nk≤6和Nk>6有所不同。

78 ① 当Nk≤6时，扩展算法如下 KeyExpansion (byteKey[4*Nk] , W[Nb*(Nr+1)]) {
for (i =0; i < Nk; i ++) W[i]=(Key[4* i],Key[4* i +1],Key[4* i +2],Key[4* i +3] ); for (i =Nk; i <Nb*(Nr+1); i ++) temp=W[i-1]; if (i % Nk= =0) temp=SubByte (RotByte (temp))^Rcon[i /Nk]; W[i]=W[i-Nk]^ temp; }

79 ① 当Nk≤6时，扩展算法如下 其中Key[4*Nk]为种子密钥，看作以字节为元素的一维阵列。函数SubByte ( )返回4字节字，其中每一个字节都是用Rijndael的S盒作用到输入字对应的字节得到。函数RotByte ( ) 也返回4字节字，该字由输入的字循环移位得到，即当输入字为(a, b, c, d)时，输出字为 (b, c, d, a)。

80 ① 当Nk≤6时，扩展算法如下 可以看出，扩展密钥的前Nk个字即为种子密钥，之后的每个字W[i]等于前一个字W[i-1]与Nk个位置之前的字W[i- Nk]的异或；不过当i/Nk为整数时，须先将前一个字W[i-1]经过以下一系列的变换： 1字节的循环移位RotByte→用S盒进行变换SubByte→异或轮常数Rcon[i/Nk]。

81 ② 当Nk>6时，扩展算法如下： KeyExpansion (byte Key[4*Nk] , W[Nb*(Nr+1)]) {
for (i=0; i < Nk; i ++) W[i]=(Key[4* i], Key[4* i +1], Key[4* i +2], Key[4* i +3] ); for (i =Nk; i <Nb*(Nr+1); i ++) temp=W[i -1]; if (i % Nk= =0) temp=SubByte (RotByte (temp))^Rcon[i /Nk]; else if (i % Nk==4) temp=SubByte (temp); W[i]=W[i - Nk]^ temp; }

82 Nk>6与Nk≤6的密钥扩展算法的区别在于：当i为Nk的4的倍数时，须先将前一个字W[i-1]经过SubByte变换。
3.3 密钥编排 Nk>6与Nk≤6的密钥扩展算法的区别在于：当i为Nk的4的倍数时，须先将前一个字W[i-1]经过SubByte变换。

83 3.3 密钥编排 以上两个算法中，Rcon[i/Nk] 为轮常数，其值与Nk无关，定义为（字节用十六进制表示，同时理解为GF(28)上的元素）： Rcon [i]=(RC[i], ‘00’, ‘00’, ‘00’) 其中RC[i] 是GF(28) 中值为xi-1的元素，因此 RC[1] =1(即‘01’) RC[i] = x(即‘02’)·RC[i-1]= xi-1

84 (2) 轮密钥选取 轮密钥i（即第i 个轮密钥）由轮密钥缓冲字W[Nb* i]到W[Nb*(i+1)]给出，如图3.23所示。
3.3 密钥编排 (2) 轮密钥选取 轮密钥i（即第i 个轮密钥）由轮密钥缓冲字W[Nb* i]到W[Nb*(i+1)]给出，如图3.23所示。 图3.23 Nb=6且Nk=4时的密钥扩展与轮密钥选取

85 3.4 加密算法 加密算法为顺序完成以下操作：初始的密钥加；(Nr-1)轮迭代；一个结尾轮。即
Rijndael (State, CipherKey) { KeyExpansion (CipherKey, ExpandedKey); AddRoundKey (State, ExpandedKey); for (i=1; i <Nr; i ++) Round (State, ExpandedKey+Nb* i); FinalRound (State, ExpandedKey+Nb*Nr) }

86 3.4 加密算法 其中CipherKey是种子密钥，ExpandedKey是扩展密钥。密钥扩展可以事先进行（预计算），且Rijndael密码的加密算法可以用这一扩展密钥来描述，即 Rijndael (State, ExpandedKey) { AddRoundKey (State, ExpandedKey); for (i=1; i <Nr; i ++) Round (State, ExpandedKey+Nb* i); FinalRound (State, ExpandedKey+Nb*Nr) }

87 3.5 加解密的相近程度及解密算法 首先给出几个引理。
引理3.1 设字节代换（ByteSub）、行移位（ShiftRow）的逆变换分别为InvByteSub、InvShiftRow。则组合部件“ByteSub→ShiftRow”的逆变换为“InvByteSub→InvShiftRow”。

88 3.5 加解密的相近程度及解密算法 证明：组合部件“ByteSub→ShiftRow”的逆变换原本为“InvShiftRow→InvByteSub”。由于字节代换（ByteSub）是对每个字节进行相同的变换，故“InvShiftRow”与“InvByteSub”两个计算部件可以交换顺序。（证毕）

89 3.5 加解密的相近程度及解密算法 引理3.2 设列混合（MixColumn）的逆变换为InvMixColumn。则列混合部件与密钥加部件（AddRoundKey）的组合部件“MixColumn→AddRoundKey (·, Key)”的逆变换为“InvMixColumn→AddRoundKey (·, InvKey)”。 其中密钥InvKey与Key的关系为： InvKey=InvMixColumn (Key)。

90 3.5 加解密的相近程度及解密算法 证明： 组合部件“MixColumn→AddRoundKey (·, Key)” 的逆变换原本为“AddRoundKey (·, Key)→InvMixColumn”，由于列混合（MixColumn）实际上是线性空间GF(28)4上的可逆线性变换，因此“AddRoundKey (·, Key)→InvMixColumn” =“InvMixColumn→AddRoundKey (·, InvMixColumn (Key))”（证毕）

91 3.5 加解密的相近程度及解密算法 引理3.3 将某一轮的后两个计算部件和下一轮的前两个计算部件组成组合部件，该组合部件的程序为
MixColumn (State)； AddRoundKey (State, Key(i)); ByteSub (State); ShiftRow (State) 则该组合部件的逆变换程序为 InvByteSub (State); InvShiftRow (State); InvMixColumn (State); AddRoundKey (State, InvMixColumn (Key(i)))

92 3.5 加解密的相近程度及解密算法 证明：这是引理3.1和引理3.2的直接推论。
注意到在引理3.3所描述的逆变换中，第2步到第4步在形状上很像加密算法的轮函数，这将是解密算法的轮函数。注意到结尾轮只有3个计算部件，因此可以得到如下定理。

93 3.5 加解密的相近程度及解密算法 定理2 Rijndael密码的解密算法为顺序完成以下操作：初始的密钥加；(Nr-1)轮迭代；一个结尾轮。其中解密算法的轮函数为 InvRound (State, RoundKey) { InvByteSub (State); InvShiftRow (State); InvMixColumn (State); AddRoundKey (State, RoundKey) }

94 3.5 加解密的相近程度及解密算法 解密算法的结尾轮为 InvFinalRound (State, RoundKey) {
InvByteSub (State); InvShiftRow (State); AddRoundKey (State, RoundKey) }

95 3.5 加解密的相近程度及解密算法 设加密算法的初始密钥加、第1轮、第2轮、…、第Nr轮的子密钥依次为
k(0), k(1), k(2), …, k(Nr-1), k(Nr) 则解密算法的初始密钥加、第1轮、第2轮、…、第Nr轮的子密钥依次为 k(Nr), InvMixColumn (k(Nr-1)), InvMixColumn (k(Nr-2)), …, InvMixColumn (k(1)), k(0)。

96 证明：这是上述3个引理的直接推论。 综上所述，Rijndael密码的解密算法与加密算法的计算网络相同，只是将各计算部件换为对应的逆部件。
3.5 加解密的相近程度及解密算法 证明：这是上述3个引理的直接推论。 综上所述，Rijndael密码的解密算法与加密算法的计算网络相同，只是将各计算部件换为对应的逆部件。

97 4. 习题 1. (1) 设M′是M的逐比特取补，证明在DES中，如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即：如果Y=DESK(X)，那么Y′=DESK′(X′) 提示：对任意两个长度相等的比特串A和B，证明(AB)′=A′B。 对DES进行穷搜索攻击时，需要在由256个密钥构成的密钥空间进行。能否根据(1)的结论减小进行穷搜索攻击时所用的密钥空间？

98 4. 习题 2. 证明DES的解密变换是加密变换的逆。
3. 在DES的ECB模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组受到影响。然而在CBC模式中，将有错误传播。例如在图3.11中C1中的一个错误明显地将影响P1和P2的结果。 (1) P2后的分组是否受到影响？ (2) 设加密前的明文分组P1中有1比特的错误，问这一错误将在多少个密文分组中传播？对接收者产生什么影响？

99 4. 习题 4. 在8比特CFB模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远？
5. 在实现IDEA时，最困难的部分是模216+1乘法运算。以下关系给出了实现模乘法的一种有效方法，其中a和b是两个n比特的非0整数： 注意： (ab mod 2n)相应于ab的n个最低有效位，(ab div 2n)是ab右移n位。

100 4. 习题 (1) 证明存在惟一的非负整数q和r使得ab=q(2n+1)+r。 (2) 求q和r的上下界。
(3) 证明q+r<2n+1。 (4) 求(ab div 2n)关于q的表达式。 (5) 求(ab mod 2n)关于q和r的表达式。 (6) 用(4)和(5)的结果求r的表达式，说明r的含义。

101 4. 习题 6. (1) 在IDEA的模乘运算中，为什么将模数取为216+1而不是216?

102 THE END！