一種面向密碼算法的輕量級可重構(gòu)陣列

張宇帆

（上海交通大學(xué)電子信息與電氣工程學(xué)院，上海200240）

0 引言

密碼算法是關(guān)乎安全隱私問題的重要算法之一，各個國家都擁有各自獨立的密碼算法標(biāo)準(zhǔn)，例如：美國所使用的DES/AES[1]對稱加密算法、SHA2/SHA3[2]系列散列算法、歐盟所使用IDEA算法、中國所使用的SM4[3]對稱算法、SM3散列算法[4]，為各種各樣的密碼算法設(shè)計擴(kuò)展指令集或?qū)Ｓ眉铀匐娐肥且豁椄叱杀镜墓ぷ鳌?/p>

可重構(gòu)處理器結(jié)合了通用處理器（GPP）的靈活性以及專用集成電路（ASIC）的性能結(jié)合到一起，可重構(gòu)電路在制造之后，可重構(gòu)的處理陣列的功能可以通過配置信息（即控制運算單元功能的二進(jìn)制信息）動態(tài)地或部分地更改。配置完成后，可重構(gòu)電路可以像ASIC電路一樣，在數(shù)據(jù)流的驅(qū)動下，在陣列中執(zhí)行多種計算?？芍貥?gòu)電路的運算效率要遠(yuǎn)高于指令驅(qū)動的處理器[5]，同時具有遠(yuǎn)高于ASIC電路的靈活性。

對稱密碼算法、散列算法這類密碼算法，普遍采用多輪迭代的加密方法、每輪迭代采用十分相似的運算步驟、具有類似的粗粒度算子，是一類具有高度確定性的算法。這些顯著特性于可重構(gòu)電路架構(gòu)高度相符，因此出現(xiàn)了許多針對密碼算法的可重構(gòu)密碼加速電路[6,7,8]?，F(xiàn)有的可重構(gòu)密碼處理器與現(xiàn)場可編程邏輯門陣列（FPGA）的細(xì)粒度配置不同，可重構(gòu)密碼電路主要采用粗粒度的重構(gòu)數(shù)據(jù)通路，減少了大量的配置信息，實現(xiàn)配置信息的高速切換。

本文提出了一種面向?qū)ΨQ加密和散列算法的動態(tài)可重構(gòu)密碼加速器，采用4×4的PE（Processing Unit）陣列結(jié)構(gòu)，陣列結(jié)構(gòu)根據(jù)常用對稱密碼算法和哈希散列函數(shù)算法的基本操作和結(jié)構(gòu)設(shè)計，由于密碼算法之間高度的相似性，該體系架構(gòu)也可適用于未來的密碼算法。為了實現(xiàn)更高的面積效率，本文提出了兩點改進(jìn)方案，為密碼算法設(shè)計了可重構(gòu)的存儲器陣列，4個存儲器可以分別配置為集中式SBOX查找表或存儲器，替代了目前主流的PE內(nèi)嵌查找表算子和寄存器堆的架構(gòu)設(shè)計[8]，大幅提升面積效率。其次設(shè)計了配置/常量混合寄存器堆，減少散列運算時的資源冗余提高面積效率。

1 密碼算法的主要特征

在稱密碼算法和哈希散列算法是確保信息安全的重要手段之一，算法的安全性取決于密鑰的安全性，對稱和哈希算法通常通過輪運算的多次迭代來實現(xiàn)，輪次映射的性能直接影響算法的實現(xiàn)性能，分組和哈希散列運算密碼的計算普遍具有以下特點：①輪內(nèi)運算單向數(shù)據(jù)流通性，②每一輪運算具有高度相似性，③輪間運算具有依賴關(guān)系；同時對稱密碼算法和哈希算法也具有相同的運算粒度和算子。表1列出了常用的密碼算法的基本操作類型和處理粒度。

表1 常用密碼算法算子統(tǒng)計

根據(jù)對幾種常用的密碼算法進(jìn)行統(tǒng)計，我們可以找出一些規(guī)律。首先，密碼算法的運算操作均為無符號整型運算，沒有浮點和定點類型。其次密碼算法的基本操作主要為邏輯操作、移位、S盒置換、bit置換、模加/減、有限域乘法。最后密碼算法的操作粒度通常普遍在32bit，AES和DES中的S盒置換為8bit細(xì)粒度操作。我們可以針對密碼算法的這類特性設(shè)計能夠加速算法的可重構(gòu)電路，兼顧算法的公共特性，同時提供更高的運算性能。

