SM3雜湊算法的SoPC組件實現

邵夢麗，殷新春,2，李艷梅

（1. 揚州大學信息工程學院，江蘇 揚州 225000；2. 揚州大學廣陵學院，江蘇 揚州 225000）

SM3雜湊算法的SoPC組件實現

邵夢麗1，殷新春1,2，李艷梅1

（1. 揚州大學信息工程學院，江蘇 揚州 225000；2. 揚州大學廣陵學院，江蘇 揚州 225000）

首先給出了SM3在SoC上的實現，然后主要分析了算法的結構，選擇Verilog語言進行算法描述，使用ModelSim進行仿真，用SoPC Builder進行接口封裝，最后在Cyclone IV 系列的EP4CE22F17C8N上進行了實現，測試表明，運行頻率可以達165 MHz，吞吐量為1 184.8 Mbit/s。

SM3；FPGA；硬件實現；SoC

1 引言

雜湊算法又叫散列（Hash）函數[1]，是密碼學中最基本的模塊之一，在密碼學中扮演著極其重要的角色[2]。它是一種單向密碼體制，可以將任意長度的輸入經過變化后得到固定長度的輸出[3～5]。為了滿足電子認證服務系統等應用需求，國家密碼管理局于2010年12月發布了SM3密碼Hash算法[2]，算法是在SHA-2基礎上設計提出的[6]，它是一種基于分組迭代結構的雜湊算法[7]。算法該算法適用于商用密碼應用中的數字簽名和驗證、消息認證碼的生成與驗證以及隨機數的生成，可滿足多種密碼應用的安全需求[2]。

隨著信息社會的進一步發展，密碼處理速度的要求進一步提升，如何提升算法的運算速度成為研究熱點[8]。SM3雜湊算法在實現方面可分為軟件實現、硬件實現和軟硬件協調實現。在軟件實現上，由于SM3算法迭代輪數多，邏輯運算多，軟件處理速度已經越來越無法滿足現階段大數據實時處理的需要[9]。軟硬件協調指的是一部分的運算由軟件實現，另一部分的運算由硬件實現，在 SM3的軟硬件協調過程中一般是由軟件實現信息填充和控制壓縮迭代，而壓縮迭代的具體實現由硬件實現[10]。硬件實現主要追求的是高運行速率以及低功耗，已經有很多文獻對算法進行了實現，但其實現大多不是針對SoC實現的。文獻[1,11,12]的實現在消息擴展處使用的是移位寄存器，消息填充采用軟件。文獻[1]的設計目的主要與以往的SHA-0、SHA-1和SHA-2進行比較，在CF壓縮函數處的關鍵路徑采用CSA樹優化進行實現，關鍵路徑延時包括2級CSA加法延時和1級LUT延時。文獻[11]設計主要與SHA-2系列算法進行比較，在CF壓縮函數處的關鍵路徑花費2級CSA延時和2級32 bit加法器延時。文獻[12]的壓縮函數的關鍵路徑和文獻[11]采用的是同一種方法，采用流水線技術實現消息塊的壓縮，實現效率高，占用硬件資源較多。文獻[13]主要改進了加法路徑，減少了加法器的延時。文獻[14]提出了一種四合一架構，即在同一周期內實現四組壓縮運算，該框架在循環展開的基礎上，針對關鍵路徑和面積進行逐一改進并給出了完整的實現，硬件實現復雜，資源消耗較多。

本文的主要目的是針對SM3算法的SoC實現，選取 Altera公司的綜合性 PLD開發軟件Quartus II進行開發，采用SoPC組件封裝的方式進行實現，對硬件實現添加適當的時序約束，最終以 IP核的方式提供使用。CF關鍵路徑花費 2級32 bit加法延時和1級CSA運算延時，運算頻率可達到165 MHz。

2 SM3算法簡介

針對長度為 l bit(l<264)的報文消息，SM3雜湊算法經過填充和迭代壓縮，生成雜湊值，雜湊值的長度為256 bit[13]，圖1給出了SM3算法流程。

首先，輸入消息，消息按規則進行消息填充，填充規則如式(1)[15]所示。

