基于FPGA的SM3算法快速實現方案

方 軼 叢林虎 鄧建球 陳澤宇

1(海軍航空大學 山東 煙臺 264001)

2(甘肅電器科學研究院 甘肅 天水 741000)

0 引 言

Hash函數是一種能夠將任意長的消息構造成定長數據的函數，屬于密碼學三大類加密算法中的一種[1]。散列函數一般具有抗碰撞性和單向性，抗碰撞性又分為弱抗碰撞性和強抗碰撞性。弱抗碰撞性是指難以找到和該條消息具有相同散列值的另外一條消息；強抗碰撞性是指難以找到散列值相同的兩條不同消息；單向性是指無法通過散列值反推出該消息。由于Hash函數的特點，使其廣泛應用于數據完整性檢測、消息認證、數字簽名、偽隨機數生成、一次性口令以及區塊鏈等方面[2]。

典型的Hash函數包括MD5[3]、SHA-1[4]、RIPEMD[3]、HAVAL[3]、SHA-256[5]、SHA-3[6]、SM3[7]等。其中SM3算法由國家商用密碼管理辦公室于2012年公布的商用密碼標準，并于2016年成為國家標準，現已提交ISO國際標準化組織。其結構新穎，適合軟硬件和智能卡實現。

在算法的安全性方面，王小云等[8]已經攻破了MD5、SHA-1、RIPEMD、HAVAL-128等Hash函數，其進一步的研究結果表明，在不同的攻擊方式下，SM3、SHA-256和SHA-3算法各有側重，同樣體現了SM3算法具有很高的安全性。

在SM3算法的實現與效率優化方面，目前已有部分學者及研究人員進行了研究：王曉燕等[9]對SM3算法進行了邏輯運算上的優化，在多種器件上進行仿真并與SHA-256算法進行對比，取得了不錯的效果；蔡冰清等[10]對SM3算法進行了流水線結構的設計，FPGA驗證結果表明其吞吐量達到了73.54 Gbit/s；于永鵬等[11]對SM3算法進行了ASIC實現，并進行了相應的硬件設計；陳博宇等[12]針對SM3算法迭代壓縮過程提出了一種并行計算的方案，充分利用硬件的并行特性，提高了算法的執行效率。

為了解決SM3算法不能滿足高吞吐量需求的問題，本文提出了一種流水線結構與并行計算相結合的SM3算法混合實現方式，繼承二者的優點，既提高單步運算的效率，又保證較高的吞吐量。

1 SM3算法

SM3算法是我國提出的一種迭代Hash算法，其輸入和輸出都是比特串。SM3算法的輸出長度為256比特，消息分組為512比特，采用MD結構。對于長度小于264比特的消息X，SM3算法經過填充和迭代壓縮，生成雜湊值，雜湊值長度為256比特[8]。

1.1 填 充

對于一個長度為l比特的消息，首先將比特“1”添加到消息的末尾，再添加k個“0”，其中是滿足l+1+k≡448 mod 512的最小非負整數，然后添加一個64位的長度l二進制比特串。經過這樣填充后的消息的長度就是512的倍數。

1.2 迭代壓縮

將填充后的消息按每512比特的長度為一組進行分組，并對分組后的消息進行編號，得到B(0)B(1)…B(n-1)，其中n=(l+k+65)÷512。對分組后的已填充消息進行如下方式的迭代：

FORi=0 TOn-1

V(i+1)=CF(V(i),B(i))

END FOR

其中：CF是壓縮函數；V(0)是SM3算法中建議的初始值IV，長度為256比特。最后一次迭代后的結果為V(n)。

1.3 消息擴展

FORj=16 TO 67

Wj←P1(Wj-16⊕Wj-9⊕(Wj-3<<<15))⊕(Wj-13<<<7)⊕Wj-6END FOR

FORj=0 TO 63

END FOR

1.4 壓縮函數CF

壓縮函數的計算過程如下：

ABCDEFGH←V(i)

FORj=0 TO 63

