基于FPGA 的ZUC-256 算法實現(xiàn)架構(gòu)分析

賈旭光，徐 頌，白海通，鄧 超

（1.華北計算機(jī)系統(tǒng)工程研究所，北京 100083；2.中電智能科技有限公司，北京 102209；3.中國人民解放軍陸軍，北京 100044）

0 引言

祖沖之密碼(ZUC)算法為我國自主設(shè)計的密碼算法，主要包含流加密算法和完整性算法。2011 年，ZUC算法被3GPP 批準(zhǔn)成為4G LTE 國際密碼算法標(biāo)準(zhǔn)。近年來，隨著新一代移動通信5G-NR 標(biāo)準(zhǔn)的確定，我國也在大力推廣5G 通信相關(guān)的研發(fā)和產(chǎn)業(yè)化。3GPP 在會議中明確5G 通信中使用128 bit 和256 bit 密鑰的對稱加密算法，并保持向4G 兼容。為此，我國在ZUC-128 的基礎(chǔ)上提出了ZUC-256 算法。ZUC-256 由128 bit 密鑰升級為256 bit 密鑰，提供消息加密和認(rèn)證功能，可廣泛應(yīng)用于5G 移動通信的安全保護(hù)。目前針對ZUC 算法的研究已經(jīng)有多種快速軟件實現(xiàn)和硬件優(yōu)化實現(xiàn)方案[1-5]，本文通過分析ZUC 算法架構(gòu)和工作流程，提出一種軟硬協(xié)同實現(xiàn)方案，經(jīng)驗證，相比單硬件實現(xiàn)有較大的性能提升。

本文將內(nèi)容分為3 個部分，第一部分為背景技術(shù)介紹，分析了ZUC-256 算法結(jié)構(gòu)，并對比了ZUC-256 和ZUC-128 的差異；第二部分為FPGA 實現(xiàn)，首先分析了ZUC 算法涉及的運(yùn)算單元，重點介紹了模231-1 加法器的實現(xiàn)方式，提出了4 種6 輸入模231-1 加法器實現(xiàn)架構(gòu)，然后通過分析關(guān)鍵路徑以及引入流水線架構(gòu)，提出了全硬件和軟硬件協(xié)同架構(gòu)實施方案，最后對不同實現(xiàn)架構(gòu)進(jìn)行了性能分析；第三部分為總結(jié)與展望。

1 背景技術(shù)介紹

首先分析了ZUC-256 算法的組成架構(gòu)，仔細(xì)討論了ZUC-256 與ZUC-128 算法差異，最后提出了一種兼容ZUC-256 和ZUC-128 算法的硬件實現(xiàn)架構(gòu)。

1.1 ZUC-256 算法介紹

ZUC-256 算法主要包含三部分：線性反饋移位寄存器（Linear Feedback Shift Register，LFSR）、比特重組（Bit Reorganization，BR）和非線性函數(shù)（Finite State Machine，F(xiàn)SM）[6]。ZUC 算法運(yùn)行過程包含兩個階段，初始化和密鑰生成階段。通過模式選擇開關(guān)選擇系統(tǒng)工作在初始化模式或密鑰生成模式，ZUC 算法結(jié)構(gòu)圖如圖1所示。

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

初始化階段：將密鑰和初始向量依次裝入相應(yīng)寄存器，進(jìn)行33 輪運(yùn)算，初始化階段無輸出。下半部分的輸出W反饋到多輸入加法器中。

密鑰生成階段：該階段與初始化階段大部分結(jié)構(gòu)一致，輸出W與Z直接異或生成密鑰流輸出。

1.2 ZUC-256 與ZUC-128 差異對比

ZUC-256 與ZUC-128 算法架構(gòu)完全一致，保持了良好的向下兼容性。兩者的差異僅僅為算法架構(gòu)的輸入密鑰由128 bit 擴(kuò)展為256 bit，初始向量由128 bit 擴(kuò)展為184 bit。另外，初始化階段的載入的初始向量和密鑰也不相同。

通過以上分析，可以很容易地設(shè)計一種硬件實現(xiàn)架構(gòu)同時運(yùn)行ZUC-256 和ZUC-128 算法。

2 算法架構(gòu)FPGA 實現(xiàn)分析

ZUC-256 算法涉及的運(yùn)算主要有模232加法、模231-1加法、異或和比特連接等運(yùn)算。模232加法可通過截取加法器輸出的低32 位實現(xiàn)，比特連接不占用FPGA 資源。運(yùn)算最為復(fù)雜的部分為模231-1 加法運(yùn)算。接下來，將分別討論2 輸入和ZUC 算法用到的6 輸入模231-1 加法器的實現(xiàn)架構(gòu)。

2.1 2 輸入模加法器架構(gòu)實現(xiàn)