其中，k取值滿足式(1)最小的非負整數，填充后得到的消息比特數為 512的倍數。然后進行分塊，將消息分成 B1,B2,…,Bn，每個分塊的長度為512 bit，其中再將分組依次輸入迭代過程中進行迭代，得到結果。迭代過程包括消息擴展、CF壓縮函數和寄存器異或。消息擴展主要經過64輪運算，完成對512 bit的分組擴展，擴展生成132個32 bit的字，結果供CF進行運算，在CF中經過迭代、移位和加等運算得到512 bit結果，再同寄存器中的數進行異或，將迭代結果提供給下一輪壓縮，如此循環，經過多次迭代，得到512 bit的雜湊值。

圖1 SM3算法流程

3 SM3算法的實現

選擇Verilog語言進行算法實現，使用Altera公司提供的SoPC平臺進行開發，該平臺可以利用Avalon平臺互連結構連接處理器和各種IP核模塊[16]，SM3硬件實現的接口就是依據 Avalon的接口進行設計和實現的，在Cyclone IV 系列的EP4CE22F178芯片上運行測試。

SM3算法實現的整體結構可分為控制模塊、消息擴展模塊、CF壓縮模塊，其中具體還包括移位寄存器、CSA加法等。SM3算法以SoPC組件的形式進行接口設計，封裝的接口描述如表1所示。

除去頂層的SoPC組建封裝，SM3的模塊實現如圖2所示。

圖2只是算法的硬件實現模塊，在消息擴展之前還有一步操作，即消息填充，此步操作采用軟件進行實現。消息擴展模塊負責向CF模塊中提供Wj和W'j，CF壓縮模塊負責對擴展的信息進行壓縮，壓縮模塊中用到的寄存器數據由寄存器模塊提供，然后通過對這3個模塊進行內部連線，實現控制。

表1 SM3封裝接口

圖2 SM3硬件實現模塊

3.1 消息擴展模塊

消息擴展模塊主要使用移位寄存器進行實現，移位寄存器由16個32 bit寄存器組成。SoPC組件的使用和直接硬件使用方式不同，直接硬件實現模塊主要注重硬件之間的時序傳輸，而SoPC組件則需要考慮軟硬件之間的協調，為了避免硬件過于復雜，此處寄存器中的初始值由處理器通過封裝接口傳輸，傳輸完成以后再進行移位等相關運算。每周期消息擴展模塊左移1個寄存器，將運算所得的新數據存入移位寄存器右邊，同時將所需的 Wj和 W'j通過相應接口傳至CF模塊。

消息擴展實現的狀態機如圖3所示。

圖3 消息擴展的狀態機

在圖3中，狀態機主要包括3個狀態，分別為idle、op和done。idle是狀態機的初始化狀態，主要對寄存器進行初始化。op是中間運算，負責生成Wj和W'j，以及判斷是否要結束運算，生成全部Wj和W'j花費64個周期。done表示狀態機結束，并使狀態機進入idle狀態。

3.2 寄存器模塊

消息擴展的主要目的是將Wj和W'j傳給CF壓縮函數進行消息壓縮，得到256 bit的壓縮數據，在消息壓縮之前需要對一些數據進行初始化。寄存器模塊是實現每一輪新的CF壓縮函數數據的初始化，迭代過程如下[15]。

寄存器模塊主要實現 V(i)的初始化及其后的V(i+1)，數值存放在8個32 bit的寄存器中，用A、B、C、D、E、F、G、H表示。其中，i代表信息塊號，當i為0時，V(0)=IV，此時A=7380166f，B=4914b2b9，C=172442d7，D=da8a0600，E=a96f30bc，F=163138aa，G=e38dee4d，H=b0fb0e4e[13]，寄存器中的數值是以初值的方式存儲的，其存儲方式可以使用ROM進行存儲，但是考慮ROM的讀取耗時，此處直接以硬件的方式進行實現。

3.3 CF壓縮模塊

