黃光紅,洪一,2,耿銳

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

黃光紅(助理工程師)、耿銳(工程師),主要研究方向?yàn)轶w系結(jié)構(gòu);洪一(博士生導(dǎo)師),主要研究方向?yàn)閿?shù)字信號(hào)處理、體系結(jié)構(gòu)。

1 概 述

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

有一種新的方法——可配置處理器,能高效地解決這個(gè)難題。其兩個(gè)特點(diǎn)是:用戶的可配置性和系統(tǒng)的自動(dòng)生成。用戶的可配置性是指,可以通過(guò)參數(shù)設(shè)置、刪除、增加處理器功能,用戶還能根據(jù)需求增加一些特殊指令。系統(tǒng)的自動(dòng)生成是指,能根據(jù)配置信息自動(dòng)生成處理器硬件邏輯及其軟件開(kāi)發(fā)工具?？膳渲锰幚砥鞣桨负芎玫貪M足了特定應(yīng)用需求。本文采用可配置處理器設(shè)計(jì)并實(shí)現(xiàn)特定應(yīng)用——AES加密解密算法。

2 可配置處理器

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

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

圖1 可配置處理器設(shè)計(jì)流程

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

3.1 算法及熱點(diǎn)分析

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

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

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

3.2 指令設(shè)計(jì)與優(yōu)化

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

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

圖3 ROTSUBXORWORD指令流程

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

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

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

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

圖4 MIXCOLUMN指令流程

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

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

4 實(shí)驗(yàn)與性能分析

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

表1 實(shí)驗(yàn)結(jié)果

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

結(jié) 語(yǔ)

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

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

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

[3]黃智穎,馮新喜,張煥國(guó).高級(jí)加密標(biāo)準(zhǔn)AES及其實(shí)現(xiàn)技巧[J].計(jì)算機(jī)工程與應(yīng)用,2002(9):112-115.

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

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