现代密码学第4章6：AES算法讲课教案

1、分组密码分组密码(m m)： AES算法算法现代(xindi)密码学第4章(6)第一页，共102页。本节主要本节主要(zhyo)内容内容n1 1、AESAES候选算法产生过程候选算法产生过程n2 2、RijndaelRijndael的数学基础和设计思想的数学基础和设计思想(sxing)(sxing)n3 3、RijndaelRijndael的算法说明的算法说明n4 4、习题、习题第二页，共102页。n背景背景n 从各方面来看，从各方面来看，DES已走到了它生命的尽头。其已走到了它生命的尽头。其56比特密钥实在太小，虽然三重比特密钥实在太小，虽然三重DES可以解决密钥可以解决密钥长度的问题，但是

2、长度的问题，但是DES的设计主要针对硬件实现，的设计主要针对硬件实现，而今在许多领域，需要用软件方法来实现它，在这而今在许多领域，需要用软件方法来实现它，在这种情况下，它的效率相对较低。鉴于此，种情况下，它的效率相对较低。鉴于此，1997年年4月月15日美国国家标准和技术研究所（日美国国家标准和技术研究所（NIST）发起）发起征集征集AES（AESAdvanced Encryption Standard）算法的活动，并成立了）算法的活动，并成立了AES工作组。目工作组。目的是为了确定的是为了确定(qudng)一个非保密的、公开披露一个非保密的、公开披露的、全球免费使用的加密算法，用于保护下一世

3、纪的、全球免费使用的加密算法，用于保护下一世纪政府的敏感信息。也希望能够成为保密和非保密部政府的敏感信息。也希望能够成为保密和非保密部门公用的数据加密标准（门公用的数据加密标准（DES）。）。1. AES候选算法产生候选算法产生(chnshng)过程过程第三页，共102页。 1997年4月15日，美国ANSI发起征集AES（advanced encryption standard）的活动，并为此成立了AES工作小组。此次活动的目的是确定一个非保密的、可以公开(gngki)技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选

4、算法的通告。对AES的基本要求是： 比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。1. AES候选(hu xun)算法产生过程第四页，共102页。n评选过程中采用的方法评选过程中采用的方法n1.用量化的或定性的尺度作为用量化的或定性的尺度作为(zuwi)选选择的标准；择的标准；n2.选择一种以上的算法；选择一种以上的算法；n3.选择一个备用算法；选择一个备用算法；n4.考虑公众的建议以改进算法。考虑公众的建议以改进算法。1. AES候选算法候选算法(sun f)产产生过程生过程第五页，共102页。 1998年8月12日，在首届AES候

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

6、，共102页。 这5个是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日，召开了第3届AES候选(hu xun)会议（third AES candidate conference），继续对最后5个候选(hu xun)算法进行讨论。2000年10月2日，NIST宣布Rijndael作为新的AES。至此，经过3年多的讨论，Rijndael终于脱颖而出。1. AES候选(hu xun)算法产生过程第七页，共102页。 Rijndael 由比利时的Joan Daemen和Vincent Rijmen设计，算法(sun f)的原型是Square算法(sun

7、 f)，它的设计策略是宽轨迹策略（wide trail strategy）。宽轨迹策略是针对差分分析和线性分析提出的，它的最大优点是可以给出算法(sun f)的最佳差分特征的概率及最佳线性逼近的偏差的界；由此，可以分析算法(sun f)抵抗差分密码分析及线性密码分析的能力。1. AES候选(hu xun)算法产生过程第八页，共102页。 在宣布在宣布(xunb)最后的最后的5个候选算法后，个候选算法后，NIST再次恳请公众参与对这些算法的评论。公众再次恳请公众参与对这些算法的评论。公众对这五种候选算法的评阅期于对这五种候选算法的评阅期于2000年年5月月15日结日结束。束。NIST发布的发布的

8、AES主页主页2提供了大量的关于提供了大量的关于算法描述、源程序、有关算法描述、源程序、有关AES3的论文以及其他公的论文以及其他公众评论的信息。众评论的信息。2000年年4月开始进行第三阶段月开始进行第三阶段（AES3）的评选，）的评选，AES3共收到共收到37篇提交给篇提交给NIST的论文，并采用了其中的的论文，并采用了其中的24篇。在这一阶段的讨篇。在这一阶段的讨论中，这些算法得到了非常深入的分析。论中，这些算法得到了非常深入的分析。NIST的的AES小组综合所有公众对候选算法的评价和分析小组综合所有公众对候选算法的评价和分析作了一个非常彻底的评论。作了一个非常彻底的评论。1. AES候

