郭泓鍵，董秀則，高獻偉

(1.西安電子科技大學通信工程學院，西安 710071;2.北京電子科技學院，北京 100070)

1 概述

長期演進(Long Term Evolution，LTE)于2010 年底被指定為第4 代移動通信標準，其中安全技術(shù)是LTE 的關(guān)鍵技術(shù)［1］。祖沖之(ZUC)算法是LTE 加密算法128-EEA3 和完整性算法128-EIA3 的核心，在2011 年被3GPP LTE 采納為第4 代移動通信國際加密標準，是第一個我國自主研究設計并成為國際密碼標準的密碼算法［2］。

ZUC 算法是一種流密碼，和分組密碼相比，具有加解密速度快、適合硬件實現(xiàn)等特點［3］。隨著集成電路技術(shù)的高速發(fā)展，硬件電路實現(xiàn)加密算法與傳統(tǒng)軟件加密方法相比具有安全性好、計算速度快、成本低、性能可靠等優(yōu)點［4］?，F(xiàn)場可編程門陣列(Field Programmable Gate Array，F(xiàn)PGA)器件因其現(xiàn)場可編程和低成本等特性在密碼算法實現(xiàn)領(lǐng)域有著突出的優(yōu)勢［5］。因此，基于FPGA 器件實現(xiàn)ZUC 算法具有一定的現(xiàn)實意義。

目前，已有多篇文獻對ZUC 算法的FPGA 實現(xiàn)進行了研究。但大都不能同時兼顧高吞吐量和低資源占用。例如文獻［6］提出的方法邏輯資源占用為385 個slice，但是只達到了2.08 Gb/s 的吞吐量。文獻［7］提出復用S 盒和CSA 樹的設計方法，在分別占用311 個slice 和356 個slice 的情況下只達到2.0 Gb/s和3.456 Gb/s 的吞吐量。文獻［8］提出的方法在CSA 樹結(jié)構(gòu)的基礎上進行了改進，在占用395 個slice 的情況下達到5.504 Gb/s 的吞吐量。文獻［3］采用流水線的設計方法僅對ZUC1.4 版本的工作階段進行了實現(xiàn)，其實現(xiàn)的內(nèi)容相比現(xiàn)在的ZUC 1.6 版本完整算法要簡單很多，參考價值不大。本文提出了一種新的方法，通過使用占用邏輯資源較少的簡單加法器完成了復雜的mod(231-1)加法運算，在僅占用305 個slice 的情況下達到了5.647 Gb/s的吞吐量。

2 ZUC 算法簡介與實現(xiàn)分析

ZUC 算法是一種面向字的流密碼，輸入為一個128 bit 的初始密鑰k 和一個128 bit 的初始矢量iv，輸出為32 bit 的密鑰流［9］。其整體結(jié)構(gòu)如圖1 所示，共包含3 個邏輯層，由上到下分別是線性反饋移位寄存器(LFSR)、比特重組(BR)和非線性函數(shù)F。

圖1 ZUC 算法整體結(jié)構(gòu)

2.1 ZUC 算法

ZUC 算法的執(zhí)行分為2 個階段:初始化階段以及工作階段。

2.1.1 初始化階段

首先，密鑰加載過程把128 bit 的初始密鑰k=k0‖k1‖…‖k15，128 bit 的初始向量iv=iv0‖iv1‖…‖iv15以及240 bit 的長字符串D=d0‖d1‖…‖d15以si=ki‖di‖ivi(0≤i≤15)的方式加載到LFSR 的16個存儲單元si(0 ≤i≤15)中。其中，ki和ivi均為8 bit，di為15 bit，si定義在素數(shù)域GF(231-1)上。然后，將32 bit 記憶單元R1和R2清零。最后，依次執(zhí)行BR、非線性函數(shù)F、LFSR 初始化模式3 個步驟，重復執(zhí)行32 次。

BR 的具體操作為:X0=s15H‖s14L，X1=s11L‖s9H，X2=s7L‖s5H，X3=s2L‖s0H，siH和siL分別是si的高位16 bit 和低位16 bit。

非線性函數(shù)F 依次執(zhí)行以下計算:W=(X0⊕R1)R2，W1=R1X1，W2=R2⊕X2，R1=S(L1(W1L‖W2H))，R2=S(L2(W2L‖W1H))。S 是32 × 32 的S 盒。

