周雍浩，董婉瑩，李斌，陳曉杰，馮峰

（1.鄭州大學(xué)電氣工程學(xué)院，鄭州450001；2.鄭州大學(xué)信息工程學(xué)院，鄭州450001；3.中國人民解放軍信息工程大學(xué)數(shù)學(xué)工程與先進(jìn)計算國家重點實驗室，鄭州450001）

0 引言

安全散列算法（Secure Hash Algorithm，SHA）是由美國NIST 發(fā)布的一種密碼散列函數(shù)，其作用是對不定長的消息計算出一個固定長度的消息摘要[1]。SHA 具有單向性和抗碰撞性，是密碼學(xué)中的一個重要工具，被廣泛應(yīng)用于數(shù)據(jù)完整性校驗、數(shù)字簽名、消息鑒別和密碼協(xié)議等信息安全領(lǐng)域[2]。但是，隨著計算機技術(shù)的快速發(fā)展和破解技術(shù)的增強，MD5 和SHA-1 相繼被成功破解，變得并不安全。因此，NIST 制定了新的SHA3 標(biāo)準(zhǔn)，并將Keccak 算法選定為SHA3 標(biāo)準(zhǔn)的單向散列算法[3]。由于SHA3 算法本身的復(fù)雜性且在應(yīng)用中經(jīng)常被多次迭代使用，所以如何實現(xiàn)更快速的SHA3 算法，成為了亟待解決的問題。FPGA 作為可重構(gòu)硬件，憑借著高性能、低功耗的特性成為了實現(xiàn)密碼算法的首選平臺。國內(nèi)外眾多學(xué)者也在FPGA 上對SHA3 算法進(jìn)行了優(yōu)化、實現(xiàn)，但是很少涉及全流水線結(jié)構(gòu)和并行的設(shè)計方案。

綜上，本文通過分析SHA3 算法的關(guān)鍵路徑，使用可重構(gòu)硬件FPGA 和流水線技術(shù)，并以展開結(jié)構(gòu)的方法進(jìn)一步優(yōu)化算法，達(dá)到了增加工作頻率和并行化的目的，以實現(xiàn)高效能的SHA3 算法。

1 背景知識

1.1 SHA3簡介

Keccak 算法是SHA3 標(biāo)準(zhǔn)選定的算法，采用不同于MD（如MD5）類結(jié)構(gòu)的海綿結(jié)構(gòu)。海綿結(jié)構(gòu)如圖1所示。

圖1 海綿結(jié)構(gòu)

其中，壓縮函數(shù)Keccak-f 是海綿結(jié)構(gòu)的計算引擎，它封裝了海綿結(jié)構(gòu)的主要計算邏輯。內(nèi)部狀態(tài)是海綿結(jié)構(gòu)計算操作數(shù)的載體，內(nèi)部狀態(tài)在海綿結(jié)構(gòu)中作為壓縮函數(shù)Keccak-f 的輸入輸出。b 代表內(nèi)部狀態(tài)的比特長度，b 的具體數(shù)值必須滿足公式（1）：

因此，b∈{25，50，100，200，400，800，1600}。海綿結(jié)構(gòu)由b 還定義了兩個分量，比特率（bitrate，用r 表示）和容量（capacity，用c 表示），且b、r 和c 滿足關(guān)系b=r+c，三者的具體值均由使用者決定。圖1 中{M1，...，Mn}是對填充后消息的分組，分組長度等于r；{H1，...，Hm}是分步提取的散列值，每個散列值的長度等于r，提取步數(shù)m 由使用者決定，所有散列值按提取順序排列合并成最終的輸出散列值。

海綿結(jié)構(gòu)在工作過程上分為吸收和擠出兩個階段，吸收階段是將輸入消息根據(jù)分組依次“攪拌”進(jìn)它的內(nèi)部狀態(tài)的過程，擠出階段是分步提取輸出散列值的過程。在吸收階段，初始時將內(nèi)部狀態(tài)的所有比特位置0，接下來反復(fù)進(jìn)行以下過程，直到消息分組耗盡。該過程是，先將消息分組Mi（1 ≤i ≤n）與內(nèi)部狀態(tài)的前r 個比特異或，然后將內(nèi)部狀態(tài)輸入壓縮函數(shù)Keccak-f，最后壓縮函數(shù)Keccak-f 處理后輸出內(nèi)部狀態(tài)。在擠出階段，根據(jù)使用者選擇的步數(shù)，分步重復(fù)以下過程。該過程是，先獲取內(nèi)部狀態(tài)的前r 個比特，然后將內(nèi)部狀態(tài)輸入壓縮函數(shù)Keccak-f，最后壓縮函數(shù)Keccak-f 處理后輸出內(nèi)部狀態(tài)。

