高级加密标准AES课件

16四月2024高级加密标准AES攻击者类型所配有的计算机资源每秒处理的密钥数个人攻击1台高性能桌式计算机及其软件217-224小组攻击16台高性能桌式计算机及其软件221-224院、校网络攻击256台高性能桌式计算机及其软件225-228大公司配有价值1百万美元的硬件243

军事情报机构配有价值1百万美元的硬件及先进的攻击技术255攻击者配有如下计算机资源的攻击能力

个人攻击小组攻击院、校网络攻击大公司军事情报机构40（bits）数周数日数小时数毫秒数微秒56数百年数十年数年数小时数秒钟64数千年数百年数十年数日数分钟80不可能不可能不可能数百年数百年128不可能不可能不可能不可能数千年1.AES的起源1997年9月，NIST征集AES方案，以替代DES。AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。1999年8月，以下5个方案成为最终候选方案：MARS,RC6,Rijndael,Serpent,Twofish。2000年10月，由比利时的JoanDaemen和VincentRijmen提出的算法最终胜出。（Rijndael读成RainDoll。）http://www.esat.kuleuven.ac.be/~rijmen/rijndael/Rijndael(Raindoll)加密算法是分组长度可变、密钥长度也可变的分组密码。分组长度、密钥长度彼此独立地确定为128、192、256比特。AES的要求是比三重DES快而且至少和三重DES一样安全，分组长度为128比特，密钥长度为128/192/256比特。所以，AES和Rijndael是有差别的。

分组长度（bit）128192256密钥长度（bit）128192256分组长度和密钥长度的不同取值设G为非空集合，在G内定义了一种代数运算，若满足下述公理：(1)有封闭性。对任意a、b∈G，恒有aοb∈G.(2)结合律成立。对任意a、b、c∈G，有(aοb)οc=aο(bοc)(3)G中有幺元e存在，对任意a∈G,有e∈G,使aοe=eοa=a(4)对任意a∈G，存在有a的逆元a-1∈G，使aοa-1=a-1οa=e则G构成一个群。若群G满足交换律，则称群G为交换群或阿贝尔群群的定义判定一个非空集合是不是群，就用群的定义去衡量例：整数全体，按加法构成群，但对乘法不构成群例：偶数全体，按加法构成群，但对乘法不构成群例：实数全体，按加法构成群，对除0以外的乘法构成群非空集合元素F，若在F中定义了加和乘两种运算，且满足下述公理：（1）F关于加法构成阿贝尔群。（2）F中非零元素全体对乘法构成阿贝尔群。其乘法幺元（单位元）记为1。（3）加法和乘法间有如下分配律：a(b+c)=ab+ac(b+c)a=ba+ca则称F为一个域若F中的元素为有限个，称F为有限域(FiniteField)。思考题:实数全体对加法、乘法是否构成域?将b7b6b5b4b3b2b1b0构成的字节b看成系数在{0,1}中的多项式:b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0系数模2，即只可0或1例如：十六进制数‘57’对应的二进制为01010111，看成一个字节，对应的多项式为x6+x4+x2+x+1。

