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

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

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

1 引言

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

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

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

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

2 AES算法基礎(chǔ)

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

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

2.1 密鑰擴(kuò)展算法

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

圖2 密鑰擴(kuò)展流程圖

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

1）循環(huán)移位：對(duì)輸入的W 向右循環(huán)移動(dòng)一個(gè)字節(jié)。

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

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

2.2 AES加密過(guò)程

在加密過(guò)程中，需要加密的明文多數(shù)情況都會(huì)大于16 字節(jié)，所以需要對(duì)明文以16 個(gè)字節(jié)長(zhǎng)度劃分為若干段，以其中一段明文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，⊕為異或運(yùn)算。

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

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

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

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

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

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

2.3 AES解密過(guò)程

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

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

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

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

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

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

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

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

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

3.2 S盒優(yōu)化

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)測(cè)試與分析

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

4.1 安全性測(cè)試

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

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

圖6 擴(kuò)散性測(cè)試結(jié)果

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

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

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

4.2 執(zhí)行效率測(cè)試

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

表3 加解密耗時(shí)

5 結(jié)語(yǔ)

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