LFSR 初始化模式的具體操作為:

(1)v=215s15+217s13+221s10+220s4+(1 +28)s0mod(231-1)。

(2)s16=(v +u)mod(231-1)，其中，u 為非線性函數(shù)F 的輸出W 去掉最右端比特位。

(3)如果s16=0，那么設置s16=231-1。

(4)(S1，S2，…，S16)→(S0，S1，…，S15)。

2.1.2 工作階段

首先，順序執(zhí)行BR、非線性函數(shù)F(丟棄非線性函數(shù)F 的輸出W)、LFSR 工作模式3 個步驟一次。然后，按順序迭代執(zhí)行BR、非線性函數(shù)F、Z=W⊕X3、LFSR 工作模式，每執(zhí)行一次得到一個32 bit 的字Z。其中，LFSR 工作模式的具體操作為:

(1)s16=215s15+217s13+221s10+220s4+(1 +28)s0mod(231-1)。

(2)如果s16=0，那么設置s16=231-1。

(3)(S1，S2，…，S16)→(S0，S1，…，S15)。

2.2 ZUC 算法實現(xiàn)分析

ZUC 算法BR 邏輯層和非線性函數(shù)F 邏輯層中涉及到的運算包括模232加法、S 盒變換、字符串的級聯(lián)、異或和循環(huán)移位。其中，2 個32 bit 數(shù)據(jù)進行模232加法運算在VHDL 語言中可以直接利用運算符“+”完成，S 盒變換可以通過查表(LUT)的方式快速實現(xiàn)。字符串的級聯(lián)、異或和循環(huán)移位這3 種運算都是對數(shù)據(jù)比特位順序的改變或者是對數(shù)據(jù)比特位的簡單運算，在硬件上都比較容易實現(xiàn)。

ZUC 算法LFSR 邏輯層中涉及到的運算主要包括素數(shù)域GF(231-1)上31 bit 的字符s 與2i(i=15，17，21，20，8)相乘，以及31 bit 數(shù)據(jù)mod(231-1)加法運算。231-1 是一個特殊的大素數(shù)［10］，其二進制形式是31 bit 1，可以看出素數(shù)域GF(231-1)上31 bit 的字符s 乘2i(i=15，17，21，20，8)可以通過數(shù)據(jù)s 向左循環(huán)移位i 位快速實現(xiàn)。由此得到LFSR 中215s15，217s13，221s10，220s4，28s0可以分別如下快速實現(xiàn):s15＜＜＜15，s13＜＜＜17，s10＜＜＜21，s4＜＜＜20，s0＜＜＜8。

但是在硬件上實現(xiàn)多個31 bit 數(shù)據(jù)mod(231-1)相加是相對復雜的，已公開發(fā)表的論文都是通過使用多個較復雜的加法器來實現(xiàn)。ZUC 算法執(zhí)行過程中mod(231-1)加法運算需要被執(zhí)行多次(ZUC算法初始化階段，LFSR 初始化模式需要被執(zhí)行32 次，每次需要執(zhí)行7 次mod(231-1)加法運算;ZUC 算法工作階段，LFSR 工作模式需要被執(zhí)行多次，每次需要執(zhí)行6 次mod(231-1)加法運算)，因此，LFSR 邏輯層中方程式(1)、方程式(2)的實現(xiàn)需要消耗較多的硬件資源，會產(chǎn)生較多的延時。

3 ZUC 算法的實現(xiàn)

根據(jù)ZUC 算法的特點，將ZUC 算法的整體結(jié)構(gòu)分為庫函數(shù)模塊和主程序模塊。主程序?qū)嶓w硬件接口如圖2 所示。各管腳定義硬件接口設計為同步接口，每一個輸入輸出信號都在時鐘周期的上升沿采樣。

通過2.2 節(jié)的分析可知，LFSR 中式(1)、式(2)的實現(xiàn)消耗時間最長，需要資源最多，是基于FPGA實現(xiàn)ZUC 算法的關(guān)鍵路徑。已公開發(fā)表的論文通過使用多個較復雜的加法器來實現(xiàn)這一關(guān)鍵路徑，其資源使用情況大致如表1 所示。

圖2 主程序?qū)嶓w接口

表1 ZUC 算法關(guān)鍵路徑資源使用

mod(231-1)加法器由2 個32 bit 加法器和1 個選通器(MUX)組成，如圖3 所示。而進位保留加法器(CSA)較mod(231-1)加法器會占用更多的資源［11］。

