一種優化的AES算法及其FPGA實現*

張 偉 高俊雄 王耘波 武文斌

(華中科技大學光學與電子信息學院 武漢 430074)

一種優化的AES算法及其FPGA實現*

張 偉 高俊雄 王耘波 武文斌

(華中科技大學光學與電子信息學院 武漢 430074)

針對AES算法加密解密結構的不一致提出了一種優化算法,得到了統一的加密解密流程,有效節省了資源消耗。為取得速度和資源的折中,AES加密解密主體采用內外混合流水線結構,其中S-box和逆S-box采用基于正規基的有限域算法實現。基于對各電路模塊路徑延時的分析,對AES輪變換進行了6級流水線劃分。在Xilinx公司XC7VX485T FPGA上綜合結果顯示:電路資源消耗為19006LUTs,最高工作頻率為724.323MHz,數據吞吐量為92.713Gbps,獲得了非常好的加速效果且有效降低了資源消耗。

AES算法; 全流水線; FPGA

Class Number TP309.7

1 引言

計算機、網絡與通信技術的飛速發展,各類敏感數據通過開放網絡進行傳輸帶來了嚴峻的信息安全問題,一個有效的解決辦法就是使用分組密碼算法。其中,高級加密標準(Advanced Encryption Standard,AES)算法[1]以其安全、簡潔和高效等優點廣泛應用在智能卡、移動電話和電子金融等各種應用中。

AES硬件實現相比軟件實現提供了更好的物理安全性及更快的處理速度,FPGA以其可編程性成為了AES算法的理想實現平臺。隨著業界不斷提高的計算性能需求,提升AES電路吞吐量相比于減小資源消耗、降低功耗等目標得到了更大的關注。Zhang[2]、Hodjat[3]、Zambreno[4]等采用全流水線結構大大提高了AES電路的吞吐量。

本文在分析AES算法結構的基礎上提出了一種加密解密流程一致的優化AES算法,有效減小了資源消耗。安全性分析及密碼學測試表明該優化方案不會減弱密碼安全強度。采用全流水線結構在FPGA平臺上實現優化算法,達到了速度與資源的平衡。

2 AES算法及優化

2.1 算法簡介

AES是一種迭代分組密碼算法,加解密主體采用代替/置換網絡(Substitution/Permutation Net,SPN)結構,算法流程如圖1所示。AES加密算法中分組長度固定為128bits,密鑰長度可選擇為128bits、196bits或256bits,對應的輪變換次數Nr分別為10、12和14,本文密鑰長度選擇為256bits。AES加密算法輪函數由四層變換組成:字節替換是對狀態矩陣中每一字節的非線性替換;行移位變換將狀態矩陣中每一行分別循環左移0、1、2和3個字節;列混合變換將狀態矩陣每一列看作系數取自GF(28)次數小于4的多項式,將其與一個固定多項式c(x)={03}x3+{01}x2+{01}x+{02}相乘后模x4+1;輪密鑰加變換將輪密鑰異或到狀態矩陣中每個字節。AES解密算法通過逆序使用加密算法中各變換的逆變換,將密文轉換為明文,其中輪密鑰加變換中各輪密鑰的使用順序與加密流程相反。對于AES算法中各變換詳細操作可參考文獻[1],不再贅述。

2.2 算法優化

AES算法中加密解密流程是不同的,在同時實現加密和解密功能的電路中解密流程一般采用等效解密算法結構,通過共用部分資源以減小電路面積。AES電路輪變換結構如圖2所示。上面的數據通路實現加密功能;下面的數據通路實現解密功能。然而,每一時刻電路只能實現加密或解密一種功能,部分功能模塊將不會起作用,造成了資源的浪費。雖然可以采用在字節替換與逆字節替換中共用乘法逆變換,將逆列混合變換矩陣分解為列混合矩陣與常數矩陣的乘積等方式實現部分電路的共用,電路中還是有部分資源浪費。

圖1 AES加解密流程