2 輸入模231-1 加法器實現(xiàn)主要有3 種方式:(1)方式1如圖2 所示，直接用兩個31 bit 加法器級聯(lián)實現(xiàn)，第一個加法器連接兩個輸入，第二個加法器輸入為第一個加法器的進(jìn)位與輸出和。(2)方式2 如圖3 所示，用兩個加法器（一個半加器和一個全加器）和一個選擇器實現(xiàn)，選擇器根據(jù)進(jìn)位選擇結(jié)果為半加器還是全加器的輸出。方式2 相比方式1，延遲由兩個加法器延遲減為一個加法器加一個選擇器延遲，因而能夠提升工作頻率。(3)文獻(xiàn)[7]提到第3 種實現(xiàn)方式，如圖4 所示，該方式占用兩個加法器和一個選擇器，延遲最高為兩個加法器和一個選擇器。方式3 在資源占用上差于方式1，延遲上差于方式2，因而不推薦使用。

圖2 模231-1 加法器方式1

圖3 模231-1 加法器方式2

圖4 模231-1 加法器方式3

2.2 多輸入模加法器架構(gòu)實現(xiàn)分析

加法器結(jié)構(gòu)的FPGA 實現(xiàn)通常有行波進(jìn)位加法器（Ripple Carry Adder，RCA）、超前進(jìn)位加法器（Carry Lookahead Adder，CLA）和進(jìn)位保存加法器（Carry Save Adder，CSA）等方式。

RCA 行波進(jìn)位加法器結(jié)構(gòu)簡單，僅需要級聯(lián)全加器即可實現(xiàn)，缺點是高位運(yùn)算需要等待低位運(yùn)算結(jié)束才能開始，延遲很高。

CLA 超前進(jìn)位加法器，進(jìn)位部分采用專用邏輯電路設(shè)計，減小延遲，然而隨著加法器輸入位寬的增加，超前部分的電路結(jié)構(gòu)也越來越復(fù)雜，不適合高位寬加法器設(shè)計。

CSA 進(jìn)位保存加法器，將和與進(jìn)位部分單獨運(yùn)算，最后將和與進(jìn)位相加得到輸出結(jié)果，適合FPGA 實現(xiàn)。

對于6 輸入加法器，如果用直接加法器實現(xiàn)需要5個2 輸入加法器實現(xiàn)，延遲為n-1 個加法器延遲。采用加法樹結(jié)構(gòu)，延遲減少為log2(n)個加法器。

ZUC-256 算法中加法器的輸入位寬為31 bit，RCA結(jié)構(gòu)的高延遲和CLA 結(jié)構(gòu)的復(fù)雜的進(jìn)位邏輯不適合本算法。本文以CSA 加法器和普通加法器（由綜合工具決定具體實現(xiàn)策略）作為基本單元，結(jié)合加法樹結(jié)構(gòu)，提出了4 種6 輸入加法器結(jié)構(gòu)，即全部采用普通加法器或CSA 加法器以及同時使用普通加法器和CSA 加法器的混合結(jié)構(gòu)，如圖5 所示。

圖5 6 輸入加法器結(jié)構(gòu)圖

方案a 包含三級加法樹，加法單元全部采用普通加法器，每過一級，加法單元位寬加一，第三級加法器的輸出分為兩部分，低31 位和剩余高位接入上節(jié)提到的2 輸入模231-1 加法器得到最終輸出結(jié)果。方案b 包含四級加法樹，前三級采用CSA 加法單元，第四級采用普通加法器單元，輸出同樣接入2 輸入模231-1 加法器。方案c和方案d 為混合結(jié)構(gòu)，加法單元同時采用CSA 和普通加法器。4 種方案的實現(xiàn)結(jié)果將在下文全硬件和軟硬件結(jié)合方案中闡述。

2.3 關(guān)鍵路徑分析

通過分析ZUC-256 算法架構(gòu)，可以看出關(guān)鍵路徑主要分為LFSR 和FSM 兩部分。

2.3.1 LFSR

LFSR 的數(shù)據(jù)處理路徑為:

（1）初始化階段

①V=(215·S15+217·S13+221·S10+220·S4+(1+28)·S0) mod(231-1)

②若V=0，則V=231-1

③S16=(V+W) mod (231-1)

④若S16=0，則S16=231-1

⑤(S15,S14,…,S1,S0)＜=(S16,S15,…,S2,S1)

（2）工作階段

①S16=(215·S15+217·S13+221·S10+220·S4+(1+28)·S0)mod (231-1)

②(S15,S14,…,S1,S0)＜=(S16,S15,…,S2,S1)