圖3 mod(231 -1)加法器

為了進一步減少硬件資源占用，提高吞吐率，本文提出了一種新的實現(xiàn)方法。mod(231-1)加法是在素數(shù)域GF(231-1)上進行的，231-1 是一個特殊的素數(shù)，其二進制形式為31 bit 1。如果方程式(1)中6 個數(shù)據(jù)相加的和小于231-1，則其模231-1 是它自身。6 個31 bit 數(shù)據(jù)相加最大可產(chǎn)生1 個34 bit數(shù)據(jù)，所以如果表(1)中6 個數(shù)據(jù)相加的和大于231-1，那么其二進制形式位數(shù)一定大于等于32 位，小于等于34 位。若其從右至左第32 bit 為1，也就是十進制數(shù)231，231模231-1 后恰好為二進制數(shù)1;若其從右至左第33 bit 為1，也就是十進制數(shù)232，232模231-1 后恰好為二進制數(shù)10;若其從右至左第34 bit為1，也就是十進制數(shù)233，233模231-1 后恰好為二進制數(shù)100?？梢钥闯鋈绻匠淌?1)中6 個數(shù)據(jù)相加的和大于231-1，其二進制形式每個從右至左第(31 +n)位為1 的比特位都會在其模231-1 后產(chǎn)生一個從右至左第n bit 為1 的二進制數(shù)。綜上可以看出，mod(231-1)加法可以使用簡單的加法器和移位操作來實現(xiàn)。

考慮到方程式(1)、方程式(2)中運算的迭代特點和很好的并行特性，為了在算法實現(xiàn)面積和速度方面取得平衡，本文根據(jù)上述結(jié)論采用混合方式對關(guān)鍵路徑對應的方程式(1)、方程式(2)進行了實現(xiàn)，具體流程為:

(1)在方程式(1)中6 個31 bit 數(shù)據(jù)最高位前分別補3 bit 0，使其變?yōu)? 個34 bit 的數(shù)據(jù)，分別記為A，B，C，D，E，F(xiàn)。

(2)使用1 個34 bit 加法器迭代計算A，B，C 三者之和，結(jié)果記為G。同時并行使用另一個34 bit 加法器迭代計算D，E，F(xiàn) 之和，結(jié)果記為H。

(3)使用第2 個34 bit 加法器計算G，H 之和，記為I。

(4)使用1 個32 bit 加法器將I 的最高3 bit，和剩余31 bit 分別作為2 個二進制數(shù)相加，結(jié)果記為J(考慮到J 可能會大于231-1)。

(5)使用1 個31 bit 加法器將32 bit 數(shù)J 的最高位1 bit 與剩余31 bit 相加(結(jié)果不可能大于231-1)，結(jié)果即為方程(1)中的v。

(6)使用上述32 bit 加法器計算方程(2)中兩數(shù)據(jù)之和，記為K。

(7)使用上述31 bit 加法器將K 的最高位1 bit與剩余31 bit 相加，結(jié)果即為s16。

本文方法無需判斷s16的計算結(jié)果是否為0，因此，可以省去1 個選通器(MUX)。這是因為LFSR的所有寄存器單元si(0≤i≤15)的初始值都不為0，故本文方法中數(shù)據(jù)相加結(jié)果不可能為0。

本文提出的方法實現(xiàn)方程式(1)的計算只使用了2 個34 bit 加法器，1 個32 bit 加法器和1 個31 bit加法器，資源占用較其他方法中使用多個CSA 和mod(231-1)加法器相比會大幅減少，同時硬件延時也會大大減少。

4 仿真驗證和性能分析

本文利用硬件描述語言VHDL 對ZUC 算法進行了編程實現(xiàn)，在Quartus Ⅱ9.0 上進行了綜合仿真。對于初始向量為84319aa8de6915ca1f6bda6bfbd 8c766，初始密鑰為3d4c4be96a82fdaeb58f641db17b 455b 的輸入，得到了輸出14f1c272，3279c419 等數(shù)據(jù)。結(jié)果與文獻［12］中測試文件保持一致，證明了本設計的正確性。仿真結(jié)果如圖4 所示。

圖4 編程實現(xiàn)綜合仿真結(jié)果

