張子昂，陳朝暉

（中國(guó)科學(xué)院大學(xué) 密碼學(xué)院，北京 100049）

0 引 言

祖沖之序列密碼算法（ZUC）是我國(guó)國(guó)產(chǎn)的序列密碼算法，現(xiàn)已成為ISO/IEC 國(guó)際標(biāo)準(zhǔn)。通過(guò)分析發(fā)現(xiàn)，在增大ZUC 硬件實(shí)現(xiàn)操作頻率同時(shí)減少產(chǎn)生密鑰字的時(shí)鐘周期數(shù)的情況下，其實(shí)際運(yùn)行的吞吐量能得到顯著的提升。基于此，在本文對(duì)ZUC 的硬件實(shí)現(xiàn)設(shè)計(jì)中，將著重優(yōu)化線性反饋移位寄存器（Linear Feedback Shift Register，LFSR）的更新過(guò)程耗時(shí)和讀取S 盒的面積消耗。

針對(duì)LFSR 更新路徑的優(yōu)化設(shè)計(jì)，郭泓鍵等人[1]提出了使用“循環(huán)左移”運(yùn)算替代“2 的冪指數(shù)乘法”運(yùn)算的設(shè)計(jì)方案，這一思路為本文提供了基礎(chǔ)優(yōu)化策略。在第十一屆國(guó)際信息與通信安全會(huì)議上，Wang 等人[2]提出了實(shí)現(xiàn)ZUC在現(xiàn)場(chǎng)可編程邏輯門(mén)陣列（Field Progammable Gate Array，F(xiàn)PGA）器件上運(yùn)行的“四級(jí)流水線”結(jié)構(gòu)，其設(shè)計(jì)使用進(jìn)位保存加法器（Carry Save Adder，CSA）樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)LFSR 的長(zhǎng)更新過(guò)程，但因缺失了LFSR 的初始化過(guò)程，故該方案并不適用于實(shí)際的應(yīng)用。在中國(guó)密碼學(xué)會(huì)2013 年密碼芯片學(xué)術(shù)會(huì)議上，Liu 等人[3]提出了一種高吞吐量的“混合二級(jí)流水線”結(jié)構(gòu)的設(shè)計(jì)方案，該方案考慮了LFSR 更新過(guò)程中初始化階段的運(yùn)算，并采用三輸入CSA 來(lái)處理數(shù)值的連續(xù)加法運(yùn)算。在INDOCRYPT 2011 上，Gupta 等人[4]提出了“THREE-ZUC”設(shè)計(jì)結(jié)構(gòu)，并生成了一個(gè)擴(kuò)展后的版本[5]，但該方案的實(shí)際運(yùn)行結(jié)果并不理想。

此外，在硬件上進(jìn)行ZUC 實(shí)現(xiàn)時(shí)，S 盒運(yùn)算過(guò)程也是影響算法運(yùn)行吞吐率的重要因素之一。在以往實(shí)現(xiàn)的設(shè)計(jì)中，郭泓鍵等人[1]提供了通過(guò)查表（Look Up Table，LUT）方式快速實(shí)現(xiàn)S 盒變換的思路。郁寧亞等人[6]提出了使用只讀存儲(chǔ)器（Read-Only Memory，ROM）對(duì)S 盒中固定數(shù)值進(jìn)行存儲(chǔ)的方案，該思路也被應(yīng)用于本文的設(shè)計(jì)中。

本文首先完善了“四級(jí)流水線”[2]結(jié)構(gòu)中LFSR 的初始化過(guò)程，并在此基礎(chǔ)上提出了一種改進(jìn)型的“五級(jí)流水線”結(jié)構(gòu)方案，該結(jié)構(gòu)在理論上能達(dá)到較高的吞吐量。

1 ZUC 在FPGA 上的實(shí)現(xiàn)

ZUC 在邏輯上采用3 層結(jié)構(gòu)設(shè)計(jì)：線性反饋移位寄存器LFSR、比特重組BR 和非線性函數(shù)F，其結(jié)構(gòu)如圖1 所示，本文基于Verilog HDL 對(duì)硬件器件、信號(hào)及時(shí)序可直接操作的特性對(duì)其硬件實(shí)現(xiàn)進(jìn)行編碼設(shè)計(jì)。

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

