張文錦+周榮+高燕

摘要：介紹AES算法的基本理論，并應(yīng)用到具體軟件實(shí)現(xiàn)中。在AES算法實(shí)現(xiàn)中，預(yù)先存儲(chǔ)正反S盒查找表，提高算法執(zhí)行的運(yùn)行速度；使用密文挪用技術(shù)，解決待處理數(shù)據(jù)長(zhǎng)度不是分組長(zhǎng)度整數(shù)倍的問(wèn)題；提出優(yōu)化文件讀寫方案，使用多線程和緩存技術(shù)，提高系統(tǒng)加密解密的吞吐量。測(cè)試加密軟件的基本功能，并對(duì)軟件性能作量級(jí)測(cè)試。

關(guān)鍵詞：AES；加密；解密；密文挪用；分組密碼

DOIDOI：10.11907/rjdk.171097

中圖分類號(hào)：TP309.7

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）006-0180-03

0 引言

隨著信息化的推進(jìn)，“互聯(lián)網(wǎng)+”應(yīng)用不斷深入。信息化滲透到人們學(xué)習(xí)、工作、生活等各方面，為人們提供便利服務(wù)的同時(shí)，也面臨著信息安全的巨大挑戰(zhàn)。個(gè)人信息安全是信息安全的重要組成部分，個(gè)人電腦或U盤中毒丟失都會(huì)造成個(gè)人信息的泄露。創(chuàng)建一個(gè)保護(hù)用戶個(gè)人信息的工具具有重要意義。

1 AES算法簡(jiǎn)介

1.1 算法背景

高級(jí)加密標(biāo)準(zhǔn)（即AES[1]），又稱Rijndael加密法，是一種區(qū)塊加密標(biāo)準(zhǔn)，用來(lái)替代原先的DES，已經(jīng)被多方分析且廣泛應(yīng)用。經(jīng)過(guò)5年的甄選流程，高級(jí)加密標(biāo)準(zhǔn)由美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）于2001年11月26日發(fā)布于FIPS PUB 197，并在2002年5月26日成為有效的標(biāo)準(zhǔn)。2006年，高級(jí)加密標(biāo)準(zhǔn)已成為對(duì)稱密鑰加密中最流行的算法之一。

1.2 算法流程

AES加密算法的處理單元是分組，分組的128bit數(shù)據(jù)（16字節(jié)）會(huì)按照順序賦值到4*4的狀態(tài)矩陣（state）中，所有變換都是基于狀態(tài)矩陣完成的。AES變換是多輪迭代的輪變換實(shí)現(xiàn)的，迭代次數(shù)與密鑰長(zhǎng)度有關(guān)（以AES-128為說(shuō)明）。輪變換包括4步變換，包括字節(jié)替換（SubBytes（））、行變換（ShiftRows（））、列混合（MixColumns（）[2]）和密鑰加（AddRoundKey（））[3]。通過(guò)非線性變換、混合函數(shù)變換，將字節(jié)代換運(yùn)算產(chǎn)生的非線性擴(kuò)散，達(dá)到重復(fù)混合，使得加密完成后的分組擴(kuò)散更均勻。輪密鑰擴(kuò)展將原始密碼擴(kuò)展成11組，每輪迭代使用不同的密鑰。加密流程如圖1所示。

2 算法實(shí)現(xiàn)

2.1 密鑰擴(kuò)展

按照列優(yōu)先的方式將種子密鑰排列成4*4矩陣，矩陣每一列就可以稱為一個(gè)32bit的字。密鑰擴(kuò)展的目的就是將種子密鑰由4個(gè)字?jǐn)U展成44個(gè)字，每一輪加密需要4個(gè)字，為了方便描述，第一個(gè)字為w[0]，第二個(gè)字為w[1]…依次類推，最后一個(gè)字為w[43]。

前4個(gè)字可以用種子密鑰初始化，然后，對(duì)數(shù)組w擴(kuò)充40個(gè)新字。遞歸方式：

（1）若i不是4的倍數(shù)，那么w[i]=w[i-4]^w[i-1]。

（2）若i是4的倍數(shù)，那么w[i]=w[i-4]^T（w[i-1]）；其中，T是一個(gè)函數(shù)。

函數(shù)T由3個(gè)部分組成：字循環(huán)、字節(jié)代換與輪常量異或。

（3）字循環(huán)：將一個(gè)字中的4個(gè)字節(jié)分別向左移動(dòng)一個(gè)字節(jié)。即[x0，x1，x2，x3]變換為[x1，x2，x3 ，x0]

（4）字節(jié)代換：即S盒置換。

