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

第五章 对称密码体制之三,信息安全技术,5.3 高级加密标准AES 5.3.0 AES概述 1997.4.15美国家标准和技术研究所NIST(National Institure of Standard Technology)发起AES征集 1997.9.12在美联邦登记处公布征集公告 1998.8.20第一次AES候选会议公布15个算法 1999.3.22第二次AES候选会议公布分析测试结果 1999.8 NIST选出5个候选算法 2000.4.13第三次AES候选会议讨论分析测试结果 2000.10.2 NIST正式宣布获胜者为Rijndael算法（读作“Rain Doll”） 2001 NIST正式发布基于Rijndael算法的AES,设计者比利时Katholieke大学电机系COSIC实验室博士后研究员Vincent Rijman、比利时Proton国际公司博士设计员Joan Daemen 设计准则 能抵抗所有已知的攻击 多平台运行时速度快、编码简单 设计简单 安全性时限至少可维持20年,AES与Rijndael算法在概念上的区别 AES是NIST所制定的数据加密标准，采用128位分组，128、192或256位密钥的Rijndael算法,Rijndael算法本身是一种可变分组长度和可变密钥长度的分组密码算法，分组长度和密钥长度可独立地设定为128256的32整数倍,密钥安全强度 128位密钥空间3.41038，用攻击DES的机器约需149 1012年才能穷举攻陷（宇宙诞生至今约小于7 1010年） 192位密钥空间 6.21057 256位密钥空间 1.1 1077,5.3.1 算法描述 Rijndael属于对称密码体制 Rijndael采用S-P网络结构 NIST对Rijndael 的评估标准及结论 一般安全性没有已知的能攻破Rijndael 的攻击方法 软件执行 具有良好的软件执行性能 受限空间环境非常适合在受限空间环境中执行操作 硬件执行在反馈模式下速度最快 对执行的攻击有利于抵抗能量攻击和计时攻击 加密与解密加密与解密算法不同，但速度相当,密钥灵活性支持加密中的快速子密钥计算 其他的多功能性和灵活性原则上分组与密钥长度为32的任意倍数 指令级并行执行的潜力对于单个分组加密有很好的并行执行能力,5.3.2 Square结构（略）,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约简，记作“ ” 例如：57H 83H = ( 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乘”。,例如： x 57H=x 01010111=10101110=AEH x AEH=x 10101110=101011100（有溢出） =101011100 100011011=01000111=47H； 显然：57H 04H= (57H 02H) 02H = x (x 57H)=x AEH =47H； 而57H 03H = (57H 02H)+57H =x 57H +57H; 这就意味着对任意字节a的乘法均可分解为 若干x乘运算，以便于算法的程序实现。,在GF(28)中的乘法幺元是01H=(00000001)=1 对于GF(28)中的非零a，必存在b，使得b a=1，也即存在c，使得b a +m c=1，或a b=1 (mod m)，称b为a的乘法逆元，记作“a-1” a = (a7,a1,a0)的乘法逆元a-1可由下述方法算出： 设a-1 = (x7,x1,x0)，则由a a-1 =1 (mod m)可得关于x7,x1,x0的联立方程组，于是可算出x7,x1,x0 ，从而得到a-1,4字节列向量的表示与运算 在Rijndael中，由4个字节组成的列向量（a0j，a1j，a2j，a3j )被表示为伽罗瓦环GF(28)x/(x4+1)中的元素a 系数为两位十六进制数、次方不超过4的多项式a0j x3 + a1j x2 + a2j x + a3j 环中两个元素相加定义为相应的字节在GF(28)中的相加（按位异或） 环中两个元素相乘定义为对模m=x4+1=01H x4+01H 的普通多项式相乘，但系数运算遵从GF(28)中的运算,5.3.4 基本变换 字节代换BS S盒变换 分别对状态的所有字节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= a0j x3 + a1j x2 + a2j x + a3j ，对一个固定的多项式c= 03H x3 + 01H x2 + 01H x + 02H作模m=01H x4+01H的乘法a * c 。,设某状态列为 a(x) = a0j x3 + a1j x2 + a2j x + a3j ， 转换后状态列为 b(x) = c(x) * a(x) = b0j x3 + b1j x2 + b2j x + b3j， 则可推出： b0j= 02H a0j + 03H a1j + 01H a2j +01H a3j b1j= 01H a0j + 02H a1j + 03H a2j +01H a3j b2j= 01H a0j + 01H a1j + 02H a2j +03H a3j b3j= 03H a0j + 01H a1j + 01H a2j +02H a3j,用矩阵乘法表示即为：,轮密钥加变换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 ;当iNk,wi-Nk BS(R(wi-1 ) Ci/Nk ;当i是Nk的倍数,wi-Nk wi-1 ;其余情况,其中： i=0,1,Nb(r+1)-1 BS表示对双字的每个字节分别进行如前字节代换 R表示将双字循环左移1字节 轮常数cj= (c0,j 00H 00H 00H)，c0,1=01H，c0,j=x c0,j-1，即左移1位，若溢出则再异或11BH,c0,2=02H， c0,3=04H， c0,4=08H， c0,5=10H， c0,6=20H， c0,7=40H， c0,8=80H， c0,9=1BH， c0,10=36H（后两个均左移后异或11BH） 例如：设Nk=4，128位种子密钥K=(k0,k1,k2,k3)，则 (w0,w1,w2,w3)=(k0,k1,k2,k3)， w4 = w0 BS(R(w3 ) (01H 00H 00H 00H) w5 = w1 w4；w6 = w2 w5 ；w7 = w3 w6 w8 = w4 BS(R(w7 ) (02H 00H 00H 00H) w9 = w5 w8 实例：P104【例5-5】,对于Nk6,wi=,ki ;当iNk,wi-Nk BS(R(wi-1 ) ci/Nk ;当i是Nk的倍数,wi-Nk wi-1 ;其余情况,wi-Nk BS(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 = w0 BS(R(w7 ) (01H 00H 00H 00H) w9 = w1 w8；w10 = w2 w9 ；w11 = w3 w10 w12 = w4 BS(w11) w13 = w5 w12；w14 = w6 w13 ；w15 = w7 w14 w16 = w8 BS(R(w15 ) (02H 00H 00H 00H) w17 = w9 w16 ,密钥调度,扩展密钥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.6 AES的解密 逆字节变换BS-1,用于逆字节运算的逆S盒,例：对输入“2aH”，在第2行第a列找到输出为“95H”,逆行移位变换SR-1 将状态的第i行循环右移Ci 个字节（Ci的意义同前） 例子：第1、2、3行循环右移1、2、3个字节,逆列混淆变换MC-1,逆列混淆的实例：,验证：0E 47+0B 37+0D 94+09 ED=87,0E 47=（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) 0B 37=(00001011) (00110111)=(00000001) +(00000010) +(00001000) (00110111) =(00110111)+(01101110) +(10111000) +(00011011) =(11111010),0D 94=(00001101) (10010100)=(0000001) +(00000100) +(00001000) (10010100) =(10010100) +(01100110) +(11001100) =(00111110) 09 ED=(00001001) (11101101)=(00000001) +(00001000) (11101101) =(11101101) +(00101001) =(11000100) 0E 47+0B 37+0D 94+09 ED=(10000111)+(11111010)+ (00111110)+ (11000100) =(10000111) =87 AES实例（P105）,AES的加密解密演示 AESRijndaelComeTrue.exe 文本加解密,作业 P107页：11、12、13、14,