張子昂，陳朝暉

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

1.2 貢獻點：完善的四級流水線

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

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

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

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

1.2.2 流水線過程分析

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

表1 完整四級流水線結(jié)構(gòu)的運算過程

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

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

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

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

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

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

1.2.3 具體優(yōu)化點

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

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

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

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

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

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

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

1.3 創(chuàng)新點：改進的五級流水線

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

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

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

1.3.2 流水線過程分析

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

表2 五級流水線結(jié)構(gòu)的運算過程

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

1.3.3 具體優(yōu)化點

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

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

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

2 實驗結(jié)果

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

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

圖8 布線后時序仿真

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

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

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

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

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

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

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

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

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

3 結(jié) 語

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