AES快速算法的擴展指令集實現(xiàn)*

封斌 齊德昱

(華南理工大學(xué)計算機系統(tǒng)研究所，廣東廣州510640)

隨著硅片制造工藝技術(shù)的發(fā)展，微處理器芯片上的晶體管數(shù)目已達到十億數(shù)量級，并且片上晶體管的密度仍然按照摩爾定律持續(xù)增加.結(jié)構(gòu)設(shè)計者在面對高性能需求壓力時，可充分利用硬件和器件技術(shù)的發(fā)展，通過芯片上豐富的邏輯資源實現(xiàn)附加的應(yīng)用專用硬件，使系統(tǒng)整體達到較高的性價比，以滿足具體應(yīng)用對性能和能耗的需求.目前，芯片級硬件加速常用的方法有協(xié)處理器和指令集擴展，如浮點協(xié)處理器、先進精簡指令集處理器(ARM)中的CP15協(xié)處理器、密碼協(xié)處理器［1］、多媒體擴展指令集MMX等.

高級加密標(biāo)準(zhǔn)(AES)已在網(wǎng)絡(luò)通信安全等領(lǐng)域得到廣泛的應(yīng)用［2－4］.Soliman 和徐志軍等［5－6］給出了AES協(xié)處理器的實現(xiàn)方案，可在不修改微處理器內(nèi)部結(jié)構(gòu)的條件下獲得較高的加速比.但在資源受限的嵌入式系統(tǒng)環(huán)境下，如無線傳感器網(wǎng)絡(luò)、智能卡、射頻標(biāo)簽等，用協(xié)處理器實現(xiàn)加密算法的硬件加速缺乏靈活性，并需要更大的芯片面積，產(chǎn)生較大的系統(tǒng)功耗，此時，用擴展指令集的方法，可在不明顯增加系統(tǒng)成本和功耗情況下，顯著提高系統(tǒng)處理速度.Arif和 Heinrich 等［7－8］在 NiosII處理器上將 AES算法作為一個整體用硬件邏輯實現(xiàn)，并給出了對應(yīng)的擴展指令，但都是將整個加密流程作為一個整體用擴展指令實現(xiàn)，此種方式實際上與協(xié)處理器法消耗的面積相同但效率更低，未體現(xiàn)出擴展指令面向細粒度任務(wù)進行硬件加速的特性.Stefan等［9］在leon2處理器上針對AES算法的S盒設(shè)計了專用的擴展指令，對加密過程的加速比為1.43，效率并不明顯.Elbirt［10］在SPARC V8結(jié)構(gòu)兼容處理器上針對AES算法中輪變換的4個輪函數(shù)設(shè)計了專用指令;夏輝等［11］對 AES算法的程序代碼進行匯編編譯后，對耗時較多的5個常用模塊設(shè)計了專用指令，并與ARM9TDMI處理器上的實現(xiàn)方案進行了比較;Bertoni等［12］在ARM處理器仿真環(huán)境下實現(xiàn)了AES算法的指令集擴展;但上述3種方案都沒有考慮在32位處理器上實現(xiàn)AES算法時，可通過優(yōu)化AES算法的結(jié)構(gòu)降低運算復(fù)雜度、提高運行效率.

Daemen等［13］以32位數(shù)據(jù)運算為基礎(chǔ)，提出了AES快速實現(xiàn)軟件算法，即將AES算法中計算密集的輪變換中的4個輪函數(shù)合并為對一組前向查找表的查找操作，大幅降低了算法本身的運算復(fù)雜度.本研究基于該快速算法，實現(xiàn)了兩種擴展指令集的AES算法硬件加速方案:(1)基于片內(nèi)存儲器存儲快速算法查找表的方法;(2)用硬件邏輯電路實現(xiàn)S盒并計算出快速算法查找表對應(yīng)元素的方法.文中在可配置處理器NiosII系統(tǒng)硬件環(huán)境下，實現(xiàn)了上述兩種方案的擴展指令集硬件加速機制;其中，AES算法中的控制部分由運行在NiosII微處理器核上的應(yīng)用軟件完成，使用VHDL語言將計算密集的輪操作部分用硬件邏輯電路實現(xiàn)，并在基于EPS2C35芯片的硬件環(huán)境下進行了驗證.

