aes加密

1、高級加密標(biāo)準(zhǔn)AES,AES算法的整體結(jié)構(gòu),Rijndael 由比利時(shí)的Joan Daemen和Vincent Rijmen設(shè)計(jì)，算法的原型是Square算法，經(jīng)過修改后確定為高級數(shù)據(jù)加密標(biāo)準(zhǔn)AES.典型的SPN結(jié)構(gòu)有較好的數(shù)學(xué)理論作為基礎(chǔ)；結(jié)構(gòu)簡單、速度快,AES算法的整體結(jié)構(gòu),,輪密鑰加,字節(jié)替代,行移位,列混合,初始狀態(tài)矩陣（state）,AES算法的分組長度固定為128比特，以字節(jié)為基本單位轉(zhuǎn)換為狀態(tài)字節(jié)，依順序 a00, a

2、10, a20, a30, a01, … a23, a33，前4個字節(jié)組成第1列，后四個字節(jié)組成第2列，依次類推，AES算法明文分組可以構(gòu)成一個4×4的字節(jié)矩陣，如圖所示3-23，加密結(jié)束時(shí)，輸出也是從狀態(tài)字節(jié)中按相同的順序提取。,AES算法舉例學(xué)習(xí),下面我們以一個128位塊為例，開始分別介紹AES加密算法基本變換的具體過程。為了表達(dá)簡潔，下面的中間結(jié)果都用16進(jìn)制來表示。則128比特二進(jìn)制示例塊用16進(jìn)制表示則對應(yīng)為0x

3、80 5E 6A 36 53 25 3A 66 63 35 69 03 20 6C 28 06,課堂思考題,例如“good good study !day day up !”采用AES算法，明文輸入初始狀態(tài)矩陣？,,初始密鑰,實(shí)例：設(shè)初始密鑰（初始子密鑰矩陣與明文類似0x 75 35 6B 99 05 61 39 56 73 62 05 31 00 55 09 32,輪密鑰加,⊕,=,此處輪密鑰是初始密鑰，輪密鑰長度等于分組長度。,字

4、節(jié)代替（SubBytes）,字節(jié)變換（SubBytes）使用一個S盒，S盒是一個16×１6的矩陣，如表所示。其非線性置換為：輸入的列的每個元素用來指定S盒的地址：前4位指定S盒的行，后4位指定S盒的列。行和列所確定S盒位置的元素取代輸入矩陣中相應(yīng)位置的元素，例如“03” ，行0，列3，因此輸入“03” ，輸出“7B”。,字節(jié)替代所用S盒,字節(jié)替代舉例,在上面的示例中，第1個基本元素為”F5”，它將被S盒行為第”F行”、列為第”

5、5”列的元素“E6“代替，其余的輸出也用相同的方法確定。,行移位（ShiftRows）,狀態(tài)陣列的4個行循環(huán)以字節(jié)為基本單位進(jìn)行左移，而每行循環(huán)做移的偏移量是由明文分組的大小和所在行數(shù)共同確定，即列數(shù)Nb和行號確定。,AES的Nb固定為4，下面兩行針對Rijndael算法,行移位舉例,3）列混合（MixColumn） 列混合變換中，將狀態(tài)陣列的每列視為GF((28)4)上的多項(xiàng)式，再與一個固定的多項(xiàng)式c(x)進(jìn)行模x4+1乘法

6、. Rijndael的設(shè)計(jì)者給出的c(x)為（系數(shù)用十六進(jìn)制數(shù)表示）： c(x)=‘03’x3+‘01’x2+‘01’x+‘02’,列混合,列混合（MixColumns）,列混合是可以表示為矩陣相乘來實(shí)現(xiàn),,,列混合舉例,列混合舉例,列混合舉例,GF(28)的多項(xiàng)式乘法，約化多項(xiàng)式為m(x)=x8+x4+x3+x+1 例：57x乘以83x (x6+x4+x2+x+1) × (x7+x+1)= (x13+x11+x9

7、+x8+x7)^ (x7+x5+x3+x2+x)^ (x6+x4+x2+x+1) = x13+x11+x9+x8+x6+x5+x4+x3+1=x7+x6+1 mod m(x),列混合舉例課堂練習(xí),課堂練習(xí)：列混合運(yùn)算(128比特分組),輪密鑰加（AddRoundKey）,將列混合的狀態(tài)矩陣與子密鑰進(jìn)行XOR邏輯運(yùn)算（子密鑰是從初始密鑰派生而來的），即將輪密鑰與狀態(tài)按比特異或。輪密鑰是通過密鑰調(diào)度過程從密碼密鑰中得到的，輪密鑰長度等于

