SM3雜湊算法的軟件快速實現研究

楊先偉，康紅娟

(1. 無錫職業技術學院 基礎部，江蘇 無錫 214121； 2. 四川長虹電器股份有限公司，四川 成都 610041)

?

SM3雜湊算法的軟件快速實現研究

楊先偉1，康紅娟2

(1. 無錫職業技術學院 基礎部，江蘇 無錫 214121； 2. 四川長虹電器股份有限公司，四川 成都 610041)

摘要：雜湊算法是密碼學中最基本的模塊之一,可廣泛應用于密碼協議、數字簽名、消息鑒別等領域。我國國家密碼管理局在2010年發布了SM3密碼雜湊算法，該算法適用于商用密碼應用中的數字簽名和驗證、消息認證碼的生成與驗證以及隨機數的生成等。該文重點研究SM3密碼雜湊算法的軟件快速實現，根據算法本身的特點，尤其是壓縮函數的特點，給出一種更加適用于軟件的快速實現方式。實驗表明利用此方法可以將算法的效率提升60%左右。

關鍵詞：SM3算法；雜湊函數；軟件快速實現; 數字簽名；消息鑒別；完整性認證；數字指紋; 壓縮函數

中文引用格式：楊先偉，康紅娟. SM3雜湊算法的軟件快速實現研究[J]. 智能系統學報， 2015, 10(6): 954-959.

哈希(Hash)函數，也叫雜湊函數，是密碼學中最基本的模塊之一，廣泛應用于密碼協議、數字簽名、消息鑒別、完整性認證等領域。因此，它在密碼學中扮演著極其重要的角色。

雜湊函數的目的是產生數據塊的“指紋”，它可以對任意長度的信息產生定長的輸出。這個變換過程軟硬件均易于計算實現，但其逆向變換過程在計算上不可行，即具有單向性。出于安全性的考慮，雜湊函數還必須滿足抗弱碰撞性和抗強碰撞性。1991年，Ron Rivest提出了MD5算法，這曾經是使用最為廣泛的雜湊算法。從20世紀90年代年開始，美國國家標準與技術研究院(NIST)陸續公布了SHA系列[1]，并通過公開競賽方式征集SHA-3[2]。

中國國家密碼管理局在2010年發布了SM3密碼雜湊算法[3]，該算法適用于商用密碼中的多種應用，滿足多種密碼應用的安全需求：1)數字簽名和驗證，如作為SM2算法中數字簽名所需的雜湊函數；2)消息認證碼的生成與驗證，消息認證碼不僅可以使用分組密碼算法基于特定的工作模式生成，也可以使用SM3等雜湊函數生成；3)隨機數的生成。

哈希函數在各種平臺和環境下的執行效率是非常重要的考量指標之一，比如服務器端常需執行的SSL/TLS協議就使用了哈希函數進行認證。目前已有大量文章對SHA系列算法的軟件快速實現進行研究，比如Acii?mez[4]提出基于SIMD技術快速實現哈希算法，Gueron等[5-6]對并行處理多個消息的情況進行了研究。同樣也有大量文章對SM3算法的軟硬件快速實現進行研究。張倩等[7]提出了一種ASIC高效實現架構；王曉燕等[8]基于FPGA設計SM3算法IP核的整體架構，對關鍵邏輯進行優化設計；伍娟[9]以同方公司THD86智能卡芯片為硬件平臺實現了SM3算法；曾小波等[10]分析了基于8051軟核的SM3算法IP原理、設計流程及實現方案，該方案在時序和面積上均做到相當程度的優化,并提高了算法的效率；沈一公等[11]基于Android平臺研究了SM3算法的快速實現，并以此為基礎研究文件防篡改以便檢查手機軟件的安裝；易叔賢等[12]結合已經將SM系列算法納入其中的PBOC 3.0新規范，分析考慮SM2、SM3、SM4算法在金融IC卡領域的實現和應用。

與這些研究相比，文本研究的側重點是SM3算法在普通軟件平臺下的快速實現方式。文本根據算法以及壓縮函數的特點，給出一種更加適用于軟件快速實現的算法描述方式和實現方法，本文提出的實現方法具有以下優點：首先，此方法避免了普通實現中可能采用的效率較低的實現架構和運算方式，可較大地提高算法的軟件效率，經多個軟件平臺對比測試，本文的實現方法可將算法效率提升60%左右；其次，此方式不基于特定的軟件平臺、架構、指令等，具有很強的跨平臺性和兼容性。

