现代密码学第4章6:AES算法_第1页
现代密码学第4章6:AES算法_第2页
现代密码学第4章6:AES算法_第3页
现代密码学第4章6:AES算法_第4页
现代密码学第4章6:AES算法_第5页
已阅读5页,还剩97页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、1分组密码:分组密码: AESAES算法算法现代密码学现代密码学第第4章章(6)2本节主要内容本节主要内容n1 1、AESAES候选算法产生过程候选算法产生过程n2 2、Rijndael的数学基础和设计思想的数学基础和设计思想n3 3、Rijndael的算法说明的算法说明n4 4、习题、习题3n背景背景 从各方面来看,从各方面来看,DESDES已走到了它生命的尽头。已走到了它生命的尽头。其其56比特密钥实在太小,比特密钥实在太小,虽然三重虽然三重DESDES可以解决密钥长度的可以解决密钥长度的问题,但是问题,但是DESDES的设计主要针对硬件实现,而今在许多的设计主要针对硬件实现,而今在许多领

2、域,需要用软件方法来实现它,在这种情况下,它领域,需要用软件方法来实现它,在这种情况下,它的效率相对较低。鉴于此,的效率相对较低。鉴于此,19971997年年4 4月月1515日美国国家标日美国国家标准和技术研究所(准和技术研究所(NISTNIST)发起征集)发起征集AESAES(AESAESAdvanced Encryption StandardAdvanced Encryption Standard)算法的活动,并成)算法的活动,并成立了立了AESAES工作组。目的是为了确定一个非保密的、公开工作组。目的是为了确定一个非保密的、公开披露的、全球免费使用的加密算法,用于保护下一世披露的、全球

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

4、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。1. AES候选算法产生过程候选算法产生过程5n评选过程中采用的方法评选过程中采用的方法1.1.用量化的或定性的尺度作为选择的标准用量化的或定性的尺度作为选择的标准;2.2.选择一种以上的算法;选择一种以上的算法;3.3.选择一个备用算法;选择一个备用算法;4.考虑公众的建议以改进算法。考虑公众的建议以改进算法。1. AES候选算法产生过程候选算法产生过程6 1998年8月12日,在首届AES候选会议(first AES candidate conference)上公布了AES的15个候选算法,任由全世界

5、各机构和个人攻击和评论,这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个。1. AES候选算法产生过程候选算法产生过程7 这5个是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日,召开了第3届AES候选会议(t

6、hird AES candidate conference),继续对最后5个候选算法进行讨论。2000年10月2日,NIST宣布Rijndael作为新的AES。至此,经过3年多的讨论,Rijndael终于脱颖而出。1. AES候选算法产生过程候选算法产生过程8 Rijndael 由比利时的Joan Daemen和Vincent Rijmen设计,算法的原型是Square算法,它的设计策略是宽轨迹策略(wide trail strategy)。宽轨迹策略是针对差分分析和线性分析提出的,它的最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界;由此,可以分析算法抵抗差分密码分析及线性

7、密码分析的能力。1. AES候选算法产生过程候选算法产生过程9 在宣布最后的在宣布最后的5个候选算法后,个候选算法后,NIST再次再次恳请公众参与对这些算法的评论。恳请公众参与对这些算法的评论。公众对这五公众对这五种候选算法的评阅期于种候选算法的评阅期于20002000年年5 5月月1515日结束。日结束。NIST发布的发布的AES主页主页2提供了大量的关于算提供了大量的关于算法描述、源程序、有关法描述、源程序、有关AES3的论文以及其他的论文以及其他公众评论的信息。公众评论的信息。2000年年4月开始进行第三阶月开始进行第三阶段(段(AES3)的评选,)的评选,AES3共收到共收到37篇提交

