趙亞亞 孫順遠(yuǎn)，2

（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 無錫 214122）（2.江南大學(xué)輕工過程先進(jìn)控制教育部重點實驗室 無錫 214122）

1 引言

隨著計算機和互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，人類已經(jīng)進(jìn)入了大數(shù)據(jù)時代，數(shù)據(jù)已經(jīng)成為人類活動中重要的生產(chǎn)因素。然而，隨著近幾年發(fā)生的數(shù)據(jù)泄露事件，引發(fā)了人們對信息安全問題的關(guān)注［1］。而數(shù)據(jù)加密技術(shù)可以對敏感信息進(jìn)行加密，實現(xiàn)信息隱藏，為敏感信息提供了從發(fā)送方到接收方之間最安全的傳輸方案，保證了這些敏感信息對第三方的不可讀性。

當(dāng)前應(yīng)用最為廣泛的加密算法是高級加密標(biāo)準(zhǔn)AES 算法，它是一種對稱加密算法，與非對稱加密相比，其加密和解密速度優(yōu)勢顯著。但隨著物聯(lián)網(wǎng)的發(fā)展，資源受限的設(shè)備已經(jīng)無處不在，對算法的執(zhí)行效率和存儲空間提出了更高的要求。

原始的AES 算法［2］使用查表法，運行前先將S盒和逆S盒存儲為兩張256字節(jié)大小的表格（數(shù)組）中，再通過編程語言實現(xiàn)加解密過程。雖然該方法占用內(nèi)存小，但實現(xiàn)過程復(fù)雜，效率低。斯托林斯［3］提出了通過犧牲內(nèi)存空間提高執(zhí)行效率的方法，將實現(xiàn)過程提前計算為8 張1024 字節(jié)的表格，然后通過查表和異或運算實現(xiàn)加解密過程，雖然提高了執(zhí)行速度，但是在資源受限的情況下，此方法并不實用。趙躍華等［4］在此基礎(chǔ)上，通過數(shù)學(xué)變換，將加解密過程中的迭代變換進(jìn)行合并，找到了通過6張256字節(jié)的表實現(xiàn)AES的方法。而謝秀穎等［5］進(jìn)一步優(yōu)化為5 張256 字節(jié)的表，并運用查表法將算法應(yīng)用到了物聯(lián)網(wǎng)智能家居中，提升了效率，并減少了對存儲空間的占用。魏國珩等［6］從硬件實現(xiàn)的角度，提出了使用電路復(fù)用技術(shù)將加解密過程進(jìn)行合并優(yōu)化的思路，并具有良好的表現(xiàn)。

不過由于AES 算法原理的公開化和普及化時間較長，也使得其安全性受到考驗。張麗紅等［7］針對加密過程中多次用到的S盒字節(jié)代換進(jìn)行優(yōu)化重構(gòu)，解決了S盒迭代輸出周期過短的問題，提高了S盒的安全性。本文將在文獻(xiàn)［7］的基礎(chǔ)上，對上述文獻(xiàn)的軟硬件實現(xiàn)方法進(jìn)行分析，并綜合考慮算法的安全性和執(zhí)行效率兩方面，對AES 進(jìn)行優(yōu)化改進(jìn)，設(shè)計輕量高效的軟件實現(xiàn)方法，并進(jìn)行實驗驗證。

2 AES算法基礎(chǔ)

美國國家標(biāo)準(zhǔn)與技術(shù)研究所（National institute of standards and technology，NIST）于1997 年發(fā)起了征集AES 的活動，經(jīng)過三年多的討論，最終在2001年確立將對稱分組密碼Rijndae 標(biāo)準(zhǔn)化為AES［8］。其數(shù)據(jù)分組長度和密鑰長度并不是唯一的，而是可以指定為128位、192位、256位，但是相對應(yīng)地需要10輪、12輪、14輪迭代加密操作。由于本文考慮的是在有資源限制的環(huán)境中運行，所以選擇的是占用資源較低的128位AES算法（簡記為AES-128）。

整個算法主要由密鑰擴展、加密和解密三部分組成［8～10］。其整體實現(xiàn)如圖1所示。

2.1 密鑰擴展算法

對于AES-128，其密鑰長度為128bit，也就是16 個字節(jié)。將密鑰K 的每個字節(jié)填入到4*4 的矩陣中，經(jīng)過10 輪的擴展，將4 列初始密鑰擴展為44列的密鑰W[i]，i ∈[0，43]。密鑰擴展算法流程［11］如圖2所示。