根據(jù)算法規(guī)范[7]，可知式（1）是ZUC 算法系統(tǒng)運(yùn)行時(shí)最為耗時(shí)的運(yùn)算路徑，后續(xù)本文將詳細(xì)闡述對(duì)該過(guò)程的設(shè)計(jì)優(yōu)化策略。同時(shí)，針對(duì)非線性函數(shù)過(guò)程中S 盒讀取操作的設(shè)計(jì)，本文通過(guò)重用一半S 盒存儲(chǔ)資源的消耗面積的方式來(lái)進(jìn)行優(yōu)化。另外，文中的設(shè)計(jì)均使用ROM對(duì)S 盒固定數(shù)據(jù)值進(jìn)行存儲(chǔ)，以加快在非線性函數(shù)過(guò)程運(yùn)行時(shí)寄存器單元R1和R2的更新頻率。

1.1 基礎(chǔ)：四級(jí)流水線結(jié)構(gòu)

為了實(shí)現(xiàn)ZUC 的高吞吐量運(yùn)行，文獻(xiàn)[2]中設(shè)計(jì)了一種四級(jí)流水線結(jié)構(gòu)，如圖2 所示。因其在硬件實(shí)現(xiàn)時(shí)關(guān)鍵路徑只包含一個(gè)加法運(yùn)算和一個(gè)模 231-1運(yùn)算，所以該設(shè)計(jì)能夠?qū)崿F(xiàn)較高的吞吐量。但由于在初始化階段關(guān)鍵路徑中包含了一個(gè)額外用于計(jì)算長(zhǎng)模加運(yùn)算結(jié)果值和外部輸入U(xiǎn)的模加結(jié)果S16的32 比特加法器，且U和S16必須是在連續(xù)的時(shí)鐘周期中計(jì)算，這就限制了該設(shè)計(jì)的流水線結(jié)構(gòu)不能達(dá)到“包含初始化階段計(jì)算過(guò)程”和“限制流水線關(guān)鍵路徑為一個(gè)兩輸入模加運(yùn)算”兩個(gè)目標(biāo)的共存，故該方案不靈活。

圖2 僅包含工作階段的四級(jí)流水線結(jié)構(gòu)

1.2 貢獻(xiàn)點(diǎn)：完善的四級(jí)流水線

本節(jié)設(shè)計(jì)了一個(gè)完整的四級(jí)流水線結(jié)構(gòu)以實(shí)現(xiàn)在一個(gè)時(shí)鐘周期內(nèi)完成LFSR 關(guān)鍵路徑和密鑰字生成的運(yùn)算。

1.2.1 算法體系結(jié)構(gòu)

該算法將LFSR 過(guò)程的關(guān)鍵路徑縮減為一個(gè)三輸入加法并模 231-1運(yùn)算，且需要添加額外的寄存器資源來(lái)存儲(chǔ)每一級(jí)流水線(x+y)或(x+y+z)的輸出數(shù)據(jù)值。同時(shí)，針對(duì)最后一級(jí)的三輸入運(yùn)算，本節(jié)采用優(yōu)化結(jié)構(gòu)CSA 來(lái)編程實(shí)現(xiàn)，這部分內(nèi)容在下文詳細(xì)敘述。如圖3 展示了完整四級(jí)流水線的體系結(jié)構(gòu)。

圖3 完整四級(jí)流水線結(jié)構(gòu)

1.2.2 流水線過(guò)程分析

在該流水線結(jié)構(gòu)初始化階段，LFSR 中的16個(gè)寄存器右移更新操作將持續(xù)4 個(gè)時(shí)鐘周期不執(zhí)行，之后進(jìn)入算法執(zhí)行過(guò)程。如表1 所示，為完整四級(jí)流水線結(jié)構(gòu)的運(yùn)算過(guò)程。

表1 完整四級(jí)流水線結(jié)構(gòu)的運(yùn)算過(guò)程

在流水線初始化過(guò)程的第一個(gè)時(shí)鐘周期中，運(yùn)算過(guò)程A 和B 將并行計(jì)算。其余的過(guò)程在這個(gè)時(shí)鐘周期中不工作，它們均處于等待狀態(tài)。

