一種面積優(yōu)化的ZUC算法的硬件架構(gòu)

陸 斌，嚴(yán)利民

(上海大學(xué) 微電子研究與開發(fā)中心，上海 200444)

作為序列密碼體系之一的祖沖之(Zu Chongzhi, ZUC)密碼是由我國自主設(shè)計的首個成為國際標(biāo)準(zhǔn)的密碼算法，主要用于無線通信領(lǐng)域的信息安全[1].隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，在資源有限的物聯(lián)網(wǎng)終端中保障信息安全的工作對密碼算法提出了更嚴(yán)苛的要求[2-3]，因此設(shè)計更少資源開銷的ZUC密碼架構(gòu)具有現(xiàn)實意義.

ZUC密碼的核心和主體是ZUC算法，以及以ZUC算法為基礎(chǔ)的完整性算法128-EIA3和機密性算法128-EEA3[4].目前除了一些ZUC算法的直接硬件實現(xiàn)[5]，也有許多文獻對ZUC算法硬件架構(gòu)進行了進一步研究： Wang等[6]對ZUC算法的線性反饋移位寄存器(Linear Feedback Shift Register, LFSR)設(shè)計了四級流水線以降低關(guān)鍵路徑延時，實現(xiàn)了較高的運行頻率，但是其硬件開銷較大；Zhang等[7]提出了基于進位保留加法器(Carry Saved Adder, CSA)結(jié)構(gòu)的LFSR以及并行運算的模(2311)加法單元，可以在不使用流水線的情況下有效降低關(guān)鍵路徑的延時；Liu等[8]在此基礎(chǔ)上設(shè)計了二級混合流水線機構(gòu)，能夠進一步提高ZUC算法的運行頻率.

上述研究主要致力于優(yōu)化LFSR從而降低關(guān)鍵路徑延時提高性能，但是很少涉及S盒部分的優(yōu)化.S盒在ZUC算法中占據(jù)了較多的資源開銷，32 bit的S盒由4個8 bitS盒并行組合而成，其中S0和S2為同一個S盒(S0-box)，S1和S3為同一個S盒(S1-box).在上述的研究文獻中S盒基本上由查找表的方式實現(xiàn)[5-8]，導(dǎo)致了較多的硬件開銷或是額外的存儲資源.ZUC算法的S0-box本質(zhì)上是一個3層Feistel結(jié)構(gòu)[9]，而S1-box與AES(Advanced Encryption Standard)算法的S盒構(gòu)造上幾乎相似，可以參考AES算法的S盒研究方法[10]對其進行優(yōu)化.

因此，本文綜合考慮了面積與延時兩方面因素，提出了一種面積優(yōu)化的ZUC算法的硬件架構(gòu)，該架構(gòu)在文獻[7]的基礎(chǔ)上提供了兩方面的改進： 一是設(shè)計了基于復(fù)合域運算的S1-box結(jié)構(gòu)；二是提出了一種基于超前進位加法器(Carry Lookahead Adder, CLA)的模(2311)加法單元，從而有效降低了ZUC算法硬件實現(xiàn)的資源開銷.

1 基于復(fù)合域運算的S1-box的設(shè)計

1.1 S1-box的整體設(shè)計

ZUC算法的S1-box是基于數(shù)學(xué)上的有限域運算和仿射變換組合實現(xiàn)的[9]，如式(1)所示：

F=Mx-1⊕B.

(1)

式中：x為8 bit輸入向量；x-1為GF(28)域(由不可約多項式M(x)=x8+x7+x3+x+1定義)上的乘法逆運算；⊕為異或運算；M和B分別為仿射變換過程中的仿射矩陣和常向量，且

(2)

式(1)中在GF(28)域上求乘法逆運算的實現(xiàn)是最為復(fù)雜的部分，由于S1-box與AES算法的S盒構(gòu)造上的相似性，因此參考AES算法的S盒研究方法[10]將有限域上的求逆運算同構(gòu)映射轉(zhuǎn)換復(fù)合域上，可以有效簡化電路復(fù)雜度.考慮到同構(gòu)映射的復(fù)雜度與優(yōu)化效率[11]，本文將轉(zhuǎn)換到復(fù)合域GF((24)2)上進行求逆運算.