圖2 密鑰擴展流程圖

根據(jù)i 數(shù)值不同，采用兩種方法求解W[i]。當(dāng)i 不是4 的倍數(shù)時，W[i]可以通過它之前的一個字與前面第四個字異或運算得到；當(dāng)i 能夠被4整除，W[i]的計算就比較復(fù)雜，需要對前面一個字進(jìn)行f變換后再與前面第四個字異或運算得到。其中f變換包括以下三個步驟：

1）循環(huán)移位：對輸入的W 向右循環(huán)移動一個字節(jié)。

2）S 盒變換：用S 盒替換步驟1）中的每個字節(jié)。

3）輪常量計算：將步驟2）的結(jié)果與常量Rcon[j]進(jìn)行異或運算。 Rcon[j]代表一個字，定義Rcon[j]=(RC[j]，0，0，0)，這個字最右邊三個字節(jié)始終為0。其中RC[1]=0x01，RC[j]=2*RC[j-1]。

2.2 AES加密過程

在加密過程中，需要加密的明文多數(shù)情況都會大于16 字節(jié)，所以需要對明文以16 個字節(jié)長度劃分為若干段，以其中一段明文P 為例。假設(shè)第x輪的輸入數(shù)據(jù)為狀態(tài)矩陣Sx，密鑰矩陣為Kx，其中x ∈[0，10]。初始的狀態(tài)矩陣S0=P ，初始密鑰為K0=(W[0]，W[1]，W[2]，W[3])，它們都是4*4的矩陣。加密流程［12］如下：

1）輪密鑰加變換：S0⊕K0，⊕為異或運算。

2）S 盒變換：對Sx中的每個字節(jié)進(jìn)行替換，而不改變原有的位置。AES 定義了一個由256 個字節(jié)組成的16*16 的表格——S 盒。在執(zhí)行替換時，把該字節(jié)的高4位作為行值，低4位作為列值，找到S盒中對應(yīng)的元素并取出代替該字節(jié)。

三要加快建設(shè)水資源配置和江河湖庫水系連通工程，逐步構(gòu)建“四橫三縱、南北調(diào)配、東西互濟(jì)”的水資源宏觀配置格局，以及引排順暢、蓄泄得當(dāng)、豐枯調(diào)劑、多源互補、調(diào)控自如的江河湖庫水網(wǎng)體系，強化水資源統(tǒng)一調(diào)度、科學(xué)調(diào)度。

3）行移位變換：對Sx的每行向左循環(huán)移動不同的位移量。第一行保持不變，第二行左移1 個字節(jié)，第三行左移2個字節(jié)，第四行左移3個字節(jié)。

4）列混合變換：將矩陣B 與Sx中的每一列相乘。以Sx中的一列為例，可表示成式（1）。之后將Sx的數(shù)據(jù)與對應(yīng)的結(jié)果一一替換。

5）輪密鑰加變換：將Sx中的每個字節(jié)與密鑰擴展算法得到的Kx進(jìn)行異或運算。

總共對步驟2）～步驟5）進(jìn)行9 輪迭代循環(huán)，并在第10 輪運算時，舍棄列混合變換，最終得到的內(nèi)容就是密文C 。

2.3 AES解密過程

AES的解密過程就是對加密的逆序。假設(shè)第x輪的輸入數(shù)據(jù)為狀態(tài)矩陣，密鑰矩陣IKx，其中x ∈[0，10] 。初 始 的 數(shù) 據(jù) 為=C ，初 始 密 鑰 為IK0=K10=(W[40]，W[41]，W[42]，W[43]) ，解 密 流程［13］如下：

與加密過程不同，解密運算在第一輪時并不進(jìn)行列混合逆變換，在第2～10輪時才進(jìn)行完整的4種逆變換［14］。

3 AES算法優(yōu)化設(shè)計

3.1 AES加解密過程復(fù)合優(yōu)化

從圖1 可以發(fā)現(xiàn)AES 的加解密過程并不是一個對稱的結(jié)構(gòu)，解密中變換的順序與加密中的并不相同，所以在算法實現(xiàn)的過程中，通常都是將加密與解密模塊獨立分開。雖然這樣做結(jié)構(gòu)上比較清晰，實現(xiàn)也比較容易，但是其執(zhí)行效率不高，也不適合一些存儲資源受限的系統(tǒng)。為了能夠?qū)⒓咏饷苓^程中相似的模塊進(jìn)行復(fù)合，可以利用兩條AES的性質(zhì)進(jìn)行優(yōu)化［4］。

