基于雙重流水同步迭代的SM3算法高速硬件設計

谷會濤 武宗濤

摘要：SM3算法是國家標準商用密碼雜湊算法，廣泛應用于數字簽名和驗證、消息認證碼的生成與驗證以及隨機數的生成等領域。介紹了SM3算法的基本流程，分析了SM3算法高速實現的3種方法，提出了基于雙重流水同步迭代的SM3算法高速硬件設計方法，進行了模擬驗證和FPGA設計實現，給出了算法性能和綜合結果，結果表明所提方法具有較高的運算性能。

關鍵詞：雜湊運算；SM3；高速設計；現場可編程門陣列

中圖分類號：TN918.4文獻標志碼：A文章編號：1008-1739（2020）02-54-3

0引言

雜湊運算是不可逆的密碼運算過程，可將任意長度的數據信息變換成固定長度的數據輸出[1]，在商用密碼中廣泛應用在數字簽名和驗證、消息認證碼的生成與驗證以及隨機數的生成等方面[2]。美國制定了安全雜湊算法（Secure Hash Algorithm，SHA）等系列標準，我國國家密碼管理局2010年公布了中國商用密碼雜湊算法標準SM3算法，該算法在SHA-256基礎上改進實現，采用Merkle-Damgard結構，消息分組長度為512 bit，摘要值長度為256 bit[2]。

SM3等密碼算法運算復雜，在計算機處理器上采用軟件實現SM3算法，性能難以滿足高速應用場景的使用需求。本文分析了SM3算法的實現原理，提出了一種高速實現方法，最后基于現場可編程門陣列（Field-Programmable Gate Array，FPGA）進行了設計實現，驗證了該方法的運算性能。

1 SM3算法

SM3算法標準約定，對于任意有限長度的消息，SM3算法可生成256 bit的雜湊值。SM3雜湊算法主要包括填充和迭代壓縮2個過程。

①將整個消息用1 bit1， bit0和64 bit消息長度進行填充，填充完畢的消息長度按512 bit對齊。消息填充后按512 bit進行分組，每個消息分組依次進行迭代壓縮運算。

2 SM3算法實現方法

SM3算法計算過程中，消息分組迭代壓縮過程計算較為復雜，實現邏輯直接影響算法的執行效率。為了實現SM3快速運算，研究人員提出了多種FPGA迭代實現方法。SM3算法中，一個消息分組一般需要進行64輪運算，每輪運算包括消息擴展和壓縮函數2步運算。根據這2步運算的耦合程度和執行順序，FPGA迭代實現方法可以分為順序迭代[3]、循環展開[4]和流水迭代[5]3種方法[6]。

順序迭代方法如圖2所示，一個消息分組的輪運算串行執行，每輪運算的消息擴展和壓縮函數運算也串行執行。順序迭代實現方法控制簡單、實現方便。但如果將消息擴展和壓縮函數運算在一個時鐘周期內完成，則導致硬件邏輯關鍵路徑較長，降低了時鐘頻率，進而影響運算速率。如果將消息擴展和壓縮函數運算劃分為2個時鐘周期執行，則一個消息分組的運算需要128個時鐘周期左右，運算速率較低。

循環展開方法如圖3所示，將消息分組的2輪消息進行擴展運算，2輪壓縮函數運算循環展開各放到一個時鐘周期執行，因此可以將一個消息分組的運算時間降低到順序迭代方法的50%左右，一個消息分組的運算需要64個時鐘周期。如果將更多輪操作循環展開，運算時間還可以進一步壓縮。循環展開方法速率較高，但需要占用更多的硬件資源。由于一個時鐘周期完成的2輪壓縮函數運算存在相關性，必須串行執行，因此單周期內需要完成的運算更多，限制了整個算法實現的工作頻率。

流水迭代方法如圖4所示，將消息擴展運算和壓縮函數流水實現，且消息擴展運算與壓縮函數并行執行。流水迭代方法控制簡單、實現方便，性能與循環展開方法相近，占用硬件資源較少。

3雙重流水同步迭代技術設計與實現

基于流水迭代方法，本文提出了SM3算法雙重流水同步迭代方法。該方法分別設計了消息擴展運算和壓縮函數運算2條流水線，并且第+1輪消息擴展運算和第輪壓縮函數運算同步執行，2條流水線同步運算極大提升了數據塊運算效率。

4 FPGA實現與性能評估

本文基于雙重流水同步迭代方法，設計實現了SM3算法，采用ModelSim工具進行了功能驗證，采用標準給出的2組測試向量進行輸入，輸出結果與標準預期值相同。本文基于Xilinx公司XC7K325T芯片，采用ISE14.7進行了綜合實現，綜合結果如表1所示，本文方法最高綜合頻率222 MHz。

按此工作頻率設置測試用例，采用ModelSim工具對長消息進行運算，本文結構性能達到約1 690 Mbps。表2給出了本文結構與順序迭代方法、循環展開方法和流水迭代方法性能對比。從表中可以看出，文獻[3-4]，算法硬件邏輯復雜、工作頻率較低，影響了計算性能。文獻[5]方法主頻和計算性能較高。不考慮器件選型的差異，相比這些方法，本文提出的方法在工作主頻和計算性能上最優。

5結束語

本文介紹了SM3算法的基本運算步驟，分析了3種典型的SM3算法實現方法，提出了基于雙重流水同步迭代技術的SM3算法高速硬件設計方法。通過對本文方法進行模擬驗證和FPGA設計實現，得出了算法性能和綜合結果。結果表明，本文提出的方法可獲得較高的工作頻率和算法性能。

參考文獻

[1]國家密碼管理局.GM/T 0004-2012 SM3密碼雜湊算法[S].北京：中國標準出版社，2012.

[2]趙睿斌，楊紹亮，王毛路，等.基于商密體系的政務鏈解決數據安全共享交換的研究[J].信息安全與通信保密，2018，（5）： 83-88.

[3]王曉燕，楊先文.基于FPGA的SM3算法優化設計與實現[J].計算機工程，2012，38（6）：244-246.

[4]周威，王博，張衛東.SM3算法硬件實現研究與應用[J].電子測量技術，2015，38（12）：67-71.

[5]劉宗斌，馬原，荊繼武，等.SM3哈希算法的硬件實現與研究[J].信息網絡安全，2011（9）：191-193.

[6]丁冬平，高獻偉.SM3算法的FPGA設計與實現[J].微型機與應用，2012，31（5）：26-28.