上述數(shù)據(jù)處理包含兩部分，加法和檢查結(jié)果是否為零。LFSR 寄存器S15的值必須確保在集合{1,2,…，231-1}中。文獻(xiàn)[8]指出，模231-1 加法器的輸入只要有一個不為零，輸出就不為零。LFSR 的所有寄存器初始值均不為零，即使FSM 的輸出結(jié)果為零，通過模231-1 加計算得到的S16也不為零，因此可以省掉檢測輸出是否為零的步驟，進(jìn)而節(jié)省了2 個選擇器。

省略掉選擇器后，可以對ZUC 算法架構(gòu)進(jìn)一步優(yōu)化。以加法樹方案a 為例，優(yōu)化后的LFSR 部分?jǐn)?shù)據(jù)流程圖如圖6 所示。

圖6 LFSR 關(guān)鍵路徑圖

假設(shè)2 輸入模231-1 加法器采用方式2，則關(guān)鍵路徑延遲為6 個加法器+2 個選擇器。關(guān)鍵路徑太長，會造成工作頻率Fmax無法提升，可以通過在中間加入寄存器減小關(guān)鍵路徑，寄存器的引入會造成密鑰流輸出多一個時鐘節(jié)拍。為了滿足每個時間節(jié)拍均輸出密鑰流，同時在中間加入寄存器減小關(guān)鍵路徑盡可能大的提升Fmax，需要引入流水線結(jié)構(gòu)。

文獻(xiàn)[9]-[10]均提出了ZUC 算法使用流水線架構(gòu)的思路，文獻(xiàn)[9]采用5 級流水，關(guān)鍵路徑僅為一個模231-1加法器，然而，需要耗費大量寄存器資源作為中間緩存；文獻(xiàn)[10]采用2 級流水，寄存器單元加在圖6 的虛線4處，本文將該流水線架構(gòu)進(jìn)一步優(yōu)化，可在圖6 中的1～4虛線處加入寄存器緩存單元。由于2 輸入模231-1 加法器延遲為一個加法器加上一個選擇器，結(jié)合理論分析，在虛線3 處加入寄存器能最大程度減小關(guān)鍵路徑延遲。經(jīng)Vivado 軟件綜合實現(xiàn)驗證，實際結(jié)果與理論分析相符。

2.3.2 FSM

FSM 部分?jǐn)?shù)據(jù)處理流程：

（1）W=(X0⊕R1+R2) mod (232)

（2）W1=(R1+X1) mod (232)

（3）W2=R2⊕X2

（4）R1=S(L1(W1L||W2H))

（5）R2=S(L2(W2L||W1H))

其中，符號⊕表示按位異或運(yùn)算，符號||表示字符串拼接，符號mod 表示取模運(yùn)算。L1、L2采用和ZUC-128 相同的MDS 矩陣[11]。S函數(shù)也與ZUC-128 采用的S-盒相同。S-盒可以用ROM 實現(xiàn)或查找表實現(xiàn)，用ROM 實現(xiàn)會占用一個時鐘周期，用查找表實現(xiàn)會占用大量的slice資源。同樣，對于R1和R2，既可以使用寄存器也可以使用wire 類型實現(xiàn)。同時采用有限狀態(tài)機(jī)和ROM 的方式實現(xiàn)FSM 部分會只占用兩個時鐘周期，縮減為一個時鐘周期的方式為用組合邏輯實現(xiàn)S-盒，或用組合邏輯實現(xiàn)R1與R2。

2.4 全硬件和軟硬件協(xié)同架構(gòu)

賽靈思創(chuàng)新性地將ARM 硬核引入FPGA 器件中，將整個FPGA 分為PS 和PL 兩部分，并提供多種PS 和PL間的高速總線作為連接通道。Zynq-7000 系列FPGA 一經(jīng)推出，便受到市場追捧。嵌入式和可編程邏輯的結(jié)合，可作為ZUC-256 算法軟硬件協(xié)同實現(xiàn)的硬件平臺。Zynq-7000 系列FPGA，PS 端為雙核ARM A9，最高主頻可達(dá)1 GHz，PL 端根據(jù)低端和高端分別配置與Artix-7或Kintex-7 系列同等規(guī)格的FPGA 資源。Zynq-7000 器件提供3 種AXI 總線滿足PS 和PL 通信需求，分別為面向高性能地址映射通信的AXI4 總線和面向高速路數(shù)據(jù)流通信的AXI4-Stream 總線以及輕量級的AXI4-Lite 總線。全硬件架構(gòu)是指僅用PL 即邏輯資源實現(xiàn)全部ZUC-256 算法，而軟硬件協(xié)同架構(gòu)則通過AXI4-Lite 總線同時使用PS 和PL 實現(xiàn)ZUC-256 算法。

在上一節(jié)中，詳述了LFSR 和FSM 部分的硬件實現(xiàn)，BR 部分不占用資源，除此之外，僅剩寄存器初始化單元模塊，ZUC-256 和ZUC-128 寄存器初始化單元不同，通過選擇器選擇不同的初始化單元即可實現(xiàn)一種硬件架構(gòu)兼容兩種算法。