2 粗粒度可重構(gòu)密碼處理器

2.1 整體架構(gòu)

可重構(gòu)密碼陣列是一種用于密碼數(shù)據(jù)流運算的架構(gòu)，是密碼算法映射的硬件基礎(chǔ)，可重構(gòu)電路主要包括運算陣列、存儲單元、數(shù)據(jù)I/O和可重構(gòu)通路四個部分。

圖1 粗粒度可重構(gòu)密碼處理器總體架構(gòu)

本文提出的可重構(gòu)架構(gòu)如圖1，可重構(gòu)密碼處理器中包含一個4×4的運算單元（PE）陣列、4個獨立的存儲器（RM），以及帶有常量寄存器堆的行間互聯(lián)模塊（RCR）。架構(gòu)采用分布式配置存儲策略，運算單元、可重構(gòu)存儲器、常量寄存器堆都擁有自己的配置存儲空間；陣列運算由數(shù)據(jù)有效令牌進(jìn)行時序控制與同步，數(shù)據(jù)的有效令牌由輸入輸出FIFO生成，有效令牌跟隨數(shù)據(jù)一起流動進(jìn)入輸出FIFO或?qū)懭氪鎯ζ骱罅钆葡А?/p>

4×4的PE陣列可以通過存儲器以及行間互聯(lián)結(jié)構(gòu)的動態(tài)配置將各種密碼算法映射為包含多級PE單元的流水線結(jié)構(gòu)，圖中的虛線箭頭則代表額外的跨行互聯(lián)結(jié)構(gòu)，每一個箭頭包含了四個跨行傳遞的PE輸出結(jié)果。

2.2 運算單元（Processing Element）

可重構(gòu)運算單元的設(shè)計主要來自于對密碼算法的基本操作分析，本文提出的運算單元（PE）為32bit的粗粒度數(shù)據(jù)位寬，為靈活映射密碼算法，設(shè)計了五種算子：①邏輯運算單元（LTU）；②模加單元（ADM）；③移位運算單元（SRU）；④置換單元（PU）；⑤伽羅華乘法單元（GM）。每個PE具有4輸入2輸出的數(shù)據(jù)通路，兩個輸出均提供了異或操作算子，根據(jù)配置信息進(jìn)行調(diào)整。兩個32bit輸出路徑可以根據(jù)配置信息實現(xiàn)1-4級寄存器輸出。

圖2 PE算子結(jié)構(gòu)

圖2（a）為邏輯樹運算單元，由6個基本邏輯運算塊LU組成一個樹形邏輯運算單元，每個基本邏輯塊可以實現(xiàn)取反、異或、與、或等基本邏輯功能，邏輯樹運算單元可以將哈希算法中復(fù)雜的功能運算映射到一個PE中，例如SHA256中的Maj函數(shù)：

圖2（b）模加運算單元由兩級32bit加法器組成，根據(jù)配置信息進(jìn)行兩操作數(shù)加法或三操作數(shù)加法，支持模32/16/8和模231-1。圖2（c）為移位運算單元，由六個移位器組成，針對散列算法的Gama函數(shù)進(jìn)行了特定優(yōu)化，可以大幅減少哈希算法所需要的PE個數(shù)，支持復(fù)雜的多輸入循環(huán)移位操作映射：

圖2（d）為bit級置換運算單元，通過配置Bense網(wǎng)絡(luò)實現(xiàn)64bit間任意bit互換，主要為DES算法以及類似算法中的P盒置換而設(shè)計。圖2（e）為伽羅華域多項式乘法運算單元，Mul模塊中的伽羅華乘法器為8bit細(xì)粒度運算。

本文利用TSMC 28nm工藝庫進(jìn)行邏輯綜合功耗面積評估，時鐘約束為1GHz。

表2 PE算子綜合結(jié)果

置換單元的大小大于其他單元的面積總和，置換運算單元和伽羅華乘法運算單元全部都用于對稱密碼算法，因此將置換運算單元和伽羅華乘法運算單元采用異構(gòu)PE的方式排布，第一行和第四行采用帶有置換運算單元、邏輯樹運算單元、模加運算單元和移位運算單元的PE，第二行和第三行則采用帶有伽羅華乘法運算單元、邏輯樹運算單元、模加運算單元、移位運算單元的PE。異構(gòu)PE的陣列方式可以為我們節(jié)省約27.9%的PE陣列面積。

