金 羽 戴紫彬 李 偉,2 馬 超

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

面向序列密碼的高效能分層式比特抽取網(wǎng)絡(luò)設(shè)計研究

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

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

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

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

0 引 言

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

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

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

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

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

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

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

表1 各序列密碼算法中非線性布爾函數(shù)統(tǒng)計

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

2 比特級抽取操作研究

要實現(xiàn)抽取操作，考慮到面積資源消耗的問題，采用Inverse Butterfly網(wǎng)絡(luò)為基本網(wǎng)絡(luò)進行設(shè)計。圖2為一個8 bit位寬的Inverse Butterfly網(wǎng)絡(luò)，它可以通過改變各級switch開關(guān)狀態(tài)實現(xiàn)不同結(jié)點之間的連接，使系統(tǒng)具有自重構(gòu)能力，從而靈活地完成數(shù)據(jù)的重新排列[13]。

圖2 Inverse Butterfly網(wǎng)絡(luò)

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

Input: Control //控制序列

Output: Control_bits //網(wǎng)絡(luò)的各級控制信息

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

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

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

//個數(shù)

(2) RLTR(1k,M)

M= M mod 2i

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

RLTR_tmp=C <<< k //循環(huán)移位

RLTR = RLTR_tmp[2k-1:k]

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

k=2i-1 //第i級的每個子蝶網(wǎng)絡(luò)的控制序列長度

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

q=j × k - 1

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

//依次輸出第 i 級中每個子蝶網(wǎng)絡(luò)的控制信息

}

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

3 分層抽取網(wǎng)絡(luò)設(shè)計技術(shù)研究

3.1 分層式抽取網(wǎng)絡(luò)設(shè)計

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

針對算法中非線性布爾函數(shù)的結(jié)構(gòu)特點，對于應(yīng)有的抽取網(wǎng)絡(luò)應(yīng)滿足如下要求：

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

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

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

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

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

圖3 Inverse Butterfly網(wǎng)絡(luò)抽取

因此，本文通過研究非線性布爾函數(shù)的數(shù)據(jù)特點，基于Inverse Butterfly網(wǎng)絡(luò)提出一種高效能分層式比特抽取網(wǎng)絡(luò)-HHBN，如圖4其兩層結(jié)構(gòu)主要分為兩層：

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

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

圖4 分層式抽取網(wǎng)絡(luò)

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

3.2 分層式抽取子網(wǎng)絡(luò)設(shè)計

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

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

總結(jié)規(guī)律得，位寬為m的Inverse Butterfly網(wǎng)絡(luò)，當僅輸出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網(wǎng)絡(luò)需要128×5+96=736個數(shù)據(jù)選擇器，32-6 bit的Inverse Butterfly需要32×2+42=106個數(shù)據(jù)選擇器。

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

4 性能評估

下面將本文設(shè)計的網(wǎng)絡(luò)與其他文獻進行對比，位寬均為128-128 bit，因NBF設(shè)計原因，本文網(wǎng)絡(luò)采取位寬相近的128-126 bit，其結(jié)果如表2所示。

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

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

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

表3 抽取網(wǎng)絡(luò)面積、延遲對比

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

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

圖6 綜合后網(wǎng)絡(luò)面積對比

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

5 結(jié) 語

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

[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] 陳濤,馬超,羅興國,等.面向序列密碼的比特級抽取指令研究與設(shè)計[J].信息工程大學(xué)學(xué)報,2015(1):123-128.

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

[4] 曲英杰.可重組密碼邏輯的設(shè)計原理[D].北京:北京科技大學(xué),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] 劉運毅,覃團發(fā),倪皖蓀,等.簡評ECRYPT的候選流密碼算法(中)[J].信息安全與通信保密,2006(8):26-28.

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

[12] 紀祥君,陳迅,戴紫彬,等.一種改進的非線性布爾函數(shù)硬件設(shè)計與實現(xiàn)[J].計算機應(yīng)用與軟件,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] 馬超,戴紫彬,常忠祥,等.高速可重構(gòu)插入與抽取單元設(shè)計[J].計算機應(yīng)用與軟件,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。國家自然科學(xué)基金項目(61404175)。金羽，碩士生，主研領(lǐng)域：安全專用芯片設(shè)計。戴紫彬，教授。李偉，副教授。馬超，博士生。

TP3

A

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