圖2 AES加解密輪變換結構圖

文獻[5]提出將列混合中固定多項式c(x)變為正交矩陣使得逆列混合變換與列混合變換相同,即d(x)=c-1(x)。這種優化方案可以減小資源消耗,并且路徑延時也會降低。令c(x)=c3x3+c2x2+c1x+c0,由c(x)·c(x)=E(E為單位矩陣)可得到c1=c3且c0+c2={01}。本文改進方案中選擇c(x)={01}x3+{02}x2+{01}x+{03},選擇較小的系數有利于減小硬件資源消耗。

將14次輪變換分為奇數輪和偶數輪交替進行,在奇數輪和偶數輪中分別使用原AES算法中加密輪變換和等效解密輪變換,即奇數輪由字節替換、行移位、列混合和輪密鑰加組成,偶數輪由逆字節替換、逆行移位、列混合(本文改進方案中列混合變換的逆變換為列混合本身)和輪密鑰加,優化后AES加密解密流程如圖3所示。由于奇數輪變換和偶數輪變換互逆,改進算法解密流程與加密流程完全相同。與原AES算法一樣,解密算法需要將中間13個輪密鑰進行一次列混合變換以得到等效的解密子密鑰。

圖3 優化算法加解密流程

2.3 優化算法安全性分析與測試

AES算法中S-box的密碼性質決定了算法的安全性。文獻[6]分析了S-box和逆S-box的密碼學性質,可以看出S-box和逆S-box差分均勻度、非線性度等完全一致,差別在于S-box比逆S-box嚴格雪崩準則距離小但代數式項數也較小,所以S-box擴散性能比逆S-box要好但代數結構復雜度要低。本文交替使用S-box和逆S-box可以充分利用兩種置換表的優點。

行移位和逆行移位都是將狀態矩陣每一列中4個字節移動到不同列中,只是字節移位的方向不同,兩種變換的擴散性能完全一樣。文獻[7]證明了當c(x)是GF(28)中不可約多項式時,改變c(x)不會降低算法抵抗截斷差分分析和差分分析的能力;文獻[8]證明了本文選擇的c(x)與原AES算法中列混合系數都具有最大分支數5,故本文優化方案不會影響列混合變換的擴散效率。

分組密碼算法本身應是一個好的偽隨機數發生器。目前分組密碼的統計測試通常關注密文隨機性、明密文獨立性和明文擴散性等,具體測試方法可參考文獻[9]。對原AES算法及改進AES算法進行統計性測試,分組長度和密鑰長度分別為128bits和256bits,顯著性水平為0.05,測試次數為120次,統計結果表明原AES算法和優化AES算法都能夠很好地隱蔽輸入明文的數據特征,使密文表現出良好的隨機性,優化算法安全性并未減弱。

3 優化算法FPGA實現

本文設計電路整體結構如圖4所示。

圖4 AES加密解密電路結構圖

KeyExpansion模塊將輸入的256bits初始密鑰擴展生成各輪變換所需輪密鑰。KeyBuffer為15個128bits寄存器組,用于存儲輪密鑰。Encryption/Decryption是加密/解密主體部分,包含上文所述的各變換。字節替換/逆字節替換、列混合電路是高性能AES硬件電路實現的關鍵,將在下文進行詳細介紹。

表1為圖4中各信號定義及功能說明。

表1 接口聲明

3.1 S-box/逆S-box

基于查找表的S-box/逆S-box方案可以避開繁雜的數學公式推導和內部邏輯優化,然而此方案缺點也很明顯:加密和解密需要兩個不同查找表使得電路資源消耗較大;固定的電路路徑延時限制了頻率提高,因此在高速應用中較少采用基于查找表結構的S-box。

文獻[10]最先提出基于復合域分解的可復用S-box方案使得電路易于進行流水線處理提高吞吐量。文獻[2]采用基于多項式基的復合域GF((24)2)運算實現了最快速的S-box。文獻[11]采用基于正規基的復合域算法得到了最緊湊的S-box電路。本文采用文獻[11]中S-box實現方案以減小資源消耗,圖5所示為奇數輪中S-box結構圖,S-box與逆S-box各部分電路資源消耗和路徑延時如表2所示。

