面向序列密碼的高效能分層式比特抽取網絡設計研究

金 羽 戴紫彬 李 偉,2 馬 超

1(信息工程大學電子技術學院 河南 鄭州 450000) 2(復旦大學專用集成電路與系統國家實驗室 上海 201203)

面向序列密碼的高效能分層式比特抽取網絡設計研究

金 羽1戴紫彬1李 偉1,2馬 超1

1(信息工程大學電子技術學院 河南 鄭州 450000)2(復旦大學專用集成電路與系統國家實驗室 上海 201203)

針對序列密碼算法中抽取操作的可重構硬件實現資源消耗大的問題，通過研究序列密碼中非線性布爾函數的變量需求，基于Inverse Butterfly網絡提出一種高效能分層式比特抽取網絡-HHBN(High-efficiency hierarchical bit-extraction network)。與其他網絡進行對比，該網絡可一次抽取出含有重復變量的多組數據，且不僅其實際性能與靈活度優于其他大多網絡，面積消耗也遠小于同靈活度的Crossbar網絡。在Synopsys公司的Design Compiler進行了綜合，實驗結果表明與Crossbar網絡在不同位寬實現相比，其面積減少約20%～50%，這就減少了實現不同序列密碼算法抽取操作的可重構硬件資源消耗，從而提高了效能。

序列密碼 比特抽取 高效能 分層式 Inverse Butterfly

0 引 言

序列密碼具有實現簡單、加密速度快、密文傳輸中有限的錯誤擴散性等優點，因此在各種應用中越來越廣泛[1]。序列密碼算法主要由移位寄存器、反饋函數運算單元和密鑰流生成函數運算單元組成，其中反饋函數用于計算反饋移位寄存器的更新值，密鑰流生成函數用于計算最終的密鑰流[2]。

無論算法中反饋函數的計算和密鑰流的生成，都需要通過反饋抽頭將反饋移位寄存器的狀態位并行地抽取出來參與后續運算，而反饋抽頭根據算法的不同，不僅位置靈活多變且個數也各不相同[3]。如何將參與運算的一個或幾個反饋移位寄存器的若干狀態位高效、并行地抽取出來完成后續運算，成為制約序列密碼算法運算性能的關鍵因素之一。

而若使用靈活度高的Crossbar全互聯網絡[4]實現抽取操作，勢必會造成巨大的資源開銷。文獻[5]使用Inverse Butterfly網絡的抽取操作雖減少了所需資源但抽取結果順序固定且比特位的抽取不能重復，導致在含有重復變量的非線性布爾函數應用時并不夠靈活，Omega-flip[6]、Benes[7]與文獻[8]也存在同樣的問題。針對上述問題，本文通過對序列密碼抽取需求進行分析，在保證靈活度下，基于Inverse Butterfly網絡設計了高效率低資源的比特抽取網絡HHBN，對節約序列密碼算法硬件資源并提高效率具有重要現實意義。

1 序列密碼抽取操作需求分析

序列密碼算法中對密鑰流要求較高，要求其滿足相應的密碼學特征。一般，安全性能越高，其設計越復雜，在具體實現時越困難。算法中通常采用的方法是由多個線性移位寄存器和一個非線性組合函數即非線性布爾函數組成。因此大多數的序列密碼算法中，都包含非線性布爾函數，而其數據來源于移位寄存器數據的抽取，如圖1所示。

圖1 序列密碼算法中的抽取操作與非線性布爾函數

序列密碼算法中的非線性反饋函數、前饋函數以及鐘控函數的實現都可以歸屬于非線性布爾函數的實現，具體的實現為任意的多輸入布爾函數。本文對序列密碼算法中的非線性布爾函數進行了分析，如表1所示[9-11]，分別對非線性布爾函數的數據來源的位寬、變量個數、最高次數進行了總結歸納。

表1 各序列密碼算法中非線性布爾函數統計

可以看出，序列密碼非線性布爾函數中存在著大量抽取操作，但大多數序列密碼的變量個數在32個以內，而通過文獻[12]所設計的基于查找表的可重構非線性布爾函數NBF(Non_Line Boolean Function)單元為6變量實現形式，且6個變量均不相同。在所進行運算的變量個數大于6時可以通過多個NBF單元級聯實現。所以在進行狀態位抽取時，只需將所需數據抽取后，以6個變量為一組分別輸入至NBF單元。