1 AES算法及其結(jié)構(gòu)優(yōu)化分析

AES算法建立在有限域GF(28)之上，屬于對稱密鑰算法中的分組迭代密碼算法，采用替代/置換(SP)網(wǎng)絡(luò)結(jié)構(gòu).其中，非線性層為字節(jié)替換函數(shù)，其包含一個作用在狀態(tài)字節(jié)上的S盒，用以完成多輪迭代后輸出的高度混淆，S盒中元素的對應(yīng)關(guān)系為對輸入字節(jié)在有限域GF(28)上求逆，再加一個仿射變換，在軟件算法中一般采用查表法實現(xiàn);線性層由行位移函數(shù)和列混合函數(shù)組成，用以確保多輪迭代后的高度擴散，行位移函數(shù)按照預(yù)先定義好的偏移量對輸入的狀態(tài)矩陣進行循環(huán)移位，列混合函數(shù)是有限域GF(28)上的線性變換;輪密鑰疊加函數(shù)實現(xiàn)了密鑰與明文的結(jié)合，該函數(shù)將輪密鑰和待加密數(shù)據(jù)行按位異或，起到子密鑰的控制作用;輪密鑰擴展模塊通過對輸入的密鑰進行迭代，產(chǎn)生各輪所需的子密鑰，密鑰擴展中也用到了字節(jié)替換步驟.

AES算法中最復(fù)雜的步驟是列混合，該步驟執(zhí)行了一個有限域GF(28)上的多項式乘法.其他所有的步驟都是替代、旋轉(zhuǎn)、移位操作.以加密過程為例，AES快速軟件算法在一次輪變換中，將輸入矩陣中一列數(shù)值的4個輪函數(shù)操作步驟，合并成對1個前向查找表(FT)的4次查表操作和4個異或操作，每張FT由256個32位的表項組成，輸入矩陣的4列數(shù)據(jù)需要4張FT.設(shè)加密過程中輪操作的128 b輸入為以字節(jié)為單位排列成4×4的矩陣a，ai，j表示a中第i行第j列的元素，aj表示 a中第 j列，S(ai，j)為字節(jié)ai，j在S盒中得到的替換字節(jié).FT0(aj)是a中第j列aj在前向查找表FT0中得到的替換值，則有

令e為128b的輸出矩陣，ej為矩陣e的第j列，kj為本輪擴展密鑰的第j列，則有

由于4張FT相互之間是旋轉(zhuǎn)的關(guān)系，因此，可以將其他3張FT通過表FT0加上shift的邏輯電路來替代.則在每次輪操作的循環(huán)迭代中，只需要通過4次查表、4次異或、3次循環(huán)移位，就能得到輸入矩陣a中1列元素的運算結(jié)果ej，即

在末輪操作中沒有列混合函數(shù)，只需要查詢S盒即可.而S盒可以通過FT的掩模得到，因此，優(yōu)化后的AES算法只需要1張FT0，占用8kb的空間.

2 AES算法擴展指令集實現(xiàn)方案

首先，將AES快速軟件算法的前向查找表存放在現(xiàn)場可編程門陣列(FPGA)片上內(nèi)存實現(xiàn)的單口rom中，用12條擴展指令分別實現(xiàn)密鑰擴展、輪變換和末輪變換的操作，F(xiàn)T需要占用1kB的片上存儲空間，這對面積、成本比較敏感的嵌入式系統(tǒng)而言，仍存在進一步優(yōu)化的空間.為了減少芯片面積消耗，文中對上述方案進行了改進，用硬件邏輯計算出輸入元素在有限域GF(28)上的逆，即得到S盒中對應(yīng)的替換值，然后推導(dǎo)出FT和S盒的邏輯關(guān)系，從而計算出輸入元素對應(yīng)的FT的表項值，省去了查表法所需要的存儲空間，同時也消除了在內(nèi)存中查找S盒的數(shù)據(jù)時可能發(fā)生的基于cache的側(cè)信道攻擊，并最大限度地降低了訪問內(nèi)存的指令所產(chǎn)生的能耗.

