【文章內(nèi)容簡介】 ④ S 一盒的對(duì)稱性 ⑥加密和解密的對(duì)稱性 所以， Rijndael 算法在綜合了分組密碼的設(shè)計(jì)準(zhǔn)則的同時(shí)，也有其自身 的設(shè)計(jì)準(zhǔn)則 ,這些設(shè)計(jì)準(zhǔn)則的優(yōu)越性，提高了算法的實(shí)現(xiàn)速度，降低了算法的復(fù)雜 第 6 頁 共 26頁 度，算法還有其它的設(shè)計(jì)準(zhǔn)則，這些設(shè)計(jì)準(zhǔn)則在算法的原理描述中，在特定的環(huán)境中給予描述。 Rijndael 算法的加密過程包括一個(gè)初始密鑰加法，記著 AddRoundKey,接著進(jìn)行 Nr一 1次輪變換 Round，最后再使用一個(gè)輪變換 FinalRound。初始的密鑰加法和每個(gè)輪變換均以狀態(tài) State 和一個(gè)輪密鑰作為輸入 。第 i 輪的輪密鑰記為Expandedkey[i]，初始密鑰加法的輸入記為 Expandedkey[0]。從 Cipherkey 導(dǎo)出 Expandedkey 的過程記為 KeyExpansion Rijndael 的高級(jí)語言 。 Rijndael 算法加密輪變換原理 輪變換 Round 由 4 個(gè)變換組成，其中的每個(gè)變換成為步驟，偽 C語言表述如下 : Round(State. ExpandedKey[i]) { SubBytes(State): ShiftRows(State)。 MixColumns(State): AddRoundKey(State, ExpandedKey[i])。 } 最后一輪 FinalRound 稍有不同，偽 C語言描述如下 : FinalRound(State, ExpandedKey[Nr]) { SubBytes(State): ShiftRows(State): AddRoundKey(State ExpandedKey[Nr])。 } Rijndael 算法加密過程示意圖如 下 : 第 7 頁 共 26頁 圖 1 AES的流程圖 SubBytes 變換 SubBytes 是一個(gè)非線性的字節(jié)替代，獨(dú)立地在每個(gè)狀態(tài)字節(jié)上進(jìn)行運(yùn)算。它包括兩個(gè)變換。 1. 在有限域 GF(28)上求乘法逆， ‘ 00’ 映射到它自身。 2. 在 GF(28)上進(jìn)行下面的仿射變換： 圖 2 仿射變換示意圖 該變換可以用一個(gè) 256 字節(jié)的表來實(shí)現(xiàn) 讀進(jìn) 明文 讀進(jìn)密鑰 （ 1 ）產(chǎn)生輪子密鑰 （ 2 ） A dd R ound K e y 變換 （ 3 ）輪變換 R ound ( S t a t e ， R ou nd K e y ) { B y t e S u b( S t a t e ) ； S h i f t R ow ( S t a t e ) ； Mi xC o l um n ( S t a t e ) ； A ddR ound K e y ( S t a t e ， R ound K e y ) ； } （ 4 ）最后輪變換 F i n a l R oun d ( S t a t e ， R ound K e y ) { B y t e S u b( S t a t e ) S h i f t R ow ( S t a t e ) A ddR ound K e y ( S t a t e ， R ound K e y ) ； } 密文 1?rN 圖 4. 10 第 8 頁 共 26頁 圖 3 SubBytes變換示意圖 ShiftRows 變換 在 ShiftRows 變換中，狀態(tài)陣列的后 3 行循環(huán)移位不同的偏移量。第 1 行循環(huán)移位 C1 字節(jié)，第 2 行循環(huán)移位 C2 字節(jié)，第 3 行循 環(huán)移位 C3 字節(jié)。 偏移量的選擇 :按照簡單性的推則，偏移量的值可以取 0，但實(shí)際上對(duì)于一個(gè)128 比特得分組，偏量的值應(yīng)當(dāng)取 0, 1, 2, 3，各所使用的偏移量可以是其中任意一個(gè)。而對(duì)于大于 128 比特的分組，則有多可能。對(duì)于簡化后的 Rijndael 算法，這里采取 128 比特作為研究對(duì)象，偏移量的值應(yīng)當(dāng)取 0,1, 2, 3 ， ShiftRows 對(duì)狀態(tài)的影響如下圖所示： 圖 4 ShiftRows變換狀態(tài)示意圖 MixColumns 變換 將 狀 態(tài) 的 列 看 作 是 有 限 域 GF(28)上 的 多 項(xiàng) 式 a(x) ， 與 多 項(xiàng) 式c(x)={03}x3+{01}x2+{01}x+{02}相乘 (模 x4＋ 1)。 令 b(x) = c(x) a(x) ， 寫 成 矩 陣 形 式 為 ： 第 9 頁 共 26頁 這一運(yùn)算作用在每一列上 圖 5 Mixcolums變換狀態(tài)示意圖 AddRoundKey 變換 將輪密鑰與狀態(tài)按比特異或。輪密鑰是通過 KeySchedule 過程從密碼密鑰中得到的，輪密鑰長度等于分組長度。如下圖所示： 圖 6 AddRoundKey變換示意圖 子密鑰生成算法 子密鑰是由密鑰導(dǎo)出的，這個(gè)過程包含了兩個(gè)組成部分，一個(gè)是密鑰膨脹，另一個(gè)是輪子密鑰的 選取，如下原理 : (1)輪子密鑰的比特總數(shù)和等于分組長度乘以輪的數(shù)目加 1，即每分組長 128比特，輪數(shù)等于 10 時(shí)，輪子密鑰的比特?cái)?shù)總和為 :128*(10+1)=1408 比特 。 (2)密鑰擴(kuò)充為密鑰膨脹 (Expanded Key)。 (3 )輪子密鑰是由這些膨脹密鑰中取出來的，第 1輪子密鑰由最先 Nb個(gè)字組成，第 2 輪子密鑰為次 Nb個(gè)字，以此類推。密鑰擴(kuò)展如下圖 ： 第 10 頁 共 26頁 圖 7 密鑰擴(kuò)展示意圖 圖 8 密鑰擴(kuò)展示意圖 在密鑰擴(kuò)展中，函數(shù) ByteRotate(a,b,c,d)=(b,c,d,a),即是輸入字的 1 字節(jié)循環(huán)。如下圖所示： 圖 9 循環(huán)示意圖 輪密鑰的選取如下圖： 第 11 頁 共 26頁 圖 10 輪密鑰選取示意圖 4 算法優(yōu)化及實(shí)現(xiàn)研究 算法優(yōu)化 通過分析 Rijndael 算法，算法主要有三大模塊組成 :密鑰擴(kuò)展模塊、明文加密模塊和密文解密模塊（此模塊暫不討論）。其中，密鑰擴(kuò)展模塊由產(chǎn)生加密密鑰的重要模塊 。明文加密模塊是由 SubByte 變換、 ShiftRows 變換、 MixColumns變換和 AddRoundKey 變換組成。 在 Rijndael 算法 中，明文加密模塊是核心，而影響其加密速度的是算法的輪變換，所以，要提高算法的效率，最重要的是精簡算法的輪函數(shù)。 描述上為簡單起見，這里選擇 128 比特分組，密鑰長度也是 128 比特。在SubByte 變換中，假設(shè)輸入為 A， A=[ai,j] (0=i, j=3)，輸出為 B,B= [bi,j](0=i, j=3 )，這里用 : B=S[A] (121) 表示 SubByte 變換，也可以寫為 : bi,j=S[ai,j] (122) 在實(shí)際中，在這個(gè)變換中可以轉(zhuǎn)換成查表操作，該表稱為 Rijndael 算法的字節(jié)變換表，也可以稱為 S 一盒，變換表如下表所示 : 圖 11 S盒圖 第 12 頁 共 26頁 在 ShiftRows 變換中，該輪完成之后的輸出為假設(shè)為 C， C=[Ci,j ](0=i, j=3)，用矩陣表示為 : (123) 在 MixColumns 變換中，是在 ShiftRows 變換 的結(jié)果看作在 GF(28)域上的多項(xiàng)式，且把分組中的每一列與特殊多項(xiàng)式 {03}x3+{ 0l}x2+{0l}x+{02}相乘（以多項(xiàng)式 x4+1 為模），設(shè)輸出結(jié)果為 D, D=[di,j] (0=i, j=3)即用矩陣表示為 : (124) 在 AddRoundKey 變 換中， 這一 輪密鑰 開始 作用， 輪密 鑰設(shè)為 K, K=[ki,j]{0=i,3=j}，這一輪的輸出結(jié)果設(shè)為 E, E=[ ei,j ]{0=i,3=j},用矩陣表示為 : (125) 將上述各輪變換矩陣的上一輪輸出結(jié)果帶入到下一輪的輸入中，用線性向量表示為 （ 126） 上述矩陣由五個(gè)矩陣異或而成，最后一個(gè)是密鑰，這是在密鑰擴(kuò)展算法中產(chǎn)生的，前四個(gè)可以通過表 S 第 13 頁 共 26頁 — 盒做成查找表，這樣，每輪操作的四個(gè)變換只需要 4 次查表，然后進(jìn)行四次異或，這樣就可以極大地提高算法的執(zhí)行速度，為了便于表示，設(shè) : （ 127） （ 128） （ 129） （ 130） 所以，各輪的變換矩陣可簡寫為： E=B0? B1? B2? B3?K （ 131） Rijdael 算法 C 語言的實(shí)現(xiàn)： 輪子密鑰產(chǎn)生（ RijndaelKeySchedule）的程序流程圖： 第 14 頁 共 26頁 圖 12 輪子密鑰產(chǎn)生流程圖 AES 加密（ RijndaelEncrypt）的程序流程圖 ： 圖 13 AES加密的程序流程圖 /*查找表 */（注：為了簡化，則 查找表 ft_tab 和 f1_tab 沒給出 具體值） static u32 rnd_con[10]= { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36}。 static u32 ft_tab[4][256] static u32 fl_tab[4][256] 將這 16個(gè)密鑰按 4個(gè)一起放在一個(gè)長度為 44 的數(shù)組（ Ekey）中 通過字節(jié)循環(huán)移位和查表和異或操作可得出第二輪加密的輪子密鑰 通過遞歸定義，可獲得 176個(gè)輪子密鑰 輸入密鑰 輸出 176 個(gè)輪子密鑰 通過 4 次查表操作 輸入 明文和密鑰 輸出密文 第 15 頁 共 26頁 static u32 Ekey[44]。 /* 存放擴(kuò)展密鑰的數(shù)組 */ /* 4個(gè)表的產(chǎn)生 */ define f_rnd(x, n) \ ( ft_tab[0][byte0(x[n])] \ ^ ft_tab[1][byte1(x[(n + 1) amp。 3])] \ ^ ft_tab[2][byte2(x[(n + 2) amp。 3])] \ ^ ft_tab[3][byte3(x[(n + 3) amp。 3])] ) define f_round(bo, bi, k) \ bo[0] = f_rnd(bi, 0) ^ k[0]。 \ bo[1] = f_rnd(bi, 1) ^ k[1]。 \ bo[2] = f_rnd(bi, 2) ^ k[2]。 \ bo[3] = f_rnd(bi, 3) ^ k[3]。 \ k += 4 /* S盒表的產(chǎn)生 */ define ls_box(x) \ ( fl_tab[0][byte0(x)] \ ^ fl_tab[1][byte1