高級加密標(biāo)準(zhǔn)AES課件

16四月2024高級加密標(biāo)準(zhǔn)AES攻擊者類型所配有的計(jì)算機(jī)資源每秒處理的密鑰數(shù)個人攻擊1臺高性能桌式計(jì)算機(jī)及其軟件217-224小組攻擊16臺高性能桌式計(jì)算機(jī)及其軟件221-224院、校網(wǎng)絡(luò)攻擊256臺高性能桌式計(jì)算機(jī)及其軟件225-228大公司配有價值1百萬美元的硬件243

軍事情報(bào)機(jī)構(gòu)配有價值1百萬美元的硬件及先進(jìn)的攻擊技術(shù)255攻擊者配有如下計(jì)算機(jī)資源的攻擊能力

個人攻擊小組攻擊院、校網(wǎng)絡(luò)攻擊大公司軍事情報(bào)機(jī)構(gòu)40（bits）數(shù)周數(shù)日數(shù)小時數(shù)毫秒數(shù)微秒56數(shù)百年數(shù)十年數(shù)年數(shù)小時數(shù)秒鐘64數(shù)千年數(shù)百年數(shù)十年數(shù)日數(shù)分鐘80不可能不可能不可能數(shù)百年數(shù)百年128不可能不可能不可能不可能數(shù)千年1.AES的起源1997年9月，NIST征集AES方案，以替代DES。AES的基本要求是：比三重DES快、至少與三重DES一樣安全、數(shù)據(jù)分組長度為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)加密算法是分組長度可變、密鑰長度也可變的分組密碼。分組長度、密鑰長度彼此獨(dú)立地確定為128、192、256比特。AES的要求是比三重DES快而且至少和三重DES一樣安全，分組長度為128比特，密鑰長度為128/192/256比特。所以，AES和Rijndael是有差別的。

分組長度（bit）128192256密鑰長度（bit）128192256分組長度和密鑰長度的不同取值設(shè)G為非空集合，在G內(nèi)定義了一種代數(shù)運(yùn)算，若滿足下述公理：(1)有封閉性。對任意a、b∈G，恒有aοb∈G.(2)結(jié)合律成立。對任意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òu)成一個群。若群G滿足交換律，則稱群G為交換群或阿貝爾群群的定義判定一個非空集合是不是群，就用群的定義去衡量例：整數(shù)全體，按加法構(gòu)成群，但對乘法不構(gòu)成群例：偶數(shù)全體，按加法構(gòu)成群，但對乘法不構(gòu)成群例：實(shí)數(shù)全體，按加法構(gòu)成群，對除0以外的乘法構(gòu)成群非空集合元素F，若在F中定義了加和乘兩種運(yùn)算，且滿足下述公理：（1）F關(guān)于加法構(gòu)成阿貝爾群。（2）F中非零元素全體對乘法構(gòu)成阿貝爾群。其乘法幺元（單位元）記為1。（3）加法和乘法間有如下分配律：a(b+c)=ab+ac(b+c)a=ba+ca則稱F為一個域若F中的元素為有限個，稱F為有限域(FiniteField)。思考題:實(shí)數(shù)全體對加法、乘法是否構(gòu)成域?將b7b6b5b4b3b2b1b0構(gòu)成的字節(jié)b看成系數(shù)在{0,1}中的多項(xiàng)式:b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0系數(shù)模2，即只可0或1例如：十六進(jìn)制數(shù)‘57’對應(yīng)的二進(jìn)制為01010111，看成一個字節(jié)，對應(yīng)的多項(xiàng)式為x6+x4+x2+x+1。

