基于STM32 的AES 算法優(yōu)化設計

趙亞亞 孫順遠，2

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

1 引言

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

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

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

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

2 AES算法基礎

美國國家標準與技術研究所（National institute of standards and technology，NIST）于1997 年發(fā)起了征集AES 的活動，經過三年多的討論，最終在2001年確立將對稱分組密碼Rijndae 標準化為AES［8］。其數據分組長度和密鑰長度并不是唯一的，而是可以指定為128位、192位、256位，但是相對應地需要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 的矩陣中，經過10 輪的擴展，將4 列初始密鑰擴展為44列的密鑰W[i]，i ∈[0，43]。密鑰擴展算法流程［11］如圖2所示。

圖2 密鑰擴展流程圖

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

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

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

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

2.2 AES加密過程

在加密過程中，需要加密的明文多數情況都會大于16 字節(jié)，所以需要對明文以16 個字節(jié)長度劃分為若干段，以其中一段明文P 為例。假設第x輪的輸入數據為狀態(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é)進行替換，而不改變原有的位置。AES 定義了一個由256 個字節(jié)組成的16*16 的表格——S 盒。在執(zhí)行替換時，把該字節(jié)的高4位作為行值，低4位作為列值，找到S盒中對應的元素并取出代替該字節(jié)。

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

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

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

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

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

2.3 AES解密過程

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

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

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

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

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

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

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

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

圖3 調序合并后的加解密流程

3.2 S盒優(yōu)化

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

傳統(tǒng)的AES 中采用的仿射變換對為（F1，63），仿射變換的周期是4，并且迭代輸出周期小于88。從數據安全性的角度考慮，S 盒的變換周期越大，數據才越安全，所以AES算法存在短周期現(xiàn)象［15～16］。針對這一現(xiàn)象，張麗紅［7］提出了尋找最佳仿射變換對的優(yōu)化思路，以嚴格雪崩準則為最終標準，找到了仿射變換周期為16，迭代輸出周期為256的仿射變換對（34，BA）。本文引入這種新的S 盒構造方法，代替了傳統(tǒng)的S 盒數據，從而提高了S 盒的性能，為其他優(yōu)化方法打好了安全的基礎。在軟件實現(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）表示行移位變換后的結果，（c）表示行移位逆變換的結果。

圖4 行移位變換及逆變換結果

通過觀察矩陣（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)化

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

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

4 實驗測試與分析

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

4.1 安全性測試

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

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

圖6 擴散性測試結果

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

圖7 混淆性測試結果

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

4.2 執(zhí)行效率測試

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

表3 加解密耗時

5 結語

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