高级加密标准的数学基础精选文档.ppt
高级加密标准的数学基础高级加密标准的数学基础本讲稿第一页，共二十四页字节运算：有限域字节运算：有限域GF(28)上的运算上的运算1.有限域有限域GF(23)2.有限域有限域GF(28)3.有限域有限域GF(28)的加法运算的加法运算4.有限域有限域GF(28)的乘法运算的乘法运算本讲稿第二页，共二十四页有限域有限域GF(23)GF(23)表示域中有表示域中有23个元素，除个元素，除0之外的之外的7个元素由个元素由本原多项式构造。本原多项式构造。假定其本原多项式为：假定其本原多项式为：m(x)=x3+x+1本讲稿第三页，共二十四页有限域有限域GF(23)的多项式表示的多项式表示GF(23):000,001,010,011,100,101,110,111 本讲稿第四页，共二十四页有限域有限域GF(23)的本原多项式的根表示的本原多项式的根表示定义为本原多项式定义为本原多项式 m(x)=x3+x+1的根，即的根，即 3+1=0 和和3=+1GF(23):0,0 0,1 1,2 2,3 3,4 4,5 5,6 6 本讲稿第五页，共二十四页有限域有限域GF(28)有限域有限域GF(28)表示特征为表示特征为2的具有的具有28元素的有限域。元素的有限域。这里表示成系数在这里表示成系数在0,1中的多项式的集合：中的多项式的集合：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0这样任意的这样任意的8位二进制数就和有限域中的一个多项式位二进制数就和有限域中的一个多项式建立了一一对应的关系。建立了一一对应的关系。本讲稿第六页，共二十四页加法运算加法运算 在多项式表示中，在多项式表示中，GF(28)上两个元素的和仍然是一上两个元素的和仍然是一个次数不超过个次数不超过7的多项式，其系数等于两个元素对应的多项式，其系数等于两个元素对应系数的模系数的模2加（比特异或）。加（比特异或）。由于每个元素的加法逆元等于自己，所以减法和加由于每个元素的加法逆元等于自己，所以减法和加法相同。法相同。本讲稿第七页，共二十四页乘法运算乘法运算 要计算要计算GF(28)上的乘法，必须先确定一个上的乘法，必须先确定一个GF(2)上的上的8次不可约多项式；次不可约多项式；GF(28)上两个元素的乘积就是这两个多项式的模乘上两个元素的乘积就是这两个多项式的模乘（以这个（以这个8次不可约多项式为模）。次不可约多项式为模）。在在Rijndael密码中，这个密码中，这个8次不可约多项式确定为次不可约多项式确定为m(x)=x8+x4+x3+x+1 它的十六进制表示为它的十六进制表示为11B。本讲稿第八页，共二十四页例题例题 例题例题.计算计算GF(28)上的两个元素上的两个元素10010001和和00100010的乘积。的乘积。答案：答案：10000100本讲稿第九页，共二十四页x乘法乘法 GF(28)上还定义了一个运算，称之为上还定义了一个运算，称之为x乘法，乘法，其定义为其定义为xb(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x(mod m(x)如果如果b7=0，求模结果不变，求模结果不变，否则为乘积结果减去否则为乘积结果减去m(x)，即求乘积结果与，即求乘积结果与m(x)的异或。的异或。由此得出由此得出x（十六进制数（十六进制数02）乘）乘b(x)可以可以 先对先对b(x)在字节内左移一位（最后一位补在字节内左移一位（最后一位补0），），若若b7=1，则再与，则再与1B（其二进制为（其二进制为00011011）做逐比特异或来实）做逐比特异或来实现，现，该运算记为该运算记为b=xtime(a)。本讲稿第十页，共二十四页 AES Logtable 本讲稿第十一页，共二十四页AES alogtable本讲稿第十二页，共二十四页字运算：系数在字运算：系数在GF(28)上的多项式运算上的多项式运算 字：字：4个字节构成的向量个字节构成的向量。4个字节构成的向量可以表示为系数在个字节构成的向量可以表示为系数在GF(28)上的次上的次数小于数小于4的多项式。的多项式。本讲稿第十三页，共二十四页字字（多项式）的加法多项式）的加法 对应的多项式的系数相加对应的多项式的系数相加 本讲稿第十四页，共二十四页字字（多项式）的乘法多项式）的乘法 规定多项式的乘法运算必须要取模规定多项式的乘法运算必须要取模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。由于。由于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。本讲稿第十五页，共二十四页字字（多项式）的乘法多项式）的乘法可将上述计算表示为可将上述计算表示为本讲稿第十六页，共二十四页例题例题例题例题.计算计算0 xB7A5662F 0 x03010102 mod M(x)=X4+1得到得到0 xC7？A0？，请将？，请将?？处填满。？处填满。例题例题.计算计算0 xC7DAA0E6 0 x0B0D090E mod M(x)=X4+1得到得到0 x？A5？2F，请将，请将?？处填满。？处填满。例题例题.计算计算0 x03010102 0 x0B0D090E mod M(x)=X4+1本讲稿第十七页，共二十四页产生过程产生过程1997年年4月月15日，美国日，美国ANSI发起征集发起征集AES（advanced encryption standard）的活动，并为此成立了）的活动，并为此成立了AES工作小组。此次活动的目的工作小组。此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。密码算法，以作为新的数据加密标准。1997年年9月月12日，美国联邦登记处公布了正式征集日，美国联邦登记处公布了正式征集AES候选算法的通候选算法的通告。告。对对AES的基本要求是：的基本要求是：比三重比三重DES快、快、至少与三重至少与三重DES一样安全、一样安全、数据分组长度为数据分组长度为128比特、密钥长度为比特、密钥长度为128/192/256比特。比特。本讲稿第十八页，共二十四页产生过程产生过程1998年年8月月12日，在首届日，在首届AES候选会议（候选会议（first AES candidate conference）上公布了）上公布了AES的的15个候选个候选算法，任由全世界各机构和个人攻击和评论。算法，任由全世界各机构和个人攻击和评论。1999年年3月，在第月，在第2届届AES候选会议（候选会议（second AES candidate conference）上经过对全球各密码机构）上经过对全球各密码机构和个人对候选算法分析结果的讨论，从和个人对候选算法分析结果的讨论，从15个候选算个候选算法中选出了法中选出了5个。个。这这5个是个是RC6、Rijndael、SERPENT、Twofish和和MARS2000年年10月月2日，日，NIST宣布宣布Rijndael作为新的作为新的AES。至此，经过至此，经过3年多的讨论，年多的讨论，Rijndael终于脱颖而出。终于脱颖而出。本讲稿第十九页，共二十四页设计思想设计思想Rijndael密码的设计力求满足以下密码的设计力求满足以下3条标准：条标准：抵抗所有已知的攻击。抵抗所有已知的攻击。在多个平台上速度快，编码紧凑。在多个平台上速度快，编码紧凑。设计简单。设计简单。本讲稿第二十页，共二十四页设计思想设计思想其轮函数是由其轮函数是由3个不同的可逆均匀变换组成的，称它个不同的可逆均匀变换组成的，称它们为们为3个个“层层”。所谓所谓“均匀变换均匀变换”是指状态的每个比特都是用类似的是指状态的每个比特都是用类似的方法进行处理的。方法进行处理的。不同层的特定选择大部分是建立在不同层的特定选择大部分是建立在“宽轨迹策略宽轨迹策略”的的应用基础上的。应用基础上的。简单地说，简单地说，“宽轨迹策略宽轨迹策略”就是提供抗线性密码分析就是提供抗线性密码分析和差分密码分析能力的一种设计。和差分密码分析能力的一种设计。本讲稿第二十一页，共二十四页设计思想设计思想为实现宽轨迹策略，轮函数为实现宽轨迹策略，轮函数3个层中的每一层都有它自个层中的每一层都有它自己的功能：己的功能：线性混合层线性混合层确保多轮之上的高度扩散；确保多轮之上的高度扩散；非线性层非线性层 将具有最优的将具有最优的“最坏情况非线性特性最坏情况非线性特性”的的S盒并行使用；盒并行使用；密钥加层密钥加层 单轮子密钥简单地异或到中间状态上，单轮子密钥简单地异或到中间状态上，实现一次性掩盖。实现一次性掩盖。本讲稿第二十二页，共二十四页下次课内容下次课内容AES算法算法本讲稿第二十三页，共二十四页谢谢大家本讲稿第二十四页，共二十四页