對于壓縮函數(shù)Keccak-f。內(nèi)部狀態(tài)在輸入壓縮函數(shù)Keccak-f 后和壓縮函數(shù)Keccak-f 輸出前都需要經(jīng)過格式轉(zhuǎn)換，即壓縮函數(shù)Keccak-f 處理過程中內(nèi)部狀態(tài)為函數(shù)可操作的格式。壓縮函數(shù)Keccak-f 中輪計算的輪數(shù)由公式（2）計算得到，其中變量l 來自于公式（1），因此間接取決于使用者的選擇。

在SHA3 標(biāo)準(zhǔn)下Keccak 算法具有以下特點：

（1）在輸入上，采用Keccak 算法的SHA3 沒有長度限制。

（2）在輸出上，Keccak 算法本身可以生成任意長度的散列值，但為了配合SHA2 的散列值長度，SHA3 標(biāo)準(zhǔn)中規(guī)定了SHA3-224、SHA3-256、SHA3-384、SHA3-512 這4 種版本。本文實現(xiàn)的是SHA3-256，即最終輸出的散列值長度為256 比特。

（3）在參數(shù)選取上，SHA3 標(biāo)準(zhǔn)選定了b 的取值為1600，從而壓縮函數(shù)Keccak-f 的輪計算輪數(shù)為24。

1.2 FPGA簡介

現(xiàn)場可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA），是一種擁有高密度邏輯、大量計算和存儲資源的高性能計算平臺。FPGA 的本質(zhì)是無指令、無需共享內(nèi)存的體系結(jié)構(gòu)，通過編程可定義其中的單元配置和鏈接架構(gòu)進(jìn)行計算。FPGA 以查找表和寄存器實現(xiàn)復(fù)雜的組合邏輯操作，且片上內(nèi)存BRAM 屬于各自的邏輯區(qū)域，無需不必要的仲裁和緩存。因此FPGA的運算速度足夠快，具有很強的計算能力和靈活性，使得FPGA 可重構(gòu)計算系統(tǒng)成為加速科學(xué)計算的一種重要選擇[4]。如圖2 所示，給出了一般的FPGA 芯片的邏輯結(jié)構(gòu)。

圖2 FPGA內(nèi)部邏輯結(jié)構(gòu)

據(jù)此，文獻(xiàn)[5]提出了一種流水線硬件架構(gòu)，該架構(gòu)支持4 種SHA3 操作模式，以及可同時支持多塊和多消息處理的FPGA 器件的高性能實現(xiàn)，在不同F(xiàn)PGA器件上的實驗結(jié)果證明提出的設(shè)計實現(xiàn)了吞吐量的顯著提高。文獻(xiàn)[6]通過流水線、子流水線和展開的方法，優(yōu)化實現(xiàn)了SHA3 的五種方案，其中方案五在吞吐量和面積效率上取得了平衡。文獻(xiàn)[7]根據(jù)SHA3 的結(jié)構(gòu)特點和FPGA 內(nèi)部邏輯，主要采用折疊的方式對其進(jìn)行了優(yōu)化，減少了所需的面積資源并獲得了更短的數(shù)據(jù)路徑，算法效率至少提高了50%。文獻(xiàn)[8]采用SoC設(shè)計，在FPGA 端實現(xiàn)了SHA3 算法，并通過AHB 接口與ARM 端互連，提高了算法應(yīng)用范圍。文獻(xiàn)[9]采用基于鎖存器的時鐘門控技術(shù)優(yōu)化了SHA3 算法，并有效降低了功耗。但是這些方案本質(zhì)上仍是串行計算，只是局部使用了流水線技術(shù)，仍有提升空間。

綜上，本文通過深入分析SHA3 算法，以全流水線結(jié)構(gòu)，優(yōu)化設(shè)計適合FPGA 的數(shù)據(jù)通路，以提高算法速度。

2 SHA3在FPGA上的優(yōu)化及流水線實現(xiàn)

2.1 關(guān)鍵計算分析

從SHA3 的算法流程中可以看出，Keccak-f 計算是關(guān)鍵。想要提高算法的性能，必須對Keccak-f 深入分析。當(dāng)b=1600 時，將輸入數(shù)據(jù)轉(zhuǎn)換為5×5×64 的三維結(jié)構(gòu)，并用元素為64 位的二維數(shù)組A 表示，則有A[x、y]，其中x、y∈[0，4]。Keccak-f 每輪總共有5 個計算步驟[10]，分別用θ，ρ，π，χ，ι表示，每個計算步驟的具體運算如下所示：