由此式(1)可以寫成式(3)的形式：

F=M(δ-1(δx)-1)⊕B.

(3)

式中：δ為有限域GF(28)至復(fù)合域GF((24)2)的同構(gòu)映射矩陣；δ-1為δ的逆矩陣.基于式(3)，ZUC算法的S1-box的結(jié)構(gòu)框圖如圖1所示.

圖1 S1-box的硬件框圖Fig.1 Hardware block diagram of S1-box

1.2 復(fù)合域的乘法逆運算過程

根據(jù)有限域基礎(chǔ)知識[12]，基于不可約多項式p(y)=y2+y+υ和標(biāo)準(zhǔn)基{γ1,γ0}，在復(fù)合域GF((24)2)上的一個元素W的表達形式為W=Whγ1+Wlγ0.其中：υ,γ1,γ0,Wh,Wl∈GF(24).繼而推導(dǎo)出W的乘法逆元W-1為

(4)

圖2 復(fù)合域求逆運算的電路Fig.2 Complex domain inversion operation circuit

從圖2中可以看到，GF(28)域乘法逆運算被分解為GF(24)域的常系數(shù)平方運算、加法運算、乘法運算和求逆運算.選取不可約多項式I(x)=x4+x+1和參數(shù)υ=(1 001)B，則GF(24)域的乘法運算、常系數(shù)平方運算和求逆運算分別為式(5)～(7)，加法運算為異或運算.可以看到式(5)、(7)中存在一些重復(fù)的公共項，通過公共項消除(Common Subexpression Elimination, CSE)算法消去冗余項進一步減少硬件開銷[11]，公共項為f1=(a0⊕a3),f2=(a2⊕a3)，f3=(c2⊕c3).

(5)

(6)

(7)

此外，式(3)中的同構(gòu)映射矩陣δ由文獻[13]中的算法求得，而δ-1可以和仿射運算中的M矩陣合并為一個8×8的Mδ-1矩陣以減少電路實現(xiàn)時的硬件開銷：

(8)

采用Synopsys Design Compiler(K-2015.06)分別對查找表實現(xiàn)、復(fù)合域?qū)崿F(xiàn)2種方案進行了綜合，工藝庫為TSMC 90 nm CLN90G.表1給出了2種S1-box結(jié)構(gòu)方案的比較(工藝角為SS，溫度為125 ℃，電壓0.9 V)，面積單位為等效2輸入與非門數(shù)量.基于復(fù)合域的S1-box相比于查找表實現(xiàn)方式節(jié)省了約47.0%的硬件開銷，在延時方面基于復(fù)合域的S1-box架構(gòu)由于邏輯級數(shù)的增加相比查找表實現(xiàn)方式增加了約7.2%.

表1 不同方案實現(xiàn)的S1-box比較

2 基于CLA的模(2311)加法單元

模(2311)(a)所示，由兩個31位加法器和一個選擇器構(gòu)成，此外還有兩個變種結(jié)構(gòu)分別如圖3(b)[14]和圖3(c)所示[7]，結(jié)構(gòu)2(圖3(b)的結(jié)構(gòu))省略了選擇器而直接使用兩個加法器實現(xiàn)，結(jié)構(gòu)3(圖3(c)的結(jié)構(gòu))為了減少延時將加法器并行實現(xiàn).

圖3 模(2311)加法單元的3種結(jié)構(gòu)Fig.3 Three structures of mod (2311) addition unit

