基于FPGA 的祖沖之算法硬件實(shí)現(xiàn)

郭泓鍵，董秀則，高獻(xiàn)偉

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

1 概述

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

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

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

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

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

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

2.1 ZUC 算法

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

2.1.1 初始化階段

首先，密鑰加載過(guò)程把128 bit 的初始密鑰k=k0‖k1‖…‖k15，128 bit 的初始向量iv=iv0‖iv1‖…‖iv15以及240 bit 的長(zhǎng)字符串D=d0‖d1‖…‖d15以si=ki‖di‖ivi(0≤i≤15)的方式加載到LFSR 的16個(gè)存儲(chǔ)單元si(0 ≤i≤15)中。其中，ki和ivi均為8 bit，di為15 bit，si定義在素?cái)?shù)域GF(231-1)上。然后，將32 bit 記憶單元R1和R2清零。最后，依次執(zhí)行BR、非線性函數(shù)F、LFSR 初始化模式3 個(gè)步驟，重復(fù)執(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í)行以下計(jì)算: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，那么設(shè)置s16=231-1。

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

2.1.2 工作階段

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 mod(231 -1)加法器

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

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

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

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

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

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

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

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

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

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

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

4 仿真驗(yàn)證和性能分析

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

［2］馮秀濤.3GPP LTE 國(guó)際加密標(biāo)準(zhǔn)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.