1SM3算法簡介

SM3雜湊算法可將長度小于264比特的消息經過填充、反復的消息擴展和壓縮，生成長度為256 比特的雜湊值。在SM3算法中，字表示長度為32的比特串。

1.1函數

布爾函數FFi(X,Y,Z)、GGi(X,Y,Z)，0≤i≤63的定義如下：

FFi(X,Y,Z)=

GGi(X,Y,Z)=

置換函數P0(X)和P1(X)的定義如下：

1.2填充

設消息的長度為l 比特。填充方式為：首先將比特“1”添加到消息的末尾；然后添加k個“0”，k是滿足l+1+k=448mod512的最小的非負整數；最后再將消息長度l的64位二進制表示添加在最末。填充后的消息比特長度為512的倍數。

1.3迭代壓縮

填充后的消息m′按512 比特進行分組：m′=B(0)‖…‖B(n-1).對每個分組利用壓縮函數CF進行迭代：

FOR i=0 TO n-1

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

END FOR

1.4壓縮函數

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

首先，計算消息擴展字Wi,0≤i≤67和Wi′,0≤i≤63，步驟如下：

W0‖…‖W15=B(i)

FOR i=16 TO 67

Wi←P1(Wi-16⊕Wi-9⊕(Wi-3<<<15))⊕(Wi-13<<<7)⊕Wi-6

END FOR

FOR i=0 TO 63

END FOR

然后，進行包含64輪迭代的壓縮，步驟如下：

A‖B‖C‖D‖E‖F‖G‖H←V(i)

FOR i=0 TO 63

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

SS2←SS1⊕(A<<<12)

TT1←FFi(A,B,C)+D+SS2+Wi′

TT2←GGi(E,F,G)+H+SS1+Wi

D←C

C←B<<<9

B←A

A←TT1

H←G

G←F<<<19

F←E

E←P0(TT2)

END FOR

V(i+1)←V(i)⊕(A‖B‖C‖D‖E‖F‖G‖H)1.5輸出雜湊值

256比特雜湊值y的計算方式為

2軟件快速實現

從理論上講，SM3算法中使用最多且最耗時的是64輪壓縮函數和消息擴展。利用Intel VTune Amplifier XE分析算法熱點，得出信息如下表。

表1　普通實現時的熱點

熱點信息顯示，壓縮函數和消息擴展的確是最耗時的2個部分，其耗時分別占總耗時的65.9%和24.3%。因此，快速實現的關鍵在怎樣快速實現壓縮函數和消息擴展。

2.1消息擴展的快速實現

1)首先在執行64輪壓縮函數前只計算初始的4個字W0,…,W3；

2.2壓縮函數的快速實現

壓縮函數的快速實現可以從結構調整、流程變更、常數計算等方面著手。

1)壓縮函數的結構可以做適當的調整。壓縮函數每一輪的最末會執行如下所示的循環右移，A‖B‖C‖D←(A‖B‖C‖D)>>>32,E‖F‖G‖H←(E‖F‖G‖H)>>>32。為了減少循環移位導致的不必要的賦值運算，可以將字的循環右移變更每輪輸入字順序的變動，且這個順序變動會在4輪后還原，具體情況如下(以下用OneRound(·)表示一輪壓縮)：

OneRound(i+0,A,B,C,D,E,F,G,H,W)

OneRound(i+1,D,A,B,C,H,E,F,G,W)

OneRound(i+2,C,D,A,B,G,H,E,F,W)

OneRound(i+3,B,C,D,A,F,G,H,E,W)

2)可以優化壓縮函數的中間變量的生成流程。此優化生成流程可以去除不必要的賦值，減少中間變量個數。優化后的執行步驟如下(其中ti=Ti<<

TT2←A<<<12

TT1←TT2+E+ti

TT1←TT1<<<7

TT2←TT2⊕TT1

3)利用上述調整以及消息擴展部分的調整可以將原來計算TT1、TT2、D和H的過程進行如下的進一步簡化。

H←H+GGi(A,B,C)+TT1+Wi

4)預先計算并存儲常數ti=Ti<<

2.3調整后的算法描述

優化后的算法將消息擴展和壓縮函數結合在一起。下面先描述調整后的消息處理算法，該算法完成消息擴展和64輪壓縮迭代；再描述調整后的一輪算法，該算法完成一輪壓縮迭代，包括計算必需的消息擴展字Wi+4。調整后的消息處理算法描述如下。

