高級(jí)加密標(biāo)準(zhǔn)

高級(jí)加密標(biāo)準(zhǔn)第1頁，共58頁，2023年，2月20日，星期二攻擊者類型所配有的計(jì)算機(jī)資源每秒處理的密鑰數(shù)個(gè)人攻擊1臺(tái)高性能桌式計(jì)算機(jī)及其軟件217-224小組攻擊16臺(tái)高性能桌式計(jì)算機(jī)及其軟件221-224院、校網(wǎng)絡(luò)攻擊256臺(tái)高性能桌式計(jì)算機(jī)及其軟件225-228大公司配有價(jià)值1百萬美元的硬件243

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

第2頁，共58頁，2023年，2月20日，星期二個(gè)人攻擊小組攻擊院、校網(wǎng)絡(luò)攻擊大公司軍事情報(bào)機(jī)構(gòu)40（bits）數(shù)周數(shù)日數(shù)小時(shí)數(shù)毫秒數(shù)微秒56數(shù)百年數(shù)十年數(shù)年數(shù)小時(shí)數(shù)秒鐘64數(shù)千年數(shù)百年數(shù)十年數(shù)日數(shù)分鐘80不可能不可能不可能數(shù)百年數(shù)百年128不可能不可能不可能不可能數(shù)千年第3頁，共58頁，2023年，2月20日，星期二1.AES的起源1997年9月，NIST征集AES方案，以替代DES。AES的基本要求是：比三重DES快、至少與三重DES一樣安全、數(shù)據(jù)分組長度為128比特、密鑰長度為128/192/256比特。1999年8月，以下5個(gè)方案成為最終候選方案：MARS,RC6,Rijndael,Serpent,Twofish。2000年10月，由比利時(shí)的JoanDaemen和VincentRijmen提出的算法最終勝出。（Rijndael讀成RainDoll。）http://www.esat.kuleuven.ac.be/~rijmen/rijndael/第4頁，共58頁，2023年，2月20日，星期二

Rijndael(Raindoll)加密算法是分組長度可變、密鑰長度也可變的分組密碼。分組長度、密鑰長度彼此獨(dú)立地確定為128、192、256比特。

AES的要求是比三重DES快而且至少和三重DES一樣安全，分組長度為128比特，密鑰長度為128/192/256比特。所以，AES和Rijndael是有差別的。

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

1.AES的數(shù)學(xué)基礎(chǔ)余式的次數(shù)至多是7次，共28=256個(gè)多項(xiàng)式第12頁，共58頁，2023年，2月20日，星期二在多項(xiàng)式表示中，GF(28)上兩個(gè)元素的和仍然是一個(gè)次數(shù)不超過7的多項(xiàng)式，其系數(shù)等于兩個(gè)元素對(duì)應(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由于每個(gè)元素的加法逆元等于自己，所以減法和加法相同。第13頁，共58頁，2023年，2月20日，星期二要計(jì)算GF(28)上的乘法，必須先確定一個(gè)GF(2)上的8次不可約多項(xiàng)式；GF(28)上兩個(gè)元素的乘積就是這兩個(gè)多項(xiàng)式的模乘（以這個(gè)8次不可約多項(xiàng)式為模）。在Rijndael密碼中，這個(gè)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))第14頁，共58頁，2023年，2月20日，星期二以上定義的乘法滿足交換律，且有單位元‘01’。另外，對(duì)任何次數(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個(gè)可能字節(jié)值構(gòu)成的集合，在以上定義的加法和乘法運(yùn)算下，有有限域GF(28)的結(jié)構(gòu)。第15頁，共58頁，2023年，2月20日，星期二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)的異或。另法:可以先對(duì)b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0），若b7=1，則再與‘1B’（其二進(jìn)制為00011011）做逐比特異或來實(shí)現(xiàn)，該運(yùn)算記為b=xtime(a)。第16頁，共58頁，2023年，2月20日，星期二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舉例第17頁，共58頁，2023年，2月20日，星期二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舉例第18頁，共58頁，2023年，2月20日，星期二例如，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。第19頁，共58頁，2023年，2月20日，星期二2.系數(shù)在GF(28)上的多項(xiàng)式4個(gè)字節(jié)構(gòu)成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項(xiàng)式。多項(xiàng)式的加法就是對(duì)應(yīng)系數(shù)相加；換句話說，多項(xiàng)式的加法就是4字節(jié)向量的逐比特異或。第20頁，共58頁，2023年，2月20日，星期二規(guī)定多項(xiàng)式的乘法運(yùn)算必須要取模M(x)=x4+1，這樣使得次數(shù)小于4的多項(xiàng)式的乘積仍然是一個(gè)次數(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。第21頁，共58頁，2023年，2月20日，星期二c0=a0b0a3b1a2b2a1b3；c1=a1b0a0b1a3b2a2b3；c2=a2b0a1b1a0b2a3b3；c3=a3b0a2b1a1b2a0b3。第22頁，共58頁，2023年，2月20日，星期二定義為x與b(x)的模x4+1乘法。其矩陣表示中，除a1=‘01’外，其他所有ai=‘00’，即因此，x（或x的冪）模乘多項(xiàng)式相當(dāng)于對(duì)字節(jié)構(gòu)成的向量進(jìn)行字節(jié)循環(huán)移位。c(x)=xb(x)(b(x)=b2x3+b1x2+b0x+b3)第23頁，共58頁，2023年，2月20日，星期二c002030101D4

c1=01

020301BF

c20101

02035D

c30301010230a(x)=03x3+01x2+01x+02b(x)=30x3+5Dx2+bfx+d4第24頁，共58頁，2023年，2月20日，星期二01234567891011121314150481215913261014371115以明文分組為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,對(duì)應(yīng)的Nb可以取的值為:4,6,8第25頁，共58頁，2023年，2月20日，星期二04812162015913172126101418223711151923048121620242815913172125292610141822263037111519232731以明文分組（或密鑰）為192bits、256bits為例組成的陣列:第26頁，共58頁，2023年，2月20日，星期二CipherKey類似地用一個(gè)4行的矩陣陣列來表示，列數(shù)記為Nk。

Nk=密鑰長度（bits）÷32k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33第27頁，共58頁，2023年，2月20日，星期二密鑰長度（Nk)分組長度（Ｎb)圈變換數(shù)目（Nr）AES-1284410AES-1926412AES-2568414圈變換數(shù)目Nr與密鑰長度Nk的關(guān)系 第28頁，共58頁，2023年，2月20日，星期二4.5.3AES的加密過程第29頁，共58頁，2023年，2月20日，星期二Plaintext(128bits)ByteSubstitutionMixColumn＋Ciphertext(128bits)K0Kii=10ByteRotationfori=1to10＋加密Rijndael加密的標(biāo)準(zhǔn)結(jié)構(gòu)