8、篇提交给给NIST的论文,并采用了其中的的论文,并采用了其中的24篇。在这篇。在这一阶段的讨论中,这些算法得到了非常深入的一阶段的讨论中,这些算法得到了非常深入的分析。分析。NIST的的AES小组综合所有公众对候选小组综合所有公众对候选算法的评价和分析作了一个非常彻底的评论。算法的评价和分析作了一个非常彻底的评论。1. AES候选算法产生过程候选算法产生过程10 经过长时间的评审和讨论之后,经过长时间的评审和讨论之后,NIST在在2000年年5月宣布选择月宣布选择Rijndael作为作为AES的算法。该算法的开发者提出以下几种发音的算法。该算法的开发者提出以下几种发音供选择供选择Reign D

9、ah1,Rain doll和和 Rhine Dah1。1. AES候选算法产生过程候选算法产生过程11n结果结果 NIST最终选择了最终选择了Rijndael作为作为AES的标的标准,因为全面地考虑,准,因为全面地考虑,Rijndael汇聚了安全,汇聚了安全,性能好,效率高,易用和灵活等优点。性能好,效率高,易用和灵活等优点。 Rijndael使用非线性结构的使用非线性结构的S-boxes,表,表现出足够的安全余地;现出足够的安全余地;Rijndael在无论有无反在无论有无反馈模式的计算环境下的硬,软件中都能显示出馈模式的计算环境下的硬,软件中都能显示出其非常好的性能;它的密钥安装的时间很好,

10、其非常好的性能;它的密钥安装的时间很好,也具有很高的灵活性;也具有很高的灵活性;Rijndael的非常低的内的非常低的内存需求也使它很适合用于受限的环境;存需求也使它很适合用于受限的环境;1. AES候选算法产生过程候选算法产生过程12 Rijndael的操作简单,并可抵御时间的操作简单,并可抵御时间和能量攻击,此外,它还有许多未被特和能量攻击,此外,它还有许多未被特别强调的防御性能;别强调的防御性能;Rijndael在分组长在分组长度和密钥长度的设计上也很灵活,算法度和密钥长度的设计上也很灵活,算法可根据分组长度和密钥长度的不同组合可根据分组长度和密钥长度的不同组合提供不同的迭代次数,虽然这

11、些特征还提供不同的迭代次数,虽然这些特征还需更深入地研究,短期内不可能被利用,需更深入地研究,短期内不可能被利用,但最终,但最终,Rijndael内在的迭代结构会显内在的迭代结构会显示良好的潜能来防御入侵行为。示良好的潜能来防御入侵行为。1. AES候选算法产生过程候选算法产生过程1314n不属于不属于Feistel结构结构n加密、解密相似但不对称加密、解密相似但不对称n支持支持128/32=Nb数据块大小数据块大小n支持支持128/192/256(/32=Nk)密钥长度密钥长度n有较好的数学理论作为基础有较好的数学理论作为基础n结构简单、速度快结构简单、速度快Rijndael 特点特点15K

12、ey Length(Nk words)Block Size(Nb words)Number of Rounds (Nr)AES-1284410AES-1926412AES-2568414AES参数参数16域的概念:一个域的概念:一个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,

13、不能得出a=0 or b=0(6)存在乘法单位元:aI=Ia=a.(7)存在乘法逆元:如果a属于G,且a不等于0,则有ba=ab=I. 给定一个素数,则必存在一个有限域,域中的元素个数为:这类有限域用 来表示。np)(npGF2. Rijndael的数学基础和设计思想的数学基础和设计思想171. 有限域有限域GF(28) 有限域中的元素可以用多种不同的方式表示。对于任意素数的方幂,都有惟一的一个有限域,因此GF(28)的所有表示是同构的,但不同的表示方法会影响到GF(28)上运算的复杂度,本算法采用传统的多项式表示法。2.1 Rijndael的数学基础的数学基础18 将b7b6b5b4b3b2

14、b1b0构成的字节b看成系数在0,1中的多项式b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 例如: 十六进制数57对应的二进制为01010111,看成一个字节,对应的多项式为x6+x4+x2+x+1。 AES的理论基础定义在GF(28) ,其基本的运算有三种,分别为加法,乘法和乘x。2.1 Rijndael的数学基础的数学基础19(1)加法)加法在AES算法中,若两个多项式进行加法运算(加法运算的符号定义为 )运算的方法为两个多项式对应的系数相加后,在取模2运算。 此加法运算可以有XOR运算进行处理,即相加的两个数进行异或运算。2.1 Rijndael的数学基础的数