PE單元采用寄存器輸入輸出，輸入數(shù)據(jù)改變后數(shù)據(jù)會廣播到每個PE的4個算子，未被選中的3個算子會產(chǎn)生不期望的翻轉(zhuǎn)功耗；引入操作數(shù)隔離的優(yōu)化方案在單個PE上實現(xiàn)了34.4%的功耗優(yōu)化。

2.3 可重構(gòu)行互聯(lián)（Reconfigurable Connect Row）

可重構(gòu)互聯(lián)模塊決定了可重構(gòu)處理器效率和靈活性，本文提出的可重構(gòu)行互聯(lián)網(wǎng)絡(luò)RCR針對密碼算法的數(shù)據(jù)單向流通性進(jìn)行設(shè)計，同時行互聯(lián)模塊還負(fù)責(zé)接收存儲器、常量寄存器堆以及輸入輸出FIFO的數(shù)據(jù)來源。行互聯(lián)RCR模塊采用Crossbar結(jié)構(gòu)，可以分為四個部分。

圖3展示了一個PE的一個輸入源的RCR互聯(lián)結(jié)構(gòu)，圖中的一個箭頭表示一個32bit的數(shù)據(jù)來源。PE_ROW_OUT模塊，接收上一行4個PE的八個輸出，對于第一行PE則接收四個輸入FIFO和四個輸出FIFO的數(shù)據(jù)來源。LATCH/MEM模塊采用異構(gòu)的功能設(shè)計，PE的4個輸入所對應(yīng)的該模塊采集不同的輸入源，PE的兩個輸入口通過該模塊接收存儲器的4個輸出，另外兩個輸入則接收常量寄存器堆的4個輸出。Y_IN模塊負(fù)責(zé)接收跨行傳輸?shù)臄?shù)據(jù)，第一行的4個RCR接收的是第三行PE的跨行數(shù)據(jù)，第二行的4個RCR則是接收最后一行PE的跨行數(shù)據(jù)，第三行的4個RCR則是接收輸入FIFO的數(shù)據(jù)源，第四行的4個RCR接收第二行的PE的跨行數(shù)據(jù)。最后的16個數(shù)據(jù)源通過一個16選1的選擇器根據(jù)配置信息進(jìn)行篩選，將結(jié)果傳輸給對應(yīng)的PE輸入端口。

圖3 RCR互聯(lián)結(jié)構(gòu)

2.4 可重構(gòu)存儲器（Reconfigurable Memory）

本文的可重構(gòu)密碼加速器擁有4組32bit位寬256深度的可重構(gòu)存儲器，存儲器由16個8bit偽雙口DRAM組成，支持同時讀寫，讀寫流水化。本文的可重構(gòu)存儲器都有用單獨的讀通道和寫通道配置信息控制器，寫通道的地址由配置信息生成，通過配置單元進(jìn)行計算；讀通道的存儲器訪問地址可以通過配置信息生成，也可以來源于PE陣列的PE輸出。為了減少互聯(lián)資源開銷，PE陣列到存儲器的互聯(lián)網(wǎng)絡(luò)進(jìn)行了優(yōu)化設(shè)計。

圖4下方為可重構(gòu)存儲器與PE陣列的寫數(shù)據(jù)通道，R1~R3代表每一列PE的8個輸出數(shù)據(jù)，根據(jù)配置信息每列選取一個數(shù)據(jù)送入下級互聯(lián)，第二級D4由4個地址譯碼器和四個寫通道組成通過配置信息內(nèi)含的地址信息和將每一列與存儲器交互的PE輸出數(shù)據(jù)寫入對應(yīng)的存儲器之中，每一個通道均可以寫入到任意一個存儲器的任意一個地址，第一列PE具有最高優(yōu)先級。

圖4 可重構(gòu)存儲器