本文在結(jié)構(gòu)2的基礎(chǔ)上進一步改進模(2311)加法單元結(jié)構(gòu)以進一步降低電路的硬件開銷.不難發(fā)現(xiàn)模(2311)加法單元的第2個加法器(adder2)僅僅是將前一個加法器的求和值加上1 bit的運算，因此可以將adder2簡化為帶有進位的單加數(shù)加法器，同時考慮到行波進位加法器(Ripple carry adder)的延遲較長，因此采用CLA的結(jié)構(gòu)來設(shè)計adder2.CLA中共有3條數(shù)據(jù)鏈路，分別為求和、進位傳播和進位生成，由于加數(shù)B為0，單bitCLA的計算可以簡化為式(9)：

(9)

將4個單bit CLA進一步抽象成一個4 bit CLA(CLA-4)(圖4(a))，可以更快速地完成計算，其進位生成和進位傳播計算如公式(10)所示.

圖4 簡化后的CLA-4結(jié)構(gòu)和CLA-3結(jié)構(gòu)Fig.4 Simplified CLA-4 structure and CLA-3 structure

(10)

由于adder2只有31位加數(shù)，因此最高位的CLA-4可以簡化為CLA-3，如圖4(b)所示.將CLA-4和CLA-3組合起來最終得到adder2的整體結(jié)構(gòu)，如圖5所示.

圖5 adder2的整體結(jié)構(gòu)Fig.5 The overall structure of adder2

在Design Compiler下(工藝角為SS，溫度為125 ℃，電壓0.9 V)綜合了不同結(jié)構(gòu)的模(2311)加法單元，所提出的基于CLA的模(2311)加法單元與圖3中3種結(jié)構(gòu)相比較分別減少了約30.5%、20.2%和32.5%的硬件開銷(等效2輸入與非門數(shù)量)，此外關(guān)鍵路徑的延時只比結(jié)構(gòu)3增加了約5.5%，相比結(jié)構(gòu)1和結(jié)構(gòu)2減少了約34.9%和32.1%，具體結(jié)果如表2所示.

表2 不同結(jié)構(gòu)的模(231-1)加法單元比較

3 驗證與分析

基于以上兩部分的改進，本文所提出的面積優(yōu)化的ZUC算法的整體硬件架構(gòu)如圖6所示.考慮到面積與時序平衡，LFSR部分采用了與文獻[8]相似的CSA樹型兩級流水線結(jié)構(gòu)，CSA樹型結(jié)構(gòu)能降低組合邏輯的延時，減少流水級數(shù)，從而使用更少的寄存器.本文的ZUC算法架構(gòu)在初始化階段每兩個時鐘周期更新一次LFSR，在工作階段第1個密鑰生成需要兩個時鐘周期，此后每個時鐘周期都生成1個密鑰Z，因此每個時鐘周期可以處理32 bit數(shù)據(jù)(即算法吞吐率為32 bit×工作頻率).

圖6 面積優(yōu)化的ZUC算法硬件架構(gòu)Fig.6 Hardware architecture of area-optimized ZUC algorithm

采用ZUC算法標(biāo)準(zhǔn)文檔中的測試向量(測試向量3)使對所提出的面積優(yōu)化的ZUC算法的硬件架構(gòu)進行功能仿真，仿真軟件為Modelsim 10.6c，如圖7所示仿真結(jié)果顯示本文方案正確生成了密鑰流.

圖7 功能仿真結(jié)果Fig.7 Functional simulation results

在Xilinx FPGA Virtex-5 XC5VLX110T-3平臺(ISE 14.7)、Xilinx FPGA Virtex-7 XC7VX330T-3平臺(Vivado 2018.3)和TSMC 90 nm工藝下分別綜合實現(xiàn)了所提出的ZUC算法硬件架構(gòu)，并與目前較優(yōu)的方案進行比較，結(jié)果如表3所示.

表3 本文方案與相關(guān)工作在硬件開銷及性能表現(xiàn)的比較

Tab.3 Comparison of hardware overhead and performance with related works