2.1 基于查表法的擴展指令集方案

由于應(yīng)用程序在處理器上對擴展指令是串行調(diào)用的，因此，密鑰擴展中的輪函數(shù)、數(shù)據(jù)加密流程中的輪函數(shù)及末輪操作可以共享一個FT和S盒.為了減少內(nèi)存消耗，本方案在硬件邏輯中通過掩碼，將輸入字節(jié)對應(yīng)的S盒值直接從FT中提取，從而可用一個FT來滿足加密環(huán)節(jié)中所有的查表操作.解密流程用到的表可以通過同樣的途徑實現(xiàn).

擴展指令的頂層設(shè)計圖如圖1所示，ft_rom是用altsyncram實現(xiàn)的單口rom，大小為256×32 b，用以存放FT的內(nèi)容.在加密過程輪操作中，所有的查找表操作都是在一條用戶指令中完成的，因此，查找表必須放到擴展指令的硬件邏輯中.末輪操作與前9輪操作類似，但其所需的S盒值通過硬件電路從ft_rom中掩模得到，并進行了額外的24個shift操作，因此需要定義針對末輪操作的擴展指令.同時，密鑰擴展的操作與加密過程類似，但具體操作不同，也需要創(chuàng)建用于密鑰擴展的擴展指令.精簡指令集計算機(RISC)架構(gòu)的NiosII處理器的擴展指令只有2個32b的輸入和1個32b的輸出，而AES算法中，每一個32b的輸出都和128b的明文及128 b的密鑰相關(guān)，要得到每個32b的輸出，就需要4條擴展指令分別對128b明文及128b密鑰的4個32b進行操作.其中，加密過程中輪變換需要4條擴展指令完成查表與對應(yīng)的邏輯操作，數(shù)據(jù)加密的末輪操作和密鑰擴展模塊中的查表操作也各需要4條擴展指令.因此，實現(xiàn)加密過程共需要12條擴展指令.由于不同的操作使用了同一個FT，這些指令需要被集成到1個擴展的用戶指令硬件邏輯中，由輸入信號n來區(qū)別具體的指令.

圖1 擴展指令的頂層設(shè)計圖Fig.1 Design of top level of extension instruction

頂層設(shè)計的硬件邏輯中，將一個查FT操作、一個shift操作和一個XOR操作結(jié)合在一起，即從擴展指令硬件邏輯的dataa端口輸入一個32 b的數(shù)據(jù)，硬件邏輯先進行shift操作，然后執(zhí)行查找表操作，查找表返回的結(jié)果與擴展指令datab端口輸入的32b數(shù)據(jù)進行XOR操作，最后通過擴展指令硬件邏輯的result端口輸出.

圖1中的硬件邏輯塊RoundFunc是一個有2個狀態(tài)的有限狀態(tài)機.在第1個狀態(tài)中，讀取32b的dataa，并通過輸入信號 n(1..0)決定 dataa的哪8個b通過addr信號輸入，即n(1..0)選擇了第一個shift操作，也決定了在查找表輸出上執(zhí)行哪一個rotation操作.在第2個狀態(tài)中，從rom中讀取查找表對應(yīng)的值，n(3..2)決定了是哪一類查表操作，并將查找表的結(jié)果與datab進行XOR操作，并輸出到result端口.

2.2 用硬件邏輯實現(xiàn)有限域分解

AES算法的S盒是通過一個有限域GF(28)求逆和一個仿射變換兩種變換構(gòu)造而成:S(ai，j)=f(g(ai，j))，其中，g(ai，j)表示元素 ai，j在有限域GF(28)上的求逆的求逆運算可采用復(fù)合域分解的方法實現(xiàn)，復(fù)合域用GF((2P)Q)表示，稱復(fù)合域GF((2P)Q)與GF(2k)(k=P×Q)是同構(gòu)的，復(fù)合域可由低階子域迭代構(gòu)造而成，即將有限域 GF(2k)求逆運算轉(zhuǎn)換成GF((2P)Q)下的求逆操作.利用同構(gòu)的復(fù)合域方法可用結(jié)構(gòu)簡單的邏輯電路實現(xiàn)復(fù)合域算法.GF(28)域求逆運算的硬件邏輯實現(xiàn)是S盒設(shè)計的關(guān)鍵，文中采用了劉政林等［14］提出的方法.

