楊錦江 曹 鵬 楊 軍
(東南大學(xué)國家專用集成電路系統(tǒng)工程技術(shù)研究中心, 南京 210096)
?
面向分組密碼算法的高面積效率可重構(gòu)架構(gòu)
楊錦江 曹鵬 楊軍
(東南大學(xué)國家專用集成電路系統(tǒng)工程技術(shù)研究中心, 南京 210096)
為了提升安全應(yīng)用中分組密碼算法的面積效率,提出了一種基于粗粒度可重構(gòu)計算的硬件架構(gòu).在可重構(gòu)架構(gòu)設(shè)計過程中采用了2種優(yōu)化方案,即利用Benes網(wǎng)絡(luò)優(yōu)化可重構(gòu)計算陣列的層間互聯(lián)和基于配置信息的使用頻度優(yōu)化配置信息的組織方式.實驗結(jié)果表明:采用基于Benes網(wǎng)絡(luò)的層間互聯(lián)方案后,可重構(gòu)陣列中層間互聯(lián)的面積開銷減少了51.61%;采用基于使用頻度的配置信息層次化組織方式后, AES分組密碼算法和DES分組密碼算法的配置時間分別縮短了80%和88%,配置時間占總時間的百分數(shù)分別下降了42%和39%.這2種分組密碼算法在該可重構(gòu)架構(gòu)上實現(xiàn)的面積效率為同類架構(gòu)的3.95和1.51倍.因此,所提的2種優(yōu)化方案能夠有效降低面積開銷,提高可重構(gòu)架構(gòu)的性能,有助于分組密碼算法高面積效率的實現(xiàn).
分組密碼算法;粗粒度可重構(gòu)架構(gòu);層次化配置;面積效率
隨著信息技術(shù)與網(wǎng)絡(luò)通信的發(fā)展,網(wǎng)絡(luò)傳輸對安全的需求不斷上升,研究者們據(jù)此提出了許多安全協(xié)議.密碼算法是安全協(xié)議的基礎(chǔ),其實現(xiàn)性能對系統(tǒng)性能具有重大影響.安全協(xié)議一般需要同時支持多種密碼算法,協(xié)議中具體使用哪種密碼算法由通信雙方事先協(xié)商決定.日益增加的網(wǎng)絡(luò)數(shù)據(jù)帶寬對密碼算法的性能提出了越來越高的要求.例如,在IPSec和SSL協(xié)議中,可以選擇AES或DES分組密碼算法對大規(guī)模數(shù)據(jù)進行加密.傳統(tǒng)的實現(xiàn)方案中,通用處理器實現(xiàn)方案[1]雖然能保證靈活性,但不能滿足密碼算法高性能的需求;專用集成電路實現(xiàn)方案[2]可以使密碼算法獲得較好的性能,但缺乏靈活性,不能滿足安全協(xié)議支持多種密碼算法的需求.可重構(gòu)計算可以在靈活性和高性能之間取得較好的平衡[3].在可重構(gòu)架構(gòu)中,計算任務(wù)被高效地映射到硬件資源上,保證了高度并行性,此外,還可以通過配置信息改變其功能,保證了在硅實現(xiàn)后的靈活性.FPGA作為一種細粒度可重構(gòu)架構(gòu),廣泛應(yīng)用于密碼算法實現(xiàn)中[4-5],AES,DES等分組密碼算法在FPGA上取得了較好的性能,但同時也消耗了大量的面積資源,面積效率不高.粗粒度可重構(gòu)架構(gòu)將FPGA中的LUT單元替換成粗粒度的計算單元,精簡了FPGA的互聯(lián)類型,在執(zhí)行算法時面積效率高于FPGA.研究者們提出了多種面向分組密碼算法的粗粒度可重構(gòu)架構(gòu),如RCPA/RCBA[6-7],ADRES[8],AESTHETIC[9]等.然而,粗粒度可重構(gòu)架構(gòu)的局部互聯(lián)靈活性導(dǎo)致互聯(lián)結(jié)構(gòu)較為復(fù)雜,實現(xiàn)過程中需要較多的面積資源和配置信息,從而制約了整個可重構(gòu)系統(tǒng)的執(zhí)行性能.本文根據(jù)分組密碼算法的特點,提出了一種面向分組密碼算法的高面積效率的粗粒度可重構(gòu)架構(gòu),有效降低了架構(gòu)面積,提高了數(shù)據(jù)處理吞吐率.
分組密碼算法將明文分為一系列固定位寬的數(shù)據(jù)分組,加密過程以數(shù)據(jù)分組為最小單位,因此分組密碼通常在安全協(xié)議中被用作大規(guī)模數(shù)據(jù)傳輸時的加密.分組密碼算法可以按照結(jié)構(gòu)特征分為SP結(jié)構(gòu)和Feistel結(jié)構(gòu)2類.前者的擴散速度較快;后者的擴散速度較慢,但加/解密過程一致.
分組密碼算法的基本特征如下:
1) 數(shù)據(jù)并行度大.分組密碼算法對明文/密文數(shù)據(jù)按固定長度進行分組,每組數(shù)據(jù)又可被分割成多塊等長的數(shù)據(jù)進行運算.例如,AES分組密碼算法按128 bit進行分組,在進行字節(jié)替換時,每組數(shù)據(jù)被進一步分割成16個8 bit數(shù)據(jù)進行操作.各組數(shù)據(jù)之間、組內(nèi)各塊數(shù)據(jù)之間均無數(shù)據(jù)依賴,因此多組/塊數(shù)據(jù)可以并行執(zhí)行.
2) 計算過程規(guī)則. 在分組密碼算法中,明文分組后經(jīng)過多輪迭代得到密文,每輪迭代操作基本一致,僅首輪或末輪的輪函數(shù)可能存在微小差異.典型的分組密碼算法流程圖如圖1所示.由圖可知,AES分組密碼算法分10輪迭代進行,與前9輪操作相比,第10輪僅省去列混合操作;DES分組密碼算法分16輪迭代進行,與前15輪操作相比,第16輪省去數(shù)據(jù)的左右交換.
(a) AES分組密碼算法
(b) DES分組密碼算法
3) 基本算子趨同.雖然分組密碼算法的具體運算過程各不相同,但都是由一些基本算子組成的.文獻[10]統(tǒng)計了41種常見的分組密碼算法,將基本操作歸納為7種類型.邏輯操作、S盒替換、移位/循環(huán)移位操作、模加/減、比特置換、模乘和Galois域上的模乘.其中,邏輯操作、S盒操作、移位/循環(huán)移位操作的發(fā)生概率超過60%.
4) 數(shù)據(jù)通路復(fù)雜.分組密碼算法在擴散過程中使用了比特置換和移位等操作,從而使得算法執(zhí)行的數(shù)據(jù)通路具有豐富的變化形式.
根據(jù)分組密碼算法的基本特征,給出了面向分組密碼算法的粗粒度可重構(gòu)架構(gòu)(見圖2).架構(gòu)由配置控制器、計算陣列、輸入FIFO、輸出FIFO以及數(shù)據(jù)緩存等部分組成.其中,配置控制器用于解析索引信息,從配置信息中選取與索引對應(yīng)的配置信息,對計算陣列進行配置;計算陣列根據(jù)配置信息執(zhí)行算法;輸入、輸出FIFO分別用于明文的輸入和密文的輸出;數(shù)據(jù)緩存用于存儲計算陣列計算過程中產(chǎn)生的中間結(jié)果數(shù)據(jù).
(a) 架構(gòu)總體框圖
(b) 計算陣列框圖
2.1計算陣列
計算陣列為面向分組密碼算法的可重構(gòu)架構(gòu)中的核心模塊,其架構(gòu)框圖如圖2(b)所示.計算陣列以行為基本單元,每行包括讀入、寫出、層間互聯(lián)和PE等單元.針對分組密碼算法數(shù)據(jù)并行度大的特點,每行陣列中包含多個PE以并行處理數(shù)據(jù).讀入單元用于從輸入FIFO或數(shù)據(jù)緩存中讀入數(shù)據(jù)至該行陣列,寫出單元用于從該行陣列中寫出結(jié)果至輸出FIFO或數(shù)據(jù)緩存.陣列的行與行之間通過層間互聯(lián)單元進行數(shù)據(jù)傳輸.
2.2配置控制器
配置控制器負責(zé)對計算陣列進行配置,使得陣列通過切換不同的數(shù)據(jù)流圖來執(zhí)行完整個算法.配置控制器中包含配置信息存儲器和索引信息存儲器,分別存放整個算法的子圖配置信息以及索引信息.其中,算法子圖配置信息包含了該子圖中數(shù)據(jù)的輸入輸出形式和計算功能,而索引信息用于快速索引到這些配置信息,并有效避免配置信息的重復(fù)存儲.配置控制器的執(zhí)行步驟如下:① 系統(tǒng)在重置時對算法的索引信息和配置信息進行初始化;② 當(dāng)計算陣列準備就緒,配置控制器開始執(zhí)行;③ 解析索引信息,根據(jù)索引信息選取對應(yīng)的配置信息,對計算陣列進行配置;④ 判斷是否需要終止配置,如果終止則退出配置解析,否則當(dāng)計算陣列再次準備就緒時,跳轉(zhuǎn)到步驟③.
3.1面向低硬件開銷的層間互聯(lián)方案優(yōu)化
由第1節(jié)可知,分組密碼算法具有數(shù)據(jù)通路復(fù)雜的特點.為了保證算法中比特置換等核心算子的執(zhí)行效率,層間互聯(lián)需要滿足PE行間全互聯(lián)的數(shù)據(jù)通路需求,同時需要有效控制豐富的互聯(lián)需求導(dǎo)致的硬件開銷增長.Crossbar結(jié)構(gòu)[11]和Benes網(wǎng)絡(luò)是2種主要的全互聯(lián)實現(xiàn)形式.以Crossbar結(jié)構(gòu)的方式實現(xiàn)全互聯(lián),可以較少的配置信息完成其功能配置,然而需要消耗較多的硬件資源;而以Benes的方式實現(xiàn)全互聯(lián),需要的硬件資源較少,但需要更多的配置信息進行功能配置.
圖3為基于Crossbar結(jié)構(gòu)的層間互聯(lián)示意圖.如圖所示,Crossbar結(jié)構(gòu)的層間互聯(lián)將前一行的L個輸出數(shù)據(jù)連接到當(dāng)前行的輸入中.
圖3 基于Crossbar結(jié)構(gòu)的層間互聯(lián)示意圖
由圖3可見,Crossbar結(jié)構(gòu)層間互聯(lián)傳輸數(shù)據(jù)的位寬與PE計算數(shù)據(jù)的位寬一致.然而,在分組密碼算法中,比特置換和移位等操作的位寬通常大于PE計算位寬比特,因此,雖然Crossbar結(jié)構(gòu)層間互聯(lián)的控制方式簡單,但無法滿足分組密碼算法中置換和移位等數(shù)據(jù)傳輸需求.
256 bit的Benes網(wǎng)絡(luò)實現(xiàn)示意圖見圖4.由圖可知,該網(wǎng)絡(luò)可由2個128 bit的Benes網(wǎng)絡(luò)構(gòu)成,并可以進一步向下拆分,網(wǎng)絡(luò)中的基本元件為一個2×2的置換開關(guān),每個2×2的置換開關(guān)存在交叉和直通2個狀態(tài),由2個1 bit的2選1數(shù)據(jù)選擇器組成.256 bit數(shù)據(jù)經(jīng)過Benes網(wǎng)絡(luò)構(gòu)成的層間互聯(lián)后,可以得到該數(shù)據(jù)的任意置換.由此可知,Benes網(wǎng)絡(luò)可實現(xiàn)比特置換、移位等操作.
圖4 Benes網(wǎng)絡(luò)實現(xiàn)示意圖
Crossbar結(jié)構(gòu)和Benes網(wǎng)絡(luò)需要的2輸入1輸出的數(shù)據(jù)選擇器數(shù)量分別為
Cmuxer=N(N-1)m
(1)
Bmuxer=2(mN)log2(mN)-mN
(2)
式中,N為每行PE的數(shù)量;m為每行PE的數(shù)據(jù)位寬.
如圖5所示,隨著每行PE數(shù)目的增長,Crossbar結(jié)構(gòu)的層間互聯(lián)實現(xiàn)所需資源的增長速度明顯快于Benes網(wǎng)絡(luò).
圖5 層間互聯(lián)實現(xiàn)所需硬件開銷對比
與Grossbar結(jié)構(gòu)相比,Benes網(wǎng)絡(luò)的層間互聯(lián)消耗資源更少,但需要更多的配置信息.2種層間互聯(lián)所需的配置信息量分別為
Cconf=Nlog2N
(3)
Bconf=mNlog2(mN)-mN
(4)
式中,Cconf,Bconf分別為Crossbar結(jié)構(gòu)和Benes網(wǎng)絡(luò)的層間互聯(lián)所需要的配置信息量.
圖6為2種互聯(lián)結(jié)構(gòu)需要的配置信息量比較.由圖可知,隨著PE數(shù)目的增長,Benes網(wǎng)絡(luò)所需要的配置信息急劇增加.配置信息量過大會影響配置的效率,從而影響整個算法的性能.
綜上所述,采用Benes網(wǎng)絡(luò)作為層間互聯(lián)的形式有助于減少面積資源消耗,但是需要消除其配置信息量過大對于整個系統(tǒng)執(zhí)行性能的影響.
圖6 層間互聯(lián)實現(xiàn)所需配置信息量對比
3.2面向高性能的配置信息組織形式優(yōu)化
架構(gòu)中計算和互聯(lián)等模塊都可以重構(gòu),故需要使用配置信息對整個架構(gòu)進行配置[6].算法的執(zhí)行時間為
Ttotal=Tconf+Tcalc
(5)
式中,Tconf,Tcalc分別為配置時間和計算時間.
由式(5)可知,通過減少Tconf可以有效減小整體執(zhí)行時間Ttotal,其計算公式為
(6)
式中,M為算法中需要切換的子圖數(shù)目;tconf-i為第i次子圖切換時需要的配置時間.
圖7描述了陣列全局配置與局部配置情況下算法總執(zhí)行時間的關(guān)系.圖中,tmax為切換子圖時對陣列進行全局配置所需要的最大配置時間;tcalc-i為第i次子圖的計算時間;Tconf-M和Tcalc-M分別為最后一張子圖的計配置時間和計算時間.由圖可知,在算法執(zhí)行過程中,局部配置可以有效地減小配置時間.
圖7 陣列局部配置與全局配置執(zhí)行時間
由分組密碼算法的特征可知,計算過程規(guī)則和基本算子趨同會導(dǎo)致算法中不同子圖間存在相似性.因此,可以按照配置信息使用的頻度對配置信息的組織形式進行優(yōu)化.
圖8描述了配置信息組織形式優(yōu)化前后的存儲形式.由圖可知,優(yōu)化前更新子圖需要將第0~R行的配置全部更新.優(yōu)化后則可按照配置信息不同的使用頻度進行層次化存儲,在更新子圖時,每行只需要更新部分配置信息.同時,如果該行的部分配置與更新前一致,則在動態(tài)生成配置時無需重復(fù)生成.因此,在配置過程中只需更新一部分配置信息即可,使得每次更新子圖時Tconf-i 圖8 基于使用頻度的配置信息組織形式優(yōu)化 綜上所述,3.1節(jié)利用Benes網(wǎng)絡(luò)層間互聯(lián)替換傳統(tǒng)的Crossbar結(jié)構(gòu)層間互聯(lián),從而優(yōu)化了層間互聯(lián)的面積;然而,Benes網(wǎng)絡(luò)層間互聯(lián)需要較大的配置信息量,影響了配置速度,從而使得整體性能下降.因此,本節(jié)中提出了面向高性能的配置信息組織形式,減少了配置信息傳輸量,加快了配置速度,提升了陣列的整體性能. 4.1硬件實現(xiàn) 采用RTL硬件描述語言完成圖2中的架構(gòu),并利用VCS工具進行功能和時序仿真.硬件實現(xiàn)基于SMIC 55 nm CMOS工藝庫,利用Synopsys公司的Design Complier (DC) 工具進行綜合,生成門級網(wǎng)表,并通過IC Compiler(ICC)工具實現(xiàn)布局布線,得到可重構(gòu)架構(gòu)的版圖(見圖9).在300 MHz頻率的約束下,本架構(gòu)的面積為5.01×106gate. 圖9 可重構(gòu)架構(gòu)版圖 4.2性能分析與比較 由3.1節(jié)可知,層間互聯(lián)可通過Crossbar結(jié)構(gòu)和Benes網(wǎng)絡(luò)2種方式實現(xiàn).表1列出了這2種方式的面積開銷與配置信息量.由表可知,Benes網(wǎng)絡(luò)的實現(xiàn)面積較Crossbar結(jié)構(gòu)減小了51.61%,但其需要的配置量為Crossbar結(jié)構(gòu)的12倍. 表1 Crossbar結(jié)構(gòu)與Benes網(wǎng)絡(luò)的面積與配置對比 采用基于使用頻度的配置信息組織形式后,切換子圖時不需要對陣列進行全局配置,子圖中冗余的配置信息不再更新,從而提升了配置的性能.采用基于使用頻度的配置信息組織形式后,AES分組密碼算法和DES分組密碼算法的配置時間分別減少了80%和88%,相應(yīng)地,AES分組密碼算法和DES分組密碼算法的配置時間占總時間的百分數(shù)分別下降了42%和39%. 表2列出了本文架構(gòu)與類似架構(gòu)的比較.由表可知道,RCPA架構(gòu)[6]的面積小于本文架構(gòu),但是配置時間過長導(dǎo)致其算法的吞吐率不高;本文架構(gòu)中采用了基于使用頻度的配置存儲和配置方案,縮短了執(zhí)行時間,使得AES分組密碼算法與DES分組密碼算法實現(xiàn)的面積效率分別為RCPA架構(gòu)的1.64與2.22倍.COBRA架構(gòu)[12]中算法的吞吐率較高,但是消耗了大量的面積資源;本文架構(gòu)采用Benes網(wǎng)絡(luò)的方式實現(xiàn)層間互聯(lián),降低了面積消耗,AES分組密碼算法在本文架構(gòu)上實現(xiàn)的面積效率為COBRA架構(gòu)的3.95倍.AsAP架構(gòu)[1]具有較高的執(zhí)行頻率,但是需要眾多的運算和互聯(lián)資源,且其計算過程中仍需要取址和譯碼,AES分組密碼算法在本文架構(gòu)上實現(xiàn)的面積效率為AsAP架構(gòu)的2.90倍.Cryptoraptor架構(gòu)[13]在較高頻率的基礎(chǔ)上對AES分組密碼算法進行了流水線技術(shù)優(yōu)化,獲得了較高的面積效率;然而,對于其他分組密碼算法,該架構(gòu)的面積效率并不理想.例如,DES分組密碼算法在本文架構(gòu)上實現(xiàn)的面積效率為Cryptoraptor架構(gòu)的1.51倍. 本文通過分析分組密碼算法的特征,提出了一個面向分組密碼算法的高面積效率可重構(gòu)架構(gòu),通過進行架構(gòu)層間互聯(lián)優(yōu)化以及配置信息層次化,提升了算法在架構(gòu)上的性能,并降低了架構(gòu)實現(xiàn)的面積.AES分組密碼算法在本文架構(gòu)上實現(xiàn)的面積效率為同類架構(gòu)COBRA的3.95倍,DES分組密碼算法在本文架構(gòu)上實現(xiàn)的面積效率為同類架構(gòu)Cryptoraptor的1.51倍. 表2 本文架構(gòu)與類似架構(gòu)的比較 References) [1]Liu B, Baas B M. Parallel AES encryption engines for many-core processor arrays[J].IEEETransactionsonComputers, 2013, 62(3):536-547. DOI:10.1109/tc.2011.251. [2]Mathew S K, Sheikh F, Kounavis M, et al. 53 Gbps native GF(24)2composite-field AES-encrypt/decrypt accelerator for content-protection in 45 nm high-performance microprocessors[J].IEEEJSolid-StateCircuits, 2011, 46(4):767-776. DOI:10.1109/jssc.2011.2108131. [3]Hartenstein R. A decade of reconfigurable computing: A visionary retrospective[C]//ProceedingsoftheConferenceonDesign,AutomationandTestinEurope. Munich, Germany, 2001:642-649. DOI:10.1109/date.2001.915091. [4]Liu Q, Xu Z, Yuan Y. A 66.1 Gbps single-pipeline AES on FPGA[C]//2013InternationalConferenceonField-ProgrammableTechnology. Kyoto,Japan, 2013: 378-381. DOI:10.1109/fpt.2013.6718392. [5]Wang Y, Ha Y. FPGA-based 40.9-Gbits/s masked AES with area optimization for storage area network[J].IEEETransactionsonCircuitsandSystemsII:ExpressBriefs, 2013, 60(1):36-40. DOI:10.1109/tcsii.2012.2234891. [6]Dai Z B, Yang X H, Ren Q, et al. The research and design of reconfigurable cipher processing architecture targeted at block cipher[C]//7thInternationalConferenceonASICASICON’07. Guilin, China, 2007:814-817.DOI:10.1109/icasic.2007.4415755. [7]Yang X, Dai Z, Zhang Y, et al. The research and design of reconfigurable computing for block cipher[J].JournalofElectronics(China), 2008, 25(4):503-510. DOI:10.1007/s11767-006-0279-y. [8]Garcia A, Berekovic M, Vander A T. Mapping of the AES cryptographic algorithm on a coarse-grain reconfigurable array processor[C]//InternationalConferenceonApplication-SpecificSystems,ArchitecturesandProcessors. Leuven,Belgium, 2008:245-250. DOI:10.1109/asap.2008.4580186. [9]Wang M Y, Su C P, Horng C L, et al. Single- and multi-core configurable AES architectures for flexible security[J].IEEETransactionsonVeryLargeScaleIntegration(VLSI)Systems, 2010, 18(4):541-552. DOI:10.1109/tvlsi.2009.2013231. [10]Elbirt A J, Paar C. An instruction-level distributed processor for symmetric-key cryptography[J].IEEETransactionsonParallelandDistributedSystems, 2005,16(5):468-480. DOI:10.1109/TPDS.2005.51. [11]Park H W, Kim W, Yoo D, et al. A scalable scheduling algorithm for coarse-grained reconfigurable architecture[C]//IEEEInternationalConferenceonConsumerElectronics(ICCE). Las Vegas, Nevada,USA, 2013:542-543. [12]Elbirt A J, Paar C. An instruction-level distributed processor for symmetric-key cryptography[J].IEEETransParallelDistribSyst, 2005, 16(5):468-480. DOI:10.1109/tpds.2005.51. [13]Sayilar G, Chiou D. Cryptoraptor:High throughput reconfigurable cryptographic processor[C]//2014IEEE/ACMInternationalConferenceonComputer-AidedDesign. Los Angeles, CA,USA, 2014:154-161. DOI:10.1109/iccad.2014.7001346. Reconfigurable architecture with high area efficiency for block cipher algorithms Yang Jinjiang Cao Peng Yang Jun (National ASIC System Engineering Technology Research Center, Southeast University, Nanjing 210096, China) A coarse-grained reconfigurable architecture is proposed to improve the area efficiency of block cipher algorithms in the security applications. Two schemes are used to optimize the architecture. One is using the Benes network to optimize the connection between rows of the reconfigurable architecture, and the other is optimizing the context organization according to the use frequency. The experimental results show that the area cost is reduced by 51.61% after using the Benes network as the optimization of row connection. After using the hierarchical context organization based on the using frequency, the configuration time of the AES(advanced encryption standard) block cipher algorithm and that of the DES(data encryption standard) block cipher algorithm decrease by 80% and 88%, and the proportions of their configuration time in the total time decrease 42% and 39%, respectively. The area efficiencies of these two block cipher algorithms implemented on the proposed reconfigurable architecture are 3.95 and 1.51 times of the similar architectures, respectively. Therefore, the two proposed schemes can effectively decrease the area cost, improve the performance of the reconfigurable architecture and favor the efficient area implementation of block cipher algorithms. block cipher algorithm;coarse-grained reconfigurable architecture;hierarchical configuration organization;area efficiency 10.3969/j.issn.1001-0505.2016.05.007 2016-04-28.作者簡介: 楊錦江(1986—),男,博士生;楊軍(聯(lián)系人),男,博士,教授,博士生導(dǎo)師,dragon@seu.edu.cn. 國家自然科學(xué)基金資助項目(61404028). TN302 A 1001-0505(2016)05-0939-06 引用本文: 楊錦江,曹鵬,楊軍.面向分組密碼算法的高面積效率可重構(gòu)架構(gòu)[J].東南大學(xué)學(xué)報(自然科學(xué)版),2016,46(5):939-944. DOI:10.3969/j.issn.1001-0505.2016.05.007.4 結(jié)果和比較
5 結(jié)語