在第二個(gè)時(shí)鐘周期，過(guò)程A 和過(guò)程B 都將進(jìn)入到第二輪的計(jì)算，相當(dāng)于提前一個(gè)周期計(jì)算結(jié)果值，并且這個(gè)周期LFSR 不執(zhí)行右移更新操作。同時(shí)，過(guò)程C 將對(duì)上一個(gè)時(shí)鐘周期中過(guò)程A 和過(guò)程B 產(chǎn)生的結(jié)果值進(jìn)行運(yùn)算，其余的運(yùn)算過(guò)程仍處于等待狀態(tài)。

時(shí)鐘脈沖到第三個(gè)周期時(shí)，過(guò)程A、過(guò)程B、過(guò)程C 都將在LFSR 不更新的情況下進(jìn)行運(yùn)算，且過(guò)程D 獲取到上一個(gè)周期過(guò)程C 產(chǎn)生的結(jié)果值并進(jìn)行運(yùn)算。而過(guò)程E 的運(yùn)算處于等待狀態(tài)。

第四個(gè)時(shí)鐘周期與第三個(gè)時(shí)鐘周期的算法執(zhí)行過(guò)程相似，但過(guò)程A、過(guò)程B、過(guò)程C 和過(guò)程D 繼續(xù)運(yùn)算并把結(jié)果值帶入到下一個(gè)計(jì)算回合。即在這一個(gè)時(shí)鐘周期是表中的過(guò)程E 的第一次運(yùn)算過(guò)程，并最終得到結(jié)果值S16，即下一輪運(yùn)算時(shí)所需要的LFSR 中的值S15。在這一個(gè)時(shí)鐘周期，需要注意對(duì)運(yùn)算輸入31 比特?cái)?shù)據(jù)U的選通。

在第五個(gè)時(shí)鐘周期，需要移動(dòng)S16賦值給S15，然后按照算法邏輯結(jié)構(gòu)中的布局LFSR進(jìn)行右移操作以使其余的寄存器單元更新。

此時(shí)，該流水線結(jié)構(gòu)的初始化過(guò)程完成，整個(gè)算法系統(tǒng)將進(jìn)入實(shí)際運(yùn)行階段，且LFSR 的寄存器單元在之后的每個(gè)時(shí)鐘周期都進(jìn)行右移更新操作，其完整的算法偽代碼如算法1 所示。

1.2.3 具體優(yōu)化點(diǎn)

在以上的算法中，“Add2Mod()”代表兩輸入的模加運(yùn)算，本節(jié)對(duì)其在硬件上的實(shí)現(xiàn)進(jìn)行了優(yōu)化，以縮短模加運(yùn)算的耗時(shí)。這里將兩輸入加法運(yùn)算(A+B) 的進(jìn)位設(shè)置為Carry。之后，第一部分操作是計(jì)算“A+B+1 ”，相當(dāng)于提前計(jì)算進(jìn)位為1 時(shí)的模運(yùn)算結(jié)果值；第二部分操作是直接計(jì)算“A+B”，把這一步產(chǎn)生的進(jìn)位值賦值給Carry。以上兩部分操作并行計(jì)算、互不干擾，最后通過(guò)對(duì)第二部分產(chǎn)生的進(jìn)位值進(jìn)行選通來(lái)確定最后模加運(yùn)算的結(jié)果值。該方法的體系結(jié)構(gòu)如圖4 所示。

圖4 優(yōu)化后的兩輸入模加運(yùn)算結(jié)構(gòu)

在利用硬件實(shí)現(xiàn)上述算法中的三輸入模加運(yùn)算“Add3Mod()”時(shí)，普通的運(yùn)算方式會(huì)消耗大量的資源且不能達(dá)到較好的耗時(shí)要求。因此，本節(jié)使用如圖5 所示的CSA 結(jié)構(gòu)來(lái)進(jìn)行這部分運(yùn)算。

圖5 三輸入模加運(yùn)算結(jié)構(gòu)

CSA 的具體邏輯過(guò)程為：當(dāng)計(jì)算(A+B+C)mod(231-1)時(shí)，首先產(chǎn)生3 個(gè)數(shù)據(jù)求和的進(jìn)位為Carry，之后計(jì)算三數(shù)相加的本位保留值Sum，最后利用進(jìn)位傳播加法器（Carry Propagate Adder，CPA）結(jié)合公式計(jì)算模運(yùn)算的結(jié)果值。如式（2）所示。