由式(1)可知，F(xiàn)T與S盒之間是基于GF(28)的一個變量與一個常量的乘法關(guān)系.用xtime(x)表示GF(28)上乘以02的乘法，硬件電路中xtime可以用移位運算和條件異或運算來實現(xiàn).xtime(x)在硬件描述語言VHDL中的函數(shù)實現(xiàn)代碼如下所示:

由于GF(28)中的每一個元素都能夠?qū)懗?2的不同冪次的和，因此，乘以任何常數(shù)的乘法都能夠通過重復(fù)調(diào)用xtime來實現(xiàn).式(1)易轉(zhuǎn)化為

從而，在用硬件電路計算出輸入列元素aj所對應(yīng)的S盒值S(aj)后，可以通過上式得到元素aj所對應(yīng)的FT0值，而對應(yīng)輸入矩陣第2/3/4列的FT1/2/3可通過對FT0中元素的shift操作得到.

2.3 NiosII用戶定制指令接口的實現(xiàn)

當(dāng)處理器用一系列復(fù)雜的標(biāo)準(zhǔn)指令序列來完成一個操作時，可以設(shè)計一個專用的硬件邏輯完成該項操作，專用的硬件邏輯被集成到處理器的算術(shù)邏輯單元中，對應(yīng)一條或多條用戶定制指令，即擴展指令.目前有多種支持可擴展指令集的可配置處理器，如Tensilica的Xtensa、Altera的NiosII等.NiosII處理器的擴展指令邏輯［15］集成在流水線結(jié)構(gòu)中.

NiosII處理器提供兩種用戶定制指令的調(diào)用接口方式:(1)利用GCC編譯工具的built－in內(nèi)建函數(shù)功能(共提供了52種內(nèi)建函數(shù)的類型)，為應(yīng)用程序提供函數(shù)接口定義;(2)直接調(diào)用匯編形式的定制指令.built－in內(nèi)建函數(shù)接口僅能滿足部分定制指令接口定義的需求;直接調(diào)用匯編形式的定制指令方式可使設(shè)計人員在程序中通過內(nèi)聯(lián)匯編指令，直接調(diào)用定制邏輯所對應(yīng)的定制指令.

用戶定制指令的匯編指令語法為

其中:N對應(yīng)圖1中的用戶指令索引信號n(3..0);vC 為 result［31..0］;vA 為 dataa ［31..0］;vB 為datab［31..0］;v可取為 r或 c，為 r時，表示該條指令訪問的是NiosII處理器內(nèi)部的寄存器文件，當(dāng)v取為c時，表示該指令訪問擴展指令內(nèi)部的寄存器文件.

完成擴展指令的硬件邏輯電路設(shè)計并完成編譯、仿真后，需在上層應(yīng)用的頭文件中定義擴展指令的調(diào)用接口，包括參數(shù)的數(shù)據(jù)類型、個數(shù)以及區(qū)分擴展指令的操作碼.本方案采用了built－in接口方式，下面給出了用于加密流程輪變換的FT查表指令及其操作碼的定義，每條指令具有2個32b輸入和1個32b輸出.

應(yīng)用程序中調(diào)用包含擴展指令的輪變換的形式如下所示:

3 實驗結(jié)果與分析

本研究所采用的硬件平臺為基于Altera CycloneII EP2C35F672C8芯片的FPGA開發(fā)板，在所有的測試方案中都統(tǒng)一采用NiosII/s標(biāo)準(zhǔn)型內(nèi)核.采用電子密碼本(ECB)模式的AES算法.測試用例中的測試向量統(tǒng)一采用 KAT(Known Answer Test)模型［16］，采用一次一密的方式，即每一次加密都生成新的密鑰.對KAT中的128組長度為128 b的明文密鑰向量組進行加密，并在測試用例中對加密出的結(jié)果與KAT給出的密文向量進行對比驗證.

