一種優(yōu)化的AES算法及其FPGA實現(xiàn)*

張 偉 高俊雄 王耘波 武文斌

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

一種優(yōu)化的AES算法及其FPGA實現(xiàn)*

張 偉 高俊雄 王耘波 武文斌

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

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

AES算法; 全流水線; FPGA

Class Number TP309.7

1 引言

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

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

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

2 AES算法及優(yōu)化

2.1 算法簡介

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

2.2 算法優(yōu)化

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

圖1 AES加解密流程

圖2 AES加解密輪變換結(jié)構(gòu)圖

文獻[5]提出將列混合中固定多項式c(x)變?yōu)檎痪仃囀沟媚媪谢旌献儞Q與列混合變換相同,即d(x)=c-1(x)。這種優(yōu)化方案可以減小資源消耗,并且路徑延時也會降低。令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},選擇較小的系數(shù)有利于減小硬件資源消耗。

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

圖3 優(yōu)化算法加解密流程

2.3 優(yōu)化算法安全性分析與測試

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

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

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

3 優(yōu)化算法FPGA實現(xiàn)

本文設(shè)計電路整體結(jié)構(gòu)如圖4所示。

圖4 AES加密解密電路結(jié)構(gòu)圖

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

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

表1 接口聲明

3.1 S-box/逆S-box

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

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

圖5 奇數(shù)輪S-box電路結(jié)構(gòu)

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

3.2 列混合電路

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

(1)

式(2)為{02}x計算結(jié)果,資源消耗和路徑延時分別為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 輪單元流水線劃分

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

圖6 奇數(shù)輪流水線

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

圖7 GF(24)乘法器

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

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

4 仿真與綜合

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

5ca71be2b73aef0857d77811f352c073b6108d72d981

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

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

445566778899aabbccddeef0等,經(jīng)驗證加解密功能完全正確。

圖8 加密功能仿真

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

5 結(jié)語

AES算法以其安全、高效得到了廣泛的應(yīng)用。本文針對AES算法加解密流程不一致提出了一種優(yōu)化方案以減小資源消耗。在FPGA實現(xiàn)中,采用基于正規(guī)基的復(fù)合域算法實現(xiàn)S-box和逆S-box有效縮減了資源消耗。通過分析電路各模塊路徑延時進行了輪單元的6級流水線劃分,實現(xiàn)了工作頻率和吞吐量的提升。最終實現(xiàn)結(jié)果表明本設(shè)計達到了資源與速度的有效折中,實現(xiàn)了高性能的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及其差分和統(tǒng)計特性[J].電子學(xué)報,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協(xié)議中的應(yīng)用[J].延邊大學(xué)學(xué)報:自然科學(xué)版,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] 馮登國.分組密碼的設(shè)計與分析[M].北京:清華大學(xué)出版社,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-盒電路優(yōu)化設(shè)計[J].電子學(xué)報,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日

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

TP309.7

10.3969/j.issn.1672-9722.2017.03.020