9、选算法候选算法(sun f)产产生过程生过程第九页，共102页。 经过长时间的评审和讨论之后，NIST在2000年5月宣布选择Rijndael作为(zuwi)AES的算法。该算法的开发者提出以下几种发音供选择Reign Dah1，Rain doll和 Rhine Dah1。1. AES候选算法候选算法(sun f)产产生过程生过程第十页，共102页。n结果结果n NIST最终选择了最终选择了Rijndael作为作为AES的标的标准准(biozhn)，因为全面地考虑，因为全面地考虑，Rijndael汇聚了安全，性能好，效率高，易用和灵活等汇聚了安全，性能好，效率高，易用和灵活等优点。优点。n R

10、ijndael使用非线性结构的使用非线性结构的S-boxes，表现出足够的安全余地；表现出足够的安全余地；Rijndael在无论有无在无论有无反馈模式的计算环境下的硬，软件中都能显示反馈模式的计算环境下的硬，软件中都能显示出其非常好的性能；它的密钥安装的时间很好，出其非常好的性能；它的密钥安装的时间很好，也具有很高的灵活性；也具有很高的灵活性；Rijndael的非常低的内的非常低的内存需求也使它很适合用于受限的环境；存需求也使它很适合用于受限的环境；1. AES候选算法产生候选算法产生(chnshng)过程过程第十一页，共102页。 Rijndael的操作简单，并可抵御时间和能量攻击，此外，它

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

12、ng)过程过程第十二页，共102页。第十三页，共102页。n不属于不属于Feistel结构结构n加密、解密相似但不对称加密、解密相似但不对称n支持支持128/32=Nb数据块大小数据块大小n支持支持128/192/256(/32=Nk)密钥长度密钥长度n有较好的数学理论有较好的数学理论(lln)作为基础作为基础n结构简单、速度快结构简单、速度快Rijndael 特点特点(tdin)第十四页，共102页。Key Length(Nk words)Block Size(Nb words)Number of Rounds (Nr)AES-1284410AES-1926412AES-2568414AES

13、参数参数(cnsh)第十五页，共102页。域的概念域的概念(ginin)：一个：一个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,不能得出(d ch)a=0 or b=0（6）存在乘法单位元：aI=Ia=a.（7）存在乘法逆元：如果a属于G,且a不等于0,则有ba=ab=I.