8、分組長度。,,輪密鑰加 舉例,密鑰排列,AES算法加密和解密過程中密碼密鑰（Cipher Key）同樣以字節(jié)為基本單位轉(zhuǎn)換，因而依順序 k00, k 10, k20, k30, k01,…k23, k33，為類似地用一個4行的矩陣陣列來表示，前4個字節(jié)組成第1列，后四個字節(jié)組成第2列，依次類推，列數(shù)記為Nk 。AES算法的密碼密鑰的列數(shù)Nk可以取的值為4,6,8,對應(yīng)的密鑰長度為128,192,256bits，因而密碼密鑰構(gòu)成一個4&

9、#215;4、4×6、4×8的密鑰字節(jié)矩陣。,密鑰陣列狀態(tài),如圖所示，192比特密鑰的密碼密鑰矩陣，Nk為6。,,,,,,,,密鑰擴(kuò)展 （NK=4）,初始密鑰,實(shí)例：設(shè)初始密鑰75 35 6B 99 05 61 39 5673 62 05 31 00 55 09 32,求K4,（1） 循環(huán)將K3按照字節(jié)為單位左移1字節(jié)，00 55 09 32變成了55 09 32 00 （2） 將55 09 32 00作為S盒

10、的輸入，查表得到輸出 fc 01 23 63 （3） 計(jì)算常量Rcon[i]=(RC(j),00,00,00)異或，RC(j)=20=01=’01‘(十六進(jìn)制) （4） 將01000000與fc 01 23 63 異或運(yùn)算得fd 01 23 63K4= 75 35 6B 99 XOR fd 01 23 63 = 88 34 48 fa,在密鑰擴(kuò)展中，函數(shù)RotByte(a,b,c,d)=(b,c,d,a),即是輸入字的1字節(jié)循環(huán),

11、,RotByte,密鑰擴(kuò)展-RotByte,密鑰擴(kuò)展程序如下：其中：Rcon[i] = (RC[i], ’00’, ’00’， ’00’)RC[1] = 1（即’01’）RC[i] = (02)(i-1)；i=2,3,......,Rcon的求法,RC[1]=’01’ (0000 0001) Rcon[1]=(’01’,00,00,00)RC[2]=‘02’ (0000 0010)

12、 Rcon[2]=(’02’,00,00,00)RC[3]=‘04’ (0000 0100) Rcon[3]=(’04’,00,00,00)RC[4]=‘08’ (0000 1000) Rcon[4]=(’08’,00,00,00)RC[5]=‘10’ (0001 0000) Rcon[5]=(’10’,00,00,00)RC

13、[6]=‘20’ (0010 0000) Rcon[6]=(’20’,00,00,00)RC[7]=‘40’ (0100 0000) Rcon[7]=(’40’,00,00,00),RC[i],求K5,K6,K7,三個子密鑰計(jì)算如下： K(5)=K(i-4) XOR K(i-1)=K(1)XOR K(4)= 05613956 XOR 883448fa =8d5571ac ；

14、K(6)=K(i-4) XOR K(i-1)=K(2)XOR K(5)= 73620531 XOR 8d5571ac =fe37749d ；K(7)=K(i-4) XOR K(i-1)=K(3)XOR K(6)= 00550932 XOR fe37749d =fe627daf ；,2) 輪密鑰選取 輪密鑰i（即第i 個輪密鑰）由輪密鑰緩沖字W[Nb* i]到W[Nb*(i+1)]給出:,AES算法的密鑰編排算法,Nb=4及N

15、k=4時(shí)的密鑰擴(kuò)展與輪密鑰選取,AES算法的密鑰編排算法,Nb=4及Nk=6時(shí)的密鑰擴(kuò)展與輪密鑰選取,Nb=4及Nk=8時(shí)的密鑰擴(kuò)展與輪密鑰選取,192bit and 256bit 的密鑰擴(kuò)展,Wi-4,Wi-3,Wi-2,Wi-1,Wi,,ByteSubstituion,,ByteRotate,,+,,Rcons,,,,,,+,,,,,,Key expansion,,,4 =< i < 4 ( Rnd + 1

16、 ),i mod 4 = 0,i mod 4 != 0,Wi-6,Wi-5,Wi-4,Wi-3,Wi-2,,ByteSubstituion,,ByteRotate,,+,,Rcons,,,,,,+,,,,,,Key expansion,,,6 =< i < 6 ( Rnd + 1 ),i mod 6 = 0,i mod 6 != 0,Wi-1,Wi,Nk<=6,若Nk<=6，則有： KeyExpa