CF壓縮是SM3算法設計的關鍵，其實現的快慢決定SM3算法的實現速率。在壓縮模塊中涉及的運算包括移位、一些數值的讀取和加法運算。其中加法運算速度的快慢對CF壓縮運算速度起關鍵作用。提高CF壓縮運算的一個措施是提高迭代并行度，但CF算法中關鍵路徑的運算結果在下一次迭代中需要使用，因此并行迭代并不可用。以往的文獻中所采用的并行迭代并不是并行的，只是將多輪運算進行合并后優化，這樣會占用大量的硬件資源。所以，本文仍然采用單輪進行實現。

另一種提高算法運算速率的方法是縮短關鍵路徑的運行時間。有一部分文獻在關鍵路徑上使用的是CSA樹優化關鍵路徑[1]，也有使用改進算法的，如文獻[13]中所使用的。本文的關鍵路徑花費2級32 bit加法延時和1級CSA運算延時，具體實現過程如圖4所示。

圖4 壓縮函數

在圖4中，A、B、C、D、E、F、G、H、A'、B'、C'、D'、E'、F'、G'、H'分別代表字（32 bit）寄存器，A'、B'、C'、D'、E'、F'、G'、H'存放的是運算后所得到的新值。壓縮函數中所涉及的函數運算包括布爾函數 FFj、布爾函數 GGj、常量Tj以及置換函數P0，具體函數分別如式(2)～式(5)[15]所示。

在式(2)～式(5)中，∧表示32 bit與運算，∨表示32 bit或運算，?表示32 bit非運算。在實現過程中，布爾函數和置換函數只涉及基本門電路的運算，硬件實現簡單。常量Tj是通過寄存器進行賦值實現的。

信息壓縮的狀態機如圖5所示。

圖5 壓縮函數的狀態機

壓縮函數運行的狀態可分為 4個，分別為idle、done、op和op1。idle是狀態機的初始狀態，主要進行數據的初始化，從寄存器模塊中讀取數據給A、B、C、D、E、F、G、H這8個寄存器。op和op1是運算部分，主要完成壓縮運算，具體運行方式按圖5給出的方式進行，其中，op1不需要預算下一組要使用的布爾函數以及常量。done標志運算結束，產生完成信號。

3.4 算法軟件實現

SM3以SoPC的組件方式進行實現，主要是為了方便CPU的調用，通過軟硬件協調的方式達到硬件的最大使用率。CPU對組件的控制主要是通過地址端口進行讀寫數據實現的，其寄存器地址映射信息如表2所示。

算法使用C語言進行硬件調用，使用到的宏變量如表3所示。

表2 寄存器映射

表3 宏變量

軟件實現的核心代碼如下所示。

4 實驗

4.1 算法實現

Quartus II是Altera公司的綜合性PLD開發軟件，支持VHDL、AHDL、VerilogHDL等硬件描述語言以及原理圖等多種設計輸入形式，可以完成從設計輸入到硬件配置的完整 PLD設計流程，內嵌自有的綜合器以及仿真器[17]。本文算法的開發就是基于這個軟件完成的。最終在Cyclone IV EP4CE22F178芯片上運行實現。實驗所選的SoPC系統中包括Nios II處理器、JTAG UART模塊、系統ID模塊、SRAM控制模塊、定時器模塊和SM3_CF各1個，其中SM3_CF是SM3的SoPC組件實現方式。實驗以國家密碼管理局頒布的 SM3雜湊算法提供的運行示例進行，對消息“abcd”進行填充，其運行結果如圖6所示，結果運行正確。

圖6 運行結果

4.2 結果分析

算法實現的資源和吞吐率[1]統計如表4所示。由于實現的目標器件的不同，同一實現方法占用的資源數也不同，從資源使用上并不能分析出確切的優劣勢，所以本文將對算法實現的吞吐率進行了統一，均化為Mbit/s。表4中的“—”表示參考文獻中并未提及的部分。

文獻[1]采用CSA優化樹作為關鍵路徑，在不同的硬件上得到的吞吐率稍有不同。文獻[2]使用2種方法對算法進行實現，一種是迭代方式，另一種是循環展開式。文獻[12]采用流水線實現方式。文獻[13]對CF壓縮函數的關鍵路徑進行改進。文獻[14]對CF關鍵路徑采用四合一進行實現。

