方 震，趙 偉，劉 勇

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

0 引言

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

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

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

1 可重構(gòu)S-box 存儲單元改進

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

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

圖1 重復(fù)RAM 塊存儲查找表

圖2 寄存器儲存查找表

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

圖3 4R/1W 存儲單元結(jié)構(gòu)

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

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

2 可重構(gòu)S-box 查找表改進

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

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

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

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

圖5 分層查找表結(jié)構(gòu)

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

圖6 可重構(gòu)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 對比實現(xiàn)

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

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

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

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

4 結(jié)論

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