基于可配置處理器的AES算法設計

黃光紅,洪一,2,耿銳

(1.華東電子工程研究所,合肥230031;2.中國科學技術大學)

黃光紅(助理工程師)、耿銳(工程師),主要研究方向為體系結構;洪一(博士生導師),主要研究方向為數(shù)字信號處理、體系結構。

1 概 述

隨著集成電路技術的快速發(fā)展,通用處理器的性能急劇提高。但通用處理器面對的是各種不同的應用需求,當它應用于特定領域時,可能很難獲得極高性能,無法體現(xiàn)其優(yōu)勢。ASIC處理器能解決這個問題,但其設計周期較長、風險較大,復用性很差。

有一種新的方法——可配置處理器,能高效地解決這個難題。其兩個特點是:用戶的可配置性和系統(tǒng)的自動生成。用戶的可配置性是指,可以通過參數(shù)設置、刪除、增加處理器功能,用戶還能根據(jù)需求增加一些特殊指令。系統(tǒng)的自動生成是指,能根據(jù)配置信息自動生成處理器硬件邏輯及其軟件開發(fā)工具。可配置處理器方案很好地滿足了特定應用需求。本文采用可配置處理器設計并實現(xiàn)特定應用——AES加密解密算法。

2 可配置處理器

本文采用Tensilica公司的可配置處理器Xtensa。該處理器基于32位RISC內(nèi)核,具有可配置性、可擴展性和可集成性。用戶可根據(jù)各種不同應用,配置處理器各參數(shù)以達到最佳性能、最低成本。可配置項目有:寄存器堆寬度和深度、各數(shù)據(jù)通路寬度、執(zhí)行單元數(shù)目和類型、外圍設備的數(shù)目和類型、讀取存儲單元和存儲器端口的數(shù)目和大小、指令長度、指令操作數(shù)數(shù)目等[1]。

可配置的Xtensa處理器具有一個基本核,支持80條基本指令,這些指令支持C語言和操作系統(tǒng)。Xtensa處理器采用5級或7級流水線,指令集寬度為24位或16位壓縮編碼方式。對于特定應用,通常需要經(jīng)過分析增加新的指令和寄存器來提高性能。TIE(Tensilica Instruction Extension)語言,為設計者提供了一種通過指令集擴展描述來擴展Xtensa處理器指令集的方法。指令集擴展描述是指,通過TIE編譯器的編譯生成處理器擴展部分的Verilog或VHDL描述,并且更新該處理器的軟件工具鏈(編譯器、匯編器、仿真器和調(diào)試器)來支持新的指令集。處理器和軟件工具鏈的自動化生成為設計者提供了極大的方便[2]。可配置處理器的設計流程如圖1所示。

圖1 可配置處理器設計流程

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

3.1 算法及熱點分析

AES(Advanced Encryption Standard,高級加密標準)是美國NIST頒布的數(shù)據(jù)加密標準,采用新的Rijndael分組加密算法,具有更高的安全性和易實現(xiàn)性[3]。AES算法的分組長度Nb和密鑰長度Nk可分別取值為4字、6字或8字(字為32位),不同的參數(shù)對應算法中不同輪循環(huán)次數(shù)Nr。該算法將分組看成4×Nb的二維字節(jié)數(shù)組,或Nb字的一維數(shù)組,并稱分組為State。加解密就是對State進行多次變換以獲得密文或明文的過程。AES算法主要由密鑰擴展(KeyExpansion)和輪循環(huán)組成,每輪由SubBytes(字節(jié)替換)、ShiftRows(行位移)、MixColumns(列混合變換)和AddRoundKey(加輪密鑰)組成。解密算法是加密算法的逆過程,每輪由InvSubBytes(逆字節(jié)替換)、InvShiftRows(逆行位移)、InvMixColumns(逆列混合變換)和 AddRoundKey組成[4]。加密、解密流程如圖 2所示。

圖2 AES算法加密和解密流程

用C/C++語言實現(xiàn)AES算法。分析其程序執(zhí)行熱點,即分析程序各個部分占用處理器執(zhí)行時間的百分比。經(jīng)過分析,在加密算法中 MixColumns、ShiftRows、Sub-Bytes和KeyExpansion都是程序的執(zhí)行熱點,可以通過在可擴展處理器中增加相應的專用指令和硬件查找表方法提高程序執(zhí)行速度。解密算法與其類似。

3.2 指令設計與優(yōu)化

發(fā)現(xiàn)程序的執(zhí)行熱點后,就可以利用可擴展處理器提供的方法優(yōu)化熱點的執(zhí)行效率。對每個熱點進行分析,設計優(yōu)化的實施方案,并用TIE語言實現(xiàn)。

KeyExpansion是加密解密前的準備工作,根據(jù)原始密鑰生成密鑰序列供輪循環(huán)使用。當加密解密的數(shù)據(jù)量很小時,KeyExpansion占用相當?shù)奶幚砥鲿r間,需進行優(yōu)化獲得更高的性能。KeyExpansion中有對密鑰某行4字節(jié)替換操作,其中的替換字節(jié)表在輪循環(huán)中使用頻率更高。對于經(jīng)常使用的常數(shù)表,TIE語言提供優(yōu)化方法,即硬件常數(shù)表table。本文設計了2個table——SBox和InvSBox,分別用于加密解密,每個表大小為 16×16字節(jié)。設計專用指令SUBWORD,可一次替換密鑰行的4字節(jié)。KeyExpansion有一個操作序列:4字節(jié)循環(huán)右移、字節(jié)替換、與常數(shù)表異或。采用融合技術將序列操作融合為一條復雜的專用指令ROTSUBXORWORD。指令流程如圖3所示。