本文主要針對的是SM3算法在SoC上的實現，選擇SoPC作為實現途徑，在實現中考慮硬件的使用量、運算部件的組件化和運算過程中數據讀取耗時，對于寄存器的初值采用直接存儲賦值方式。實現中消息擴展模塊花費64個周期，CPU通過寫地址對寄存器進行初始化要花費16個時鐘周期，算法運行采用軟硬件同步進行的方式，在寫入數據的同時可以進行硬件的運行操作，所以此處忽略CPU寫入花費的周期。硬件運行過程中，CPU控制開始要花費一個周期，判斷硬件是否就緒需要一個周期，CF運算相對于消息擴展會延遲一個周期，完成運算時向CPU發出完成信號需花費一個周期，所以，總的花費周期是 68(1+1+1+ 64+1=68)，吞吐率為1 184.8 Mbit/s。

表4 資源統計比較

5 結束語

雜湊算法在密碼加密中具有很重要的作用，SM3算法是國家密碼局頒布的，主要用于商用密碼。SM3算法的實現可分為軟件實現和硬件實現，為了提高算法的運算速度，一些場合需要對算法進行硬件實現。本文 SM3算法的實現主要用于SoC的實現，主要分析以往的實現算法，最終根據實際要求選取算法進行硬件實現。算法在實現上以Avalon接口為標準進行封裝，封裝成SoPC組件，最終在Cyclone IV EP4CE22F 17C8N上運行實現，測試表明其運行頻率可達165 MHz，吞吐量為1 184.8 Mbit/s。

[1] 劉宗斌, 馬原, 荊繼武. SM3散列算法的硬件實現與研究[J]. 信息網絡安全, 2011,(9): 191-193.

LIU B, MA Y, JING W, et al. Implementation of SM3 Hash function on FPGA[J]. Netinfo Security,2011,(9):191-193.

[2] 丁冬平,高獻偉. SM3算法的FPGA設計與實現[J]. 微型機與應用,2012,31(5):26-28.

DING D P, GAO X W. Design and implementation of SM3 algorithm on FPGA[J]. Microcomputer & Its Applications, 2012, 31(5): 26-28.

[3] 郭文平, 劉政林, 陳毅成, 等. 高吞吐率、低能耗的SHA-1加密算法的硬件實現[J]. 微電子學與計算機,2008,25(5):76-79.

GUO W P, LIU Z L, CHEN Y C, et al. A high throughput and low-power implementation of the SHA-1 Hash function[J]. Microelectronics & Computer, 2008, 25(5):76-79.

[4] HENZEN L, AUMASSON J P, MEIER W, et al. VLSI characterization of the cryptographic hash function blake[J]. IEEE Transactions on Very Large Scale Integration Systems, 2011, 19(10): 1746-1754.

[5] MA Y, XIA L N, LIN J Q, et al, Hardware performance optimization and evaluation of SM3 Hash algorithm on FPGA[M]// Information and Communications Security. 2012:105-118.

[6] 田椒陵. SM3算法界面設計及安全性分析[J]. 信息安全與技術, 2014,(5):24-26.

TIAN J L. SM3 algorithm interface design and safety analysis[J]. Information Security and Technology,2014,(5):24-26.

[7] 鄭強, 高能, 張令臣. 基于 SM3算法的動態口令卡的設計與實現[J]. 計算機應用與軟件,2013,30(2):14-17.

ZHENG Q, GAO N, ZHANG L C. Design and implementation of dynamic password card based on SM3 algorithm[J]. Computer Applications and Software, 2013, 30(2):14-17.

[8] 于永鵬, 嚴迎建, 李偉. SM3算法高速ASIC設計及實現[J]. 微電子學與計算機,2016,33(4):21-26.

YU Y P, YAN Y J, LI W. High speed ASIC design and implementation of SM3 algorithm[J]. Microelectronics & Computer, 2016, 33(4): 21-26.