上述運算步驟中，⊕代表按位異或運算，?代表按位取反運算，∧代表按位與運算。rot 函數(shù)表示循環(huán)移位。r[x][y]和RC 分別是移位位數(shù)和輪常數(shù)。

θ的處理過程較復(fù)雜，可預(yù)先循環(huán)展開，對操作的數(shù)據(jù)進(jìn)行計算，并確定需要操作數(shù)據(jù)的位置，從而方便后續(xù)的實現(xiàn)。ρ是對θ的輸出進(jìn)行移位，π的功能是對ρ的輸出進(jìn)行位置交換，因此可通過預(yù)先計算出交換的位置以及需要的移位，從而將ρ、π進(jìn)行合并。χ是對π的輸出進(jìn)行運算，ι對χ的輸出進(jìn)行一次常量的異或運算，因此可將χ與ι進(jìn)行合并。通過對這五個步驟進(jìn)行預(yù)計算、合并等預(yù)處理，從而簡化了Keccak-f 的計算且降低了實現(xiàn)復(fù)雜度。

2.2 全流水線實現(xiàn)

SHA3 算法中Keccak-f 包含24 輪重復(fù)的運算，且每一輪的輸入、輸出僅與相鄰的輪具有依賴關(guān)系，因此可將SHA3 算法通過流水線技術(shù)實現(xiàn)為并行算法，從而降低時間復(fù)雜度。

流水線是一種通過增加空間的利用來減少時間消耗的時空映射技術(shù)。通過前述的預(yù)處理，每輪的五個步驟變?yōu)榱甩?、ρπ、χι三步，可以采?4 級流水線結(jié)構(gòu)實現(xiàn)。具體的，每一級流水線都包含三步運算，并壓縮在一個子模塊中，共24 個子模塊，對應(yīng)24 輪運算。同時，為了在一個時鐘計算出一輪運算結(jié)果，將θ、ρπ實現(xiàn)為線網(wǎng)型的組合邏輯，而χι實現(xiàn)為依賴于時鐘信號的時序邏輯，算法在FPGA 中實現(xiàn)的時序結(jié)構(gòu)如圖3所示。

圖3 SHA3算法FPGA實現(xiàn)流水線結(jié)構(gòu)

圖3 中一個時鐘周期的每級流水線內(nèi)三個計算步驟串行執(zhí)行，而24 個子計算模塊并行運行，圖中的箭頭指向表示數(shù)據(jù)的傳遞方向。當(dāng)有一組數(shù)據(jù)需要進(jìn)行Keccak-f 處理時，需經(jīng)過24 個時鐘周期處理完畢，而當(dāng)有n 組數(shù)據(jù)需要進(jìn)行Keccak-f 處理時，只需要n+23 個時鐘周期，時間復(fù)雜度為Ο（n）。因此，在滿負(fù)荷的情況下，一組數(shù)據(jù)僅需要一個時鐘周期即可產(chǎn)生結(jié)果，從而通過算法的并行化，減少了計算的時間，提升了運行效率。

2.3 展開再優(yōu)化

通過對Keccak-f 的分析可知，其每輪運算包含76次異或運算，25 次位非運算，50 次位與運算以及49 次移位運算。雖然FPGA 對于位運算具有較好的性能表現(xiàn)，但是在一個時鐘周期內(nèi)將200 次運算串行執(zhí)行結(jié)束，會存在較大的延時。在全流水線結(jié)構(gòu)中，算法的執(zhí)行效率由頻率決定，因此，提高算法的頻率，減少算法的延時是一種有效的優(yōu)化方法。

Keccak-f 每輪運算的計算步驟間數(shù)據(jù)是依次傳遞的，因此可將每個時鐘周期內(nèi)串行執(zhí)行的三步進(jìn)行時鐘展開。由于ρπ僅包含移位運算，結(jié)構(gòu)特殊，因此可將ρπ獨立進(jìn)行一個時鐘周期的運算，而將θ和χι在另一個時鐘周期內(nèi)串行運行，即由原來的一個時鐘展開為兩個時鐘，加上最后輸出消耗的一個時鐘，最終采用的是49 級全流水線結(jié)構(gòu)進(jìn)行實現(xiàn)，該優(yōu)化結(jié)構(gòu)如圖4 所示。