1）S盒變換與逆S盒變換只對輸入字節(jié)進(jìn)行非線性替換，并不更改其順序。行移位變換與逆行移位變換只影響輸入字節(jié)的順序，并不更改其數(shù)值。

2）輪密鑰加變換及其逆變換，列混合變換與它的逆變換都是線性變換。都有F(X+Y)=F(X)+F(Y)成立。

結(jié)合上述兩條性質(zhì)，可以調(diào)整加密過程中S 盒變換與行移位變換的順序，再將解密過程中的逆列混合變換與輪密鑰加逆變換調(diào)序。最終合并為一個整體，如圖3 所示。經(jīng)過調(diào)整后的AES 加解密過程完全共享一個迭代結(jié)構(gòu)。與原來的AES 算法相比，該優(yōu)化方法去除了一些加解密中重復(fù)性的實現(xiàn)過程，節(jié)省了存儲空間，也為迭代中的變換提供了優(yōu)化的基礎(chǔ)。

圖3 調(diào)序合并后的加解密流程

3.2 S盒優(yōu)化

S 盒作為AES 算法中唯一的一個非線性結(jié)構(gòu)，在很大程度上決定了整個算法的安全強度。它的構(gòu)造原理是先定義一個256 字節(jié)的表格，并按字節(jié)升序進(jìn)行逐行排列，然后把表格中的每個字節(jié)映射到它在有限域GF(28)中的逆，最后經(jīng)過仿射變換成為S盒。

傳統(tǒng)的AES 中采用的仿射變換對為（F1，63），仿射變換的周期是4，并且迭代輸出周期小于88。從數(shù)據(jù)安全性的角度考慮，S 盒的變換周期越大，數(shù)據(jù)才越安全，所以AES算法存在短周期現(xiàn)象［15～16］。針對這一現(xiàn)象，張麗紅［7］提出了尋找最佳仿射變換對的優(yōu)化思路，以嚴(yán)格雪崩準(zhǔn)則為最終標(biāo)準(zhǔn)，找到了仿射變換周期為16，迭代輸出周期為256的仿射變換對（34，BA）。本文引入這種新的S 盒構(gòu)造方法，代替了傳統(tǒng)的S 盒數(shù)據(jù)，從而提高了S 盒的性能，為其他優(yōu)化方法打好了安全的基礎(chǔ)。在軟件實現(xiàn)上，可以通過查表法來減少運算的消耗。

3.3 行移位（逆）變換的優(yōu)化

在行移位變換中，對狀態(tài)矩陣的第n 行向左循環(huán)移動n-1 個字節(jié)；在行移位逆變換中，對狀態(tài)矩陣的第n 行向右循環(huán)移動n-1 個字節(jié)。其中n ∈[1，4]。如圖4 所示，（a）表示原始的狀態(tài)矩陣，（b）表示行移位變換后的結(jié)果，（c）表示行移位逆變換的結(jié)果。

圖4 行移位變換及逆變換結(jié)果

通過觀察矩陣（b）和矩陣（c），可以發(fā)現(xiàn)第0 行與第2 行完全相同。所以這部分運算可以重合，流程如圖5 所示，ML（n，n-1）表示第n 行左移n-1 個字節(jié)，MR（n，n-1）表示第n 行右移n-1個字節(jié)。

圖5 行移位（逆）變換優(yōu)化圖

3.4 列混合（逆）變換的優(yōu)化

結(jié)合等式（1）和（2），可以發(fā)現(xiàn)列混合變換比其逆變換所使用的矩陣簡單的多。在軟件實現(xiàn)上，列混合變換需要執(zhí)行4次XOR運算和2次xtimes乘法運算；其逆變換則需要執(zhí)行9 次XOR 運算和12 次xtimes乘法運算［6］。因為這兩者的運算復(fù)雜程度的不同，導(dǎo)致加密與解密在時間消耗上存在一定的差距。所以在一些實時性要求高的情況下，這通常是不可接受的。針對這一問題，文獻(xiàn)［4］提出將逆列混合變換的復(fù)雜矩陣分解成兩個簡單的矩陣，以此來提高運算的速度。但是這種方法實現(xiàn)比較復(fù)雜，效率提高不怎么明顯。文獻(xiàn)［5］應(yīng)用了一種運算更為簡單的矩陣A，并滿足式（3）：

