一種面向密碼算法的輕量級可重構陣列

張宇帆

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

0 引言

密碼算法是關乎安全隱私問題的重要算法之一，各個國家都擁有各自獨立的密碼算法標準，例如：美國所使用的DES/AES[1]對稱加密算法、SHA2/SHA3[2]系列散列算法、歐盟所使用IDEA算法、中國所使用的SM4[3]對稱算法、SM3散列算法[4]，為各種各樣的密碼算法設計擴展指令集或專用加速電路是一項高成本的工作。

可重構處理器結合了通用處理器（GPP）的靈活性以及專用集成電路（ASIC）的性能結合到一起，可重構電路在制造之后，可重構的處理陣列的功能可以通過配置信息（即控制運算單元功能的二進制信息）動態地或部分地更改。配置完成后，可重構電路可以像ASIC電路一樣，在數據流的驅動下，在陣列中執行多種計算。可重構電路的運算效率要遠高于指令驅動的處理器[5]，同時具有遠高于ASIC電路的靈活性。

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

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

1 密碼算法的主要特征

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

表1 常用密碼算法算子統計

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

2 粗粒度可重構密碼處理器

2.1 整體架構

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

圖1 粗粒度可重構密碼處理器總體架構

本文提出的可重構架構如圖1，可重構密碼處理器中包含一個4×4的運算單元（PE）陣列、4個獨立的存儲器（RM），以及帶有常量寄存器堆的行間互聯模塊（RCR）。架構采用分布式配置存儲策略，運算單元、可重構存儲器、常量寄存器堆都擁有自己的配置存儲空間；陣列運算由數據有效令牌進行時序控制與同步，數據的有效令牌由輸入輸出FIFO生成，有效令牌跟隨數據一起流動進入輸出FIFO或寫入存儲器后令牌消失。

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

2.2 運算單元（Processing Element）

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

圖2 PE算子結構

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

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

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

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

表2 PE算子綜合結果

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

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

2.3 可重構行互聯（Reconfigurable Connect Row）

可重構互聯模塊決定了可重構處理器效率和靈活性，本文提出的可重構行互聯網絡RCR針對密碼算法的數據單向流通性進行設計，同時行互聯模塊還負責接收存儲器、常量寄存器堆以及輸入輸出FIFO的數據來源。行互聯RCR模塊采用Crossbar結構，可以分為四個部分。

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

圖3 RCR互聯結構

2.4 可重構存儲器（Reconfigurable Memory）

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

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

圖4 可重構存儲器

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

讀操作產生的數據會通過一個可旁路的Bense網絡轉換后廣播到每行RCR的副本寄存器中，為RCR提供存儲器數據來源。

2.5 可重構配置、常量鎖存器堆

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

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

3 架構實現及性能分析

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

表3 芯片參數以及性能

本文所提出的架構對于AES-ECB模式的非反饋加密算法能夠實現12Gbps的加密速率，SM4由于需要更多的迭代輪所以性能低于AES；對于帶有反饋的哈希散列函數仍能維持較高的性能水平。

該架構使用輕量級的設計策略，采用4×4的PE陣列規模，在執行AES-ECB算法時，擁有略強于Anole的面積效率；由于對一些哈希算法的復雜操作進行了優化設計，SHA256算法的面積效率遠高于同類型的可重構陣列。

表4 性能對比

圖5 歸一化面積效率比較

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

4 結語

本文提出了一種面向對稱和哈希散列算法的輕量級粗粒度可重構陣列，通過軟硬件協同設計對硬件結構進行針對性優化，相比以往的大規模可重構密碼陣列具有更高的面積效率，同時還保證了較高的算法性能，適用于一些的嵌入式領域。