方案平臺工藝面積頻率/MHz吞吐率/(Gb·s-1)吞吐率/面積文獻[5]FPGASpartan-6575 slices156.254.988.65文獻[6]FPGAVirtex-5 XC5VLX110T-3575 slices222.407.1012.30文獻[7]FPGAVirtex-5 XC5VLX110T-3395 slices172.005.5013.90文獻[8]FPGAVirtex-5 XC5VLX110T-3350 slices246.007.8022.30本文FPGAVirtex-5 XC5VLX110T-3313 slices235.307.3523.50本文FPGAVirtex-7 XC7VX330T-3276 slices312.6010.0033.80文獻[8]ASICTSMC 65nm12.5K Gates250080.06.4文獻[15]ASICTSMC 130nm11.76K Gates---本文ASICTSMC 90nm(slow)9.6K Gates75024.02.5本文ASICTSMC 90nm(fast)9.6K Gates180057.68.0

在Xilinx Virtex-5 FPGA平臺下，本文所提出的ZUC算法硬件架構(gòu)與文獻[5]、文獻[6]、文獻[7]、文獻[8]的方案相比分別降低了45.6%，45.6%，20.7%，10.6%的硬件開銷(以邏輯資源slice為標(biāo)準(zhǔn))，在頻率上僅比文獻[8]的降低了4.3%，這是因為隨著結(jié)構(gòu)優(yōu)化電路的關(guān)鍵路徑已經(jīng)從LSFR部分轉(zhuǎn)移到了非線性函數(shù)部分(S盒運算)，而本文提出的S盒結(jié)構(gòu)由于邏輯深度的增加引入了部分延時.綜合分析各方案的吞吐率與面積情況，本文方案在綜合表現(xiàn)上相比于文獻[7]提高了5.4%.

在ASIC平臺下的ZUC優(yōu)化實現(xiàn)研究較少，本文所提出的硬件架構(gòu)與文獻[8]、文獻[15]的相比較減少了23.2%和18.36%的等效2輸入與非門數(shù)量，可以看出由于本文提出的改進更針對門級電路進行優(yōu)化，因此在ASIC平臺上的優(yōu)化效果要更好于FPGA平臺.由于不同工藝節(jié)點原因，本文方案在頻率上與文獻[8]有一定差距(文獻[15]未給出頻率)，本文方案在工藝角為SS，溫度為125 ℃，電壓0.9 V的條件下頻率為750 MHz，而在工藝角為FF、溫度為-40 ℃，電壓為1.1 V條件下頻率能達到1.8 GHz.從吞吐率和面積綜合表現(xiàn)來看，本文提出的架構(gòu)仍然具有較大的優(yōu)勢.

此外，在最新的Xilinx Virtex-7 FPGA平臺上實現(xiàn)本文提出的硬件架構(gòu)，由于FPGA內(nèi)部基本邏輯結(jié)構(gòu)的升級，硬件開銷僅為276 slices，吞吐率達到了10 Gb/s.

4 結(jié) 語

針對ZUC密碼在嵌入式終端等領(lǐng)域的應(yīng)用，本文圍繞ZUC算法硬件架構(gòu)的面積優(yōu)化展開，提出了基于復(fù)合域的S1-box設(shè)計和基于CLA的模(2311)加法單元設(shè)計，并且在此基礎(chǔ)上設(shè)計了面積優(yōu)化的ZUC算法的硬件架構(gòu).與主流方案相比，本文所提出的架構(gòu)具有更小的硬件資源開銷，同時在性能表現(xiàn)上 接近最好的方案.本文的架構(gòu)在Virtex-5 FPGA上僅消耗了313個Slices，達到了225.3 MHz的頻率；在TSMC 90 nm工藝下硬件開銷為9.6 K等效NAND門，在兩種平臺上較目前主流的方案分別減少了10.6%～45.6%的硬件資源.在最新的Virtex-7 FPGA平臺上，本文的ZUC算法架構(gòu)共消耗了276 Slices硬件資源，吞吐率為10 Gb/s.實驗結(jié)果表明，所提出的ZUC算法硬件架構(gòu)能同時兼顧硬件資源開銷少與性能表現(xiàn)好的優(yōu)點.