17、nsion（byte Key[4*Nk]，W[Nb* (Nr+1)]）{ for(i=0;i< Nk;i++) W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]); for(i= Nk;i< Nb* (Nr+1);i++) { temp=W[i-1]; if(i% Nk= =0) temp=SubByte(R

18、otByte(temp))^Rcon[i/ Nk]; W[i]=W[i- Nk]^temp;}},Wi-6,Wi-5,Wi-4,Wi-3,Wi-2,,ByteSubstituion,,+,,,,,,+,,,,,,Key expansion,,,8 =< i < 8 ( Rnd + 1 ),i mod 8 = 0,i mod 4 != 0,Wi-1,Wi,Wi-8,Wi-7,,ByteSub

19、stituion,,ByteRotate,,+,,Rcons,,,,i mod 4 = 0,i mod 4 = 0,Nk=8時(shí)的密鑰擴(kuò)展,KeyExpansion（byte Key[4*Nk]，W[Nb* (Nr+1)]）{ for(i=0;i< Nk;i++) W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]); for(i= Nk;i< Nb* (N

20、r+1);i++) { temp=W[i-1]; if(i% Nk= =0) temp=SubByte(RotByte(temp))^Rcon[i/ Nk]; else if(i% Nk= =4) temp=SubByte(temp);W[i]=W[i- Nk]^temp;}},輪數(shù)（Round）的不同取值,輪數(shù)（R

21、ound）的不同取值,AES 的密鑰調(diào)度,密鑰調(diào)度包括兩個部分：密鑰擴(kuò)展和輪密鑰選取。密鑰bit的總數(shù)＝分組長度×（輪數(shù)Round＋1）例如當(dāng)分組長度為128bits和輪數(shù)Round為10時(shí)，輪密鑰長度為128×(10＋1)＝1408bits。將密碼密鑰擴(kuò)展成一個擴(kuò)展密鑰。從擴(kuò)展密鑰中取出輪密鑰：第一個輪密鑰由擴(kuò)展密鑰的第一個Nb個字（其實(shí)就是Nb 列），第二個輪密鑰由接下來的Nb個字組成，以此類推。,解密,

22、輪密鑰加,與加密時(shí)相同,逆行移位,逆列混合,對于矩陣ABC，如果C=AB,且A可逆，則A-1C=A-1AB=B,逆字節(jié)替代（逆S盒）,作業(yè),1 對于分組長度128比特，密鑰長度128比特的AES算法，若已知明文是各自名字組成，密鑰是學(xué)號，若不夠則填充，填充方法為(除最后一個字節(jié)外)均以0x00填充,填充序列的最后一個字節(jié)記錄填充序列的長度。求第一輪字節(jié)代換、行移變換和列變換的輸出.例如 王二是“WANG ER”, 學(xué)號是“2013

23、122000”W?87?0x57 A?65?0x41 N?78?0x4E G?71?0x47 space?32?0x20 E?69?0x45 R?82?0x520?50?0x30 1 ?50?0x31 2 ?50?0x32 3?50?0x33 明文：0x57414E47324552000000000000000007; 密鑰：0x32303133313232303030000000000006.,后面內(nèi)容僅供參

24、考,,基本運(yùn)算,在AES中選擇的不可約多項(xiàng)式是p(x) = x8 + x4 + x3 + x + 1，余式的次數(shù)至多是7次，共28=256個多項(xiàng)式，這256個余式構(gòu)成了一個有限域。,字節(jié)在GF(28)上的表示,字節(jié)b用二進(jìn)制表示為b=b7b6b5b4b3b2b1b0為有限域GF(28)上的域元素，若用多項(xiàng)式表示，bi可看作是多項(xiàng)式的系數(shù)，bi∈{0,1}，則字節(jié)b對應(yīng)多項(xiàng)式為：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2