Block,KeyLength=128bits第30頁，共58頁，2023年，2月20日，星期二(1)字節(jié)代換（ByteSub）字節(jié)代換是非線形變換，獨(dú)立地對(duì)狀態(tài)的每個(gè)字節(jié)進(jìn)行。①首先，將字節(jié)看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。②其次，對(duì)①的結(jié)果做如下的（GF(2)上的，可逆的）仿射變換：第31頁，共58頁，2023年，2月20日，星期二也可查p61表4.9第32頁，共58頁，2023年，2月20日，星期二列的每個(gè)元素作為輸入用來指定S盒的地址：前4位指定S盒的行，后4位指定S盒的列。由行和列所確定S盒位置的元素取代輸入矩陣中相應(yīng)位置的元素，例如“12”，行1，列2，因此輸入“12”，輸出“c9”第33頁，共58頁，2023年，2月20日，星期二S-box第34頁，共58頁，2023年，2月20日，星期二2.行移位變換04812159132610143711150481259131101426153711循環(huán)左移1字節(jié)循環(huán)左移2字節(jié)循環(huán)左移3字節(jié)第35頁，共58頁，2023年，2月20日，星期二３．MixColumn(列混合)

將狀態(tài)的列看作是有限域GF(28)上的多項(xiàng)式s(x)，列混合變換是s(x)與多項(xiàng)式a(x)=03x3+01x2+01x+02相乘(模x4＋1)的結(jié)果(模x4＋1)即：第36頁，共58頁，2023年，2月20日，星期二第37頁，共58頁，2023年，2月20日，星期二寫成矩陣形式為：s’0j02030101s0j

s’1j=01

020301s1j

s’2j0101

0203s2j

s’3j03010102s3j第38頁，共58頁，2023年，2月20日，星期二

?

02030101D4

?=01

020301BF

?

0101

02035D

?

0301010230第39頁，共58頁，2023年，2月20日，星期二S0,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(輪密鑰加)第40頁，共58頁，2023年，2月20日，星期二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ò)展第41頁，共58頁，2023年，2月20日，星期二K0K1K2K3K4K5K6K7ByteRotateByteSubstitution+Rcon第42頁，共58頁，2023年，2月20日，星期二在密鑰擴(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ò)展-RotByte第43頁，共58頁，2023年，2月20日，星期二Rcon：Rcon[i]=(RC[i],

’00’,’00’，’00’)RC[1]=1（即’01’）RC[i]=(02)(i-1)；i=2,3,......第44頁，共58頁，2023年，2月20日，星期二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)第45頁，共58頁，2023年，2月20日，星期二Wi-4Wi-3Wi-2Wi-1WiByteSubstituionByteRotate+Rcons+Keyexpansion4=<i<4(Nr+1)imod4=0imod4!=0第46頁，共58頁，2023年，2月20日，星期二

輪密鑰選取K0K1K2K3K4K5K6K7K8K9K10K11K12輪密鑰0輪密鑰1輪密鑰2第47頁，共58頁，2023年，2月20日，星期二第48頁，共58頁，2023年，2月20日，星期二Rijndael加密及解密的標(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加密解密第49頁，共58頁，2023年，2月20日，星期二RijndaelRound解密的構(gòu)成InvByteSubstitution（InvSubBytes逆字節(jié)代換）InvByteRotation（InvShiftRow逆行移位）InvMixColumn（逆列混合）+RoundKey一般的解密輪變換InvByteSubstitutionInvByteRotation+RoundKey最后一輪的輪變換第50頁，共58頁，2023年，2月20日，星期二逆循環(huán)移位（InvShiftRowsByteRotation）04812159132610143711150481259131101426153711循環(huán)右移1字節(jié)循環(huán)右移2字節(jié)循環(huán)右移3字節(jié)第51頁，共58頁，2023年，2月20日，星期二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.仿射變換該變換可以用一個(gè)256