目前業(yè)界評估密碼算法硬件實現(xiàn)的關(guān)鍵指標主要有吞吐率和芯片面積。為了與其他實現(xiàn)方法進行對比，本文采用XILINX 公司的Virtex5XC5VLX110T 芯片，使用ISE 軟件對本文方法進行了綜合實現(xiàn)，在僅占用305 個slice 的情況下達到了5.322 Gb/s 的吞吐量。本文方法與其他方法的吞吐率與芯片面積等指標如表2 所示。

本文采用了FPGA 邏輯資源Slice 作為比較的基礎，通過對比可以看出，本文方法硬件資源占用最少，僅為305 個slice。而在吞吐率方面，除了文獻［8］的方法達到了最高。文獻［2］中的方法是對ZUC1.4版本的實現(xiàn)，其余方法都是對ZUC1.6 版本的實現(xiàn)。ZUC1.4 版本是通過方程s16=v⊕u 計算得到s16的，計算量要比ZUC1.6 小很多，而且其初始化部分是在軟件中實現(xiàn)的，所以大大減少了延時和硬件資源占用，不具有可比性。本文方法在吞吐量/面積方面達到了最高，較文獻［8］方法提高了25.9%。這充分說明，本文方法通過對ZUC 算法關(guān)鍵路徑的優(yōu)化實現(xiàn)，在大幅減少硬件資源消耗的同時保證了極高的吞吐率。

表2 本文方法與其他方法的數(shù)據(jù)比較

5 結(jié)束語

本文在FPGA 平臺上設計并實現(xiàn)了一種新的ZUC 算法實現(xiàn)方法，在保證較高吞吐率的前提下，與目前最優(yōu)實現(xiàn)方法相比，芯片資源占用減少了近23%，單位面積的吞吐量提高了25.9%，具有一定的實際價值。但是本文方法的吞吐量還有待進一步提高，這也是下一步的研究方向。

［1］江麗娜，高 能，馬 原，等.祖沖之序列密碼算法IP核的設計與實現(xiàn)［J］.信息網(wǎng)絡安全，2012，(8):219-222.

［2］馮秀濤.3GPP LTE 國際加密標準ZUC 算法［J］.信息安全與通信保密，2011，9(12):45-46.

［3］Liu Zongbin，Zhang Lingchen，Jing Jiwu，et al.Efficient Pipelined Stream Cipher ZUC Algorithm in FPGA［C］//Proc.of the 1st International Workshop on ZUC Algorithm.Beijing，China:［s.n.］，2010.

［4］Zhang Xinmiao，Parhi K.High-speed VLSI Architectures for the AES algorithm［J］.IEEE Transactions on Very Large Scale Integration Systems，2004，12(9):957-967.

［5］Galanis M D，Kitsos P.Comparison of the Hardware Architectures and FPGA Implementations of Stream Ciphers［C］//Proc.of the 11th IEEE International Conference on Electronics，Circuits and Systems.Tel-Aviv，Israel:［s.n.］，2004:571-574.

［6］Kitsos P，Sklavos N，Skodras A N.An FPGA Implementation of the ZUC Stream Cipher［C］//Proc.of the 14th Euromicro Conference on Digital System Design.［S.l.］:IEEE Press，2011:814-817.

［7］Wang Lei，Jing Jiwu，Liu Zongbin，et al.Evaluating Optimized Implementations of Stream Cipher ZUC Algorithm on FPGA［C］//Proc.of 13th International Conference on Information，Communication and Signal Processing.Beijing，China:［s.n.］，2011:202-215.

［8］Zhang Lingchen，Xia Luning，Liu Zongbin，et al.Evaluating the Optimized Implementation of SNOW 3G and ZUC on FPGA ［C］//Proc.of the 11th IEEE International Conference on Trust，Security and Privacy in Computing and Communications.Liverpool，UK:［s.n.］，2012:436-442.

［9］ESTI/SAGE Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 ＆ 128-EIA3 Document 2:ZUC Specification［Z］.2011.

［10］ESTI/SAGE Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 ＆ 128-EIA3 Document 4:Design and Evaluation Report［Z］.2011.

［11］Murugeswari S.An Area Efficient and Low Power Multiplier Using Modified Carry Save Adder for Parallel Multipliers［C］//Proc.of the 2nd International Joint Conference.Bangalore，India:［s.n.］，2012.

［12］ESTI/SAGE Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 ＆ 128-EIA3 Document 3:Implementor's Test Data［Z］.2011.