基于FPGA的SM3算法快速實(shí)現(xiàn)方案

方 軼 叢林虎 鄧建球 陳澤宇

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

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

0 引 言

Hash函數(shù)是一種能夠?qū)⑷我忾L的消息構(gòu)造成定長數(shù)據(jù)的函數(shù)，屬于密碼學(xué)三大類加密算法中的一種[1]。散列函數(shù)一般具有抗碰撞性和單向性，抗碰撞性又分為弱抗碰撞性和強(qiáng)抗碰撞性。弱抗碰撞性是指難以找到和該條消息具有相同散列值的另外一條消息；強(qiáng)抗碰撞性是指難以找到散列值相同的兩條不同消息；單向性是指無法通過散列值反推出該消息。由于Hash函數(shù)的特點(diǎn)，使其廣泛應(yīng)用于數(shù)據(jù)完整性檢測(cè)、消息認(rèn)證、數(shù)字簽名、偽隨機(jī)數(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)新穎，適合軟硬件和智能卡實(shí)現(xiàn)。

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

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

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

1 SM3算法

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

1.1 填 充

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

1.2 迭代壓縮

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

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 消息擴(kuò)展

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ù)的計(jì)算過程如下：

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是字寄存器。且字的存儲(chǔ)方式為大端存儲(chǔ)。

最后輸出的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算法的硬件快速實(shí)現(xiàn)方案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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