15、学基础20 在多项式表示中,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 由于每个元素的加法逆元等于自己,所以减法和加法相同。2.1 Rijndael的数学基础的数学基础21(2)乘法)乘法在AES算法中,若两个多项式进行乘法运算(乘法运算的符号定义为 )运算的方法为两个多项式相乘。若运算的结果超过8次方,则必须对此结果对一个多项

16、式m(x)进行模运算。AES算法中定义m(x)多项式为:例如:运算过程如下:2.1 Rijndael的数学基础的数学基础222.1 Rijndael的数学基础的数学基础23 要计算GF(28)上的乘法,必须先确定一个GF(2)上的8次不可约多项式;GF(28)上两个元素的乘积就是这两个多项式的模乘(以这个8次不可约多项式为模)。 在Rijndael密码中,这个8次不可约多项式确定为 m(x)= x8+x4+x3+x+1它的十六进制表示为11B。2.1 Rijndael的数学基础的数学基础24n 例如,5783=C1可表示为以下的多项式乘法:n (x6+x4+x2+x+1)(x7+x+1)=x7

17、+x6+1(mod m(x)n 乘法运算虽然不是标准的按字节的运算,但也是比较简单的计算部件。2.1 Rijndael的数学基础的数学基础25 以上定义的乘法满足交换律,且有单位元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)的结构。2.1 Rijndael的数学基础的数学基础26(

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

19、基础28 GF(28)上还定义了一个运算,称之为x乘法,其定义为xb(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x(mod m(x) 如果b7=0,求模结果不变,否则为乘积结果减去m(x),即求乘积结果与m(x)的异或。2.1 Rijndael的数学基础的数学基础29n 由此得出x(十六进制数02)乘b(x)可以先对b(x)在字节内左移一位(最后一位补0),若b7=1,则再与1B(其二进制为00011011)做逐比特异或来实现,该运算记为b=xtime(a)。n 在专用芯片中,xtime只需4个异或。x的幂乘运算可以重复应用xtime来实现。而任意常数

20、乘法可以通过对中间结果相加实现。2.1 Rijndael的数学基础的数学基础30例如,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的数学基础的数学基础312. 系数在系数在GF(28)上的多项式上的多项式 4个字节构成的向量可以表示为系数在GF(28)上的次数小于4的多项式。 多项式的加法就是对应系数相加;换句话说,多项式的加法就是4字节向量的逐比特异或。2.1 Rijndael的数学基础的

21、数学基础32 规定多项式的乘法运算必须要取模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。2.1 Rijndael的数学基础的数学基础33n由于xj mod (x4+1)= x j mod 4,所以nc0=a0b0a3b1a2b2a1b3;nc1= a1b0a0b1a3b2a2b3;nc2= a2b0a1b1a0b2a3b3;nc3= a3b0a2b1a1b2a0b3。2.

22、1 Rijndael的数学基础的数学基础34可将上述计算表示为321001233012230112303210bbbbaaaaaaaaaaaaaaaacccc2.1 Rijndael的数学基础的数学基础35 注意到M(x)不是GF(28)上的不可约多项式(甚至也不是GF(2)上的不可约多项式),因此非0多项式的这种乘法不是群运算。 不过在Rijndael密码中,对多项式b(x),这种乘法运算只限于乘一个固定的有逆元的多项式a(x)= a3x3+a2x2+a1x+a0。2.1 Rijndael的数学基础的数学基础36定理定理1 系数在系数在GF(28)上的多项式上的多项式a3x3+a2x2+a1

23、x+a0是模是模x4+1可逆的,当可逆的,当且仅当矩阵且仅当矩阵在在GF(28)上可逆。上可逆。0321103221033210aaaaaaaaaaaaaaaa2.1 Rijndael的数学基础的数学基础37证明: 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+h0 x+h3)=x mod (x4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0 x2+h3x+h2)=x

24、2 mod (x4+1)(a3x3+a2x2+a1x+a0)(h0 x3+h3x2+h2x+h1)=x3 mod(x4+1);2.1 Rijndael的数学基础的数学基础38将以上关系写成矩阵形式即得(证毕)032103211032103221032103321032101000010000100001aaaahhhhaaaahhhhaaaahhhhaaaahhhh 2.1 Rijndael的数学基础的数学基础39 c(x)=xb(x)定义为x与b(x)的模x4+1乘法,即c(x)= xb(x)= b2x3+b1x2+b0 x+b3。其矩阵表示中,除a1=01外,其他所有ai= 00,即 因此

25、,x(或x的幂)模乘多项式相当于对字节构成的向量进行字节循环移位。0011223300000001010000000001000000000100cbcbcbcb2.1 Rijndael的数学基础的数学基础40Rijndael密码的设计力求满足以下3条标准: 抵抗所有已知的攻击。 在多个平台上速度快,编码紧凑。 设计简单。2.2 Rijndael的设计思想的设计思想41 当前的大多数分组密码,其轮函数是Feistel结构,即将中间状态的部分比特不加改变地简单放置到其他位置。Rijndael没有这种结构,其轮函数是由3个不同的可逆均匀变换组成的,称它们为3个“层”。所谓“均匀变换”是指状态的每个

26、比特都是用类似的方法进行处理的。不同层的特定选择大部分是建立在“宽轨迹策略”的应用基础上的。简单地说,“宽轨迹策略”就是提供抗线性密码分析和差分密码分析能力的一种设计。2.2 Rijndael的设计思想的设计思想42 为实现宽轨迹策略,轮函数3个层中的每一层都有它自己的功能: 线性混合层线性混合层 确保多轮之上的高度扩散; 非线性层非线性层将具有最优的“最坏情况非线性特性”的S盒并行使用; 密钥加层密钥加层单轮子密钥简单地异或到中间状态上,实现一次性掩盖。2.2 Rijndael的设计思想的设计思想43 在第一轮之前,用了一个初始密钥加层,其目的是在不知道密钥的情况下,对最后一个密钥加层以后的

27、任一层(或者是当进行已知明文攻击时,对第一个密钥加层以前的任一层)可简单地剥去,因此初始密钥加层对密码的安全性无任何意义。许多密码的设计中都在轮变换之前和之后用了密钥加层,如IDEA、SAFER和Blowfish。2.2 Rijndael的设计思想的设计思想44 为了使加密算法和解密算法在结构上更加接近,最后一轮的线性混合层与前面各轮的线性混合层不同,这类似于DES的最后一轮不做左右交换。可以证明这种设计不以任何方式提高或降低该密码的安全性。2.2 Rijndael的设计思想的设计思想45 Rijndael是一个迭代型分组密码,其分组长度和密钥长度都可变,各自可以独立地指定为128比特、192

28、比特、256比特。3. Rijndael的算法说明的算法说明46 类似于明文分组和密文分组,算法的中间结果也须分组,称算法中间结果的分组为状态,所有的操作都在状态上进行。状态可以用以字节为元素的矩阵阵列表示,该阵列有4行,列数记为Nb,Nb等于分组长度除以32。 例如用128比特密钥加密192比特的明文,则明文和密钥被表示成下面的状态:3.1 状态、种子密钥和轮数状态、种子密钥和轮数47明文状态密钥状态48 种子密钥类似地用一个以字节为元素的矩阵阵列表示,该阵列有4行,列数记为Nk,Nk等于分组长度除以32。表3.8是Nb=6的状态和Nk=4的种子密钥的矩阵阵列表示。(见65页表3.8) 有时

29、可将这些分组当作一维数组,其每一元素是上述阵列表示中的4字节元素构成的列向量,数组长度可为4、6、8,数组元素下标的范围分别是03、05和07。4字节元素构成的列向量有时也称为字。3.1 状态、种子密钥和轮数状态、种子密钥和轮数49 算法的输入和输出被看成是由8比特字节构成的一维数组,其元素下标的范围是0(4Nb 1),因此输入和输出以字节为单位的分组长度分别是16、24和32,其元素下标的范围分别是015、023和031。输入的种子密钥也看成是由8比特字节构成的一维数组,其元素下标的范围是0(4Nk 1),因此种子密钥以字节为单位的分组长度也分别是16、24和32,其元素下标的范围分别是01

30、5、023和031。3.1 状态、种子密钥和轮数状态、种子密钥和轮数50 算法的输入(包括最初的明文输入和中间过程的轮输入)以字节为单位按a00a10a20a30a01a11a21a31的顺序放置到状态阵列中。 同理,种子密钥以字节为单位按k00k10k20k30k01k11k21k31的顺序放置到种子密钥阵列中。 而输出(包括中间过程的轮输出和最后的密文输出)也是以字节为单位按相同的顺序从状态阵列中取出。3.1 状态、种子密钥和轮数状态、种子密钥和轮数51n 若输入(或输出)分组中第n个元素对应于状态阵列的第(i, j)位置上的元素,则n和(i, j)有以下关系:i=n mod 4; j=

31、;n=i+4jn 迭代的轮数记为Nr,Nr与Nb和Nk有关,表给出了Nr与Nb和Nk的关系。4n3.1 状态、种子密钥和轮数状态、种子密钥和轮数 14 14 14 14 12 12 14 12 10rN4bN6bN8bN4kN6kN8kN52 Rijndael的轮函数由4个不同的计算部件组成,分别是:字节代换(ByteSub)、行移位(ShiftRow)、列混合(MixColumn)、密钥加(AddRoundKey)。3.2 轮函数轮函数53(1) 字节代换(ByteSub) 字节代换是非线形变换,独立地对状态的每个字节进行。代换表(即S-盒)是可逆的,由以下两个变换的合成得到: 首先,将字节

32、看作GF(28)上的元素,映射到自己的乘法逆元,00映射到自己。 其次,对字节做如下的(GF(2)上的,可逆的)仿射变换:3.2 轮函数轮函数540011223344556677100011111110001111111000110111100010111110000011111001001111101000111110yxyxyxyxyxyxyxyx 3.2 轮函数轮函数55 上述S-盒对状态的所有字节所做的变换记为ByteSub (State)图3.19是字节代换示意图。图3.19 字节代换示意图3.2 轮函数轮函数56 ByteSub的逆变换由代换表的逆表做字节代换,可通过如下两步实现:

33、 首先进行仿射变换的逆变换,再求每一字节在GF(28)上逆元。3.2 轮函数轮函数5758S盒对状态的所有字节所做的变换记为:盒对状态的所有字节所做的变换记为: ByteSub(State)59(2) 行移位(ShiftRow) 行移位是将状态阵列的各行进行循环移位,不同状态行的位移量不同。第0行不移动,第1行循环左移C1个字节,第2行循环左移C2个字节,第3行循环左移C3个字节。位移量C1、C2、C3的取值与Nb有关,由表3.10给出。(见66页表3.10) 按指定的位移量对状态的行进行的行移位运算记为ShiftRow (State)图3.20是行移位示意图。3.2 轮函数轮函数60图3.2

34、0 行移位示意图3.2 轮函数轮函数61例如当Nb=4时,具体的操作如下: 按指定的位移量对状态的行进行的行移位运算记为: ShiftRow(state)行移位(行移位(ShiftRow)62 ShiftRow的逆变换是对状态阵列的后3列分别以位移量Nb-C1、Nb-C2、Nb-C3进行循环移位,使得第i行第j列的字节移位到(j+Nb-Ci) mod Nb。3.2 轮函数轮函数63(3) 列混合(MixColumn) 在列混合变换中,将状态阵列的每个列视为GF(28)上的多项式,再与一个固定的多项式c(x)进行模x4+1乘法。当然要求c(x)是模x4+1可逆的多项式,否则列混合变换就是不可逆的

35、,因而会使不同的输入分组对应的输出分组可能相同。Rijndael的设计者给出的c(x)为(系数用十六进制数表示): c(x)=03x3+01x2+01x+023.2 轮函数轮函数64 c(x)是与x4+1互素的,因此是模x4+1可逆的。列混合运算也可写为矩阵乘法。设b(x)= c(x)a(x),则3210321002010103030201010103020101010302aaaabbbb3.2 轮函数轮函数65 这个运算需要做GF(28)上的乘法,但由于所乘的因子是3个固定的元素02、03、01,所以这些乘法运算仍然是比较简单的。 对状态State的所有列所做的列混合运算记为MixColu

36、mn(State) 图3.21是列混合运算示意图。3.2 轮函数轮函数66图3.21 列混合运算示意图3.2 轮函数轮函数 67列混合运算列混合运算68列混合运算列混合运算69列混合运算列混合运算70 列混合运算的逆运算是类似的,即每列都用一个特定的多项式d(x)相乘。d(x)满足(03x3+01x2+01x+02)d(x)=01由此可得d(x)=0Bx3+0Dx2+09x+0E3.2 轮函数轮函数71(4) 密钥加(AddRoundKey) 密钥加是将轮密钥简单地与状态进行逐比特异或。轮密钥由种子密钥通过密钥编排算法得到,轮密钥长度等于分组长度Nb。状态State与轮密钥RoundKey的密

37、钥加运算表示为 AddRoundKey (State, RoundKey)图3.22是密钥加运算示意图。3.2 轮函数轮函数72图3.22 密钥加运算示意图3.2 轮函数轮函数73 密钥加运算的逆运算是其自身。 综上所述,组成Rijndael轮函数的计算部件简捷快速,功能互补。轮函数的伪C代码如下:Round (State, RoundKey) ByteSub (State); ShiftRow (State); MixColumn (State); AddRoundKey (State, RoundKey)3.2 轮函数轮函数74 结尾轮的轮函数与前面各轮不同,将MixColumn这一步去掉

38、。其伪C代码如下: FinalRound (State, RoundKey) ByteSub (State); ShiftRow (State); AddRoundKey (State, RoundKey)3.2 轮函数轮函数75 在以上伪C代码记法中,State、RoundKey 可用指针类型,函数Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey都在指针State、RoundKey所指向的阵列上进行运算。3.2 轮函数轮函数76 密钥编排指从种子密钥得到轮密钥的过程,它由密钥扩展和轮密钥选取两部分组成。其基本原则如下: (1)轮密

39、钥的比特数等于分组长度乘以轮数加1;例如要将128比特的明文经过10轮的加密,则总共需要(10+1)*128=1408比特的密钥。 (2)种子密钥被扩展成为扩展密钥; (3)轮密钥从扩展密钥中取,其中第1轮轮密钥取扩展密钥的前Nb个字,第2轮轮密钥取接下来的Nb个字,如此下去。3.3 3.3 密钥编排密钥编排77(1) 密钥扩展 扩展密钥是以4字节字为元素的一维阵列,表示为WNb* (Nr+1),其中前Nk个字取为种子密钥,以后每个字按递归方式定义。扩展算法根据Nk6和Nk6有所不同。3.3 3.3 密钥编排密钥编排78KeyExpansion (byteKey4*Nk , WNb*(Nr+1

40、) 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时,扩展算法如下时,扩展算法如下 79 其中Key4*Nk为种子密钥,看作以字节为元素的一维阵列。函数SubByte ( )返回4字节字,其中每一个字节都是用Rijndael的S盒作用到输入字对应的字节得到。函数RotByte (

41、) 也返回4字节字,该字由输入的字循环移位得到,即当输入字为(a, b, c, d)时,输出字为 (b, c, d, a)。 当当Nk6时,扩展算法如下时,扩展算法如下 80 可以看出,扩展密钥的前Nk个字即为种子密钥,之后的每个字Wi等于前一个字Wi-1与Nk个位置之前的字Wi- Nk的异或;不过当i/Nk为整数时,须先将前一个字Wi-1经过以下一系列的变换: 1字节的循环移位RotByte用S盒进行变换SubByte异或轮常数Rconi/Nk。 当当Nk6时,扩展算法如下时,扩展算法如下 81KeyExpansion (byte Key4*Nk , WNb*(Nr+1) for (i=0;

42、 i Nk; i +)Wi=(Key4* i, Key4* i +1, Key4* i +2, Key4* i +3 );for (i =Nk; i 6时,扩展算法如下:时,扩展算法如下:82Nk6与Nk6的密钥扩展算法的区别在于:当i为Nk的4的倍数时,须先将前一个字Wi-1经过SubByte变换。3.3 3.3 密钥编排密钥编排83 以上两个算法中,Rconi/Nk 为轮常数,其值与Nk无关,定义为(字节用十六进制表示,同时理解为GF(28)上的元素): Rcon i=(RCi, 00, 00, 00) 其中RCi 是GF(28) 中值为xi-1的元素,因此RC1 =1(即01)RCi =

43、 x(即02)RCi-1= xi-13.3 3.3 密钥编排密钥编排84(2) 轮密钥选取 轮密钥i(即第i 个轮密钥)由轮密钥缓冲字WNb* i到WNb*(i+1)给出,如图3.23所示。图3.23 Nb=6且Nk=4时的密钥扩展与轮密钥选取3.3 3.3 密钥编排密钥编排85 加密算法为顺序完成以下操作:初始的密钥加;(Nr-1)轮迭代;一个结尾轮。即Rijndael (State, CipherKey)KeyExpansion (CipherKey, ExpandedKey);AddRoundKey (State, ExpandedKey);for (i=1; i Nr; i +) Ro

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

45、 ExpandedKey+Nb*Nr)3.4 3.4 加密算法加密算法87首先给出几个引理。 引理3.1 设字节代换(ByteSub)、行移位(ShiftRow)的逆变换分别为InvByteSub、InvShiftRow。则组合部件“ByteSubShiftRow”的逆变换为“InvByteSubInvShiftRow”。3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法88n 证明:组合部件“ByteSubShiftRow”的逆变换原本为“InvShiftRowInvByteSub”。由于字节代换(ByteSub)是对每个字节进行相同的变换,故“InvShiftRow”与“InvB

46、yteSub”两个计算部件可以交换顺序。(证毕)3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法89 引理3.2 设列混合(MixColumn)的逆变换为InvMixColumn。则列混合部件与密钥加部件(AddRoundKey)的组合部件“MixColumnAddRoundKey (, Key)”的逆变换为“InvMixColumnAddRoundKey (, InvKey)”。 其中密钥InvKey与Key的关系为: InvKey=InvMixColumn (Key)。3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法90证明:组合部件“MixColumnAddRou

47、ndKey (, Key)” 的逆变换原本为“AddRoundKey (, Key)InvMixColumn”,由于列混合(MixColumn)实际上是线性空间GF(28)4上的可逆线性变换,因此“AddRoundKey (, Key)InvMixColumn”=“InvMixColumnAddRoundKey (, InvMixColumn (Key)”(证毕)3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法91引理3.3 将某一轮的后两个计算部件和下一轮的前两个计算部件组成组合部件,该组合部件的程序为MixColumn (State); AddRoundKey (State, Key(i); ByteSub (State); ShiftRow (State)则该组合部件的逆变换程序为InvByteSub (State); InvShiftRow (State); InvMixColumn (State); AddRoundKey (State, InvMixColumn (Key(i)3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法92 证明:这是引理3.1和引理3.2的直接推论。 注意到在引理3.3所描述的逆变换中,第2步到第4步在形状上很像加密算法的轮函数,这将是解密算法的轮函数。

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论