（5）輪常量異或：將前兩步的結(jié)果與輪常量Rcon[j]進(jìn)行異或。

2.2 S盒置換和逆S盒置換

S盒置換又稱字節(jié)代換。正S盒（Sbox），逆S盒（Inv Sbox）提前計(jì)算存儲(chǔ)在代碼中，字節(jié)代換可以簡(jiǎn)化成一個(gè)簡(jiǎn)單的查表操作。通過(guò)下標(biāo)取出對(duì)應(yīng)的值就是這個(gè)映射操作，如圖2所示。S盒置換使用正S盒，逆S盒置換使用逆S盒。

2.3 行移位變換與逆向行移位變換

行移位的功能是將字節(jié)矩陣通過(guò)簡(jiǎn)單的左循環(huán)移位操作。當(dāng)密鑰長(zhǎng)為128bit，狀態(tài)矩陣的第i行左移i個(gè)字節(jié)，如圖3所示。逆行移位就是還原行移位，狀態(tài)矩陣向右循環(huán)移位，狀態(tài)矩陣的第i行右移i個(gè)字節(jié)。

2.4 列混合變換和逆列混合變換

列混合算法：使用GF（）域[4]算術(shù)特性替代

根據(jù)矩陣的乘法可知，在列混淆過(guò)程中，每個(gè)字節(jié)對(duì)應(yīng)的值只與該列的4個(gè)值有關(guān)系。此處的乘法和加法都定義在GF（28）有限域上。

需要注意如下幾點(diǎn)：

（1）將某個(gè)字節(jié)的值乘2，即該值的二進(jìn)制位左移一位，如果該值的最高位為1（即該數(shù)值不小于128），則還需要將移位后的結(jié)果異或00011011。

（2）乘法對(duì)加法滿足分配率，例如：07·S0，0=（01⊕02⊕04）·S0，0= S0，0⊕（02·S0，0）（04·S0，0）。

（3）此處矩陣乘法與矩陣的乘法不同，各個(gè)值在相加時(shí)使用的是模2加法（相當(dāng)于是異或運(yùn)算）。

逆列混合操作同樣使用GF（）域上算術(shù)特性替代，只是多項(xiàng)式c（x）不同。

2.5 輪密鑰加

將128位輪密鑰與狀態(tài)矩陣中的數(shù)據(jù)進(jìn)行按位異或操作。因?yàn)楫惢虿僮鞯哪娌僮骷词潜旧?，所以解密輪密鑰加也是本身。

3 軟件優(yōu)化

3.1 密文挪用

AES算法是分組加密算法，所以不可避免地要處理待處理數(shù)據(jù)不是分組數(shù)據(jù)的整數(shù)倍的問(wèn)題。如果不處理這部分不夠的數(shù)據(jù)，那么加密解密以后得到的原始信息將在最后一個(gè)分組多出一部分錯(cuò)誤信息，而沒(méi)有被賦值的數(shù)據(jù)往往就是內(nèi)存中的垃圾值，從而影響正確信息的可讀性。本軟件在實(shí)現(xiàn)過(guò)程中采取的方法是“密文挪用”。

為了便于解釋，設(shè)分組長(zhǎng)度為blen；待處理（加密/解密）的數(shù)據(jù)為d，長(zhǎng)度為dlen；待處理剩余的數(shù)據(jù)為rd，長(zhǎng)度為rdlen。已經(jīng)處理數(shù)據(jù)s。加密實(shí)現(xiàn)過(guò)程如圖4所示。

（1）當(dāng)rdlen>=blen，即剩余數(shù)據(jù)大于分組長(zhǎng)度，轉(zhuǎn)2；否則，轉(zhuǎn)3。

（2）從rd的頭部取大小為blen的數(shù)據(jù)作加密操作，所得數(shù)據(jù)拼接到s尾部，轉(zhuǎn)1。

（3）若rdlen>0，即剩余數(shù)據(jù)不夠一個(gè)分組。在已經(jīng)加密的數(shù)據(jù)s末尾取出大小為blen-rdlen的數(shù)據(jù)與rd拼接構(gòu)成一個(gè)長(zhǎng)度為blen的分組數(shù)據(jù)塊，對(duì)其加密并將結(jié)果拼接到已經(jīng)加密數(shù)據(jù)（除被取出的blen-rdlen的數(shù)據(jù)）后，轉(zhuǎn)4。

（4）若relen==0，所有數(shù)據(jù)加密完成，結(jié)束加密。S為密文。