圖5 奇數輪S-box電路結構

表2 S-box與逆S-box資源消耗和路徑

3.2 列混合電路

優化算法選擇c(x)={01}x3+{02}x2+{01}x+{03}作為固定多項式來統一實現列混合和逆列混合,相應矩陣形式為

(1)

式(2)為{02}x計算結果,資源消耗和路徑延時分別為3XOR和1XOR,帶入式(1)可得列混合電路資源消耗和路徑延時分別為86XOR和3XOR,其中s0,c+s2,c、s1,c+s3,c、{02}(s0,c+s2,c)和{02}(s1,c+s3,c)為公共項。{02}x={02}·{x7,x6,x5,x4,x3,x2,x1,x0}

={x6,x5,x4,x3⊕x7,x2⊕x7,x1,x0⊕x7,x7}

(2)

3.3 輪單元流水線劃分

根據上述對S-box、逆S-box、列混合電路的設計,考慮到各模塊的路徑延時,對AES算法中輪變換進行6級流水線劃分,圖6為奇數輪變換示意圖。

圖6 奇數輪流水線

由各模塊路徑延時可得出流水線關鍵路徑出現在第2級和第4級,路徑延時為5XOR+1AND,最小路徑延時為第5級的3XOR,顯然路徑延時不夠均勻。

圖7 GF(24)乘法器

圖7為GF(24)中乘法器電路,根據路徑延時將乘法器分為了三部分:第1部分計算乘數和被乘數各自高低2位的異或,路徑延時為1XOR;第2部分路徑延時為GF(22)中乘法器延時(2XOR+1AND)加上N×c模塊路徑延時(1XOR)的和,即3XOR+1AND;第3部分為N×c模塊輸出與第2部分中上下2個乘法器輸出的異或,路徑延時為1XOR。為平衡流水線各級路徑延時,實現第2級中乘法器時將乘法器中第1部分移動到流水線第1級,實現第4級中2個乘法器時將乘法器第3部分移動到流水線第5級。通過對GF(24)中乘法器的分解,可將流水線關鍵路徑減小為4XOR+1AND,提高了系統時鐘頻率。本設計中最終流水線結構各分段延時如表3所示。

表3 AES-256輪單元流水線各級路徑時延

4 仿真與綜合

加密算法仿真結果如圖8所示,輸入初始明文為128′h00112233445566778899aabbccddeef0,此后每一時鐘周期明文加1;密鑰為256′h603deb101

5ca71be2b73aef0857d77811f352c073b6108d72d981

0a30914dff4,輸出初始密文為128′h82ac6b0710da9

87ad96d8867c2141f56。采用同樣的密鑰,將加密輸出密文進行解密可得輸出明文為128′h00112233

445566778899aabbccddeef0等,經驗證加解密功能完全正確。

圖8 加密功能仿真

選擇Xilinx公司的XC7VX485T,使用ISE綜合顯示資源消耗為19006LUTs,最高工作頻率為724.323MHz,計算得到數據吞吐量為92.713Gbps,獲得了非常好的加速效果且有效降低了資源消耗。

5 結語

AES算法以其安全、高效得到了廣泛的應用。本文針對AES算法加解密流程不一致提出了一種優化方案以減小資源消耗。在FPGA實現中,采用基于正規基的復合域算法實現S-box和逆S-box有效縮減了資源消耗。通過分析電路各模塊路徑延時進行了輪單元的6級流水線劃分,實現了工作頻率和吞吐量的提升。最終實現結果表明本設計達到了資源與速度的有效折中,實現了高性能的AES加解密電路。

[1] Dobbertin H, Knudsen L, Robshaw M, et al. Advanced Encryption Standard — AES[J]. Lecture Notes in Computer Science,2005,3373(8):2200-2203.

