一種基于Hierarchy LUT 的可重構S-box 實現方法

方 震，趙 偉，劉 勇

（中國電子科技集團公司第五十八研究所，江蘇 無錫 214035）

0 引言

通信領域中，高吞吐量的加密和解密技術一直是研究的重點。分組密碼算法在高速、海量數據加密解密應用中廣泛使用。為使分組密碼達到高的性能，通常采用硬件加速。專用集成電路（ASIC）雖然性能高，但是在算法切換、參數可變的應用中缺乏靈活性?？芍貥嫾軜嫾夹g則可在一定程度上彌補短板，平衡高性能和靈活性，有利于分組密碼算法硬件加速應用，進而通過優化分組密碼算法實現。分組密碼算法主要包括邏輯運算、算數運算[1]、置換處理[2]、字節替換（S-box）[2-3]。S-box作為分組密碼算法的非線性處理單元，在分組密碼算法中發揮著重要的作用。一般而言，不同的分組密碼算法，S-box 的結構都有所不同，這也是分組密碼算法的瓶頸所在。因而S-box 的性能和面積的優化成為了分組密碼算法主要研究目標。

S-box 的構建方法通常有兩種：一是基于邏輯結構的構建方法，二是基于查找表結構的方法。第一種方法主要基于真值表生成或基于生成規則的邏輯運算。例如 Product of Sums(POS)[4]、Positive Polarity Reed-Muller form(PPRM)[5]、Binary Decision Diagram(BDD)[6]采用兩級邏輯實現，或者采用GF(28)、GF((24)2[7]或者GF(((22)2)2)[8]有限域運算邏輯實現。雖然邏輯構建實現占用資源較少，但缺乏靈活性，不能適配不同的S-box 結構。此外S-box 綜合時會產生很大的累積資源占用。第二種方法基于查找表。通常將存儲單元用于Look Up Table(LUT)，存儲字節替換表。由于存儲單元中的字節替換表可以很方便地更新，這種方法被廣泛應用于分組密碼的可重構實現[2-3,9-10]。相比與基于邏輯的方法，其缺點是需要占用更多的硬件資源，特別是在支持幾種不同的S-box 操作時[3]。為了減少面積的資源消耗，文獻[2]提出由多個子系統組成存儲系統，謀求性能和資源的平衡，實用效果有限。

基于上述問題，本文提出了一種4R/1W 存儲結構，并基于此存儲單元構建分層查找表（Hierarchy LUT），以節省資源消耗，提高面積利用效率。

1 可重構S-box 存儲單元改進

在基于查找表的實現中，S-box 的數據信息存儲在一個基本的存儲單元中。這些存儲單元的數量會隨著輸入輸出位寬、并行端口數量的增加而急劇增大。因此需要分析影響存儲單元開銷的因素。

例如，一個經典的分組密碼算法Advanced Encryp‐tion Standard(AES)，每輪需要16 個相同的S-box，傳統的S-box 查找表的實現如圖1 所示，16 個RAM 存儲塊用來存儲相同的查找表信息，每個RAM 塊都有獨立的讀寫端口。因為每個RAM 塊存儲的信息都一樣，可以共用輸入端口，將其換成圖2 所示的結構，用觸發器來存儲查找表信息。這些觸發器存儲結構共用一個輸入端口，而輸出端口則通過多路選擇器選擇輸出。

圖1 重復RAM 塊存儲查找表

圖2 寄存器儲存查找表

基于此思路，本文提出一個定制的4R/1W(4 個讀端口，1 個寫端口)存儲單元，用來減少整體存儲的面積開銷。如圖3 所示，該電路基于6 管SRAM 結構，包括1 對寫信號線（WBL 和WBLB）以及4 個單端的讀信號線（RBL_1、RBL_2、RBL_3、RBL_4）。每個讀信號線都由兩個NMOS 組成，以M7 和M8 組成的讀端口為例，M7的漏極連接M8 的源極，M8 的漏極接到讀信號端口。其他三個讀端口結構相同。這種存儲結構可以同時接收4路彼此獨立的讀信號，獲取4 個地址的數據，而無需額外例化3 個存儲單元，因而有很高的存儲密度。

圖3 4R/1W 存儲單元結構

用來存儲S-box 的RAM 存儲單元所占用的面積占據總面積的相當大的比重。以AES 算法為例，盡管IP vendors提供的RAM 存儲器經過優化，占用很少的資源，但在AES算法中需要16 個RAM 單元存儲S-box，這些累計存儲單元面積開銷則不容忽略，如圖4 所示。通過主從觸發器搭建的存儲的結構雖然能夠減少重復的存儲面積的占用，但是其輸出端口中的選擇器占用的資源卻很大。而采用本文提出的4R/1W 結構的存儲器則占用很小的資源開銷。

圖4 各類存儲在電路中面積開銷

2 可重構S-box 查找表改進

S-box 有四個主要的特性，分別為輸入位寬、輸出位寬、S-box 的數量和每輪并行端口數量。不同的S-box 結構，四個特性有著較大的差異。為便于表述，在本文中定義了AW、DW、N、m四個參數：AW 為地址最大位寬，DW 為數據最大位寬，N為最大的S-box 數量，m為最大并行端口數量。表1 展示了幾個常用的分組密碼加密算法，其中RU 參數表征加解密處理的性能[2]。分組密碼算法的S-box 結構不一樣，其對應的一些參數也各不相同。

表1 不同算法中S-box 性能及特性表

當AW、DW、N和m四個參數變化時，分組密碼算法的面積開銷大有不同。如果只有一個讀端口，則會大大增加面積的開銷。為盡可能減小面積的開銷，適當增大可讀的端口數量、AW 和DW。但要注意，因為讀寫控制邏輯會占用一定的資源，過多的讀寫端口同樣會引起面積開銷增大。

基于上節提出的4R/1W 存儲單元，本節提出一個分層查找表Hierarchy LUT，如圖5 所示。Hierarchy LUT包括4 個32 端口存儲器以及輸入輸出控制邏輯。其中32 端口的存儲器由8 個4R/1W 存儲單元組成，它們共用一個寫數據線。

圖5 分層查找表結構

Hierarchy LUT 可以根據S-box 的結構來配置重構輸入輸出位寬，進而重構電路。根據輸入輸出的位寬，可以提供6 種不同的查找表模式，如圖6 所示。

圖6 可重構S-box 查找表模式

Mode1：工作于4 個256×8 的多端口模式。

Mode2：工作于2 個256×16 的多端口模式。

Mode3：工作于1 個512×16 的多端口模式。

Mode4：工作于1 個256×32 的多端口模式。

Mode5：工作于1 個1024×8 的多端口模式。

Mode6：工作于2 個512×8 的多端口模式。

3 對比實現

本文在40 nm CMOS 工藝下，通過Synopsys IC com‐piler 工具進行綜合，實現Hierarchy LUT 構造可重構Sbox，結果如表2 所示，面積利用率為1.724。與之對比的是基于Table Lookup Unit(TLU)[2]和Memory Sharing[3]的可重構S-box 結構。

表2 S-box 面積利用率對比表

基于TLU 結構的S-box 是可重構加解密處理器的一個主要部分。為了提供并行的數據端口，TLU 結構提供比較大的輸入輸出位寬，存儲深度達1 024，其基本結構是由單端口的存儲單元組成的。本文提出的基于Hier‐archy LUT 結構的S-box，減少了存儲器的冗余，具有較高的存儲密度，與TLU 結構相比，面積利用效率從1.136提高到1.724，性能提升51.76%。

基于Memory Sharing[3]觸發器結構的可重構S-box，適用于AES、DES 及Serpent 的算法。該結構有16 個端口，其占用的面積很小，但是此結構不夠靈活，且并行度不高，最大輸入輸出位寬為8 位，而且在數量多的端口情況下，因其端口數據選擇器控制占用較多的資源，面積會迅速增大。與之相比，本文提出的基于Hierarchy LUT 結構的S-box，面積利用效率從1.613 提高到1.724，性能提升6.88%。

4 結論

本文提出了一種4R/1W 存儲結構，構建一種分層的查找表結構（Hierarch LUT），在40 nm CMOS 工藝下，實現了可重構S-box 設計。與Table Lookup Unit (TLU)和Memory Sharing 觸發器的可重構方案提出的結構相比，本文基于Hierarchy LUT 結構的可重構S-box 面積利用率得到有效改善，利用效率分別提高51.76% 和6.88%。