2 比特級抽取操作研究

要實現抽取操作，考慮到面積資源消耗的問題，采用Inverse Butterfly網絡為基本網絡進行設計。圖2為一個8 bit位寬的Inverse Butterfly網絡，它可以通過改變各級switch開關狀態實現不同結點之間的連接，使系統具有自重構能力，從而靈活地完成數據的重新排列[13]。

圖2 Inverse Butterfly網絡

比特抽取操作即為從給定的控制序列Control中為“1”的控制位對應的輸入數據抽取出來并依次排在輸出序列的右側，控制序列為“0”的控制位所對應的數據逆序排在輸出序列的左側。位寬為N的Inverse Butterfly網絡，根據控制序列生成控制信息的算法[14]如下：

Input: Control //控制序列

Output: Control_bits //網絡的各級控制信息

(1) for (i = 1; i<=N-2; i++)

Sum[i]=Popcnt(Control{i:0})

//Popcnt為統計控制序列Control中[i:0]位的“1”

//個數

(2) RLTR(1k,M)

M= M mod 2i

C=11…1100…00 //K個1與K個零

RLTR_tmp=C <<< k //循環移位

RLTR = RLTR_tmp[2k-1:k]

(3) for (i=1 ; i<=lg(N); i++)

k=2i-1 //第i級的每個子蝶網絡的控制序列長度

for (j=1,j<= N/2i-1-1,j=j+2) {

q=j × k - 1

Control_bits(i)= RLTR(1k, Sum[q])

//依次輸出第 i 級中每個子蝶網絡的控制信息

}

其中，(1)為對控制序列的連加求和，將其從最低位到每一位為止的“1”的個數求出；(2)RLTR單元為左移反填充，可以視為11…1100…00(K個“1”與K個“0”)的左循環移位；通過執行(3)中的循環即可求出Inverse Butterfly網絡各級各子蝶網絡所需要的控制信息。這樣通過上述算法所給出的控制信息即可將所需要的對應比特位數據通過網絡抽取出來。

3 分層抽取網絡設計技術研究

3.1 分層式抽取網絡設計

通過第1節分析可以看出，大多數序列密碼算法所需變量在32個以內，單個變量可能會被多個NBF單元使用，而每個NBF單元需要至多6個的變量輸入，且這6個變量每個都不相同。

針對算法中非線性布爾函數的結構特點，對于應有的抽取網絡應滿足如下要求：

(1) 因非線性運算函數表達式差異較大且位寬不同，因此必須能實現多種位寬操作。

(2) 因同一運算因子可能會被多個NBF多次使用，因此必須支持單比特多次重復抽取。

(3) 因抽取位置不固定，必須支持任意位置的抽取。

本文以128 bit位寬的移位寄存器為例，若使用Crossbar網絡[4]，即128個128選1數據選擇器，雖然可以非常靈活地實現抽取操作，但對于資源的消耗很大。每一位均為128選1選擇器，即7級2選1數據選擇器組成，每一位就需要127個數據選擇器，則128 bit抽取N位就需要數量為127N的2選1數據選擇器。且因單個NBF單元所需變量各不相同，但該網絡的每一位的輸出均可能彼此相同，其硬件資源相對于功能需求而言會形成一種較大的浪費。

若直接使用Inverse Butterfly網絡實現抽取操作，雖然資源消耗較小，但其每位數據之間不會相同且輸出結果的順序固定，當使用多個NBF單元且有重復變量時其抽取結果無法直接提供給其進行運算。如圖3所示，要抽取出6、5、3、1、0的數據，其抽取結果順序必定為24765310，在實際使用時就需要使用多個該網絡或進行多次抽取才能實現，顯然在位寬較大時其靈活度并不適應非線性布爾函數單元具體的需求。而其他類似網絡如Benes網絡等也存在相同問題。

圖3 Inverse Butterfly網絡抽取

因此，本文通過研究非線性布爾函數的數據特點，基于Inverse Butterfly網絡提出一種高效能分層式比特抽取網絡-HHBN，如圖4其兩層結構主要分為兩層：

(1) 第一層從輸入128 bit數據中抽取32 bit，包含非線性布爾函數所需的全部變量，且變量之間不重復；

(2) 第二層子網絡從第一層抽取的32 bit中分別抽取出6 bit共6Nbit以供NBF單元使用，6 bit數本身不重復，但每個32-6 bit子網絡的輸入可以重復。

