《信息安全技术LJ》PPT课件

第五章对称密码体制之三,信息安全技术,5.3高级加密标准AES5.3.0AES概述1997.4.15美国家标准和技术研究所NIST(NationalInstitureofStandardTechnology)发起AES征集1997.9.12在美联邦登记处公布征集公告1998.8.20第一次AES候选会议公布15个算法1999.3.22第二次AES候选会议公布分析测试结果1999.8NIST选出5个候选算法2000.4.13第三次AES候选会议讨论分析测试结果2000.10.2NIST正式宣布获胜者为Rijndael算法（读作“RainDoll”）2001NIST正式发布基于Rijndael算法的AES,设计者比利时Katholieke大学电机系COSIC实验室博士后研究员VincentRijman、比利时Proton国际公司博士设计员JoanDaemen设计准则能抵抗所有已知的攻击多平台运行时速度快、编码简单设计简单安全性时限至少可维持20年,AES与Rijndael算法在概念上的区别AES是NIST所制定的数据加密标准，采用128位分组，128、192或256位密钥的Rijndael算法,Rijndael算法本身是一种可变分组长度和可变密钥长度的分组密码算法，分组长度和密钥长度可独立地设定为128256的32整数倍,密钥安全强度128位密钥空间3.41038，用攻击DES的机器约需1491012年才能穷举攻陷（宇宙诞生至今约小于71010年）192位密钥空间6.21057256位密钥空间1.11077,5.3.1算法描述Rijndael属于对称密码体制Rijndael采用S-P网络结构NIST对Rijndael的评估标准及结论一般安全性没有已知的能攻破Rijndael的攻击方法软件执行具有良好的软件执行性能受限空间环境非常适合在受限空间环境中执行操作硬件执行在反馈模式下速度最快对执行的攻击有利于抵抗能量攻击和计时攻击加密与解密加密与解密算法不同，但速度相当,密钥灵活性支持加密中的快速子密钥计算其他的多功能性和灵活性原则上分组与密钥长度为32的任意倍数指令级并行执行的潜力对于单个分组加密有很好的并行执行能力,5.3.2Square结构（略）,5.3.3基本运算4种变换AK轮密钥加(AddRoundKey)，即异或运算“”BS字节代换(ByteSub)SR行移变换(ShiftRow)MC列混合变换(MixColumn)2种基本运算字节运算（8位）双字运算（4字节）,算法总流程,BS、SR和MC,明文X,轮密钥K0,轮密钥K1,BS、SR和MC,轮密钥Kr-1,BS、SR,轮密钥Kr,密文Y,SR-1、BS-1,明文X,MC-1,SR-1、BS-1,密文Y,MC-1,SR-1、BS-1,AK,AK,AK,AK,AK,AK,AK,AK,第1轮,第r-1轮,第r轮,第1轮,第r-1轮,第r轮,加密,解密,其中：SR-1、BS-1、MC-1分别是SR、BS、MC的逆变换,状态列,明文、密文、中间结果（称为“状态”）和密钥均以先列后行的顺序映射到4行的字节矩阵上，每列对应一个双字（4字节、32位）状态列数记作Nb，Nb=分组长度/32密钥列数记作Nk，Nk=种子密钥长度/32可能的列数Nb、Nk有48（对应的分组或密钥长度为128、160、192、224、256）实际应用时Nb、Nk常取4、6、8之一,轮数r取决于分组长度和密钥长度：,迭代轮数,GF(28)上的字节运算伽罗瓦(Galois)域GF(28)中的元素a是一个字节矢量(a7,a1,a0)=xxH，可表作系数是0或1的次数小于8的多项式：a=a7x7+a1x+a0如：3BH=(00111011)在GF(28)中可以表作x5+x4+x3+x+1在GF(28)中的加法是按位异或在Rijndael中取模m=11BH=(100011011)=x8+x4+x3+x+1,在GF(28)中的乘法是以m为模的多项式乘法，即相乘后再用m约简，记作“”例如：57H83H=(x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1=(x13+x11+x9+x8+x6+x5+x4+x3+1)+x5(x8+x4+x3+x+1)（可任意加上模的倍数）=(x11+x4+x3+1)+x3(x8+x4+x3+x+1)=x7+x6+1=C1H,GF(28)中的元素a乘以x（对应02H）相当于字节(a7,a1,a0)左移1位，但当有溢出时必须用模m=11BH=(100011011)=x8+x4+x3+x+1来约简，这相当于异或11BH。称这种特殊的一元运算为“x乘”。,例如：x57H=x01010111=10101110=AEHxAEH=x10101110=101011100（有溢出）=101011100100011011=01000111=47H；显然：57H04H=(57H02H)02H=x(x57H)=xAEH=47H；而57H03H=(57H02H)+57H=x57H+57H;这就意味着对任意字节a的乘法均可分解为若干x乘运算，以便于算法的程序实现。,在GF(28)中的乘法幺元是01H=(00000001)=1对于GF(28)中的非零a，必存在b，使得ba=1，也即存在c，使得ba+mc=1，或ab=1(modm)，称b为a的乘法逆元，记作“a-1”a=(a7,a1,a0)的乘法逆元a-1可由下述方法算出：设a-1=(x7,x1,x0)，则由aa-1=1(modm)可得关于x7,x1,x0的联立方程组，于是可算出x7,x1,x0，从而得到a-1,4字节列向量的表示与运算在Rijndael中，由4个字节组成的列向量（a0j，a1j，a2j，a3j)被表示为伽罗瓦环GF(28)x/(x4+1)中的元素a系数为两位十六进制数、次方不超过4的多项式a0jx3+a1jx2+a2jx+a3j环中两个元素相加定义为相应的字节在GF(28)中的相加（按位异或）环中两个元素相乘定义为对模m=x4+1=01Hx4+01H的普通多项式相乘，但系数运算遵从GF(28)中的运算,5.3.4基本变换字节代换BSS盒变换分别对状态的所有字节a进行如下仿射变换：,a-1+,b=BS(a)=,其中：a-1是a的乘法逆元,注：计算上定义了一个S盒由16*16个字节组成的矩阵（见下页），包含了256种可能的变换。以输入字节的高4位为行值、低4位作为列值，然后取出S盒中的对应字节作为输出。,用于字节运算的S盒,例：对输入“95H”，在第9行第5列找到输出为“2aH”,行移变换SR将状态的第i行循环左移Ci个字节（i=1,2,3;第0行不动）Ci=1,2,3或4,Ci取决于明文长度(i=1,2,3)：,列混合变换MC对状态的各个字节列Aj进行变换(j=0,1,Nb-1)：,把状态列当作伽罗瓦环GF(28)x/(x4+1)中的多项式a=a0jx3+a1jx2+a2jx+a3j，对一个固定的多项式c=03Hx3+01Hx2+01Hx+02H作模m=01Hx4+01H的乘法a*c。,设某状态列为a(x)=a0jx3+a1jx2+a2jx+a3j，转换后状态列为b(x)=c(x)*a(x)=b0jx3+b1jx2+b2jx+b3j，则可推出：b0j=02Ha0j+03Ha1j+01Ha2j+01Ha3jb1j=01Ha0j+02Ha1j+03Ha2j+01Ha3jb2j=01Ha0j+01Ha1j+02Ha2j+03Ha3jb3j=03Ha0j+01Ha1j+01Ha2j+02Ha3j,用矩阵乘法表示即为：,轮密钥加变换AK对状态的各个字节列与密钥字wj进行按位异或,密钥扩展,种子密钥K=(k0,k1,kNk-1),扩展密钥W=(w0,w1,wNb*(r+1)-1),共Nk个双字，32*Nk位,因需(r+1)个含Nb个双字的轮密钥，故共需Nb*(r+1)个双字的扩展密钥,每个双字4字节32位,5.3.5密钥扩展与调度,对于Nk6,wi=,ki;当i6,wi=,ki;当iNk,wi-NkBS(R(wi-1)ci/Nk;当i是Nk的倍数,wi-Nkwi-1;其余情况,wi-NkBS(wi-1);当i-4是Nk的倍数,例如：设Nk=8，256位种子密钥K=(k0,k1,k2,k3,k4,k5,k6,k7)，则(w0,w1,w2,w3,w4,w5,w6,w7)=(k0,k1,k2,k3,k4,k5,k6,k7)，w8=w0BS(R(w7)(01H00H00H00H)w9=w1w8；w10=w2w9；w11=w3w10w12=w4BS(w11)w13=w5w12；w14=w6w13；w15=w7w14w16=w8BS(R(w15)(02H00H00H00H)w17=w9w16,密钥调度,扩展密钥W=(w0,w1,wNb*(r+1)-1),共Nb*(r+1)个双字,初始轮密钥K0=(w0,w1,wNb-1),第1轮轮密钥K1=(wNb,wNb+1,w2Nb-1),第2轮轮密钥K2=(w2Nb,w2Nb+1,w3Nb-1),第r轮轮密钥Kr=(wr*Nb,wr*Nb+1,w(r+1)*Nb-1),各轮密钥均为Nb个双字,即4*Nb个字节或32*Nb位,例如：设Nb=4、Nk=4，则r=10、扩展密钥双字共4(10+1)=44个。故轮密钥：K0=(w0,w1,w2,w3)、K1=(w4,w5,w6,w7)、K2=(w8,w9,w10,w11)、K10=(w40,w41,w42,w43),又如：设Nb=8、Nk=6，则r=14、扩展密钥双字共8(14+1)=120个。故轮密钥：K0=(w0,w1,w2,w3,w4,w5,w6,w7)、K1=(w8,w9,w10,w11,w12,w13,w14,w15)、K2=(w16,w17,w18,w19,w20,w21,w22,w23)、K14=(w112,w113,w114,w115,w116,w117,w118,w119),5.3.6AES的解密逆字节变换BS-1,用于逆字节运算的逆S盒,例：对输入“2aH”，在第2行第a列找到输出为“95H”,逆行移位变换SR-1将状态的第i行循环右移Ci个字节（Ci的意义同前）例子：第1、2、3行循环右移1、2、3个字节,逆列混淆变换MC-1,逆列混淆的实例：,验证：0E47+0B37+0D94+09ED=87,0E47=（00001110）（01000111）(00000010）+(00000100)+(00001000)（01000111）=(00000010)（01000111）+(00000100)（01000111）+(00001000)（01000111）=(10001110)（左移1位）+(00011100)+(00011011)（左移2位，因有溢出加1BH）+(00001000)（01000111)（左移3位，移2位后再移1位）=(10001110)+(00000111)+(00001110)=(10000111)0B37=(00001011)(00110111)=(00000001)+(00000010)+(00001000)(00110111)=(00110111)+(01101110)+(10111000)+(00011011)=(11111010),0D94=(00001101)(10010100)=(0000001)+(00000100)+(00001000)(10010100)=(10010100)+(01100110)+(11001