式中：Carry為A，B，C3 個(gè)數(shù)相加的進(jìn)位；Sum為A，B，C3 個(gè)數(shù)相加的本位保留值；Out為計(jì)算 (A+B+C)mod(231-1)得到的結(jié)果值。

綜合以上對(duì)算法中的加法運(yùn)算和模運(yùn)算的優(yōu)化設(shè)計(jì)，該設(shè)計(jì)最終使LFSR 的關(guān)鍵路徑耗時(shí)縮短為一個(gè)三輸入32 比特加法器和一個(gè)兩輸入32 比特加法器的延遲。ZUC 算法系統(tǒng)的關(guān)鍵路徑則是在此基礎(chǔ)上增加一個(gè)32 比特加法器的延遲，這是因?yàn)樗惴ㄏ到y(tǒng)中非線性函數(shù)過(guò)程的32比特輸出W影響著LFSR初始化階段的輸入U(xiǎn)，故W的計(jì)算過(guò)程和完整的四級(jí)流水線結(jié)構(gòu)最后一級(jí)的運(yùn)算必然是串行的，這就嚴(yán)重影響了整個(gè)算法運(yùn)行的吞吐量，下文中提出了針對(duì)這一部分耗時(shí)進(jìn)行優(yōu)化的具體方案。

1.3 創(chuàng)新點(diǎn)：改進(jìn)的五級(jí)流水線

1.3.1 算法體系結(jié)構(gòu)

由于LFSR 在初始化階段的路徑包含了外部輸入數(shù)據(jù)的運(yùn)算，比其在工作階段的耗時(shí)更大，因此本節(jié)提出了一種在“四級(jí)流水線結(jié)構(gòu)”基礎(chǔ)上的改進(jìn)型流水線結(jié)構(gòu)。如圖6 展示了該五級(jí)流水線的體系結(jié)構(gòu)。

圖6 五級(jí)流水線結(jié)構(gòu)

1.3.2 流水線過(guò)程分析

在這種體系結(jié)構(gòu)中，LFSR 無(wú)論是在初始化模式還是在工作模式都是每個(gè)時(shí)鐘周期更新一次，其算法邏輯如表2 所示。

表2 五級(jí)流水線結(jié)構(gòu)的運(yùn)算過(guò)程

相對(duì)于上一節(jié)提出的四級(jí)流水線體系結(jié)構(gòu)，本節(jié)的方案僅僅是把LFSR 過(guò)程外部輸入U(xiǎn)的模加運(yùn)算作為一級(jí)流水線，并且該運(yùn)算位于五級(jí)流水線計(jì)算下一輪S15值的操作之前。在四級(jí)流水線體系結(jié)構(gòu)中，最后一級(jí)過(guò)程的W運(yùn)算和S16運(yùn)算是串行的，這意味著必須先有W的結(jié)果值而后才能計(jì)算S16的值。而在本節(jié)提出的五級(jí)流水線結(jié)構(gòu)中，下一輪需要的W值將提前計(jì)算，這個(gè)計(jì)算過(guò)程的前提輸入是該時(shí)鐘周期在線網(wǎng)器件上的經(jīng)流水線最后一級(jí)計(jì)算而得的S16值（將在下一個(gè)時(shí)鐘節(jié)拍上升沿賦值到寄存器單元中）。

1.3.3 具體優(yōu)化點(diǎn)

在表2 描述的流水線算法流程中，每一級(jí)都是一個(gè)兩輸入的模加法運(yùn)算。針對(duì)這一運(yùn)算過(guò)程，使用如圖7 所示的體系結(jié)構(gòu)進(jìn)行運(yùn)算。該結(jié)構(gòu)由兩個(gè)32 比特加法器直接相連接實(shí)現(xiàn)加法運(yùn)算、模 231-1運(yùn)算，這種方案實(shí)現(xiàn)的運(yùn)算耗時(shí)是兩個(gè)32 比特加法器的延遲。該體系結(jié)構(gòu)是處于“控制流水線關(guān)鍵路徑為一個(gè)兩輸入模加運(yùn)算”和“在完整四級(jí)流水線基礎(chǔ)上改進(jìn)最后的三輸入模加運(yùn)算”兩種方案折中的優(yōu)化，并在實(shí)際的硬件實(shí)現(xiàn)上能夠得到比1.2 節(jié)提出的完整四級(jí)流水線體系結(jié)構(gòu)更好的性能結(jié)果。

