方 軼 叢林虎 鄧建球 陳澤宇

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

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

0 引 言

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

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

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

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

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

1 SM3算法

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

1.1 填 充

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

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是壓縮函數(shù)；V(0)是SM3算法中建議的初始值IV，長度為256比特。最后一次迭代后的結(jié)果為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 壓縮函數(shù)CF

壓縮函數(shù)的計算過程如下：

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算法中使用到的常量有：

布爾函數(shù)有：

置換函數(shù)有:

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

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

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

2 SM3算法的硬件快速實現(xiàn)方案

2.1 流水線結(jié)構(gòu)設(shè)計

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

圖1 流水線結(jié)構(gòu)設(shè)計

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

2.2 并行計算優(yōu)化

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

圖2 關(guān)鍵路徑并行計算初步優(yōu)化

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

圖3 關(guān)鍵路徑并行計算最終優(yōu)化

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

3 FPGA實現(xiàn)與性能對比分析

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

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

將本文方案的實現(xiàn)結(jié)果數(shù)據(jù)進行整理，與原SM3算法以及其他方案進行對比，具體情況如表1所示。

表1 SM3算法的FPGA實現(xiàn)方案性能對比

4 結(jié) 語

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