1.AES的数学基础余式的次数至多是7次，共28=256个多项式在多项式表示中，GF(28)上两个元素的和仍然是一个次数不超过7的多项式，其系数等于两个元素对应系数的模2加（比特异或）。例如：‘57’+‘83’=‘D4’，用多项式表示为:(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2用二进制表示为:01010111+10000011=11010100由于每个元素的加法逆元等于自己，所以减法和加法相同。要计算GF(28)上的乘法，必须先确定一个GF(2)上的8次不可约多项式；GF(28)上两个元素的乘积就是这两个多项式的模乘（以这个8次不可约多项式为模）。在Rijndael密码中，这个8次不可约多项式确定为: m(x)=x8+x4+x3+x+1它的十六进制表示为‘11B’。例如，‘57’·‘83’=‘C1’可表示为以下的多项式乘法：(x6+x4+x2+x+1)·(x7+x+1)=x7+x6+1(modm(x))以上定义的乘法满足交换律，且有单位元‘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)的结构。GF(28)上x乘法:x·b(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x(modm(x))如果b7=0，求模结果不变，否则为乘积结果减去m(x)，即求乘积结果与m(x)的异或。另法:可以先对b(x)在字节内左移一位（最后一位补0），若b7=1，则再与‘1B’（其二进制为00011011）做逐比特异或来实现，该运算记为b=xtime(a)。b7＝0举例02·54=(00000010)·(01010100)=(x)·(x6+x4+x2)=x7+x5+x3=x7+x5+x3≡x7+x5+x3(modp(x))=（10101000）由上面的规则：把(01010100)在字节内左移一位即得（10101000）（最后一位补0）b7＝0举例02·D4=(00000010)·(11010100)=(x)·(x7+x6+x4+x2)=x8+x7+x5+x3≡(x4+x3+x+1)+x7+x5+x3(modp(x))//***相当（00011011）与（10101000）异或****//≡x7+x5+x4+x+1(modp(x))=(10110011)由上面的规则：先把(11010100)在字节内左移一位即得（10101000）（最后一位补0），因为b7＝1，故（10101000）再与（00011011）异或得（10110011）b7＝1举例例如，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·(010210)=578E07=FE。2.系数在GF(28)上的多项式4个字节构成的向量可以表示为系数在GF(28)上的次数小于4的多项式。多项式的加法就是对应系数相加；换句话说，多项式的加法就是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。c0=a0b0a3b1a2b2a1b3；c1=a1b0a0b1a3b2a2b3；c2=a2b0a1b1a0b2a3b3；c3=a3b0a2b1a1b2a0b3。c0=a0b0a3b1a2b2a1b3；c1=a1b0a0b1a3b2a2b3；c2=a2b0a1b1a0b2a3b3；c3=a3b0a2b1a1b2a0b3。定义为x与b(x)的模x4+1乘法。其矩阵表示中，除a1=‘01’外，其他所有ai=‘00’，即因此，x（或x的幂）模乘多项式相当于对字节构成的向量进行字节循环移位。c(x)=xb(x)(b(x)=b2x3+b1x2+b0x+b3)c002030101D4

c1=01

020301BF

c20101

02035D

c30301010230a(x)=03x3+01x2+01x+02b(x)=30x3+5Dx2+bfx+d401234567891011121314150481215913261014371115以明文分组为128bits为例组成的状态阵列4.5.2AES的输入输出和中间状态状态（State）：密码运算的中间结果称为状态,状态用以字节为基本构成元素的矩阵阵列来表示，该阵列有4行，列数记为Nb。Nb=分组长度（bits）÷32分组长度为128,192,256bits,对应的Nb可以取的值为:4,6,804812162015913172126101418223711151923048121620242815913172125292610141822263037111519232731以明文分组（或密钥）为192bits、256bits为例组成的阵列:CipherKey类似地用一个4行的矩阵阵列来表示，列数记为Nk。Nk=密钥长度（bits）÷32k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33密钥长度（Nk)分组长度（Ｎb)圈变换数目（Nr）AES-1284410AES-1926412AES-2568414圈变换数目Nr与密钥长度Nk的关系 4.5.3AES的加密过程Plaintext(128bits)ByteSubstitutionMixColumn＋Ciphertext(128bits)K0Kii=10ByteRotationfori=1to10＋加密Rijndael加密的标准结构