25、+b1x+b0例如：字節(jié)‘57’ （十六進(jìn)制數(shù)）對應(yīng)的二進(jìn)制為01010111，為GF(28)上域元素，字節(jié)‘57’對應(yīng)的多項(xiàng)式為x6+x4+x2+x+1。,GF(28)上兩個域元素的和,GF(28)上兩個域元素的和對應(yīng)的多項(xiàng)式仍然是一個次數(shù)不超過7的多項(xiàng)式，其多項(xiàng)式系數(shù)等于兩個元素對應(yīng)多項(xiàng)式系數(shù)的模2加，即域元素對應(yīng)二進(jìn)制按位異或運(yùn)算。例如:‘57’+‘83’= ‘D4’，用多項(xiàng)式表示為:(x6+x4+x2+x+1)+(x7+

26、x+1)≡x7+x6+x4+x2(modp(x))用二進(jìn)制表示為：01010111⊕10000011=11010100由于每個元素的加法逆元等于自己，所以有限域減法和加法相同。,GF(28)上兩個域元素的乘,要計(jì)算GF(28)上域元素的乘法，必須先確定一個GF(2)上的8次不可約多項(xiàng)式；GF(28)上兩個元素的乘積就是這兩個多項(xiàng)式的模乘。在Rijndael密碼中，這個8次不可約多項(xiàng)式確定為：p(x)= x8+x4+x3+x+1

27、它的十六進(jìn)制表示為‘11B’。例如，‘57’·‘83’=‘C1’可表示為以下的多項(xiàng)式乘法：(x6+x4+x2+x+1)·(x7+x+1)≡x7+x6+1(mod p(x)),x乘法,GF(28)上還定義了一個運(yùn)算，稱之為x乘法，其定義為x·b(x)≡b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x(mod p(x)) 如果b7=0，求模結(jié)果不變，否則為乘積結(jié)果減去p(x)

28、，即求乘積結(jié)果與p(x)的異或。由此得出x（十六進(jìn)制數(shù)‘02’）乘b(x)可以先對b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0）?！∪鬮7=1，則再與‘1B’（其二進(jìn)制為00011011）做逐比特異或來實(shí)現(xiàn)，而任意常數(shù)乘法可以通過對中間結(jié)果相加實(shí)現(xiàn)。,b7＝0實(shí)例舉例,02 ·54 =(0000 0010)·(0101 0100)=(x)·(x6+x4+x2) =x7+ x5+x3

29、 =x7+ x5+x3 ≡ x7+ x5+x3 (mod p(x)) =(1010 1000）由上面的規(guī)則：相當(dāng)于把字節(jié)(0101 0100)左移一位即得（1010 1000）（最后一位補(bǔ)0）。,b7＝1實(shí)例舉例,02 ·D4=(0000 0010) ·(1101 0100) =(x) ·(x7+x6+x4+x2) (modp(x))

30、 =x8+x7+ x5+x3(modp(x)) ≡(x4+x3+x+1)+x7+x5+x3(modp(x)) ≡ x7+x5+x4+x+1(modp(x)) 多項(xiàng)式 x7+x5+x4+x+1映射為二進(jìn)制即為：(1011 0011)由上面的規(guī)則：先把(1101 0100) 在字節(jié)內(nèi)左移一位即得（10101000）（最后一位補(bǔ)0），因?yàn)閎7＝1，故（1010 1000）再與（0001

31、 1011）異或得（1011 0011）,‘57’·‘13’,‘57’·‘02’=‘AE’；‘57’·‘04’= ‘AE’ ·‘02’ =‘47’；‘57’·‘08’= ‘47’ ·‘02’ =‘8E’；‘57’·‘10’= ‘8E’ ·‘02’ =‘07’；‘57’·‘13’=‘57’·(‘01’ ⊕ ‘02’ ⊕‘10’)

32、=‘57’⊕‘AE’ ⊕‘07’=‘FE’。 因?yàn)椤?3’=‘01’ ⊕ ‘02’ ⊕‘10’=‘01’ +‘02’ +‘10’,GF(28)上域元素的乘法逆元,在有限域GF(28)中，域元素的乘法滿足交換律，且有單位元,并且每個域元素都有乘法逆元。在GF(28)中求乘法逆元可利用多項(xiàng)式的擴(kuò)展的歐幾里得算法計(jì)算出來。求次數(shù)小于8的非零多項(xiàng)式b(x)的乘法逆元，首先利用多項(xiàng)式的擴(kuò)展歐幾里得算法得出兩個多項(xiàng)式a(x)和c(x)，使得滿

