《新一代密码系统AdvancedEncryptionStandard.ppt》由会员分享，可在线阅读，更多相关《新一代密码系统AdvancedEncryptionStandard.ppt（69页珍藏版）》请在三一文库上搜索。
1、新一代密碼系統 (Advanced Encryption Standard),2,本章內容,6.1 前言 6.2 Rijndael密碼系統 6.3 Rijndael密碼系統的數學背景 6.4 回合金鑰的產生 6.5 Rijndael的加密演算法 6.6 Rijndael的解密演算法,3,6.1 前言,就目前科技而言，現有之DES密碼系統所使用之金鑰長度過短(僅56位元)，其安全性已遭受質疑，為提高其安全性，便有了Triple-DES的構想。 隨著電腦技技的發展，可預見未來Triple-DES的加密演算法也勢必淘汰，有鑑於此，美國國家標準技術局(NIST)於1997年元月二日開始著手計劃公開徵求
2、新一代加密標準(簡稱AES)。,4,1997年元月二日由NIST經由公開程序對外徵求 1997年四月十五日舉辦AES研討會，研討制訂AES之功能需求。NIST於1997年九月十二日，正式公佈AES功能規格標準需求： - AES為一對稱性加密演算法 - AES為一區塊加密演算法 - AES為進行加密之區塊最小為128位元 - AES秘密金鑰之長度是變動的，可以為128、192 或 256位元 - 可以同時由硬體及軟體來實作 - 沒有專利的限制，可以自由使用,AES (Advanced Encryption Standard),5,1998年8月20日NIST舉行第一屆AES會議，會中並宣佈及介紹
3、15個獲AES初選之演算法：CAST-256、CRYPTON、DEAL、DFC、E2、FROG、HPC、LOKI97、MAGENTA、MARS、RC6、RIJNDAEL、SAFER+、SERPENT、TWOFISH。 針對此15個初選AES之安全性、效率及相容性做分析，並於1999年3月22日第二屆AES會議中提出分析報告。 1999年8月20日公佈MARS、RC6、Rijndael、Serpent及Twofish等5個演算法可進入第二回合決選。,AES (Advanced Encryption Standard),6,NIST於2000年4月13日再舉行第三屆AES會議，對五個決選AES演算
4、法再進行分析。 2000年10月2日正式宣佈由比利時二位密碼專家Joan Daemen及Vincent Rijmen二位博士所設計Rijndael（發音為Rain Doll）獲選為AES之演算法。,AES (Advanced Encryption Standard),7,AES初選演算法,AES加密演算法之架構,AddRoundKey,1:SubBytes,2:ShiftRows,3:MixColumns,4:AddRoundKey,1:SubBytes,2:ShiftRows,3:AddRoundKey,密文,明文,AddRoundKey,1:SubBytes,2:ShiftRows,3:M
5、ixColumns,4:AddRoundKey,1:SubBytes,2:ShiftRows,3:AddRoundKey,初次 Round Key,Round 1,Round Key,Round 1,2,3,4,5,6,7,8,Nr-1,最後 Round Key,密文,明文,By :施冠州 邱敬智 許修維,9,6.2 Rijndael 密碼系統, Rijndael,反覆運算的加密演算法 資料區塊及金鑰可獨立變動 128, 192, 256 bits State: 運算過程所產生的中間值，用一個以byte為單位的長方型矩陣來表示(4列，行數為資料區塊除以32bits)，成為一個 4Nb 的矩陣，
6、也就是把資料分割成 Nb 個區塊或 行數。,8 bits * 4 = 32 bits X / 32 = Nb 行 X / 8 = 4 * Nb byte,加解密資料會先被複製到此state矩陣,AES演算法相關參數說明,Nb (明文區塊數目) 由資料長度除以32位元求得 Nk (金鑰區塊數目) 由金鑰長度除以32位元求得 Nr (回合數) 由Nb、Nk共同決定 State (要加密的資料) 加密的資料會先被複製到此一矩陣(size:4 * Nb) W(存放金鑰字元的陣列) 陣列中每個元素為32位元(size:Nb * (Nr+1),10,11,Cipher Key: 加密金鑰，一個 4Nk b
7、ytes的矩陣，也就是把金鑰分割成 Nk 個32位元之子金鑰。,6.2 Rijndael 密碼系統, Rijndael,Nk=6 if cipher key size = 192 bits, then 192/32 = 6,Nb vs. Nk,12,Nb = 4,Nk = 6,4 bytes,決定出回數,如下表,Nr: 回合數，由Nb及Nk決定出回數。,Rijndael 執行的回合數,13,Nr(回合數)，由Nb及Nk所決定的，回合的變動數如表:,加密流程,14,6.3 Rijndael密碼系統的數學背景, GF(28)的定義,假設位元組,由,組成，將,當作一個7,次多項式的係數。,例如:,表
8、示成多項式為:,GF(28) = GF(256),15,數學背景, 加法,兩個多項式的加法，即係數做XOR。,例如:,表示成多項式為:,0,16,數學背景, 乘法,在GF(28)中的乘法運算，也可視為兩個多項式相乘。,0,?!,17,數學背景, 乘法,多項式相乘之後的結果很容易造成溢位，在Rijndael中 將其溢位再modulo一個固定的多項式:,例如:,Mathematical Preliminaries,Addition XOR operation Multiplication In the polynomial representation, multiplication in GF(
9、28)corresponds with the multiplication of polynomials modulo an irreducible polynomial of degree 8. m(x) = x8+x4+x3+x+1 EX, 5783 = c1 0101011110000011=11000001 (x6+x4+x2+x+1)(x7+x+1) =x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1 =x13+x11+x9+x8+x6+x5+x4+x3+1 (x13+x11+x9+x8+x6+x5+x4+x3+1) modulo x8+x4+
10、x3+x+1 =x7+x6+1,by Dr. 林仁宏,19,6.4 回合金鑰的產生,在Rijndael的密碼系統中，不管加密或解密都需要產生各回合所使用的回合金鑰(Round Key)或副金鑰(Subkey)。 回合金鑰的產生方式可分兩階段，第一階段為金鑰的擴充，第二階段為回合金錀的選擇。,20, Cipher key Expanded key,Expanded key是一個線性的4byte矩陣，以WNb (Nr+1)表示，前Nk個字組包含了加密金鑰(Cipher key)，剩下的字組 依不同的Nk值，會有不同的處理如下:,6.4.1 金鑰的擴充,Example: Nb=4, Nk=6, Nr
11、=12 W4 * 13= W52=W0W51,原始金鑰(128bit) Ki= 1 byte = 8 bits Key=ABCDEFGHIJKLMNOP 4word(128bit) Key將擴充成為4*11word key 6word(192bit) Key將擴充成為4*13word key 8word(256bit) Key將擴充成為4*15word key,金鑰之擴充程序(1/4),K1,K2,K3,K4,K1,K2,K3,K4,K1,K2,K3,K4,K1,K2,K3,K4,128 / 8 = 16,By :施冠州 邱敬智 許修維,擴充程序(2/4),41,42,43,44,45,46,
12、47,48,49,4a,4b,4c,4d,4e,4f,50,4e,4f,50,4d,RotWord,SubBytes,4,e,2f,4e,2f,84,53,e3,=,RCON,Wi-4 Wi-1 Wi,If (i mod 4)=0 Wi = Wi-4 SubBytes(RotWord(Wi-1) RCON(i) RCON(i) = 2(i-4)/4 = 1,2,4,8,W4,23,XOR,AES Key Schedule,移動到最下面,RotWord,(經過S-Box轉換後),09,XOR,XOR,Cipher key,Round key 1,Rcon,By: 韋宜成、 劉伯伸、 陳昱潭、 曾
13、劭逸,24,AES Key Schedule(1/2),XOR,總共10個round,Cipher key,Round key 1,擴充程序(3/4),41,42,43,44,Wi-4 Wi-1 Wi,If (i mod 4) 0 Wi = Wi-4 Wi-1,If (i mod 4)=0 Wi = Wi-4 SubBytes(RotWord(Wi-1) RCON(i) Else Wi = Wi-4 Wi-1 128bit的 Key 需 11 回合加解密, 因此 i = 4 - 44,擴充金鑰之規則(4/4),第二 組後擴充金鑰之規則 If (i mod kw)=0 then Wi= Wi-
14、kw SubBytes( RotWord(Wi-1) ) 2(i/kw)-1 Else If (kw6) and (i mod 4)=0) then Wi= eKi- kw SubBytes( Wi-1 ) Else Wi= eKi- kw Wi-1 kw :key之word數 128bit Key, kw=4, 需 10 次 i = 4 - 43 192bit Key, kw=6, 需 8 次 i = 6 - 51 256bit Key, kw=8, 需 7 次 i = 8 - 59,27, Expanded key Round key,子金鑰的選擇是由擴充金鑰中所依序給定的，即 第i把回合
15、金鑰由WNbi WNb(i+1)-1,Round Key 1: W4W7 Round Key 2: W8W11 Round Key 3: W12W15,6.4.2 選擇回合金鑰,Round Key 11: W44W47,Round Key 0: W0W3,Round Key 12: W48W51,Initial Round,Standard Round,Final Round,28,Standard Round,Standard Round Byte Sub Shift Row Mix Column Add Round Key,29, Add Round Key(state,Round key
16、),將狀態值與子金鑰作互斥或運算,6.5.1 回合金鑰的加密函數,W0,W1,W2,W3,Ex,State,RK0,30,a3, 5,a3, 4,a3, 3,a3, 2,a3, 1,a3, 0,a2, 5,a2, 4,a2, 3,a2, 2,a2, 1,a2, 0,a1, 5,a1, 4,a1, 3,a1, 2,a1, 1,a1, 0,a0, 5,a0, 4,a0, 3,a0, 2,a0, 1,a0, 0,S-Box,6.5.2 位元組取代轉換Byte Sub函數,31,位元組取代轉換 (Byte Sub),位元組轉換是一個以位元組為單位的線性取代運算，取代表(S-Box)是經過兩個運算過程而
17、建立，並且是可逆的。,55,(95)16 (2a)16,32,Byte Sub 位元組取代轉換,33,Byte Sub 例子,34,Byte Sub 例子的驗證,35,Byte Sub 查表,36,Byte Sub 反運算,37,Byte Sub 反運算例子,的乘法反元素為,38,Byte Sub 反運算查表,39,Byte Sub 查表,EX,40,每一個State的第一列不變，後三列被循環轉換(cyclically shift)不同的大小，且依Nb的大小也會有所不同，如下:,6.5.3 移列轉換函數,41,Shift Row 例子,ShiftRows()：列移位運算,Data ShiftR
18、ows(Data),3d,08,3d,3d,左旋1,左旋2,左旋3,08,43,6.5.4 MixColumn混行轉換函數,每一 entity 視為一個在 GF(28)中之多項式,44,6.5.4 MixColumn混行轉換函數,MixColumns()：混合行運算,Data MixColumns(Data),d4,bf,5d,30,d4,bf,5d,30,04,66,81,e5,04,66,81,e5,For more details, see next page,?,By 施冠州 邱敬智 許修維,AES加密運算實例(5/6 ),混合行運算 (Mix Column Operation),D4
19、 11010100 02 00000010,00000000 11010100,110101000 超過有限場需 以11B調整,x8+x7+x5+ x3 x8+ x4+x3+x+1,x7+x5+x4+ x+1 10110011,BF 10111111 03 00000011,10111111 10111111,111000001 超過有限場需 以11B調整,x8+x7+x6+ +1 x8+ x4+x3+x+1,1,1,x7+x6+x4+x3+x 11011010,AES加密運算實例(6/6 ),混合行運算 (Mix Column Operation),10110011 02 d4 結果,110
20、11010 03 bf 結果,01101001,01011101 5d,00110100,00110000 30,00000100 04,以此類推，求得其他值,48,Final Round,Final Round Byte Sub Shift Row Add Round Key,49,加密範例,加密的文件訊息為(D49F42BC01F2D4DBBC0FD12F0CFD0240)16 初始的狀態值矩陣其內容為,50,步驟一： 回合金鑰RK0 狀態值矩陣與回合金鑰RK0透過回合金鑰加密函數 (Add Round Key)的運算過程,51,步驟二： 狀態值矩陣經過SubByte函數轉換之後所得到的結
21、果,52,步驟三： 狀態值矩陣的內容做完ShiftRow函數轉換後的結果,53,步驟四 做完MixColumn函數轉換的結果 如何得到的S0,0的值？,54,步驟五： 將步驟四所得到的結果與相對應的回合金鑰再執行一次AddRoundKey函數的運算。反覆執行步驟二至五，共執行 (Nr-1)回合。 步驟六： 再重複執行步驟二的SubByte轉換及步驟三的ShiftRow轉換，所得到的結果再與最後一回合的回合金鑰RKNr執行步驟五的AddRoundKey函數運算，最後狀態值矩陣的內容就是我們要獲得的密文。,55,6.6 Rijndael的解密演算法,Cipher Text,Initial Roun
22、d Add Round Key,Inv Standard Round,Inv Byte Sub,Inv Shift Row,Inv Mix Column,Add Round Key,Final Round Inv Byte Sub Inv Shift Row Add Round Key,Plain Text,Nr-1 Rounds,Cipher Key,Expansion,Expanded Key,Selection,Round Key 1,Round Key 2,Round Key 3,Round Key Nr-1,Round Key Nr,Round Key 0,56,6.6.1 反位元組
23、取代轉換,轉換矩陣,57,Inverse S-Box,從S-Box的(9,5)座標中找到其對應值2A。 從Inverse S-Box的(2, A)座標找到其對應值為95,58,6.6.2 反移列轉換,移列轉換的反運算其移位的規則與ShiftRow相反，狀態值中第一列保持不變，第二列向右做1個位元組的旋轉位移，第三列向右做2個位元組的旋轉位移，第四列向右做3個位元組的旋轉位移，其餘依此類推。,59,6.6.3 反混行轉換,概念是希望再乘上一個多項式d(x)，使其 回復到轉換前的狀態。 可用下列矩陣表示 例如： 其中d(x)=0Bx3+0Dx2+09x+0E,60,6.6.4 解密流程,步驟一：
24、先將密文轉換成一狀態值矩陣，再將狀態值矩陣與回合金鑰RKNr經由回合金鑰加密函數 (AddRoundKey)來做運算。 步驟二： 將狀態值矩陣中的結果經過InvShiftRow函數的轉換，InvShiftRow的轉換是將狀態值中的位元組向右做循環列位移轉換，其轉換規則為狀態值中的第一列維持不變，第二列向左循環位移一個位元組，依此類推。,61,步驟三 將步驟二所產生的結果經由InvByteSub函數轉換。利用Inverse S-Box來做查表。藉由行與列的索引，可找出反向的S-box中所對應的位元組，再用此位元組替換掉原來的位元組。 步驟四： 將步驟三所得到的結果與回合金鑰再執行一次AddRou
25、ndKey的轉換。,62,步驟五： 將上一步驟轉換後的結果再經由InvMixColumn函數轉換，其轉換方式就是將狀態值矩陣與單位矩陣做矩陣相乘。 步驟六： 重複執行步驟二至五 (Nr-1)回合後，將其結果，再執行一次步驟二的InvShiftRow的轉換及步驟三的InvByteSub轉換，所得到的結果再與初始回合的回合金鑰RK0執行一次AddRoundKey的轉換，最後的輸出就是我們想要獲得的文件訊息。,63,加密與解密的對應關係,AES的數論基礎,89053302 林仁宏 2005.01,Galois Field F28,AES所用到之Galois Field F28，並非直接從整數Z作模運
26、算可得 其中一個典型的做法是先考慮多項式環,再行模運算 (mod t8 + t4 + t3 + t +1) 當中 t8 + t4 + t3 + t +1為首項係數為1不可約(Monic irreducible) F2多項式,AES的數論基礎,By:林仁宏,Fpt (p為質數)的除法,考慮兩多項式除法 p(t)、m(t) Fpt 可唯一表達成 p(x) = m(t)q(t) + r(t) 其中 q(t) 為商式，r(t) 為餘式 Fpt /(t) (其中(t) 為首項係數為1不可約多項式)代表所有Fpt 多項式模 (t) 之同餘類所形成之集合 由於(t) 為不可約多項式，所有非(t) 倍數之多項
27、式，都與(t) 互質,同構,所有的Galois Field凡是元素個數(又稱秩(order)相同，皆同構，故F3t / (t2+1) F3t / (t2+t+1) 其中 t2+1與t2+t+1皆為次數3之不可約多項式 因此在考量Galois Field K之代數結構時，只需知道K之秩，任何所選取之模型都是同構 K之秩必然是pn ，其中p為質數，n為正整數；在考量K上之計算，一般是考慮模型K Fpt /(t) (其中(t) 為首項係數為1 ，次數為n之不可約之Fp之多項式),Galois Field Fp 與 Fpt /(t) 之異同處,Z Fpt 質數q (t) (mod q) (mod (t
28、) | | deg() Zq Fpt /(t) Fq Fpn AES所用之Galois Field F28 F2t / (t8 + t4 + t3 + t +1)之元素可很自然地化成為2進位數，譬如 t7 + t6 + t3 + t +1(11001011)2,加法與乘法,F2多項式之加法，即XOR運算 (t7 + t6 + t3 + t +1)+(t7 + t5 + t2) = t6 + t5 + t3 + t2+ t + 1(01101111)2 = (11001011)2 (10100100)2 而乘上t ，即左移一位元，末位填0 ( t5 + t3 +1)t= t6 + t4 + t(01010010)2 = (00101001)2 1 這些運算，包括模運算，都非常容易以硬體實現。,