圖4上方為可重構(gòu)存儲器和PE陣列的讀數(shù)據(jù)通道，箭頭0代表PE的第0列和第1列的16個輸出，箭頭1代表PE的第2列和第3列的16個輸出。根據(jù)配置信息由4個16選1的選擇器選出4個數(shù)據(jù)送入到第二級互聯(lián)模塊。第二級包含4個地址譯碼器和一個可旁路的128bit Bense互換網(wǎng)絡(luò)，可以根據(jù)配置信息將任意一個MEM配置為查找表模式，查找表模式的讀通道會將PE數(shù)據(jù)通過Bense互換網(wǎng)絡(luò)送入MEM中，可以實現(xiàn)16個8bit的并行查表，方便映射對稱算法中的非線性代換操作。

讀操作產(chǎn)生的數(shù)據(jù)會通過一個可旁路的Bense網(wǎng)絡(luò)轉(zhuǎn)換后廣播到每行RCR的副本寄存器中，為RCR提供存儲器數(shù)據(jù)來源。

2.5 可重構(gòu)配置、常量鎖存器堆

PE單元內(nèi)含的Bense 64bit置換單元，需要352bit配置信息進(jìn)行控制，而本文設(shè)計的其他功能單元，只需要32bit就可以實現(xiàn)重構(gòu)配置；算法映射時，一部分算法并不需要Bense置換網(wǎng)絡(luò)這一個硬件資源，因此本文將Bense置換網(wǎng)絡(luò)的配置存儲空間進(jìn)行了重新設(shè)計。為減少動態(tài)切換的大位寬數(shù)據(jù)開銷，將Bense配置信息和密碼算法運算需要的常量通過靜態(tài)配置的方式存儲到常量存儲器堆中。

靜態(tài)配置在整個陣列運算的時候一般處于保持狀態(tài)，所以將配置信息用鎖存器存儲，可以實現(xiàn)45%的面積優(yōu)化。鎖存器堆會存儲四組Bense網(wǎng)絡(luò)信息，PE被映射為置換操作時，會根據(jù)配置信息的2bit索引選取對應(yīng)的配置信息。常量鎖存器堆還有四個位寬均為32bit的只讀端口，每一個端口讀出對應(yīng)16個鎖存器中的一個數(shù)據(jù)。鎖存器堆的四個讀數(shù)據(jù)端口廣播到RCR模塊中，作為PE單元的次要輸入源之一。

3 架構(gòu)實現(xiàn)及性能分析

使用Verilog語言實現(xiàn)本文提出的粗粒度可重構(gòu)密碼處理器架構(gòu)，使用Cadence Genus工具基于TSMC28nm工藝庫進(jìn)行邏輯綜合；配置信息通過手動編程實現(xiàn)對應(yīng)的算法功能。

表3 芯片參數(shù)以及性能

本文所提出的架構(gòu)對于AES-ECB模式的非反饋加密算法能夠?qū)崿F(xiàn)12Gbps的加密速率，SM4由于需要更多的迭代輪所以性能低于AES；對于帶有反饋的哈希散列函數(shù)仍能維持較高的性能水平。

該架構(gòu)使用輕量級的設(shè)計策略，采用4×4的PE陣列規(guī)模，在執(zhí)行AES-ECB算法時，擁有略強(qiáng)于Anole的面積效率；由于對一些哈希算法的復(fù)雜操作進(jìn)行了優(yōu)化設(shè)計，SHA256算法的面積效率遠(yuǎn)高于同類型的可重構(gòu)陣列。

表4 性能對比

圖5 歸一化面積效率比較

圖5為歸一化后的面積效率柱狀圖，柱形代表AES算法的面積效率，對應(yīng)為左邊的坐標(biāo)軸，本文提出的架構(gòu)對比128個PE陣列的Anole架構(gòu)實現(xiàn)了10%的效率提升；折線代表SHA256算法對應(yīng)的面積效率，可以看到本文的架構(gòu)對比160個PE陣列的Cryptor架構(gòu)面積效率提升了180%，實現(xiàn)2.8倍的面積效率。

4 結(jié)語

本文提出了一種面向?qū)ΨQ和哈希散列算法的輕量級粗粒度可重構(gòu)陣列，通過軟硬件協(xié)同設(shè)計對硬件結(jié)構(gòu)進(jìn)行針對性優(yōu)化，相比以往的大規(guī)模可重構(gòu)密碼陣列具有更高的面積效率，同時還保證了較高的算法性能，適用于一些的嵌入式領(lǐng)域。