可重構的SHA-3 算法流水線結構優化及實現

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

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

0 引言

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

綜上，本文通過分析SHA3 算法的關鍵路徑，使用可重構硬件FPGA 和流水線技術，并以展開結構的方法進一步優化算法，達到了增加工作頻率和并行化的目的，以實現高效能的SHA3 算法。

1 背景知識

1.1 SHA3簡介

Keccak 算法是SHA3 標準選定的算法，采用不同于MD（如MD5）類結構的海綿結構。海綿結構如圖1所示。

圖1 海綿結構

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

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

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

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

在SHA3 標準下Keccak 算法具有以下特點：

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

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

（3）在參數選取上，SHA3 標準選定了b 的取值為1600，從而壓縮函數Keccak-f 的輪計算輪數為24。

1.2 FPGA簡介

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

圖2 FPGA內部邏輯結構

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

綜上，本文通過深入分析SHA3 算法，以全流水線結構，優化設計適合FPGA 的數據通路，以提高算法速度。

2 SHA3在FPGA上的優化及流水線實現

2.1 關鍵計算分析

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

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

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

2.2 全流水線實現

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

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

圖3 SHA3算法FPGA實現流水線結構

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

2.3 展開再優化

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

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

圖4 SHA3算法流水線優化結構圖

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

3 實驗結果與分析

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

3.1 仿真分析

優化后的SHA3 算法流水線仿真如圖5 所示。其中in_valid 為輸入有效信號；in_data 為輸入數據；out_valid 為輸出有效信號；out_data 為輸出數據；其他為中間結果信號。

圖5 SHA3算法仿真圖

從圖5 中可以看出，對于優化后的SHA3 算法，當連續輸入50 個數據后，在4866.191ns 連續產生50 組輸出，充分發揮了流水線并行的優勢。

3.2 資源占用

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

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

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

3.3 與GPU對比

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

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

表2 FPGA 與GPU 指標對比

從表2 中可以看出，FPGA 不僅性能較高，且功耗較低，具有很高的能效比，是GPU 的5.65 倍，更具有應用價值。

3.4 與其他方案對比

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

通過對比可以發現，除文獻[3]外，本文實現的頻率優于大多數方案。同時由于采用了全流水線結構，本文實現的吞吐量高于其他方案，充分發揮了FPGA 的計算優勢。

4 結語

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

表3 與其他方案對比