[9] 周威, 王博, 張衛東. SM3算法硬件實現研究與應用[J]. 電子測量技術, 2015, 38(12):67-71.

ZHOU W, WANG B, ZHANG W D. Research and application of SM3 hardware implementation[J]. Electronic Measurement Technology, 2015,38(12):67-71.

[10] QU, K G, WANG A. A novel masking scheme for SM3 basedMAC[J]. China Communications.2016.12 (6):11-21.

[11] 朱寧龍, 戴紫彬, 張立朝. SM3及SHA-2系列算法硬件可重構設計與實現[J]. 微電子學,2015,45(6):777-780+784.

ZHU N L, DAI Z B, ZHANG L C, et al. Design and implementation of hardware reconfiguration for SM3 and SHA-2 Hash function[J]. Microelectronics,2015,45(6):777-780+784.

[12] 蔡冰清, 白國強. SM3雜湊算法的流水線結構硬件實現[J]. 微電子學與計算機,2015,32(1):15-18.

CAI B Q, BAI G Q. Implementation of pipeline structure of SM3 algorithm on FPGA[J]. Microelectronics & Computer, 2015, 32(1): 15-18.

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

WANG X Y, YANG X W. Optimization design and Implementation of SM3 algorithm based on FPGA[J]. Computer Engineering, 2012, 38(6):244-246.

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

ZHANG Q, LI S G. Design and Implementation of SM3 Algorithm in ASIC[J]. Microelectronics & Computer, 2014, 31(9): 143- 146.

[15] 國家密碼管理局. SM3密碼雜湊算法[EB/OL]. http://www.oscca. gov.cn/News/201012/News_1199.htm.

State Cryptography Administration Office of Security Commercial Code Administration. SM3 Cryptographic Hash algorithm [EB/OL]. http://www.oscca.gov.cn/News/201012/News_1199.htm.

[16] PONG P. 基于Nios II的嵌入式SoPC系統設計與Verilog開發實例[M].北京：電子工業出版社, 2015:311-323.

PONG P. Embedded SoPC design with Nios II processor and Verilog examples[M]. Beijing: Publishing House of Electronics Industry, 2015:311-323.

[17] 王樂井. 基于SOPC技術的實時圖像處理系統的設計與研究[D].長春: 吉林大學, 2010.

WANG L J. The design and research of real time image processing system based on SOPC technology[D]. Changchun: Jilin University, 2010.

Implementation of SM3 algorithm based on SoPC component

SHAO Meng-li1, YIN Xin-chun1,2, LI Yan-mei3

(1. School of Information Engineering,Yangzhou University, Yangzhou 225000, China; 2. School of Guangling, Yangzhou University, Yangzhou 225000, China)

Firstly the realization of SM3 on SoC was given. The structure of the algorithm was analyzed mainly, and the algorithm was realized by the Verilog hardware description language, in order to simulate this algorithm, the Altera simulation software ModelSim was chosen, SoPC Builder was used for interface package, and finally it was implemented in the Cyclone IV EP4CE22F17C8N. Its operation frequency can reach 165 MHz and its throughput rate is 1 184.8 Mbit/s.

SM3, FPGA, hardware implementation, SoC

s: The National Natural Science Foundation of China (No.61472343), The Ordinary University Graduate Student Scientific Research Innovation Project of Jiangsu Province (No.KYLX15_1362)

TP393

A

10.11959/j.issn.2096-109x.2017.00146

邵夢麗（1991-），女，江蘇鹽城人，揚州大學碩士生，主要研究方向為國密算法的SoC設計與實現。

殷新春（1962-），男，江蘇姜堰人，博士，揚州大學教授、博士生導師，主要研究方向為密碼學、軟件質量保障、高性能計算。

李艷梅（1991-），女，江蘇徐州人，揚州大學碩士生，主要研究方向為信息安全。

2016-11-28；

2017-01-05。通信作者：殷新春，xcyin@yzu.edu.cn

國家自然科學基金資助項目（No.61472343）；江蘇省普通高校研究生科研創新計劃項目（No.KYLX15_1362）