SS1←((A<<<12)+E+(Tj<<

SS2←SS1⊕(A<<<12)

TT2←GGj(E,F,G)+H+SS1+Wj

D←C

C←B<<<9

B←A

A←TT1

H←G

G←F<<<19

F←E

E←P0(TT2)

END FOR

V(i+1)←ABCDEFGH⊕V(i)

式中：A、B、C、D、E、F、G、H是中間變量；SS1、SS2、TT1、TT2是字寄存器。且字的存儲方式為大端存儲。

最后輸出的256比特雜湊值為y=ABCDEFGH。

SM3算法中使用到的常量有：

布爾函數有：

置換函數有:

P0(X)=X⊕(X<<<9)⊕(X<<<17)

P1(X)=X⊕(X<<<15)⊕(X<<<23)

以上常量與函數中的X、Y、Z均為長度為32的比特串。

2 SM3算法的硬件快速實現方案

2.1 流水線結構設計

進行流水線結構設計的主要思想是使多個寄存器同時工作，并行處理多組輸入的數據，主要用于消息擴展模塊和迭代壓縮模塊中。根據前文對SM3算法的描述首先對整個迭代壓縮過程進行分析。每進行一輪迭代壓縮，總共要進行64次壓縮函數中Hash值。進行壓縮函數計算之前首先需要對本次迭代壓縮輸入的原消息填充分組數據Bi進行消息擴展，用于本輪壓縮。然后將本次得到的Hash運算值V(i+1)作為下一次迭代壓縮的輸入值Vi進行下一輪次的計算。同時作為下一次迭代壓縮輸入的還有對原消息進行填充分組后的分組數據輸入下一計算一輪壓縮函數中，再重新進行消息擴展與壓縮函數計算，直到將原消息的所有填充分組數據都計算完畢，得到最終的Hash值。

圖1 流水線結構設計

其中消息擴展模塊中的流水線結構和時鐘頻率需要跟迭代壓縮模塊相匹配，可以根據需要做延時處理或增加并行處理寄存器的個數。

2.2 并行計算優化

通過分析前文描述的SM3算法流程，在壓縮函數中計算SS1、SS2、TT1、TT2時需要進行多次加法運算，產生較大時延。對算法進行并行計算優化時首先對以上四個字寄存器中的運算進行優化，優化思路是使用進位保留加法器(CSA)[13]來降低有多個輸入(多于兩個)時的加法時延，并將更多的順序加法運算并行執行，以此來降低一次迭代壓縮中完成以上四步運算的時鐘周期。關鍵路徑并行計算初步優化方案如圖2所示。

圖2 關鍵路徑并行計算初步優化

通過對優化方案的分析，以上關鍵路徑中最后計算得到的TT2在壓縮函數中還作為輸入量進行了置換函數P0(TT2)的計算，因此繼續對壓縮函數中的一次置換函數進行并行計算優化，并與圖2的優化方案進行合并，最終的關鍵路徑并行計算優化方案如圖3所示。

圖3 關鍵路徑并行計算最終優化

設壓縮函數中的時鐘周期為clk，則根據圖2，該優化方案只需要6個clk即可完成一次壓縮函數中關鍵路徑的計算，其中CSA之后需要增加一個超前進位加法器(CLA)和一個clk來完成最終結果的輸出，因此該優化方案實際需要9個clk。而未經過并行計算優化處理的情況下，完成一次壓縮函數中關鍵路徑的計算需要14個clk才能完成。因此，該優化方案相比原SM3算法減少了大約38%所需的clk，同時減少了約34%的加法時延，大大提高了壓縮函數的執行效率。同樣地對消息擴展模塊中計算Wj時進行置換函數P1的計算也進行并行計算優化，優化后減少了大約18%所需的clk，有一定的優化效果，但由于邏輯運算占多數，幾乎沒有加法運算。因此相比對壓縮函數中進行的優化效果不是很明顯，只要重點將擴展模塊中的并行運算所需時鐘周期設計至與壓縮函數所需時鐘周期相匹配即可。

3 FPGA實現與性能對比分析

根據本文設計的方案，采用Verilog語言進行方案實現。為了方便與其他方案之間進行性能對比，選擇與文獻[9]、文獻[10]和文獻[12]中性能相近的的Altera公司Cyclone IV系列芯片，在Quartus 13.0 sp1和Modelsim 10.4環境下進行方案的實現與驗證。對方案實現的分析主要從資源占用、最大工作頻率和吞吐率三方面進行。其中吞吐率計算方式為：

式中：B為數據塊的比特數；fmax為最大工作頻率；CB為處理完成一個數據塊所需要的時鐘周期。

將本文方案的實現結果數據進行整理，與原SM3算法以及其他方案進行對比，具體情況如表1所示。

表1 SM3算法的FPGA實現方案性能對比

4 結 語

本文將流水線結構與并行計算優化相結合，對SM3算法進行了高吞吐率快速實現的設計，通過對消息擴展模塊和迭代壓縮模塊的流水線結構設計以及對壓縮函數中關鍵路徑的并行計算優化，使SM3算法的吞吐率達到了80.43 Gbit/s。但本文方案占用資源過多，不適用于對面積要求嚴格的場景。