圖3 ROTSUBXORWORD指令流程

加密輪的SubBytes對State進行字節(jié)替換,使用字節(jié)替換表SBox。為了節(jié)約硬件資源,可復用專用指令SUBWORD。

ShiftRows操作是將State中的4行字節(jié)數(shù)分別循環(huán)左移0、1、2、3字節(jié)位。本文將 State看作字的一維數(shù)組,移位操作涉及一維數(shù)組中的所有字。因為ShiftRows在每輪中都被調(diào)用,優(yōu)化加速比很高。ShiftRows操作簡單,但被操作的數(shù)很多,一般指令的輸入?yún)?shù)少。TIE語言提供狀態(tài)寄存器,可用于任何指令操作。它不出現(xiàn)在指令的匯編代碼的參數(shù)表中,而是被指令隱式地使用。設置讀寫屬性后處理器生成器自動生成指令,負責狀態(tài)寄存器和通用寄存器之間的數(shù)據(jù)傳輸。根據(jù)Nb大小,設計8個32位寬的狀態(tài)寄存器保存分組State。設計指令SHIFTROWS實現(xiàn)行移,輸入?yún)?shù)為Nb。在指令SHIFTROWS操作前將State寫入各狀態(tài)寄存器,操作后再讀出。

在優(yōu)化前,MixColumns是占用處理器時間最多的操作。列混合變換是將State中的每列乘以矩陣A:

這里的乘法和加法是GF(28)域上的運算[5]。耗時的矩陣乘法應通過設計專用指令進行優(yōu)化。為實現(xiàn)矩陣乘法需實現(xiàn)字節(jié)乘2、乘3運算,可借助TIE語言中的function關鍵字實現(xiàn)。function定義一個功能模塊,TIE文件中每次調(diào)用都重新復制硬件邏輯。本文定義2個function——GFMultBy02和GFMultBy03,分別表示乘 2和乘3操作。定義列混合變換專用指令MIXCOLUMN,它調(diào)用GFMultBy02和GFMultBy03實現(xiàn)列變換功能,流程如圖4所示。

圖4 MIXCOLUMN指令流程

解密算法中的InvSubBytes采用替換表InvSBox進行字節(jié)替換,設計專用指令 INVSUBWORD實現(xiàn)。Inv-ShiftRows是將State中的4行字節(jié)數(shù)分別循環(huán)右移0、1、2、3字節(jié)。同理,為其設計專用指令INVSHIFTROWS。

解密中的列混合變換InvMixColumns是加密的逆過程,它是將State中的每列乘矩陣B。同理,用function實現(xiàn)GFMultBy0E、GFMultBy0B、GFMultBy0D 和 GFMult-By09,定義逆列混合變換專用指令INVMIXCOLUMN。

4 實驗與性能分析

本文用C/C++語言實現(xiàn)了未優(yōu)化的AES算法。在優(yōu)化設計后,用TIE語言實現(xiàn)了專用指令和相關模塊,再用C/C++語言實現(xiàn)優(yōu)化后的算法。實驗程序相關參數(shù)設置為:Nk為4,Nb為6,Nr為12。加密解密程序分別循環(huán)調(diào)用分組加密解密100次,即總共分別加解密2 400字節(jié)。相關的實驗結果如表1所列。

表1 實驗結果

從實驗結果可以看出,使用TIE語言設計多條專用指令后,算法的優(yōu)化效果相當明顯。函數(shù)ShiftRows、MixColumns、InvShiftRows和 InvMixColumns優(yōu)化后獲得很高的加速比,因為優(yōu)化前操作的通用指令執(zhí)行序列占大量的處理器時鐘周期,而采用專用指令后時鐘周期大大減少。尤其是InvMixColumns,由于含有乘 9等操作(通過乘2和加操作實現(xiàn)),因此優(yōu)化后的加速比非常高。

結 語

本文介紹了可配置處理器的優(yōu)點和利用可配置處理器實現(xiàn)特定應用的流程;分析了AES加解密算法的特定應用,研究其優(yōu)化方案并用 TIE語言實現(xiàn)了多條專用指令。實驗證明,采用可配置處理器方法可大大提高 AES算法的執(zhí)行性能。在AES算法中,含有大量的可并行執(zhí)行的循環(huán)。可配置處理器可通過SIMD技術和VLIW技術實現(xiàn)高度的并行計算,采用這些技術將進一步提高執(zhí)行性能,這是下一步的研究工作。

[1]陳雙燕,張鐵軍,王東輝,等.基于一種可配置可擴展處理器的M ELP語音算法的改進與實現(xiàn)[J].微電子學與計算機,2006,23(6):42-43.

[2]Chris Rowen.復雜SOC設計[M].吳武臣,等譯.北京:機械工業(yè)出版社,2006.

[3]黃智穎,馮新喜,張煥國.高級加密標準AES及其實現(xiàn)技巧[J].計算機工程與應用,2002(9):112-115.

[4]Daemem J,Rijmem V.AES Proposal:Rijndael[OL].[2009-11].http://www.Daemen.j@banksys.

[5]張德學,郭立,傅忠謙.一種基于 FPGA的 AES加解密算法設計與實現(xiàn)[J].中國科技大學學報,2007,37(12):1461-1464.