初始化單元僅在初期運(yùn)行階段使用，隨著ZUC-256密鑰的增大，初始化單元占用大量的邏輯單元，因此可以將該部分放在軟件端進(jìn)行。軟件端運(yùn)行完畢后將結(jié)果載入S0-S15寄存器和R1、R2寄存器，即可繼續(xù)執(zhí)行輸出密鑰流階段。初始化階段放在軟件端，軟硬件協(xié)同架構(gòu)，也可以很容易地實現(xiàn)ZUC-256 和ZUC-128 復(fù)用。另外，軟硬件協(xié)同架構(gòu)LFSR 部分結(jié)構(gòu)進(jìn)一步縮減掉一個加法器和一個選擇器，從而進(jìn)一步減小關(guān)鍵路徑。

軟件端可采用前文提到的ZUC-256 算法快速軟件實現(xiàn)方法。FPGA PS 端運(yùn)行初始化階段完畢后，依次通過AXI4-Lite 總線寫入PL 端的R1、R2和S0～S15寄存器，最后一個寄存器S15寫入后拉高load 信號，指示PL 端開始運(yùn)行密鑰輸出階段。軟硬件協(xié)同架構(gòu)圖如圖7 所示。

圖7 ZUC 軟硬件協(xié)同架構(gòu)圖

以密鑰和初始向量均為零為例，初始化階段運(yùn)行結(jié)束后R1、R2和S0～S15寄存器依次為 0xa870958e，0x783f6cd9,0x7307b910,0x18826230,0x02177063,0x47acb519,0x20757378,0x245ed478,0x2c3cd51e,0x29a8a61e,0x03fe3241,0x5f04fb97,0x578905be,0x20ffcf8e,0x6e895b73,0x62b5d1ad,0x538967b5,0x1d7307be。將上述值加載到相應(yīng)寄存器運(yùn)行仿真圖如圖8 所示。

圖8 ZUC-256 軟硬件協(xié)同仿真圖

從圖8 中可以看出，在寄存器載入后的第二個時鐘，密鑰流data 開始輸出，輸出數(shù)據(jù)依次為0x58d03ad6,0x2e032ce2,0xdafc683a，…，另外，更換為ZUC-128 所用測試集，所得輸出也與預(yù)計結(jié)果一致[12]。

2.5 性能對比

本文以XC7Z045 為例，詳細(xì)對比了上述4 種加法器結(jié)構(gòu)在全硬件和軟硬件協(xié)同架構(gòu)下的資源占用量和關(guān)鍵路徑延遲。2 輸入模231-1 加法器采用方式2，Vivado軟件的綜合和實現(xiàn)策略均設(shè)置為性能優(yōu)先，全硬件架構(gòu)和軟硬件協(xié)同架構(gòu)資源占用和性能對比如表1 和表2所示。

表1 全硬件架構(gòu)資源占用及性能對比

表2 軟硬件協(xié)同架構(gòu)資源占用及性能對比

從表1 可以看出，全部采用加法器的方案a，關(guān)鍵路徑延遲最小，但面積占用最大；采用CSA 的加法樹結(jié)構(gòu)的方案b 關(guān)鍵路徑延遲最大；混合架構(gòu)的面積占用和延遲均折中。從表2 可以看出，方案a 延遲最小，面積占用也最小。隨著加法樹結(jié)構(gòu)中CSA 加法器單元占比的增加，關(guān)鍵路徑延遲逐漸增大。表1 和表2 比，軟硬件協(xié)同架構(gòu)比全硬件架構(gòu)，方案a 資源占用節(jié)省了56%，延遲降低了21%。軟硬件協(xié)同架構(gòu)的吞吐率可達(dá)6 180 Mb/s。

3 結(jié)論

本文提出了4 種實現(xiàn)6 輸入模加法器架構(gòu)，并提出了全硬件和軟硬件協(xié)同架構(gòu)實施方案，用戶可以根據(jù)所用器件和使用場景，在面積和速度間折中，選擇最終實現(xiàn)方案，具有很高的實用價值。同時，本文提出了靈活的流水線實現(xiàn)架構(gòu)，在增加少量寄存器的代價下進(jìn)一步提高工作頻率，實現(xiàn)每個時鐘輸出一個密鑰數(shù)據(jù)，極大地提高了吞吐率，也可以通過選用UltraScale 系列FPGA進(jìn)一步提升吞吐率。本文提出的實現(xiàn)架構(gòu)向下兼容ZUC-128 算法，易于FPGA 實現(xiàn)，可廣泛應(yīng)用于4G-LTE和5G-NR 移動通信中。