原文被分成n個(gè)組，第n個(gè)分組不足一個(gè)分組長(zhǎng)度。前面n-2個(gè)分組直接加密即可，第n-1分組加密后要借給n分組然后對(duì)n分組加密。解密實(shí)現(xiàn)過(guò)程如圖5所示。

setp1：當(dāng)rdlen>2*blen，轉(zhuǎn)2；否則，轉(zhuǎn)3。

setp2：rd的頭部取出blen長(zhǎng)的數(shù)據(jù)做解密操作，結(jié)果拼接到s尾部，轉(zhuǎn)1。

setp3：當(dāng)rdlen=2*blen，轉(zhuǎn)4；否則，轉(zhuǎn)5。

setp4：取出rdlen數(shù)據(jù)解密。直到rdlen==0；結(jié)果拼接到s尾部，轉(zhuǎn)6。

setp5：取出剩余數(shù)據(jù)rd末尾blen大小的數(shù)據(jù)塊（剩余的rd-blen大小數(shù)據(jù)塊記作rd）并作解密操作，得到數(shù)據(jù)塊data2；對(duì)剩余的待解密數(shù)據(jù)rd與data2的頭部b1en-rdlen的數(shù)據(jù)進(jìn)行拼接、解密，得到data3。順序拼接s，data3，data2的末尾rdlen個(gè)位數(shù)據(jù)，得到完整解密數(shù)據(jù)、轉(zhuǎn)6。

setp6：所有密文均被解密成原文。結(jié)束解密。

說(shuō)明：密文被分成n個(gè)分組，前n-2分組直接解密。結(jié)尾部分，先取出后面一個(gè)分組，然后n-1分組和解密完的前面部分組成一個(gè)分組解密，然后拼接起來(lái)。

3.2 多線程I/0優(yōu)化

文件讀取和加解密處理的速度是不匹配的。如每次處理一個(gè)分組就讀寫文件一次顯然會(huì)處于空等狀態(tài)，而且多次打開關(guān)閉文件相當(dāng)費(fèi)時(shí)間，而待加密的文件也是可大可小的，可能是幾K的文本，也有可能遇到幾個(gè)G的圖像視頻等，全部讀取到內(nèi)存中也是不可能的?？紤]到以上問(wèn)題，設(shè)置緩沖區(qū)。

文件處理過(guò)程如圖6所示，系統(tǒng)主進(jìn)程實(shí)現(xiàn)加密解密操作，讀文件操作由文件讀進(jìn)程實(shí)現(xiàn)，寫文件操作由文件寫進(jìn)程實(shí)現(xiàn)。待處理數(shù)據(jù)和待寫入文件數(shù)據(jù)緩沖區(qū)使用循環(huán)隊(duì)列實(shí)現(xiàn)，主進(jìn)程直接在緩存區(qū)讀取數(shù)據(jù)，并將數(shù)據(jù)存入寫緩沖區(qū)。

4 軟件運(yùn)行測(cè)試

4.1 基本功能測(cè)試

測(cè)試文件test.txt。內(nèi)容 “這是基于AES加密算法的測(cè)試用例，張文錦zhangwenjin”。加密結(jié)果如圖7。

進(jìn)行解密操作能夠還原文件原來(lái)的內(nèi)容。

4.2 性能測(cè)試

軟件處理大小不同文件的性能如表1。

5 結(jié)語(yǔ)

本文介紹了AES加密算法的實(shí)現(xiàn)原理和過(guò)程，并給出了算法密鑰加、行移位、S盒置換、列混合等關(guān)鍵操作的實(shí)現(xiàn)方法。在實(shí)際應(yīng)用過(guò)程中應(yīng)用密文挪用技術(shù)，巧妙處理分組問(wèn)題，為了提高文件處理效率使用了緩沖區(qū)技術(shù) 。通過(guò)測(cè)試，加密軟件不但在功能上滿足要求，性能方面也令人滿意。

參考文獻(xiàn)：

[1]何明星，范平志.新一代私鑰加密標(biāo)準(zhǔn)AES進(jìn)展與評(píng)述[J].計(jì)算機(jī)應(yīng)用研究，2001，18（10）：4-6.

[2]曾祥勇，張煥國(guó).高級(jí)加密標(biāo)準(zhǔn)Mixcolumn變換設(shè)計(jì)分析[J].武漢大學(xué)學(xué)報(bào)：理學(xué)版，2003，49（5）：597-600.

[3]何明星，林昊.AES算法原理及其實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2001，18（10）：4-6.

[4]Announcing the Advanced Encryption Standard（AES） [p].NIST，2001：1-53.

（責(zé)任編輯：陳福時(shí)）