圖4 分層式抽取網絡

這樣對于不同非線性布爾函數時，都可保證一次抽取出所有NBF單元所需要的數據，這就在其靈活度滿足需求的前提下，大大減少抽取網絡所占用的資源。

3.2 分層式抽取子網絡設計

因為使用的Inverse Butterfly子網絡僅需完成128-32 bit與32-6 bit操作，為節約資源，可以對其結構進行優化。若以16-3 bit為例，如圖5所示，最后一級僅需要3 bit數據輸出，則最后一級原本8個switch即16個數據選擇器中僅需保留3個數據選擇器即可。3個數據選擇器需6個數據輸入，對應第二級保留6個數據器。16-3 bit的Inverse Butterfly網絡需要3+6+12+16=37個數據選擇器，而原本16-16 bit的網絡需要16×4=64個數據選擇器。

圖5 簡化后的16-3 bit Inverse Butterfly

總結規律得，位寬為m的Inverse Butterfly網絡，當僅輸出nbit(n

x=m×(log2m-a)+n×2a-1+n×2a-2+…+n×20=

m×(log2m-a)+n×(2a-1)

同理可得，128-32 bit的Inverse Butterfly網絡需要128×5+96=736個數據選擇器，32-6 bit的Inverse Butterfly需要32×2+42=106個數據選擇器。

據上述分析可知，若網絡第一層使用的128-32 bit的Inverse Butterfly網絡，第二層若使用5個32-6 bit網絡，則共使用736+5×106=1 266個數據選擇器。數據網絡相比于等效的128-30 bit的Crossbar網絡使用的127×30=3 810個數據選擇器個數減少約67%，而靈活度相應于非線性布爾函數的要求而言并無下降。

4 性能評估

下面將本文設計的網絡與其他文獻進行對比，位寬均為128-128 bit，因NBF設計原因，本文網絡采取位寬相近的128-126 bit，其結果如表2所示。

表2 不同方法的抽取資源占用

表2中第二列為實現所需要的2選1數據選擇器數量，第三列為網絡的級數，第四列則為是否支持重復的比特位抽取，第五列為抽取出21組含有公共變量的6 bit數據所需要通過網絡的次數。可以看出，Omega-flip、Inverse Butterfly、Benes與文獻[8]所提出的網絡雖面積小但均不支持重復的比特位抽取，在實際運用時需使用多個網絡并行放置或單個網絡進行多次抽取，這就變相增加了其資源消耗并降低了實際性能。而對比HHBN網絡與同樣支持重復比特位抽取的Crossbar網絡，雖級數增加，但理論面積減小約80%。

為更加客觀地評價本文所設計的網絡，在Synopsys公司的Design Compiler軟件上基于SMIC 65-nm工藝進行了邏輯綜合。綜合時環境參數設置為：最慢工藝角(ss)、最高溫度(125℃)、和最低電壓(1.08 V)。采用flatten優化策略，因Crossbar與本文網絡靈活度相近，且結構較為簡單，這里同時對其進行了編碼并綜合以進行比較，結果如表3所示。

表3 抽取網絡面積、延遲對比

表3中第一行為128-30bit的全置換Crossbar網絡，在SIMC 65 nm工藝下的約束為0.96 ns時，其面積為9 496.4 μm2；第二行為本文的HHBN網絡，在SMIC 65 nm工藝下其延遲為0.96 ns，面積為7 482.6 μm2。

若將抽取結果位寬擴展至6×21=126 bit，即HHBN第二層使用21個子網絡進行抽取，如表3中第三行所示，HHBN網絡在128-126 bit情況下，其延遲為1 ns，面積為20 495.5 μm2；表3中第四行為128-126 bit的Crossbar網絡在1 ns約束下面積為40 697.2 μm2。如圖6所示。

圖6 綜合后網絡面積對比

經上述分析可知，HHBN網絡不僅實際實現的效率上強于Omega-flip、Benes等網絡，且與Crossbar網絡相比面積大大減少，抽取30 bit時實際面積資源消耗減少約20%，抽取126 bit時實際面積減少約50%。雖在延遲上不如Crossbar網絡，但因選擇器本身延遲較低，對算法整體的影響并不會很大，這就有效減少了抽取網絡所占用的資源，提高了抽取網絡的效能。

5 結 語

本文通過分析序列密碼算法中狀態位抽取后進行的非線性布爾函數及非線性布爾函數硬件單元的實際需求，基于Inverse Butterfly網絡提出了一種高效能的分層式抽取網絡(HHBN)。并針對實際的數據需求對網絡中各子網絡進行了優化，使其在可以靈活高效地抽取非線性布爾函數所需求的數據的同時，大大減少了抽取操作所需的面積資源，對提高序列密碼可重構實現的效率與節約其硬件資源消耗具有重要意義。

[1] Seward B R,Aaron R,Shiffman A.Localized bioimpedance analysis in the evaluation of neuromuscular disease[J].Muscle & Nerve,2002,25(3):390-397.

[2] 陳濤,馬超,羅興國,等.面向序列密碼的比特級抽取指令研究與設計[J].信息工程大學學報,2015(1):123-128.

[3] 徐建博,戴紫彬,李偉,等.面向序列密碼的抽取與插入單元可重構設計研究[J].電子技術應用,2011,37(7):65-67.

[4] 曲英杰.可重組密碼邏輯的設計原理[D].北京:北京科技大學,2003.

[5] Yang X,Lee R B.Fast Subword Permutation Instructions Using Omega and Flip Network Stages[C]//IEEE International Conference on Computer Design:Vlsi in Computers & Processors.IEEE Computer Society,2000:15-22.

[6] Shi Z J.Bit permutation instructions:architecture,implementation,and cryptographic properties[M].Princeton University,2004.

[7] Shan W W,Chen X,Yinchao L U,et al.A Novel Combinatorics-Based Reconfigurable Bit Permutation Network and Its Circuit Implementation[J].Chinese Journal of Electronics,2015,24(3):513-523.

[8] Hilewitz Y,Lee R B.A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations[J].IEEE Transactions on Computers,2009,58(8):1035-1048.

[9] 張玉安,馮登國.歐洲流密碼加密標準的競評[J].信息安全與通信保密,2003(3):38-41.

[10] 劉運毅,覃團發,倪皖蓀,等.簡評ECRYPT的候選流密碼算法(中)[J].信息安全與通信保密,2006(8):26-28.

[11] Robshaw M J B.Stream Ciphers[R].RSA Laboratories Technical Report,1995.

[12] 紀祥君,陳迅,戴紫彬,等.一種改進的非線性布爾函數硬件設計與實現[J].計算機應用與軟件,2014,31(7):283-285,302.

[13] Nassimi D,Sahni S.A Self-Routing Benes Network and Parallel Permutation Algorithms[J].IEEE Transactions on Computers,1981,C-30(5):332-340.

[14] 馬超,戴紫彬,常忠祥,等.高速可重構插入與抽取單元設計[J].計算機應用與軟件,2013,30(10):326-330.

DESIGNANDRESEARCHOFHIGH-EFFICIENCYHIERARCHICALBIT-EXTRACTIONNETWORKFORSTREAMCIPHER

Jin Yu1Dai Zibin1Li Wei1,2Ma Chao1

1(InstitutionofElectronicTechnology,InformationEngineeringUniversity,Zhengzhou450000,Henan,China)2(StateKeyLabofASICandSystem,FudanUniversity,Shanghai201203,China)

Aiming at the problems in stream cipher algorithm that the high areas of the reconfigurable hardware implementation of bit-extraction, we propose a high-efficiency hierarchical bit-extraction network based on the Inverse Butterfly network named HHBN(High-efficiency hierarchical bit-extraction network), through the studying of the non-lineal boolean function in stream cipher algorithm. Compared with other networks, the proposed network can extract multiple sets data with common variables. The actual performance and flexibility of HHBN are better than most other networks, and area is far less than the Crossbar network that has same flexibility with HHBN. We integrated the design compiler software at Synopsys company. The results show that compared with the Crossbar network in different width, HHBN reduce the area about 20%～50%, which reduces the resources consumption of extraction operation for different stream cipher algorithm, so as to improve the efficiency of it.

Stream cipher Bit-extraction High-efficiency Hierarchical Inverse Butterfly

2017-03-14。國家自然科學基金項目(61404175)。金羽，碩士生，主研領域：安全專用芯片設計。戴紫彬，教授。李偉，副教授。馬超，博士生。

TP3

A

10.3969/j.issn.1000-386x.2017.12.032