33、足b(x)a(x)+p(x)c(x)=1， 即滿足a(x)·b(x) ≡1 mod p(x)，因此a(x)是b(x)的乘法逆元。,乘法逆元舉例,求GF(28)上域元素，‘F5’(十六進(jìn)制)的乘法逆元。（1）‘F5’用對應(yīng)二進(jìn)制為11111001，則用多項(xiàng)式表示為b(x)=x7+x6+x5+x4+x2+1，然后計(jì)算兩個多項(xiàng)式a(x)和c(x)滿足(x7+x6+x5+x4+x2+1)·a(x)+p(x)c(x)=1

34、 (2) 采用多項(xiàng)式的擴(kuò)展歐幾里得算法按照如下步驟計(jì)算：因?yàn)椋?x8+x4+ x3+x+1)=(x7+x6+x5+x4+x2+1)(x+1)+ x2(x7+x6+x5+x4+x2+1)=x2(x5+x4+x3+x2+ 1)+1,,1=(x7+x6+x5+x4+x2+1)-x2(x5+x4+x3+x2+ 1)=(x7+x6+x5+x4+x2+1)-[(x8+x4+x3+x+1)-(x7+x6+x5+x4+x2+1)( x+1)]

35、(x5+x4+x3+x2+1)=(x8+x4+x3+x+1)(x5+x4+x3+x2+1)-(x7+x6+x5+x4+x2+1)[1+(x+1)(x5+x4+x3+x2+1)]=x8+x4+x3+x+1)(x5+x4+x3+x2+1)-(x7+x6+x5+x4+x2+1)(x6+x2+x),S盒和逆S盒的關(guān)系,一個表是另一個表的反查,S盒詳解-SubBytes變換的兩個步驟,步一：把S盒中的每個字節(jié)映射為它在有限域GF(28)中的

36、乘法逆 步二：,,例子,“95”的乘法逆為“8a”，二進(jìn)制表示為“10001010”結(jié)果為“00101010”，十六進(jìn)制表示為“2a”,,以輸入“F5”為示例,1）其輸入十六進(jìn)制“F5”對應(yīng)二進(jìn)制為“11110101”，多項(xiàng)式為(x7+x6+x5+x4+x2+1)，求其模f(x)=x8+x4+x2+x+1的逆，即求b(x)：(x7+x6+x5+x4+x2+1)·b(x)≡1(mod f(x))通過多項(xiàng)

37、式歐幾里得擴(kuò)展算法，求解得：(x7+x6+x5+x4+x2+1)(x6+x2+x)≡1 mod(x8+x4+x3+x+1) 即：(x7+x6+x5+x4+x2+1)模(x8+x4+x3+x+1)的乘法逆元為x6+x2+x，即 ‘F5’的乘法逆元為‘46’,實(shí)例,2）十六進(jìn)制‘46’其二進(jìn)制為01000110，進(jìn)行第2步的仿射變換，代入矩陣運(yùn)算運(yùn)行：,即二進(jìn)制結(jié)果為11100110，對應(yīng)十六進(jìn)制結(jié)果為“E6”，,Subbyte原理,（

38、加密時(shí)）輸入為m,其modp(x)的逆為m’仿射變換y=Am’+b（解密時(shí)）則Am’=y-bA-1Am’=m’ =A-1(y-b)=A-1y-A-1b=A-1y+A-1b再求m’ modp(x)的逆為m,仿射變換中的矩陣,A為：,A-1為：,b為：,A-1b為,仿射變換中的兩矩陣的關(guān)系,=,驗(yàn)證A-1b,要想到，這也是在做有限域的乘法,列混合中的兩個矩陣,驗(yàn)證AA-1=I,對于矩陣ABC，如果C=AB

39、,且A可逆，則A-1C=A-1AB=B,一起看看標(biāo)準(zhǔn)fips-197,,DES擴(kuò)散,課堂練習(xí)，R0前四個比特全部翻轉(zhuǎn)，一輪加密的擴(kuò)散情況如何？,第一輪擴(kuò)散,,,第一輪擴(kuò)散,,,,,,,,,,,第二輪擴(kuò)散,,,第二輪擴(kuò)散,,,,,,,,,,,DES擴(kuò)散,,,,,,,,,,,,,,,,,,,,,DES擴(kuò)散,思考：L0的一塊數(shù)據(jù)（4比特）要幾輪才能影響所有的數(shù)據(jù)塊？S盒的擴(kuò)散和混淆情況如何？,第一輪擴(kuò)散,第二輪擴(kuò)散,AES擴(kuò)散,輪函數(shù),輪