算法1 調整后的消息處理算法

ProcessBlock(V,M)

輸入：上輪迭代結果V，一個消息分組B

輸出：本輪迭代結果V

中間變量：字寄存器A—H，

步驟：

1)W0‖W1‖W2‖W3←B0‖B1‖B2‖B3，

2)A‖B‖C‖D‖E‖F‖G‖H←V，

3)FOR (i=0,4,8,…,60)，

OneRound(i+0,A,B,C,D,E,F,G,H,W)，

OneRound(i+1,D,A,B,C,H,E,F,G,W)，

OneRound(i+2,C,D,A,B,G,H,E,F,W)，

OneRound(i+3,B,C,D,A,F,G,H,E,W)，

END FOR

4)V←V⊕(A‖B‖C‖D‖E‖F‖G‖H)，

5)返回V。

對算法1做以下幾點說明：這里的B0‖B1‖…‖B15=B分別代表消息的16個字；前4個消息擴展字W0、W1、W2、W3需在循環前計算出來，進入后面的循環后，每次執行OneRound(i,*)將計算Wi+4。

調整后的一輪壓縮算法如下。

算法2調整后的一輪壓縮算法

OneRound(i,A,B,C,D,E,F,G,H,W)

輸入：字寄存器A—H，輪序號i，消息擴展字數組W=(W0,…,W67)

輸出：更新后的A—H和W=(W0,…,W67)

步驟：

1)計算消息擴展字Wi+4

IF(i<12)Wi+4←Bi+4

ELSE Wi+4←P1(Wi-12⊕Wi-5⊕(Wi+1<<<15))⊕(Wi-9<<<7)⊕Wi-2

END IF

2)計算中間變量TT1和TT2

TT2←A<<<12

TT1←TT2+E+ti

TT1←TT1<<<7

TT2←TT2⊕TT1

3)僅更新字寄存器B、D、F、H。

H←H+GGi(E,F,G)+TT1+Wi

F←F<<<19

H←P0(H)

4)返回更新后的A—H和W=(W0,…,W67)。

對算法2做以下幾點說明：進入第i輪的算法2之時，消息擴展字只有{Wk|k

32種實現方式的計算量分析評估

為了從理論上評估新方法的效率，本節對2種方法的計算量進行詳細對比。由于算法的操作主要集中在壓縮函數中，因此以下對壓縮函數的計算量進行統計、分析和對比。優化前的方法嚴格按照標準文檔，先計算消息擴展字，再進行64輪迭代，優化后的方法則按照上一節描述的算法1和算法2進行實現。以下用LOAD和STORE表示數據加載和存儲，XOR表示異或運算，ROT表示移位運算，ADD表示加法運算，AND表示與運算，OR表示或運算，NOT表示非運算。

優化前的算法中，消息擴展的計算量為：

1)計算前16個Wi時每個需執行1次LOAD和1次STORE，計算后52個Wi時每個需執行5次LOAD、1次STORE、6次XOR、4次ROT；

3)計算壓縮函數的一次迭代需要執行3次LOAD、12次STORE、8次ADD、3次XOR、8次ROT、1次FFi函數和1次GGi函數，

4)FFi函數和GGi函數的計算量是，前16次FFi函數需執行2次XOR和2次ROT，前16次GGi函數需執行2次XOR和2次ROT，后48次FFi函數需執行3次AND和2次OR，后48次GGi函數需執行2次AND、1次OR、1次NOT。

根據以上統計分析，表2列出了優化前的算法中對一個512 比特的消息塊執行一次完整的壓縮所需的計算量。

優化后的算法中，消息擴展的計算量為：

1)計算前12個Wi+4時每個需執行1次LOAD和1次STORE，計算后52個Wi+4時每個需執行5次LOAD、1次STORE、6次XOR、4次ROT；

2)計算中間變量TT1和TT2需要執行1次LOAD、2次STORE、2次ADD、1次XOR、2次ROT；

3)更新字寄存器B、D、F、H需要執行：1次LOAD、1次STORE、6次ADD、3次XOR、4次ROT、1次FFi函數和1次GGi函數；

4)FFi函數和GGi函數的計算量同優化前的計算量。

根據以上統計分析，表2列出了優化后的算法中對一個512 比特的消息塊執行一次完整的壓縮所需的計算量。

表2　優化前后一次壓縮函數的計算量