圖4 SHA3算法流水線優(yōu)化結(jié)構(gòu)圖

圖4 中算法的實現(xiàn)結(jié)構(gòu)與圖3 相比，雖然時鐘周期數(shù)增加了一倍，但是時間復(fù)雜度仍為Ο（n），即在相同頻率下，兩種結(jié)構(gòu)性能相同。但是，由于每一級流水線上的計算延時降低，使得該實現(xiàn)在FPGA 的綜合編譯結(jié)果中可以獲得更高的頻率表現(xiàn)，從而使SHA3 算法的性能得到進(jìn)一步提升。

3 實驗結(jié)果與分析

本實驗中的一塊FPGA 加速卡包含四顆FPGA 芯片，該芯片型號為Xilinx 公司的xcku060，其查找表LUTs 資源是331680，F(xiàn)lipFlops 寄存器資源是663360，軟件為Vivado 2018.2。實驗對優(yōu)化后的SHA3 算法流水線進(jìn)行了仿真分析；并對比了SHA3 串行和兩種流水線資源使用情況；然后與GPU 在性能和功耗方面進(jìn)行了對比；最后與其他方案進(jìn)行了對比，說明本文方案的有效性。

3.1 仿真分析

優(yōu)化后的SHA3 算法流水線仿真如圖5 所示。其中in_valid 為輸入有效信號；in_data 為輸入數(shù)據(jù)；out_valid 為輸出有效信號；out_data 為輸出數(shù)據(jù)；其他為中間結(jié)果信號。

圖5 SHA3算法仿真圖

從圖5 中可以看出，對于優(yōu)化后的SHA3 算法，當(dāng)連續(xù)輸入50 個數(shù)據(jù)后，在4866.191ns 連續(xù)產(chǎn)生50 組輸出，充分發(fā)揮了流水線并行的優(yōu)勢。

3.2 資源占用

這里分別采用串行和兩種流水線實現(xiàn)了SHA3，其資源占用對比如表1 所示。

表1 SHA3 串行和兩種流水線資源占用

從表1 中可以看出，串行SHA3 每24 個時鐘處理1 組數(shù)據(jù)，而流水線SHA3 可連續(xù)處理n 組數(shù)據(jù)，兩種流水線結(jié)構(gòu)分別從第25 個時鐘和第50 個時鐘開始依次輸出它們的結(jié)果。由于優(yōu)化后的全流水線SHA3 算法通過增加流水線的級數(shù)來降低單個時鐘周期的延時，因此從實驗結(jié)果也可以看出優(yōu)化后的實現(xiàn)與未優(yōu)化的相比具有更高的頻率。對應(yīng)的，SHA3 串行的處理速度為13 M 次/秒，而展開流水線為415 M 次/秒，在處理速度上SHA3 流水線是串行的31.92 倍，具有明顯優(yōu)勢。

3.3 與GPU對比

描述SHA3 計算部件性能的指標(biāo)有速度、功率、能效比。其中能效比表示計算部件性能與功率之比，簡記為EER（Energy Efficiency Ratio），計算公式3 如下：

表2 給出了本實驗中的FPGA 加速卡與GPU 在各方面指標(biāo)上的對比。其中，單顆FPGA 芯片內(nèi)放置了4 個優(yōu)化后的SHA3 流水線模塊，工作頻率為200 MHz；GPU 型號為NVIDIA GeForce GTX 1080。

表2 FPGA 與GPU 指標(biāo)對比

從表2 中可以看出，F(xiàn)PGA 不僅性能較高，且功耗較低，具有很高的能效比，是GPU 的5.65 倍，更具有應(yīng)用價值。

3.4 與其他方案對比

與其他方案的對比如表3 所示。

通過對比可以發(fā)現(xiàn)，除文獻(xiàn)[3]外，本文實現(xiàn)的頻率優(yōu)于大多數(shù)方案。同時由于采用了全流水線結(jié)構(gòu)，本文實現(xiàn)的吞吐量高于其他方案，充分發(fā)揮了FPGA 的計算優(yōu)勢。

4 結(jié)語

本文提出了可重構(gòu)的SHA3 算法流水線結(jié)構(gòu)及其優(yōu)化、實現(xiàn)。通過對SHA3 算法的深入分析，使用高效能的FPGA 硬件計算平臺，縮短了SHA3 關(guān)鍵路徑，并以全流水線結(jié)構(gòu)和展開的實現(xiàn)方式，有效地提高了工作頻率和計算速度，具有很高的實際應(yīng)用價值。

表3 與其他方案對比