為了全面體現(xiàn)擴展指令集方案的特點，共完成了5種AES算法實現(xiàn)方案.基準(zhǔn)算法方案為AES算法在NiosII處理器上的C代碼實現(xiàn)，其運行環(huán)境的硬件平臺配置及性能數(shù)據(jù)為其他方案的對比基準(zhǔn)點，字節(jié)替換函數(shù)采用了查表法，輪操作中的每個函數(shù)用單獨的函數(shù)體實現(xiàn);快速算法方案為AES快速算法在NiosII處理器上的C代碼實現(xiàn)，該方案用以說明針對嵌入式處理器進行應(yīng)用程序的結(jié)構(gòu)優(yōu)化，可對嵌入式應(yīng)用軟件的性能產(chǎn)生重大影響;擴展指令(CI)查表和有限域(GF)分解方案為文中描述的兩種擴展指令集實現(xiàn)方案;協(xié)處理器方案是將AES算法整體用硬件邏輯實現(xiàn)后作為協(xié)處理器集成進NiosII處理器系統(tǒng).

在Quartus9.1環(huán)境下，通過性能分析工具，記錄、分析了各方案中AES算法所占用的時間百分比、單次調(diào)用所消耗的時鐘周期數(shù)、加速比，及硬件邏輯所占用的LE(Logic Element)資源數(shù)、片上內(nèi)存數(shù)等數(shù)據(jù).各方案的上述性能數(shù)據(jù)如表1所示，各方案的時鐘周期數(shù)、LE資源數(shù)和加速比如圖2所示.

表1 各方案的性能數(shù)據(jù)Table 1 Performance data of each schemes

圖2 AES加密算法各實現(xiàn)方案性能數(shù)據(jù)對比Fig.2 Performance data comparison of schemes of AES algorithm

由表1、圖2所示結(jié)果可見:文中實現(xiàn)的第2種擴展指令集方案，通過計算有限域上元素的逆的方法來替代S盒查表法，可取消查表法所需的片上內(nèi)存，并且比第1種方案的加速比略有提高，LE資源數(shù)略有下降;該方案相比于未經(jīng)優(yōu)化的純軟件AES算法可加速241倍，相比于經(jīng)過結(jié)構(gòu)優(yōu)化的純軟件快速AES算法可加速1.47倍.在不考慮任務(wù)粒度劃分以及芯片面積不是主要約束條件的情況下，用協(xié)處理器方式實現(xiàn)AES算法所達到的加速比遠遠超過擴展指令集的方案.

4 結(jié)語

利用硬件加速機制來提升處理器針對特定應(yīng)用的性能，可顯著提高計算密集型任務(wù)的執(zhí)行效率.文中結(jié)合了AES算法的結(jié)構(gòu)優(yōu)化和用邏輯電路實現(xiàn)字節(jié)替換操作中有限域元素求逆兩個層面的措施，用擴展指令集的方法實現(xiàn)了AES算法的硬件加速，顯著減少了面積消耗，提高了算法實現(xiàn)的加速比.由于AES算法的關(guān)鍵步驟(如S盒替換、移位、異或等操作)，普遍應(yīng)用在各種加密算法中，文中針對AES的硬件加速實現(xiàn)方案對各種分組加密算法的硬件加速實現(xiàn)都具有參考價值.與協(xié)處理器的硬件加速機制對比，擴展指令集機制更適用于面積受限條件下細粒度任務(wù)的加速.在面向復(fù)雜應(yīng)用時，按照任務(wù)粒度及具體環(huán)境，采用擴展指令集和協(xié)處理器兩種加速機制的混合加速機制，以兼顧系統(tǒng)的性能和靈活性，將是一個高效的、具有廣闊發(fā)展前景的方法.

［1］ 何德彪，陳建華，胡進.高速橢圓曲線密碼協(xié)處理器的設(shè)計與實現(xiàn)［J］.華南理工大學(xué)學(xué)報:自然科學(xué)版，2010，38(5):90－94.He De－biao，Chen Jian－h(huán)ua，Hu Jin.Design and implementation of high－speed coprocessor for elliptic curve cryptography［J］.Journal of South China University of Technology:Natural Science Edition，2010，38(5):90－94.