1.AES的數(shù)學(xué)基礎(chǔ)余式的次數(shù)至多是7次，共28=256個多項(xiàng)式在多項(xiàng)式表示中，GF(28)上兩個元素的和仍然是一個次數(shù)不超過7的多項(xiàng)式，其系數(shù)等于兩個元素對應(yīng)系數(shù)的模2加（比特異或）。例如：‘57’+‘83’=‘D4’，用多項(xiàng)式表示為:(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2用二進(jìn)制表示為:01010111+10000011=11010100由于每個元素的加法逆元等于自己，所以減法和加法相同。要計(jì)算GF(28)上的乘法，必須先確定一個GF(2)上的8次不可約多項(xiàng)式；GF(28)上兩個元素的乘積就是這兩個多項(xiàng)式的模乘（以這個8次不可約多項(xiàng)式為模）。在Rijndael密碼中，這個8次不可約多項(xiàng)式確定為: m(x)=x8+x4+x3+x+1它的十六進(jìn)制表示為‘11B’。例如，‘57’·‘83’=‘C1’可表示為以下的多項(xiàng)式乘法：(x6+x4+x2+x+1)·(x7+x+1)=x7+x6+1(modm(x))以上定義的乘法滿足交換律，且有單位元‘01’。另外，對任何次數(shù)小于8的多項(xiàng)式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個可能字節(jié)值構(gòu)成的集合，在以上定義的加法和乘法運(yùn)算下，有有限域GF(28)的結(jié)構(gòu)。GF(28)上x乘法:x·b(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x(modm(x))如果b7=0，求模結(jié)果不變，否則為乘積結(jié)果減去m(x)，即求乘積結(jié)果與m(x)的異或。另法:可以先對b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0），若b7=1，則再與‘1B’（其二進(jìn)制為00011011）做逐比特異或來實(shí)現(xiàn)，該運(yùn)算記為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）由上面的規(guī)則：把(01010100)在字節(jié)內(nèi)左移一位即得（10101000）（最后一位補(bǔ)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))//***相當(dāng)（00011011）與（10101000）異或****//≡x7+x5+x4+x+1(modp(x))=(10110011)由上面的規(guī)則：先把(11010100)在字節(jié)內(nèi)左移一位即得（10101000）（最后一位補(bǔ)0），因?yàn)閎7＝1，故（10101000）再與（00011011）異或得（10110011）b7＝1舉例例如，57·13可按如下方式實(shí)現(xiàn)：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.系數(shù)在GF(28)上的多項(xiàng)式4個字節(jié)構(gòu)成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項(xiàng)式。多項(xiàng)式的加法就是對應(yīng)系數(shù)相加；換句話說，多項(xiàng)式的加法就是4字節(jié)向量的逐比特異或。規(guī)定多項(xiàng)式的乘法運(yùn)算必須要取模M(x)=x4+1，這樣使得次數(shù)小于4的多項(xiàng)式的乘積仍然是一個次數(shù)小于4的多項(xiàng)式，將多項(xiàng)式的模乘運(yùn)算記為：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的冪）模乘多項(xiàng)式相當(dāng)于對字節(jié)構(gòu)成的向量進(jìn)行字節(jié)循環(huán)移位。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為例組成的狀態(tài)陣列4.5.2AES的輸入輸出和中間狀態(tài)狀態(tài)（State）：密碼運(yùn)算的中間結(jié)果稱為狀態(tài),狀態(tài)用以字節(jié)為基本構(gòu)成元素的矩陣陣列來表示，該陣列有4行，列數(shù)記為Nb。Nb=分組長度（bits）÷32分組長度為128,192,256bits,對應(yīng)的Nb可以取的值為:4,6,804812162015913172126101418223711151923048121620242815913172125292610141822263037111519232731以明文分組（或密鑰）為192bits、256bits為例組成的陣列:CipherKey類似地用一個4行的矩陣陣列來表示，列數(shù)記為Nk。Nk=密鑰長度（bits）÷32k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33密鑰長度（Nk)分組長度（Ｎb)圈變換數(shù)目（Nr）AES-1284410AES-1926412AES-2568414圈變換數(shù)目Nr與密鑰長度Nk的關(guān)系 4.5.3AES的加密過程Plaintext(128bits)ByteSubstitutionMixColumn＋Ciphertext(128bits)K0Kii=10ByteRotationfori=1to10＋加密Rijndael加密的標(biāo)準(zhǔn)結(jié)構(gòu)

Block,KeyLength=128bits(1)字節(jié)代換（ByteSub）字節(jié)代換是非線形變換，獨(dú)立地對狀態(tài)的每個字節(jié)進(jìn)行。①首先，將字節(jié)看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。②其次，對①的結(jié)果做如下的（GF(2)上的，可逆的）仿射變換：也可查p61表4.9列的每個元素作為輸入用來指定S盒的地址：前4位指定S盒的行，后4位指定S盒的列。由行和列所確定S盒位置的元素取代輸入矩陣中相應(yīng)位置的元素，例如“12”，行1，列2，因此輸入“12”，輸出“c9”S-box2.行移位變換04812159132610143711150481259131101426153711循環(huán)左移1字節(jié)循環(huán)左移2字節(jié)循環(huán)左移3字節(jié)３．MixColumn(列混合)將狀態(tài)的列看作是有限域GF(28)上的多項(xiàng)式s(x)，列混合變換是s(x)與多項(xiàng)式a(x)=03x3+01x2+01x+02相乘(模x4＋1)的結(jié)果(模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密鑰擴(kuò)展K0K1K2K3K4K5K6K7ByteRotateByteSubstitution+Rcon在密鑰擴(kuò)展中，函數(shù)RotByte(a,b,c,d)=(b,c,d,a),即是輸入字的1字節(jié)循環(huán)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密鑰擴(kuò)展-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加密及解密的標(biāo)準(zhǔn)結(jié)構(gòu)Block,KeyLength=128bitsPlaintext(128bits)ByteSubstitutionMixColumn＋Ciphertext(128bits)

K0Kii=10ByteRotationfori=1to10Ciphertext(128bits)

K10InvMixCoumnInvByteRotationInvByteSubstitution＋＋

Ki＋Plaintext(128bits)i=9fori=9to0加密解密RijndaelRound解密的構(gòu)成InvByteSubstitution（InvSubBytes逆字節(jié)代換）InvByteRotation（InvShiftRow逆行移位）InvMixColumn（逆列混合）+RoundKey一般的解密輪變換InvByteSubstitutionInvByteRotation+RoundKey最后一輪的輪變換逆循環(huán)移位（InvShiftRowsByteRotation）04812159132610143711150481259131101426153711循環(huán)右移1字節(jié)循環(huán)右移2字節(jié)循環(huán)右移3字節(jié)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字節(jié)的表來實(shí)現(xiàn)MixColumn(列混合)將狀態(tài)的列看作是有限域GF(28)上的多項(xiàng)式，與多項(xiàng)式a-1(x)=0bx3+0dx2+09x+0e相乘(模x4＋1),寫成矩陣形式為：

s1j0e0b0d09s’0js2j=090e0b0ds’1js3j0d090e0b