现代密码学第4章6：AES算法

1分组密码：AES算法《现代密码学》第4章(6)2本节主要内容1、AES候选算法产生过程2、Rijndael的数学基础和设计思想3、Rijndael的算法说明4、习题3背景从各方面来看，DES已走到了它生命的尽头。其56比特密钥实在太小，虽然三重DES可以解决密钥长度的问题，但是DES的设计主要针对硬件实现，而今在许多领域，需要用软件方法来实现它，在这种情况下，它的效率相对较低。鉴于此，1997年4月15日美国国家标准和技术研究所（NIST）发起征集AES（AES—AdvancedEncryptionStandard）算法的活动，并成立了AES工作组。目的是为了确定一个非保密的、公开披露的、全球免费使用的加密算法，用于保护下一世纪政府的敏感信息。也希望能够成为保密和非保密部门公用的数据加密标准（DES）。1.AES候选算法产生过程41997年4月15日，美国ANSI发起征集AES（advancedencryptionstandard）的活动，并为此成立了AES工作小组。此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。1.AES候选算法产生过程5评选过程中采用的方法1.用量化的或定性的尺度作为选择的标准；2.选择一种以上的算法；3.选择一个备用算法；4.考虑公众的建议以改进算法。1.AES候选算法产生过程61998年8月12日，在首届AES候选会议（firstAEScandidateconference）上公布了AES的15个候选算法，任由全世界各机构和个人攻击和评论，这15个候选算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。1999年3月，在第2届AES候选会议（secondAEScandidateconference）上经过对全球各密码机构和个人对候选算法分析结果的讨论，从15个候选算法中选出了5个。1.AES候选算法产生过程7这5个是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日，召开了第3届AES候选会议（thirdAEScandidateconference），继续对最后5个候选算法进行讨论。2000年10月2日，NIST宣布Rijndael作为新的AES。至此，经过3年多的讨论，Rijndael终于脱颖而出。1.AES候选算法产生过程8Rijndael由比利时的JoanDaemen和VincentRijmen设计，算法的原型是Square算法，它的设计策略是宽轨迹策略（widetrailstrategy）。宽轨迹策略是针对差分分析和线性分析提出的，它的最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界；由此，可以分析算法抵抗差分密码分析及线性密码分析的能力。1.AES候选算法产生过程9在宣布最后的5个候选算法后，NIST再次恳请公众参与对这些算法的评论。公众对这五种候选算法的评阅期于2000年5月15日结束。NIST发布的AES主页[2]提供了大量的关于算法描述、源程序、有关AES3的论文以及其他公众评论的信息。2000年4月开始进行第三阶段（AES3）的评选，AES3共收到37篇提交给NIST的论文，并采用了其中的24篇。在这一阶段的讨论中，这些算法得到了非常深入的分析。NIST的AES小组综合所有公众对候选算法的评价和分析作了一个非常彻底的评论。1.AES候选算法产生过程10经过长时间的评审和讨论之后，NIST在2000年5月宣布选择Rijndael作为AES的算法。该算法的开发者提出以下几种发音供选择ReignDah1，Raindoll和RhineDah1。1.AES候选算法产生过程11结果NIST最终选择了Rijndael作为AES的标准，因为全面地考虑，Rijndael汇聚了安全，性能好，效率高，易用和灵活等优点。Rijndael使用非线性结构的S-boxes，表现出足够的安全余地；Rijndael在无论有无反馈模式的计算环境下的硬，软件中都能显示出其非常好的性能；它的密钥安装的时间很好，也具有很高的灵活性；Rijndael的非常低的内存需求也使它很适合用于受限的环境；1.AES候选算法产生过程12Rijndael的操作简单，并可抵御时间和能量攻击，此外，它还有许多未被特别强调的防御性能；Rijndael在分组长度和密钥长度的设计上也很灵活，算法可根据分组长度和密钥长度的不同组合提供不同的迭代次数，虽然这些特征还需更深入地研究，短期内不可能被利用，但最终，Rijndael内在的迭代结构会显示良好的潜能来防御入侵行为。1.AES候选算法产生过程1314不属于Feistel结构加密、解密相似但不对称支持128/32=Nb数据块大小支持128/192/256(/32=Nk)密钥长度有较好的数学理论作为基础结构简单、速度快Rijndael特点15KeyLength(Nkwords)BlockSize(Nbwords)NumberofRounds(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,不能得出a=0orb=0（6）存在乘法单位元：aI=Ia=a.（7）存在乘法逆元：如果a属于G,且a不等于0,则有ba=ab=I.给定一个素数，则必存在一个有限域，域中的元素个数为：这类有限域用来表示。np)(npGF2.Rijndael的数学基础和设计思想171.有限域GF(28)有限域中的元素可以用多种不同的方式表示。对于任意素数的方幂，都有惟一的一个有限域，因此GF(28)的所有表示是同构的，但不同的表示方法会影响到GF(28)上运算的复杂度，本算法采用传统的多项式表示法。2.1Rijndael的数学基础18将b7b6b5b4b3b2b1b0构成的字节b看成系数在{0,1}中的多项式b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如：十六进制数‘57’对应的二进制为01010111，看成一个字节，对应的多项式为x6+x4+x2+x+1。AES的理论基础定义在GF(28),其基本的运算有三种，分别为加法，乘法和乘x。2.1Rijndael的数学基础19（1）加法在AES算法中，若两个多项式进行加法运算（加法运算的符号定义为）运算的方法为两个多项式对应的系数相加后，在取模2运算。此加法运算可以有XOR运算进行处理，即相加的两个数进行异或运算。2.1Rijndael的数学基础20在多项式表示中，GF(28)上两个元素的和仍然是一个次数不超过7的多项式，其系数等于两个元素对应系数的模2加（比特异或）。例如：‘57’+‘83’=‘D4’，用多项式表示为(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2(modm(x))用二进制表示为01010111+10000011=11010100由于每个元素的加法逆元等于自己，所以减法和加法相同。2.1Rijndael的数学基础21（2）乘法在AES算法中，若两个多项式进行乘法运算（乘法运算的符号定义为）运算的方法为两个多项式相乘。若运算的结果超过8次方，则必须对此结果对一个多项式m(x)进行模运算。AES算法中定义m(x)多项式为：例如：运算过程如下：2.1Rijndael的数学基础222.1Rijndael的数学基础23要计算GF(28)上的乘法，必须先确定一个GF(2)上的8次不可约多项式；GF(28)上两个元素的乘积就是这两个多项式的模乘（以这个8次不可约多项式为模）。在Rijndael密码中，这个8次不可约多项式确定为m(x)=x8+x4+x3+x+1它的十六进制表示为‘11B’。2.1Rijndael的数学基础24例如，‘57’·‘83’=‘C1’可表示为以下的多项式乘法：(x6+x4+x2+x+1)·(x7+x+1)=x7+x6+1(modm(x))乘法运算虽然不是标准的按字节的运算，但也是比较简单的计算部件。2.1Rijndael的数学基础25以上定义的乘法满足交换律，且有单位元‘01’。另外，对任何次数小于8的多项式b(x)，可用推广的欧几里得算法得b(x)a(x)+m(x)c(x)=1即a(x)·b(x)=1modm(x)，因此a(x)是b(x)的乘法逆元。再者，乘法还满足分配律：a(x)·(b(x)+c(x))=a(x)·b(x)+a(x)·c(x)所以，256个字节值构成的集合，在以上定义的加法和乘法运算下，有有限域GF(28)的结构。2.1Rijndael的数学基础26（3）乘X运算在AES算法中，若一最高项指数不大于7的多项式b(x)乘上x的乘法运算，称为xtime运算。例如：如果，求模结果不变，否则要对乘积结果对m(x)求模。求模过程可以用乘积结果减去m(x).在具体运算时可以用下面的方法：x乘b(x)可以先对b(x)在字节内左移一位，若，则再与‘1b’做逐比特的异或运算来实现。该运算记为b=xtime(a)。在专用的芯片中只需4个异或。07b17b注意：X的幂乘运算可以重复应用xtime来实现。对任意常数的乘法可以通过对中间结果相加来实现。2.1Rijndael的数学基础27例如：2.1Rijndael的数学基础28GF(28)上还定义了一个运算，称之为x乘法，其定义为x·b(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x(modm(x))如果b7=0，求模结果不变，否则为乘积结果减去m(x)，即求乘积结果与m(x)的异或。2.1Rijndael的数学基础29由此得出x（十六进制数‘02’）乘b(x)可以先对b(x)在字节内左移一位（最后一位补0），若b7=1，则再与‘1B’（其二进制为00011011）做逐比特异或来实现，该运算记为b=xtime(a)。在专用芯片中，xtime只需4个异或。x的幂乘运算可以重复应用xtime来实现。而任意常数乘法可以通过对中间结果相加实现。2.1Rijndael的数学基础30例如，‘57’·‘13’可按如下方式实现：‘57’·‘02’=xtime(57)=‘AE’；‘57’·‘04’=xtime(AE)=‘47’；‘57’·‘08’=xtime(47)=‘8E’；‘57’·‘10’=xtime(8E)=‘07’；‘57’·‘13’=‘57’·(‘01’‘02’‘10’)=‘57’‘AE’‘07’=‘FE’。2.1Rijndael的数学基础312.系数在GF(28)上的多项式4个字节构成的向量可以表示为系数在GF(28)上的次数小于4的多项式。多项式的加法就是对应系数相加；换句话说，多项式的加法就是4字节向量的逐比特异或。2.1Rijndael的数学基础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.1Rijndael的数学基础33由于xjmod(x4+1)=xjmod4，所以c0=a0b0a3b1a2b