從表2可知，優化后的壓縮函數通過輪函數的調整和消息擴展函數的優化，大大減少了LOAD和STORE的次數，同時中間變量TT1和TT2的優化實現又進一步減少了ROT的次數，其余運算的計算量無變化。

如果從操作總數的角度考慮，優化后算法的速度可提升(3 792-2 824)/2 824=34.3%。但實際上CPU執行這些操作指令時，不同的操作具有不同的指令執行周期(cycle)，甚至不同的CPU執行相同的運算所需的指令周期也各不相同。大部分CPU執行整數的算數運算和邏輯運算需1個時鐘周期，而執行LOAD和STORE則需要多個時鐘周期，且各CPU的執行時間也有較大差異。以下假設執行每個算數邏輯運算需1個時鐘周期。如果執行LOAD需1個時鐘周期，執行STORE需2個時鐘周期，則優化后算法的速度可提升52.3%。；如果假設執行LOAD需1.5個時鐘周期，執行STORE需2.5個時鐘周期，則優化后算法的速度可提升59.6%；如果假設執行LOAD需2個時鐘周期，執行STORE需3個時鐘周期，則優化后算法的速度可提升65.6%。不同假設下的速度提升情況見下表3。

表3　不同情況下的優化前后速度提升估計值

4模擬實驗與對比測試

為了模擬真實環境中對SM3算法軟件實現的需求，下面的實驗中進行了4組測試，每組測試方法對多個數據包進行雜湊，每個數據包為特定長度字節，然后統計耗時和速度。以下為4組測試的詳細情況說明。

1)第1組測試中測試1個數據包，該數據包為256×106個字節，此測試用以模擬大量數據雜湊的情況，如大型文件雜湊；

2)第2組測試中雜湊200個數據包，每個數據包1.28×106個字節，此測試用以模擬中型數據包雜湊的情況，如圖片等；

3)第3組測試中雜湊40 000個數據包，每個數據包6.4×103個字節，此測試用以模擬普通網絡數據包雜湊的情況；

4)第4組測試中雜湊8×106個數據包，每個數據包32個字節，此測試用以模擬頻繁的微小型數據包雜湊的情況。

為了統計每種測試的準確耗時值，每組測試都反復進行21次并記錄各次的時間，最后從大到小排列后取最中間的值作為統計耗時值。

測試使用的軟件平臺詳情如下：Windows XP SP3 32 比特、Intel Core i3@3400 MHz、4 GB DDR3-1600 SDRAM、Microsoft Visual Studio 8.0。速度單位為Mbit/s。其中處理器的緩存情況為[13]：一級緩存為每個核心32 KB，2級緩存為每個核心64 KB，3級緩存為多核共享3 MB。

表42種實現方式的性能比較

Table 4The performance comparison of two implementation methods

測試類別速度/(Mb·s-1)優化前優化后速度提升/%第1組測試739120362.8第2組測試733119162.5第3組測試701107453.2第4組測試64297351.6平均704111057.7

上表列出的測試結果表明：1)數據包越大，執行效率越高，這是因為大型數據包減少了一頭一尾的初始化、消息填充和反初始化等工作：2)優化調整后的算法效率提升顯著，可以提升60%左右，在雜湊大中型數據包時速度提升60%以上，即使在雜湊微小型數據包時效率也能提升50%以上。

4結束語

本文對我國國家密碼管理局發布的SM3密碼雜湊算的軟件快速實現進行研究，根據算法自身的特點，尤其是壓縮函數的特點，給出一種更加適用于軟件快速實現的算法描述方式和實現方法。理論分析得出的算法計算量以及模擬實驗結果均表明，利用此軟件快速實現方法可以將算法的效率提升60%左右。另外，此軟件快速實現方式不基于特定的平臺、架構、指令等，因此具有很強的跨平臺性和兼容性。

參考文獻:

[1]NIST. Federal information processing standards publication 180-3, secure hash standards (SHS) [S]. Gaithersburg, MD, USA: Information Technology Laboratory of National Institute of Standards and Technology, 2008. http://csrc.nist.gov/publications.

[2]NIST. Cryptographic hash algorithm competition [EB/OL]. (2005-04-15)[2015-08-05]. http://csrc.nist.gov/groups/ST/hash/sha-3/index.html.

[3]國家密碼管理局. SM3密碼雜湊算法[S]. 北京: 國家密碼管理局, 2010.