其特點是該矩陣在有限域GF(28)上的逆矩陣也是它本身。用此矩陣代替原算法中列混合變換及其逆變換的矩陣，可以使得它們消耗相同的計算資源并解決加解密過程中的時間不對稱問題。另外，在軟件實現(xiàn)上，相同的變換矩陣可以進(jìn)一步合并這兩種變換，可以有效地減少重復(fù)運算，降低存儲資源的消耗，提升執(zhí)行效率。

4 實驗測試與分析

本文通過第3 節(jié)的四個優(yōu)化措施，對原AES 算法進(jìn)行了優(yōu)化，為了驗證改進(jìn)后的算法效果，除了對執(zhí)行效率進(jìn)行測試之外，還對其安全性進(jìn)行了實驗分析。本次實驗的硬件環(huán)境是STM32F103c8t6，工作主頻是72MHz，有64KB Flash 和20KB SRAM，開發(fā)工具為Keil 5，算法的軟件實現(xiàn)是通過C 語言編程。

4.1 安全性測試

檢驗密碼算法是否滿足雪崩效應(yīng)是基本的安全性要求［7］。理想狀態(tài)下，當(dāng)任意改變輸入的1 位時，平均有一半的輸出位會發(fā)生改變。在分組密碼算法中，雪崩效應(yīng)的實現(xiàn)主要依靠擴散和混淆兩部分，它們是影響密碼安全的兩個主要因素。擴散的目的是為了讓密文中的多個信息受到明文中單個信息的影響，從而使得明文的統(tǒng)計特征在密文中消失。而混淆則是為了讓密文與密鑰之間的關(guān)系變得復(fù)雜化，使得破譯方即時竊取了密文也無法推出密鑰。下面通過實驗來對比驗證兩種算法在雪崩效應(yīng)方面的表現(xiàn)。

首先測試算法擴散性。為方便統(tǒng)計，任意選取一段16 字節(jié)長度的明文，使用原AES 算法和改進(jìn)的算法進(jìn)行加密。測試過程中，保證密鑰不變，隨機改變明文中的一位，記錄密文變化的位數(shù)。實驗結(jié)果如圖6 所示，雖然原算法的平均密文變化位數(shù)是64，但是并不穩(wěn)定，與優(yōu)化后的算法相比，原算法波動范圍比較大。

圖6 擴散性測試結(jié)果

然后測試算法混淆性。同樣任意選取一段16字節(jié)長度的明文，并保證其在測試過程中不變。記錄密鑰變化1位對密文的影響。實驗結(jié)果如圖7所示，原算法的密文改變位數(shù)的范圍是61±9，改進(jìn)后的密文改變位數(shù)的波動范圍是62±5，波動范圍顯著縮小。

圖7 混淆性測試結(jié)果

通過以上測試，可以發(fā)現(xiàn)改進(jìn)后的算法在擴散和混淆方面有良好的表現(xiàn)，能夠滿足雪崩效應(yīng)的基本要求，而且在安全性上有一定程度的提高。

4.2 執(zhí)行效率測試

測試時，由于加密一個16 字節(jié)的字符串時間相當(dāng)短，為了使實驗效果更加明顯，對5 組長度為100 字節(jié)的數(shù)據(jù)加解密各100 次，并記錄其平均消耗的時間。實驗結(jié)果如表3 所示。對表中的測試數(shù)據(jù)進(jìn)行分析，改進(jìn)的算法對加解密過程中的相似部分進(jìn)行合并，使得改進(jìn)后的算法在存儲空間上比原AES算法節(jié)省了25%，列混合與逆列混合變換中采用簡易矩陣，也使得加解密的耗時誤差變小，決了原AES 算法中解密與加密的時間延遲問題。另外，在執(zhí)行效率方面，改進(jìn)后的加密速度比原算法提高了19%，解密速度比原算法提高了22%。這說明改進(jìn)的算法較原算法有一定的優(yōu)勢。

表3 加解密耗時

5 結(jié)語

針對AES算法的不足之處，本文從安全性和執(zhí)行效率兩個角度對AES 算法進(jìn)行了改進(jìn)。采用新的高安全性S 盒可以增加被破譯的難度；而對行移位變換和列混合變換的優(yōu)化，也為加解密過程的整合降低了難度，提高了算法的執(zhí)行速度。最終的實驗結(jié)果也證實了改進(jìn)算法在STM32 上運行具有一定的優(yōu)勢。下一階段將在密鑰管理方面做深入研究。