高級加密標準

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

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

第2頁,共58頁，2024年2月25日，星期天個人攻擊小組攻擊院、校網(wǎng)絡(luò)攻擊大公司軍事情報機構(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ù)千年第3頁,共58頁，2024年2月25日，星期天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/第4頁,共58頁，2024年2月25日，星期天

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

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

第5頁,共58頁，2024年2月25日，星期天第6頁,共58頁，2024年2月25日，星期天分組長度（bit）128192256密鑰長度（bit）128192256分組長度和密鑰長度的不同取值第7頁,共58頁，2024年2月25日，星期天設(shè)G為非空集合，在G內(nèi)定義了一種代數(shù)運算，若滿足下述公理：(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為交換群或阿貝爾群群的定義第8頁,共58頁，2024年2月25日，星期天判定一個非空集合是不是群，就用群的定義去衡量例：整數(shù)全體，按加法構(gòu)成群，但對乘法不構(gòu)成群例：偶數(shù)全體，按加法構(gòu)成群，但對乘法不構(gòu)成群例：實數(shù)全體，按加法構(gòu)成群，對除0以外的乘法構(gòu)成群第9頁,共58頁，2024年2月25日，星期天非空集合元素F，若在F中定義了加和乘兩種運算，且滿足下述公理：（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)。第10頁,共58頁，2024年2月25日，星期天思考題:實數(shù)全體對加法、乘法是否構(gòu)成域?第11頁,共58頁，2024年2月25日，星期天將b7b6b5b4b3b2b1b0構(gòu)成的字節(jié)b看成系數(shù)在{0,1}中的多項式:b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0系數(shù)模2，即只可0或1例如：十六進制數(shù)‘57’對應(yīng)的二進制為01010111，看成一個字節(jié)，對應(yīng)的多項式為x6+x4+x2+x+1。

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

c1=01

020301BF

c20101

02035D

c30301010230a(x)=03x3+01x2+01x+02b(x)=30x3+5Dx2+bfx+d4第24頁,共58頁，2024年2月25日，星期天01234567891011121314150481215913261014371115以明文分組為128bits為例組成的狀態(tài)陣列4.5.2AES的輸入輸出和中間狀態(tài)狀態(tài)（State）：密碼運算的中間結(jié)果稱為狀態(tài),狀態(tài)用以字節(jié)為基本構(gòu)成元素的矩陣陣列來表示，該陣列有4行，列數(shù)記為Nb。

Nb=分組長度（bits）÷32分組長度為128,192,256bits,對應(yīng)的Nb可以取的值為:4,6,8第25頁,共58頁，2024年2月25日，星期天04812162015913172126101418223711151923048121620242815913172125292610141822263037111519232731以明文分組（或密鑰）為192bits、256bits為例組成的陣列:第26頁,共58頁，2024年2月25日，星期天CipherKey類似地用一個4行的矩陣陣列來表示，列數(shù)記為Nk。

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

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

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

s’1j=01

020301s1j

s’2j0101

0203s2j

s’3j03010102s3j第38頁,共58頁，2024年2月25日，星期天

?

02030101D4

?=01

020301BF

?

0101

02035D

?

0301010230第39頁,共58頁，2024年2月25日，星期天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頁，2024年2月25日，星期天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密鑰擴展第41頁,共58頁，2024年2月25日，星期天K0K1K2K3K4K5K6K7ByteRotateByteSubstitution+Rcon第42頁,共58頁，2024年2月25日，星期天在密鑰擴展中，函數(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密鑰擴展-RotByte第43頁,共58頁，2024年2月25日，星期天Rcon：Rcon[i]=(RC[i],

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

輪密鑰選取K0K1K2K3K4K5K6K7K8K9K10K11K12輪密鑰0輪密鑰1輪密鑰2第47頁,共58頁，2024年2月25日，星期天第48頁,共58頁，2024年2月25日，星期天Rijndael加密及解密的標準結(jié)構(gòu)Block,KeyLength=128bitsPlaintext(128bits)ByteSubstitutionMixColumn＋Ciphertext(128bits)

K0Kii=10ByteRotationfori=1to10Ciphertext(128bits)

K10InvMixCoumnInvByteRotationInvByteSubstitution＋＋

Ki＋Plaintext(128bits)i=9fori=9to0加密解密第49頁,共58頁，2024年2月25日，星期天RijndaelRound解密的構(gòu)成InvByteSubstitution（InvSubBytes逆字節(jié)代換）InvByteRotation（InvShiftRow逆行移位）InvMixColumn（逆列混合）+RoundKey一般的解密輪變換InvByteSubstitutionInvByteRotation+RoundKey最后一輪的輪變換第50頁,共58頁，2024年2月25日，星期天逆循環(huán)移位（InvShiftRowsByteRotation）04812159132610143711150481259131101426153711循環(huán)右移1字節(jié)循環(huán)右移2字節(jié)循環(huán)右移3字節(jié)第51頁,共58頁，2024年2月25日，星期天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é)的表來實現(xiàn)第52頁,共