圖7 兩輸入模加運(yùn)算結(jié)構(gòu)

另外，在編碼實(shí)現(xiàn)時(shí)，使用如算法2 所示的邏輯以控制整個(gè)算法的時(shí)鐘節(jié)拍的統(tǒng)計(jì)與定位，這樣方便控制ZUC 的初始化階段和工作階段的轉(zhuǎn)換。

2 實(shí)驗(yàn)結(jié)果

2.1 仿真及FPGA 測(cè)試結(jié)果

在設(shè)計(jì)具體實(shí)現(xiàn)時(shí)，使用硬件描述性語(yǔ)言Verilog HDL 來(lái)編程，如圖8 展示了利用Vivado 在XILINX-AX7325 開(kāi)發(fā)板上布線后時(shí)序仿真的結(jié)果。

圖8 布線后時(shí)序仿真

將工程源程序綜合、布線、生成比特文件并下載到FPGA 上，運(yùn)行后可看到如圖9 中的調(diào)試結(jié)果。

圖9 上板后調(diào)試結(jié)果

這里對(duì)本文提出的兩種方案的實(shí)際運(yùn)行結(jié)果進(jìn)行記錄及分析。評(píng)估算法系統(tǒng)的運(yùn)行效率時(shí)，主要考慮吞吐率和芯片面積兩個(gè)指標(biāo)[8]。其中，吞吐量的計(jì)算方式為：吞吐量=（輸入信息數(shù)據(jù)塊比特?cái)?shù)×算法系統(tǒng)最大工作頻率）÷算法系統(tǒng)處理一個(gè)數(shù)據(jù)分塊需要消耗的時(shí)鐘周期數(shù)[9]。

如表3 所示，祖沖之序列密碼算法能夠根據(jù)在硬件上不同的實(shí)現(xiàn)來(lái)滿足其對(duì)吞吐量和資源消耗的調(diào)整需求，這符合對(duì)現(xiàn)代密碼算法的設(shè)計(jì)要求。實(shí)驗(yàn)使用Vivado 開(kāi)發(fā)工具對(duì)源程序進(jìn)行綜合布線，表4、表5 分別顯示了四級(jí)流水線和五級(jí)流水線結(jié)構(gòu)在進(jìn)行手動(dòng)物理布線優(yōu)化后的資源面積消耗情況。

表3 ZUC 理論運(yùn)行結(jié)果

表4 四級(jí)流水線布線后資源消耗結(jié)果

對(duì)比本文提出的四級(jí)流水線和五級(jí)流水線兩種體系結(jié)構(gòu)，發(fā)現(xiàn)后者在前者的基礎(chǔ)上僅僅進(jìn)行了運(yùn)算結(jié)構(gòu)上的改變，就可以在增大極小部分資源消耗面積的情況下顯著提高算法系統(tǒng)的運(yùn)算吞吐量。

2.2 算法系統(tǒng)關(guān)鍵路徑對(duì)比

本文提出的兩種方案與以往設(shè)計(jì)的關(guān)鍵路徑對(duì)比如表6 所示。

3 結(jié) 語(yǔ)

為滿足服務(wù)器對(duì)數(shù)據(jù)實(shí)時(shí)高速加密傳輸、備份的需求，本文提出了兩種基于ZUC 在FPGA硬件平臺(tái)上的高吞吐量設(shè)計(jì)方案，其理論工作頻率分別為7.10 Gbit/s 和7.73 Gbit/s。但受硬件平臺(tái)晶振產(chǎn)生的時(shí)鐘頻率大小的限制，以上結(jié)構(gòu)在測(cè)試所用的XILINX-AX7325 平臺(tái)上實(shí)際最大吞吐量為6.4 Gbit/s。通過(guò)分析文中的算法系統(tǒng)，可以發(fā)現(xiàn)其運(yùn)行時(shí)的關(guān)鍵路徑還不是最短的，因此，之后將在技術(shù)設(shè)計(jì)方面繼續(xù)深入探尋具備更短關(guān)鍵路徑的體系結(jié)構(gòu)。