14、给定一个素数，则必存在一个有限域，域中的元素个数为：这类有限域用 来表示。np)(npGF2. Rijndael的数学(shxu)基础和设计思想第十六页，共102页。1. 有限域有限域GF(28) 有限域中的元素可以用多种不同的方式有限域中的元素可以用多种不同的方式表示。对于任意素数的方幂，都有惟一的一表示。对于任意素数的方幂，都有惟一的一个有限域，因此个有限域，因此GF(28)的所有表示是同构的，的所有表示是同构的，但不同的表示方法但不同的表示方法(fngf)会影响到会影响到GF(28)上运算的复杂度，本算法采用传统的多项式上运算的复杂度，本算法采用传统的多项式表示法。表示法。2.1 Rij

15、ndael的数学的数学(shxu)基础基础第十七页，共102页。 将b7b6b5b4b3b2b1b0构成的字节(z ji)b看成系数在0,1中的多项式b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 例如： 十六进制数57对应的二进制为01010111，看成一个字节(z ji)，对应的多项式为x6+x4+x2+x+1。 AES的理论基础定义在GF(28) ,其基本的运算有三种，分别为加法，乘法和乘x。2.1 Rijndael的数学的数学(shxu)基础基础第十八页，共102页。（1）加法）加法(jif)在AES算法中，若两个多项式进行加法运算（加法运算的符号(fho)定

16、义为 ）运算的方法为两个多项式对应的系数相加后，在取模2运算。 此加法运算可以有XOR运算进行处理(chl)，即相加的两个数进行异或运算。2.1 Rijndael的数学基础第十九页，共102页。 在多项式表示中，GF(28)上两个元素的和仍然是一个次数不超过7的多项式，其系数等于两个元素对应系数的模2加（比特异或）。 例如： 57+83=D4，用多项式表示为(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+ x4+ x2 (mod m(x) 用二进制表示为 01010111+10000011=11010100 由于每个元素的加法逆元等于自己，所以(suy)减法和加法相同。2.1 Ri

17、jndael的数学的数学(shxu)基础基础第二十页，共102页。（2）乘法）乘法(chngf)在AES算法中，若两个多项式进行(jnxng)乘法运算（乘法运算的符号定义为 ）运算的方法为两个多项式相乘。若运算的结果超过8次方，则必须对此结果对一个多项式m(x)进行(jnxng)模运算。AES算法中定义m(x)多项式为：例如(lr)：运算过程如下：2.1 Rijndael的数学基础第二十一页，共102页。2.1 Rijndael的数学(shxu)基础第二十二页，共102页。 要计算GF(28)上的乘法，必须先确定一个GF(2)上的8次不可约多项式；GF(28)上两个元素的乘积就是这两个多项式的

18、模乘（以这个8次不可约多项式为模）。 在Rijndael密码(m m)中，这个8次不可约多项式确定为 m(x)= x8+x4+x3+x+1它的十六进制表示为11B。2.1 Rijndael的数学的数学(shxu)基础基础第二十三页，共102页。n 例如(lr)，5783=C1可表示为以下的多项式乘法：n (x6+x4+x2+x+1)(x7+x+1)=x7+x6+1(mod m(x)n 乘法运算虽然不是标准的按字节的运算，但也是比较简单的计算部件。2.1 Rijndael的数学的数学(shxu)基基础础第二十四页，共102页。 以上定义的乘法(chngf)满足交换律，且有单位元01。另外，对任何

19、次数小于8的多项式b(x)，可用推广的欧几里得算法得 b(x)a(x)+m(x)c(x)=1即a(x)b(x)=1 mod m(x)，因此a(x)是b(x)的乘法(chngf)逆元。 再者，乘法(chngf)还满足分配律：a(x)(b(x)+c(x)= a(x)b(x)+a(x)c(x) 所以，256个字节值构成的集合，在以上定义的加法和乘法(chngf)运算下，有有限域GF(28)的结构。2.1 Rijndael的数学的数学(shxu)基础基础第二十五页，共102页。（3）乘）乘X运算运算(yn sun)在AES算法中，若一最高项指数(zhsh)不大于7的多项式b(x)乘上x的乘法运算，称为

20、xtime运算。例如：如果 ，求模结果不变，否则要对乘积结果对m(x)求模 。求模过程可以用乘积结果减去m(x).在具体(jt)运算时可以用下面的方法：x乘b(x)可以先对b(x)在字节内左移一位，若 ，则再与1b做逐比特的异或运算来实现。该运算记为b=xtime(a)。在专用的芯片中只需4个异或。07b17b注意：注意：X的幂乘运算可以重复应用xtime来实现。对任意常数的乘法可以通过对中间结果相加来实现。2.1 Rijndael的数学基础第二十六页，共102页。例如例如(lr)：2.1 Rijndael的数学(shxu)基础第二十七页，共102页。 GF(28)上还定义了一个运算，称之为x

21、乘法，其定义为xb(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x(mod m(x) 如果b7=0，求模结果(ji gu)不变，否则为乘积结果(ji gu)减去m(x)，即求乘积结果(ji gu)与m(x)的异或。2.1 Rijndael的数学的数学(shxu)基础基础第二十八页，共102页。n 由此得出x（十六进制数02）乘b(x)可以先对b(x)在字节内左移一位（最后一位补0），若b7=1，则再与1B（其二进制为00011011）做逐比特异(ty)或来实现，该运算记为b=xtime(a)。n 在专用芯片中，xtime只需4个异或。x的幂乘运算可以重复

22、应用xtime来实现。而任意常数乘法可以通过对中间结果相加实现。2.1 Rijndael的数学的数学(shxu)基基础础第二十九页，共102页。例如(lr)，5713可按如下方式实现： 5702=xtime(57)=AE；5704=xtime(AE)=47；5708=xtime(47)=8E；5710=xtime(8E)=07；5713=57(010210) =57AE07=FE。2.1 Rijndael的数学的数学(shxu)基础基础第三十页，共102页。2. 系数在系数在GF(28)上的多项式上的多项式 4个字节构成的向量可以表示为系数在个字节构成的向量可以表示为系数在GF(28)上的次数

23、小于上的次数小于4的多项式。的多项式。 多项式的加法就是多项式的加法就是(jish)对应系数相加；对应系数相加；换句话说，多项式的加法就是换句话说，多项式的加法就是(jish)4字节字节向量的逐比特异或。向量的逐比特异或。2.1 Rijndael的数学的数学(shxu)基础基础第三十一页，共102页。 规定多项式的乘法运算必须要取模M(x)=x4+1，这样使得次数(csh)小于4的多项式的乘积仍然是一个次数(csh)小于4的多项式，将多项式的模乘运算记为，设 a(x)= a3x3+a2x2+a1x+a0， b(x)= b3x3+b2x2+b1x+b0， c(x)= a(x)b(x)=c3x3+

24、c2x2+c1x+c0。2.1 Rijndael的数学的数学(shxu)基础基础第三十二页，共102页。n由于(yuy)xj mod (x4+1)= x j mod 4，所以nc0=a0b0a3b1a2b2a1b3；nc1= a1b0a0b1a3b2a2b3；nc2= a2b0a1b1a0b2a3b3；nc3= a3b0a2b1a1b2a0b3。2.1 Rijndael的数学的数学(shxu)基基础础第三十三页，共102页。可将上述计算(j sun)表示为321001233012230112303210bbbbaaaaaaaaaaaaaaaacccc2.1 Rijndael的数学的数学(shx

25、u)基础基础第三十四页，共102页。 注意到M(x)不是GF(28)上的不可约多项式（甚至也不是GF(2)上的不可约多项式），因此非0多项式的这种乘法不是群运算。 不过在Rijndael密码中，对多项式b(x)，这种乘法运算只限于乘一个(y )固定的有逆元的多项式a(x)= a3x3+a2x2+a1x+a0。2.1 Rijndael的数学的数学(shxu)基础基础第三十五页，共102页。定理定理(dngl)1 系数在系数在GF(28)上的多项式上的多项式a3x3+a2x2+a1x+a0是模是模x4+1可逆的，可逆的，当且仅当矩阵当且仅当矩阵在在GF(28)上可逆。上可逆。03211032210

26、33210aaaaaaaaaaaaaaaa2.1 Rijndael的数学的数学(shxu)基础基础第三十六页，共102页。证明： a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当存在(cnzi)多项式h3x3+h2x2+h1x+h0，(a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1 mod(x4+1)因此有(a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0 x+h3)=x mod (x4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0 x2+h3x+h2)=x2 mod (x4+1)(a3x3+a2x2+a1x+a0)(h0 x3+

27、h3x2+h2x+h1)=x3 mod(x4+1)；2.1 Rijndael的数学的数学(shxu)基础基础第三十七页，共102页。将以上关系(gun x)写成矩阵形式即得（证毕）032103211032103221032103321032101000010000100001aaaahhhhaaaahhhhaaaahhhhaaaahhhh 2.1 Rijndael的数学的数学(shxu)基础基础第三十八页，共102页。 c(x)=xb(x)定义(dngy)为x与b(x)的模x4+1乘法，即c(x)= xb(x)= b2x3+b1x2+b0 x+b3。其矩阵表示中，除a1=01外，其他所有ai=

28、 00，即 因此，x（或x的幂）模乘多项式相当于对字节构成的向量进行字节循环移位。0011223300000001010000000001000000000100cbcbcbcb2.1 Rijndael的数学的数学(shxu)基础基础第三十九页，共102页。Rijndael密码的设计力求满足以下(yxi)3条标准： 抵抗所有已知的攻击。 在多个平台上速度快，编码紧凑。 设计简单。2.2 Rijndael的设计的设计(shj)思想思想第四十页，共102页。 当前的大多数分组密码，其轮函数是Feistel结构，即将中间状态的部分比特不加改变地简单放置到其他位置。Rijndael没有这种结构，其轮函

29、数是由3个不同的可逆均匀变换组成的，称它们为3个“层”。所谓“均匀变换”是指状态的每个比特都是用类似的方法进行处理的。不同层的特定选择大部分是建立在“宽轨迹策略”的应用基础上的。简单地说，“宽轨迹策略”就是提供(tgng)抗线性密码分析和差分密码分析能力的一种设计。2.2 Rijndael的设计的设计(shj)思想思想第四十一页，共102页。 为实现宽轨迹(guj)策略，轮函数3个层中的每一层都有它自己的功能： 线性混合层 确保多轮之上的高度扩散； 非线性层将具有最优的“最坏情况非线性特性”的S盒并行使用； 密钥加层单轮子密钥简单地异或到中间状态上，实现一次性掩盖。2.2 Rijndael的设

30、计的设计(shj)思想思想第四十二页，共102页。 在第一轮之前，用了一个初始密钥加层，其目的是在不知道密钥的情况下，对最后一个密钥加层以后的任一层（或者是当进行已知明文攻击时，对第一个密钥加层以前的任一层）可简单地剥去，因此初始密钥加层对密码的安全性无任何意义。许多(xdu)密码的设计中都在轮变换之前和之后用了密钥加层，如IDEA、SAFER和Blowfish。2.2 Rijndael的设计的设计(shj)思想思想第四十三页，共102页。 为了使加密算法和解密算法在结构上更加接近，最后一轮的线性混合(hnh)层与前面各轮的线性混合(hnh)层不同，这类似于DES的最后一轮不做左右交换。可以证

31、明这种设计不以任何方式提高或降低该密码的安全性。2.2 Rijndael的设计的设计(shj)思想思想第四十四页，共102页。 Rijndael是一个迭代型分组密码，其分组长度和密钥长度都可变，各自可以独立地指定(zhdng)为128比特、192比特、256比特。3. Rijndael的算法(sun f)说明第四十五页，共102页。 类似于明文分组和密文分组，算法的中间结果(ji gu)也须分组，称算法中间结果(ji gu)的分组为状态，所有的操作都在状态上进行。状态可以用以字节为元素的矩阵阵列表示，该阵列有4行，列数记为Nb，Nb等于分组长度除以32。 例如用128比特密钥加密192比特的明

32、文，则明文和密钥被表示成下面的状态：3.1 状态状态(zhungti)、种子密钥和轮数、种子密钥和轮数第四十六页，共102页。明文(mngwn)状态密钥状态(zhungti)第四十七页，共102页。 种子密钥类似地用一个以字节为元素的矩阵阵列表示，该阵列有4行，列数记为Nk，Nk等于分组长度除以32。表3.8是Nb=6的状态和Nk=4的种子密钥的矩阵阵列表示。（见65页表3.8） 有时可将这些分组当作一维数组，其每一元素是上述阵列表示中的4字节元素构成的列向量，数组长度可为4、6、8，数组元素下标的(bio de)范围分别是03、05和07。4字节元素构成的列向量有时也称为字。3.1 状态状态

33、(zhungti)、种子密钥和轮数、种子密钥和轮数第四十八页，共102页。 算法的输入和输出被看成(kn chn)是由8比特字节构成的一维数组，其元素下标的范围是0(4Nb 1)，因此输入和输出以字节为单位的分组长度分别是16、24和32，其元素下标的范围分别是015、023和031。输入的种子密钥也看成(kn chn)是由8比特字节构成的一维数组，其元素下标的范围是0(4Nk 1)，因此种子密钥以字节为单位的分组长度也分别是16、24和32，其元素下标的范围分别是015、023和031。3.1 状态状态(zhungti)、种子密钥和轮数、种子密钥和轮数第四十九页，共102页。 算法的输入（包

34、括最初的明文(mngwn)输入和中间过程的轮输入）以字节为单位按a00a10a20a30a01a11a21a31的顺序放置到状态阵列中。 同理，种子密钥以字节为单位按k00k10k20k30k01k11k21k31的顺序放置到种子密钥阵列中。 而输出（包括中间过程的轮输出和最后的密文输出）也是以字节为单位按相同的顺序从状态阵列中取出。3.1 状态状态(zhungti)、种子密钥和轮数、种子密钥和轮数第五十页，共102页。n 若输入（或输出）分组中第n个元素对应于状态(zhungti)阵列的第(i, j)位置上的元素，则n和(i, j)有以下关系：i=n mod 4; j= ;n=i+4jn 迭

35、代的轮数记为Nr，Nr与Nb和Nk有关，表给出了Nr与Nb和Nk的关系。4n3.1 状态状态(zhungti)、种子密钥和轮数、种子密钥和轮数 14 14 14 14 12 12 14 12 10rN4bN6bN8bN4kN6kN8kN第五十一页，共102页。 Rijndael的轮函数由4个不同(b tn)的计算部件组成，分别是：字节代换（ByteSub）、行移位（ShiftRow）、列混合（MixColumn）、密钥加（AddRoundKey）。3.2 轮函数轮函数(hnsh)第五十二页，共102页。(1) 字节代换（ByteSub） 字节代换是非线形变换，独立地对状态的每个字节进行。代换表

36、（即S-盒）是可逆的，由以下两个(lin )变换的合成得到： 首先，将字节看作GF(28)上的元素，映射到自己的乘法逆元，00映射到自己。 其次，对字节做如下的（GF(2)上的，可逆的）仿射变换：3.2 轮函数轮函数(hnsh)第五十三页，共102页。0011223344556677100011111110001111111000110111100010111110000011111001001111101000111110yxyxyxyxyxyxyxyx 3.2 轮函数轮函数(hnsh)第五十四页，共102页。 上述(shngsh)S-盒对状态的所有字节所做的变换记为ByteSub (Sta

37、te)图3.19是字节代换示意图。图3.19 字节(z ji)代换示意图3.2 轮函数轮函数(hnsh)第五十五页，共102页。 ByteSub的逆变换由代换(di hun)表的逆表做字节代换(di hun)，可通过如下两步实现: 首先进行仿射变换的逆变换，再求每一字节在GF(28)上逆元。3.2 轮函数轮函数(hnsh)第五十六页，共102页。第五十七页，共102页。S盒对状态盒对状态(zhungti)的所有字节所做的变换记为：的所有字节所做的变换记为： ByteSub(State)第五十八页，共102页。(2) 行移位（ShiftRow） 行移位是将状态阵列的各行进行(jnxng)循环移位

38、，不同状态行的位移量不同。第0行不移动，第1行循环左移C1个字节，第2行循环左移C2个字节，第3行循环左移C3个字节。位移量C1、C2、C3的取值与Nb有关，由表3.10给出。（见66页表3.10） 按指定的位移量对状态的行进行(jnxng)的行移位运算记为ShiftRow (State)图3.20是行移位示意图。3.2 轮函数轮函数(hnsh)第五十九页，共102页。图3.20 行移位(y wi)示意图3.2 轮函数轮函数(hnsh)第六十页，共102页。例如(lr)当Nb=4时，具体的操作如下： 按指定的位移(wiy)量对状态的行进行的行移位运算记为： ShiftRow(state)行移位

39、行移位(y wi)（ShiftRow）第六十一页，共102页。 ShiftRow的逆变换是对状态阵列的后3列分别以位移量Nb-C1、Nb-C2、Nb-C3进行循环移位(y wi)，使得第i行第j列的字节移位(y wi)到(j+Nb-Ci) mod Nb。3.2 轮函数轮函数(hnsh)第六十二页，共102页。（3） 列混合（MixColumn） 在列混合变换中，将状态阵列的每个列视为GF(28)上的多项式，再与一个固定的多项式c(x)进行模x4+1乘法。当然要求c(x)是模x4+1可逆的多项式，否则列混合变换就是不可逆的，因而(yn r)会使不同的输入分组对应的输出分组可能相同。Rijndae

40、l的设计者给出的c(x)为（系数用十六进制数表示）： c(x)=03x3+01x2+01x+023.2 轮函数轮函数(hnsh)第六十三页，共102页。 c(x)是与x4+1互素的，因此(ync)是模x4+1可逆的。列混合运算也可写为矩阵乘法。设b(x)= c(x)a(x)，则3210321002010103030201010103020101010302aaaabbbb3.2 轮函数轮函数(hnsh)第六十四页，共102页。 这个运算需要做GF(28)上的乘法(chngf)，但由于所乘的因子是3个固定的元素02、03、01，所以这些乘法(chngf)运算仍然是比较简单的。 对状态State的

41、所有列所做的列混合运算记为MixColumn（State） 图3.21是列混合运算示意图。3.2 轮函数轮函数(hnsh)第六十五页，共102页。图3.21 列混合(hnh)运算示意图3.2 轮函数轮函数(hnsh) 第六十六页，共102页。列混合列混合(hnh)运算运算第六十七页，共102页。列混合列混合(hnh)运算运算第六十八页，共102页。列混合列混合(hnh)运算运算第六十九页，共102页。 列混合运算的逆运算是类似的，即每列都用一个特定(tdng)的多项式d(x)相乘。d(x)满足(03x3+01x2+01x+02)d(x)=01由此可得d(x)=0Bx3+0Dx2+09x+0E3

42、.2 轮函数轮函数(hnsh)第七十页，共102页。(4) 密钥加（AddRoundKey） 密钥加是将轮密钥简单地与状态进行逐比特异或。轮密钥由种子(zhng zi)密钥通过密钥编排算法得到，轮密钥长度等于分组长度Nb。状态State与轮密钥RoundKey的密钥加运算表示为 AddRoundKey (State, RoundKey)图3.22是密钥加运算示意图。3.2 轮函数轮函数(hnsh)第七十一页，共102页。图3.22 密钥加运算(yn sun)示意图3.2 轮函数轮函数(hnsh)第七十二页，共102页。 密钥加运算的逆运算是其自身。 综上所述，组成Rijndael轮函数的计算部

43、件简捷快速(kui s)，功能互补。轮函数的伪C代码如下：Round (State, RoundKey) ByteSub (State); ShiftRow (State); MixColumn (State); AddRoundKey (State, RoundKey)3.2 轮函数轮函数(hnsh)第七十三页，共102页。 结尾轮的轮函数(hnsh)与前面各轮不同，将MixColumn这一步去掉。其伪C代码如下： FinalRound (State, RoundKey) ByteSub (State); ShiftRow (State); AddRoundKey (State, Round

44、Key)3.2 轮函数轮函数(hnsh)第七十四页，共102页。 在以上伪C代码记法中，State、RoundKey 可用指针类型(lixng)，函数Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey都在指针State、RoundKey所指向的阵列上进行运算。3.2 轮函数轮函数(hnsh)第七十五页，共102页。 密钥编排指从种子密钥得到轮密钥的过程，它由密钥扩展和轮密钥选取两部分组成。其基本原则如下： （1）轮密钥的比特数等于分组长度乘以轮数加1；例如(lr)要将128比特的明文经过10轮的加密，则总共需要（10+1）*128=1

45、408比特的密钥。 （2）种子密钥被扩展成为扩展密钥； （3）轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，如此下去。3.3 3.3 密钥编排密钥编排(binpi)(binpi)第七十六页，共102页。(1) 密钥扩展 扩展密钥是以4字节字为元素的一维阵列，表示为WNb* (Nr+1)，其中(qzhng)前Nk个字取为种子密钥，以后每个字按递归方式定义。扩展算法根据Nk6和Nk6有所不同。3.3 3.3 密钥编排密钥编排(binpi)(binpi)第七十七页，共102页。KeyExpansion (byteKey4*Nk , WNb*(Nr+1)

46、 for (i =0; i Nk; i +)Wi=(Key4* i,Key4* i +1,Key4* i +2,Key4* i +3 ); for (i =Nk; i Nb*(Nr+1); i +) temp=Wi-1;if (i % Nk= =0)temp=SubByte (RotByte (temp)Rconi /Nk;Wi=Wi-Nk temp; 当当Nk6时，扩展算法时，扩展算法(sun f)如下如下 第七十八页，共102页。 其中Key4*Nk为种子密钥，看作以字节为元素的一维阵列。函数SubByte ( )返回4字节字，其中每一个字节都是用Rijndael的S盒作用到输入字对应的字

47、节得到。函数RotByte ( ) 也返回4字节字，该字由输入的字循环(xnhun)移位得到，即当输入字为(a, b, c, d)时，输出字为 (b, c, d, a)。 当当Nk6时，扩展时，扩展(kuzhn)算法如下算法如下 第七十九页，共102页。 可以看出，扩展密钥的前Nk个字即为种子密钥，之后的每个字Wi等于前一个字Wi-1与Nk个位置(wi zhi)之前的字Wi- Nk的异或；不过当i/Nk为整数时，须先将前一个字Wi-1经过以下一系列的变换： 1字节的循环移位RotByte用S盒进行变换SubByte异或轮常数Rconi/Nk。 当当Nk6时，扩展算法时，扩展算法(sun f)如

48、下如下 第八十页，共102页。KeyExpansion (byte Key4*Nk , WNb*(Nr+1) for (i=0; i Nk; i +)Wi=(Key4* i, Key4* i +1, Key4* i +2, Key4* i +3 );for (i =Nk; i 6时，扩展算法时，扩展算法(sun f)如下：如下：第八十一页，共102页。Nk6与Nk6的密钥扩展(kuzhn)算法的区别在于：当i为Nk的4的倍数时，须先将前一个字Wi-1经过SubByte变换。3.3 3.3 密钥编排密钥编排(binpi)(binpi)第八十二页，共102页。 以上两个算法中，Rconi/Nk 为

49、轮常数，其值与Nk无关，定义(dngy)为（字节用十六进制表示，同时理解为GF(28)上的元素）： Rcon i=(RCi, 00, 00, 00) 其中RCi 是GF(28) 中值为xi-1的元素，因此RC1 =1(即01)RCi = x(即02)RCi-1= xi-13.3 3.3 密钥编排密钥编排(binpi)(binpi)第八十三页，共102页。(2) 轮密钥选取(xunq) 轮密钥i（即第i 个轮密钥）由轮密钥缓冲字WNb* i到WNb*(i+1)给出，如图3.23所示。图3.23 Nb=6且Nk=4时的密钥扩展(kuzhn)与轮密钥选取3.3 3.3 密钥编排密钥编排(binpi)

50、(binpi)第八十四页，共102页。 加密算法为顺序(shnx)完成以下操作：初始的密钥加；(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)3.4 3.4 加密算法加密算法第八十五页，共102页。 其中(qzhng)CipherKey

51、是种子密钥，ExpandedKey是扩展密钥。密钥扩展可以事先进行（预计算），且Rijndael密码的加密算法可以用这一扩展密钥来描述，即Rijndael (State, ExpandedKey)AddRoundKey (State, ExpandedKey);for (i=1; i Nr; i +)Round (State, ExpandedKey+Nb* i);FinalRound (State, ExpandedKey+Nb*Nr)3.4 3.4 加密算法加密算法第八十六页，共102页。首先给出几个引理。 引理3.1 设字节代换（ByteSub）、行移位(y wi)（ShiftRow）的

52、逆变换分别为InvByteSub、InvShiftRow。则组合部件“ByteSubShiftRow”的逆变换为“InvByteSubInvShiftRow”。3.5 加解密加解密(ji m)的相近程度及解密的相近程度及解密(ji m)算法算法第八十七页，共102页。n 证明：组合部件“ByteSubShiftRow”的逆变换原本(yunbn)为“InvShiftRowInvByteSub”。由于字节代换（ByteSub）是对每个字节进行相同的变换，故“InvShiftRow”与“InvByteSub”两个计算部件可以交换顺序。（证毕）3.5 加解密的相近加解密的相近(xin jn)程度及解密

53、算法程度及解密算法第八十八页，共102页。 引理3.2 设列混合(hnh)（MixColumn）的逆变换为InvMixColumn。则列混合(hnh)部件与密钥加部件（AddRoundKey）的组合部件“MixColumnAddRoundKey (, Key)”的逆变换为“InvMixColumnAddRoundKey (, InvKey)”。 其中密钥InvKey与Key的关系为： InvKey=InvMixColumn (Key)。3.5 加解密的相近程度加解密的相近程度(chngd)及解密算法及解密算法第八十九页，共102页。证明：组合部件(bjin)“MixColumnAddRound

54、Key (, Key)” 的逆变换原本为“AddRoundKey (, Key)InvMixColumn”，由于列混合（MixColumn）实际上是线性空间GF(28)4上的可逆线性变换，因此“AddRoundKey (, Key)InvMixColumn”=“InvMixColumnAddRoundKey (, InvMixColumn (Key)”（证毕）3.5 加解密加解密(ji m)的相近程度及解密的相近程度及解密(ji m)算法算法第九十页，共102页。引理3.3 将某一轮的后两个计算部件和下一轮的前两个计算部件组成组合(zh)部件，该组合(zh)部件的程序为MixColumn (S

55、tate)； AddRoundKey (State, Key(i); ByteSub (State); ShiftRow (State)则该组合(zh)部件的逆变换程序为InvByteSub (State); InvShiftRow (State); InvMixColumn (State); AddRoundKey (State, InvMixColumn (Key(i)3.5 加解密的相近程度加解密的相近程度(chngd)及解密算法及解密算法第九十一页，共102页。 证明：这是引理3.1和引理3.2的直接推论。 注意到在引理3.3所描述的逆变换中，第2步到第4步在形状上很像加密算法的轮函数，这将是解密算法的轮函数。注意到结尾轮只有(zhyu)3个