［2］ Algredo－Badillo I，F(xiàn)eregrino－Uribe C，Cumplido R，et al.FPGA implementation cost and performance evaluation of the IEEE 802.16e and IEEE 802.11i security architectures based on AES－CCM［C］∥5th International Conference on Electrical Engineering，Computing Science and Automatic Control.Mexico:IEEE ComputerSociety，2008:304－309.

［3］ Li Zhen－rong，Zhuang Yi－qi，Zhang Chao，et al.Low－power and area－optimized VLSI implementation of AES coprocessor for Zigbee system ［J］.The Journal of China Universities of Posts and Telecommunications，2009，16(3):89－94.

［4］ Arshad A，Nassar I.An FPGA－based AES－CCM crypto core for IEEE802.11i architecture ［J］.International Journal of Network Security，2007，5(2):224－232.

［5］ Soliman M I，Abozaid G Y.Performance evaluation of a high throughput crypto coprocessor using VHDL［C］∥International Conference on Computer Engineering and Systems(ICCES).Cairo:IEEE Computer Society，2010:231－237.

［6］ 徐志軍，周順，謝波.AES_Rijndael算法協(xié)處理器設(shè)計與實現(xiàn) ［J］.電路與系統(tǒng)學(xué)報，2007，12(4):37－40.Xu Zhi－jun，Zhou Shun，Xie Bo.Design and implementation of AES/Rijndael algorithm coprocessor［J］.Journal of Circuits and Systems，2007，12(4):37－40.

［7］ Arif I，Vishnu P N，Mohamed K H.An AES tightly coupled hardware accelerator in an FPGA－based embedded processor core［C］∥International Conference on Computer Engineering and Technology.Singapore:IEEE Com－puter Society，2009:521－526.

［8］ Heinrich E，Staamann S，Joost R，et al.Comparison of FPGA－based implementation alternatives for complex algorithms in networked embedded systems the encryption example［C］∥13th IEEE International Conference on Emerging Technologies and Factory Automation.Hamburg:IEEE Computer Society，2008:1449－1456.

［9］ Stefan Tillich，Johann Gro?sch?dl.Instruction set extensions for efficient AES implementation on 32－bit processors［C］∥Cryptographic Hardware and Embeded Systems－CHES 2006.volume 4249 of Lecture Notes in Computer Science.BerLin:Springer，2006:270－284.

［10］ Elbirt A J.Fast and efficient implementation of AES via instruction set extensions［C］∥21st International Conference on Advanced Information Networking and Applications Workshops.Niagara Falls:IEEE Computer Society，2007:396－403.

［11］ 夏輝，賈智平，張峰，等.AES專用指令處理器的研究與實現(xiàn)［J］.計算機研究與發(fā)展，2011，48(8):1554－1563.Xia Hui，Jia Zhi－ping，Zhang Feng，et al.The research and application of a specific instruction processor for AES［J］.Journal of Computer Research and Development，2011，48(8):1554－1563.

［12］ Bertoni G M，Breveglieri L，Roberto F，et al.Speeding up AES by extending a 32 bit processor instruction set［C］∥Application－Specific Systems，Architectures and Processors.Steamboat:IEEE Computer Society，2006:275－282.

［13］ Daemen J，Rijmen V.The Design of Rijndael:AES－－the advanced encryption standard ［M］.Berlin:Springer，2002.

［14］ 劉政林，曾永紅，鄒雪城，等.復(fù)合域算法的AES S盒電路實現(xiàn)［J］.應(yīng)用科學(xué)學(xué)報，2008，26(6):622－626.Liu Zheng－lin，Zeng Yong－h(huán)ong，Zou Xue－cheng，et al.AES S－box circuit implementation based on composite field arithmetic ［J］.Journal of Applied Sciences Electronics and Information Engineering，2008，26(6):622－626.

［15］ Altera Corporation.Nios II custom instruction user guide［Z］.San Jose:Altera Corporation，2008.

［16］ National Institute of Standards and Technology(NIST).Description of known answer tests and Monte Carlo test for advanced encryption standard(AES)candidate algorithm submission ［EB/OL］.(2011－04－22)［2011－11－20］.http:∥csrc.nist.gov/groups/STM/cavp/.