[2] Zhang X, Parhi K K. High-speed VLSI architectures for the AES algorithm[J]. IEEE Transactions on Very Large Scale Integration Systems,2004,12(9):957-967.

[3] Hodjat, A, Verbauwhede, I. A 21.54 Gbits/s fully pipelined AES processor on FPGA[M]. IEEE,2004:308-309.

[4] Zambreno J, Nguyen D, Choudhary A. Exploring Area/Delay Tradeoffs in an AES FPGA Implementation[M]. Heidelberg: Springer Berlin Heidelberg,2004:575-585.

[5] Jing M H, Chen J H, Chen Z H. Diversified Mixcolumn transformation of AES[C]//International Conference on Information, Communications & Signal Processing,2008:1-3.

[6] 張麗紅,凌朝東.基于AES算法中S盒的分析研究與改進[J].信號處理,2011,27(9):1428-1433. ZHANG Lihong, LING Chaodong. The analysis and improvement of S box based on AES[J]. Signal Processing,2011,27(9):1428-1433.

[7] 馮國柱,李超,多磊,等.變型的Rijndael及其差分和統計特性[J].電子學報,2002,30(10):1544-1546. FENG Guozhu, LI Chao, DUO Lei, et al. Transmutative Rijndael with the Differential and Statistical Charactartics[J]. Acta Electronica Sinica,2002,30(10):1544-1546.

[8] 李京,李永珍.AES改進算法在CCMP協議中的應用[J].延邊大學學報:自然科學版,2015(3):244-248. LI Jing, LI Yongzhen. Improvement of the AES encryption algorithm and its application in CCMP protocol[J]. Journal of Yanbian University(Nature Science Edition),2015(3):244-248.

[9] 馮登國.分組密碼的設計與分析[M].北京:清華大學出版社,2000:407-415. FENG Dengguo. Design and analysis of block cipher[M]. Beijing: Tsinghua university press,2000:407-415.[10] Wolkerstorfer J, Oswald E, Lamberger M. An ASIC Implementation of the AES SBoxes[C]//Topics in Cryptology-CT-RSA 2002, The Cryptographer’s Track at the RSA Conference, 2002, San Jose, CA, USA, February 18-22, 2002, Proceedings,2002:67-78.

[11] 曾純,吳寧,張肖強,等.基于多因子CSE算法的AES S-盒電路優化設計[J].電子學報,2014(6):1238-1243. ZENG Chun, WU Ning, ZHANG Xiaoqiang, et al. The Optimization Circuit Design of AES S-Box Basedon a Multiple-Term Common Subexpression Elimination Algorithm[J]. Acta Electronica Sinica,2014(6):1238-1243.

An Optimized AES Algorithm and Its FPGA Implementation

ZHANG Wei GAO Junxiong WANG Yunbo WU Wenbin

(School of Optical and Electronic Information, Huazhong University of Science and Technology, Wuhan 430074)

For the encryption and decryption structure of AES is not consistent,an optimized AES algorithm with a unified encryption and decryption process is proposed in this paper. Using the fully pipelined architecture, the proposed circuit achieves an effective tradeoff between speed and resources, among which the S-box and inverse S-box are implemented applying the finite field algorithm based on regular basis. With the analysis of the path delay of each module, the AES round transformation is divided into 6 stages. Results implemented in the Xilinx’s XC7VX485T FPGA show that the hardware resource consumption is 19006LUTs,the maximum frequency is 724.323MHz and the throughput can get to 92.713Gbps, thus obtaining a very good acceleration effect.

AES, full pipelining, FPGA

2016年9月7日,

2016年10月20日

張偉,男,碩士研究生,研究方向:加密算法。高俊雄,男,博士,講師,研究方向:虹膜識別。王耘波,男,博士,副教授,碩士生導師,研究方向:人工智能與系統集成。武文斌,男,碩士研究生,研究方向:人臉識別。

TP309.7

10.3969/j.issn.1672-9722.2017.03.020