Block,KeyLength=128bits(1)字节代换（ByteSub）字节代换是非线形变换，独立地对状态的每个字节进行。①首先，将字节看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。②其次，对①的结果做如下的（GF(2)上的，可逆的）仿射变换：也可查p61表4.9列的每个元素作为输入用来指定S盒的地址：前4位指定S盒的行，后4位指定S盒的列。由行和列所确定S盒位置的元素取代输入矩阵中相应位置的元素，例如“12”，行1，列2，因此输入“12”，输出“c9”S-box2.行移位变换04812159132610143711150481259131101426153711循环左移1字节循环左移2字节循环左移3字节３．MixColumn(列混合)将状态的列看作是有限域GF(28)上的多项式s(x)，列混合变换是s(x)与多项式a(x)=03x3+01x2+01x+02相乘(模x4＋1)的结果(模x4＋1)即：写成矩阵形式为：s’0j02030101s0j

s’1j=01

020301s1j

s’2j0101

0203s2j

s’3j03010102s3j

?

02030101D4

?=01

020301BF

?

0101

02035D

?

0301010230S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3＋S'0,0S'0,1S'0,2S'0,3S'1,0S'1,1S'1,2S'1,3S'2,0S'2,1S'2,2S'2,3S'3,0S'3,1S'3,2S'3,3S3,3＋K3,3＝S'3,3(mod2)4.SddRoundKey(轮密钥加)K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3K0K1K2K3K0K1K2K3K4K5K6K7+++K0,0,K1,0,K2,0,K3,0,K0,1,…K3,34.5.4密钥扩展K0K1K2K3K4K5K6K7ByteRotateByteSubstitution+Rcon在密钥扩展中，函数RotByte(a,b,c,d)=(b,c,d,a),即是输入字的1字节循环K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3RotByteK0,0K0,1K0,2K1,3K1,0K1,1K1,2K2,3K2,0K2,1K2,2K3,3K3,0K3,1K3,2K0,3密钥扩展-RotByteRcon：Rcon[i]=(RC[i],

’00’,’00’，’00’)RC[1]=1（即’01’）RC[i]=(02)(i-1)；i=2,3,......RC[1]=’01’(00000001)Rcon[1]=(’01’,00,00,00)RC[2]=‘02’(00000010)Rcon[2]=(’02’,00,00,00)RC[3]=‘04’(00000100)Rcon[3]=(’04’,00,00,00)RC[4]=‘08’(00001000)Rcon[4]=(’08’,00,00,00)RC[5]=‘10’(00010000)Rcon[5]=(’10’,00,00,00)RC[6]=‘20’(00100000)Rcon[6]=(’20’,00,00,00)RC[7]=‘40’(01000000)Rcon[7]=(’40’,00,00,00)Wi-4Wi-3Wi-2Wi-1WiByteSubstituionByteRotate+Rcons+Keyexpansion4=<i<4(Nr+1)imod4=0imod4!=0轮密钥选取K0K1K2K3K4K5K6K7K8K9K10K11K12轮密钥0轮密钥1轮密钥2Rijndael加密及解密的标准结构Block,KeyLength=128bitsPlaintext(128bits)ByteSubstitutionMixColumn＋Ciphertext(128bits)

K0Kii=10ByteRotationfori=1to10Ciphertext(128bits)

K10InvMixCoumnInvByteRotationInvByteSubstitution＋＋

Ki＋Plaintext(128bits)i=9fori=9to0加密解密RijndaelRound解密的构成InvByteSubstitution（InvSubBytes逆字节代换）InvByteRotation（InvShiftRow逆行移位）InvMixColumn（逆列混合）+RoundKey一般的解密轮变换InvByteSubstitutionInvByteRotation+RoundKey最后一轮的轮变换逆循环移位（InvShiftRowsByteRotation）04812159132610143711150481259131101426153711循环右移1字节循环右移2字节循环右移3字节InvByteSubstitutionB0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3(逆S盒)1.取逆2.仿射变换该变换可以用一个256字节的表来实现MixColumn(列混合)将状态的列看作是有限域GF(28)上的多项式，与多项式a-1(x)=0bx3+0dx2+09x+0e相乘(模x4＋1),写成矩阵形式为：

s1j0e0b0d09s’0js2j=090e0b0ds’1js3j0d090e0b