National Cryptography Administration. SM3 cryptographic hash algorithm[S]. Beijing: National Cryptography Administration, 2010.

[4]ACIICMEZ O. Fast hashing on pentium SIMD architecture[D]. Corvallis, Oregon: Oregon State University, 2004.

[5]GUERON S, KRASNOV V. Parallelizing message schedules to accelerate the computations of hash functions[R]. 2012. http://eprint.iacr.org/2012/067.pdf

[6]GUERON S, KRASNOV V. Simultaneous hashing of multiple messages[J]. Journal of Information Security, 2012, 3(4): 319-325.

[7]張倩, 李樹國. SM3雜湊算法的ASIC設計和實現[J]. 微電子學與計算機, 2014, 31(9): 143-146, 152.

ZHANG Qian, LI Shuguo. Design and implementation of SM3 algorithm in ASIC[J]. Microelectronics & Computer, 2014, 31(9): 143-146, 152.

[8]王曉燕, 楊先文. 基于FPGA的SM3算法優化設計與實現[J]. 計算機工程, 2012, 38(6): 244-246.

WANG Xiaoyan, YANG Xianwen. Optimization design and implementation of SM3 algorithm based on FPGA[J]. Computer Engineering, 2012, 38(6): 244-246.

[9]伍娟. 國密SM3算法在COS上的研究與實現[J]. 科技信息, 2013, (2): 294-295.

WU Juan. Research and implementation of SM3 algorithm on COS[J]. Science & Technology Information, 2013, (2): 294-295.

[10]曾小波, 唐忠彪, 焦歆. 基于單片機的SM3算法優化及Verilog模型驗證[J]. 電子科技, 2015, 28(2): 38-40.

ZENG Xiaobo, TANG Zhongbiao, JIAO Xin. Optimization of SM3 algorithm and Verilog model validation based on SCM[J]. Electronic Science and Technology, 2015, 28(2): 38-40.

[11]沈一公, 蘇厚勤. 基于Android的SM3密碼雜湊算法研究與實現[J]. 電子技術與軟件工程, 2013(18): 69-70.

SHEN Yigong, SU Houqin. Research and implementation of SM3 algorithm based on android[J]. Electronic Technology & Software Engineering, 2013(18): 69-70.

[12]易叔賢, 張非凡. SM系列算法在金融IC卡領域的應用[J]. 金融電子化, 2013(7): 49-52.

YI Shuxian, ZHANG Feifan. Application of SM series algorithm in the field of financial IC card[J]. Financial Computerizing, 2013(7): 49-52.

[13]ntel. 2nd generation intel?coreTM processor family desktop datasheet[EB/OL]. (2011-01-04)[2013-07-08]. http://www.intel.com/content/www/us/en/processors/core/2nd-gen-core-desktop-vol-1-datasheet.html.

楊先偉，男，1980年生，講師，主要研究方向為通信與系統工程。

康紅娟，女，1983年生，工程師，主要研究方向為保密通信。

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151110.1354.004.html

英文引用格式：YANG Xianwei， KANG Hongjuan. Fast software implementation of SM3 Hash algorithm[J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 954-959.

Fast software implementation of SM3 Hash algorithm

YANG Xianwei1， KANG Hongjuan2

(1. Department of Fundamental Courses, Wuxi Prof Technology inst., Wuxi 214121, China； 2. Sichuan Changhong Electric Co., Ltd., Chengdu 610041, China)

Abstract：The hash algorithm is one of the most basic cryptography modules, and is widely used in cryptographic protocols, digital signatures, message authentication, and in other fields. The Chinese National Cryptography Administration released the SM3 hash algorithm in 2010. This algorithm is applied to digital signature and verification, the generation and verification of message authentication codes, and random number generation. This paper addresses the fast software implementation of the SM3 algorithm. Based on the SM3 features, and especially its compression function characteristics, we propose a method that is highly suitable for fast software implementation. Experimental results show that this method can improve the implementation speed by 60%.

Keywords：SM3 algorithm; hash function; fast software implementation; digital signature; message authentication; integrity authentication; digital fingerprint; compression function

作者簡介：

通信作者：楊先偉. E-mail：yangxianwei2018@163.com.

基金項目：國家自然科學基金資助項目(11471144).

收稿日期：2015-07-23. 網絡出版日期：2015-11-10.

中圖分類號：TP309

文獻標志碼：A

文章編號：1673-4785(2015)06-0954-06

DOI:10.11992/tis.201507036