FPGA芯片EP2S90F1508C3實現SM3算法的硬件實現策略

在分析SM3算法的基礎上詳細介紹了目前Hash函數的4種硬件實現策略，同時給出了迭代方式和基于充分利用時鐘周期的循環(huán)展開方式下的FPGA實現。該循環(huán)展開方式有效地減少了一半的工作時鐘數和11%的運算時間，吞吐量提高了11%，且占用的硬件資源較少。

Hash函數是密碼學中最基本的模塊之一，在密碼學中扮演著極其重要的角色，廣泛應用于數字簽名、消息鑒別和偽隨機數生成器等領域，是近幾年密碼學研究的熱點領域[1]。Hash函數是將任意長度的信息通過算法變成固定長度的輸出，且這個變換過程是不可逆的。Hash函數的不可逆特性使得攻擊者不能通過Hash值推出任何部分的原始信息。因為對于原始信息中的任意一個比特數據發(fā)生改變，其Hash值都將發(fā)生明顯變化。此外，Hash函數還具有碰撞約束性，即不能找到一個輸入使其輸出結果等于一個已知的輸出結果，或者不能同時找到兩個不同的輸入使其輸出結果完全一致。正是這些特性，使得Hash值可以用來驗證信息是否被修改。

1 SM3算法簡介

為了滿足電子認證服務系統等應用需求，國家密碼管理局于2010年12月發(fā)布了SM3密碼Hash算法。該算法適用于商用密碼應用中的數字簽名和驗證、消息認證碼的生成與驗證以及隨機數的生成，可滿足多種密碼應用的安全需求。SM3算法能夠對任何小于264 bit的數據進行計算，輸出長度為256 bit的Hash值。SM3算法包括預處理、消息擴展和計算Hash值三部分。預處理部分由消息填充和消息分組兩部分組成。首先將接收到的消息末尾填充一個“1”，再添加k個“0”，使得填充后的數據成為滿足Length=448 mod 512 bit的數據長度，再在末尾附上64 bit消息長度的二進制表示數，然后將消息分成512 bit的子塊，最后將每個512 bit的消息子塊擴展成132個字W0，W1，…，W67，W0′，W1′，…，W63′用于Hash值的計算。SM3算法計算流程圖如圖1所示。

SM3算法的Hash運算主要是在壓縮函數部分，壓縮函數共包含64輪，每輪包括12步運算，64輪循環(huán)計算結束后，再將計算結果與輸入到本輪計算的初始數據進行異或運算，即上一次Hash運算的Hash值輸出Hi與輸入到本輪計算的初始數據異或得到本次Hash值輸出Hi+1。Hn即為最終的Hash值，H0為設計者提供的初始值IV。2 Hash算法的硬件實現策略在通過FPGA編程實現Hash算法過程中，提高吞吐量以及減少硬件資源占用是衡量硬件實現算法的重要指標，高效率、低功耗以及面積優(yōu)化設計都是FPGA設計中最受關注的方面。目前為止，Hash算法的FPGA實現策略大致有以下4種方式[1-2]，如圖2所示。

（1）迭代方式：該方式將單步運算的結果重新反饋到輸入端，在節(jié)約硬件資源的同時造成了較大的時延，雖然效率較低，但比較實用?！。?）循環(huán)展開方式：該方式根據算法的具體特性，將多步運算合并成單步運算，以加大并行運算規(guī)模的方式來提高單步運算的效率?！。?）流水線方式：該方式將所有單步運算全部在時鐘的控制下予以實現，每個時鐘均有輸出。全流水線時的吞吐量達到最高，但是硬件資源消耗相當大。由于Hash函數的運算特點，該方式很少在實際中使用?！。?）混合方式：該方式實現的算法能在面積和速度上取得平衡。

3 SM3算法的FPGA實現

由于SM3算法消息擴展部分的軟硬件實現的效率相差不大，因此本文著重討論該算法的計算部分在FPGA上的兩種實現方式。

3.1 迭代方式

由于SM3算法的每輪計算過程大致相同，因此可以采用迭代方式實現。實現過程中，將存放常數Tj和IV的常量矩陣利用ROM結構實現。分析SM3算法的消息擴展和壓縮函數的計算過程與特點可以看出，預先通過組合邏輯計算全部W0，W1，…，W67，W0′，W1′，…，W63′的值需要消耗大量的硬件資源。而在每輪的壓縮函數計算過程中，只需使用相應的一組Wj和Wj′，因此便無需預先將W0，W1，…，W67，W0′，W1′，…，W63′值全部計算出來，可以利用時鐘的控制，在每次運算壓縮函數之前，預先計算將要被使用的一組Wj和Wj′，顯然這將使獲得每輪壓縮函數運算結果消耗2個時鐘周期。加上初始值的輸入、明文輸入以及Hash結果輸出共消耗的3個時鐘周期，采用迭代方式進行一次SM3算法需要消耗1+1+1+64×2=131個時鐘周期。

3.2 循環(huán)展開方式

仔細分析SM3算法的運算過程及迭代方式實現SM3算法的設計過程可知，時間主要耗費在消息擴展和壓縮函數的計算上[3]。在SM3算法的迭代方式實現中，每輪壓縮函數的運算和消息擴展運算中均需消耗一個時鐘周期，尤其是在進行消息擴展過程中，每組Wj和Wj′計算量都比較小，利用一個時鐘周期去進行運算實在過于浪費。如果在一個時鐘周期里進行兩組Wj和Wj′的計算，同時把一個時鐘中本來只進行一輪壓縮函數的運算也增加到兩輪，這樣不僅能更充分地利用一個時鐘周期提高計算速度，而且整個SM3算法核心運算過程的時鐘消耗也將縮短到64個時鐘周期。

3.3 FPGA實現結果

本文采用Altera公司Stratix II系列的EP2S90F1508C3芯片，以Quartus II 8.1為開發(fā)環(huán)境[4]，采用硬件描述語言VHDL進行SM3算法的FPGA實現。SM3算法實現的整體結構可分為庫函數模塊和主程序模塊兩大模塊[1，5]。在SM3算法庫函數模塊中定義了6個左循環(huán)移位函數ROL7、ROL9、ROL12、ROL15、ROL19、ROLk和4個函數FF、GG、P0、P1，均用組合邏輯資源實現，常數Tj和IV的常量矩陣利用ROM結構實現。主程序中定義了實體端口（如圖3所示），編譯生成的模塊圖如圖4所示。用狀態(tài)機對運算過程進行控制，SM3算法的主程序中包含了s00、s01、s02、s03、s04和s05 6個狀態(tài)。

以2010年12月國家密碼管理局發(fā)布SM3算法所附錄的運算示例中提供的數據為標準，將實驗仿真所得到的計算數據與該標準進行對照，對于一個512 bit分組和兩個512 bit分組，采用迭代方式實現和采用循環(huán)展開方式實現均計算出了正確的Hash值“66c7f0f4 62eeedd9 d1f2d46b dc10e4e2 4167c487 5cf2f7a2 297da02b 8f4ba8e0”和“debe9ff9 2275b8a1 38604889 c18e5a4d 6fdb70e5 387e5765 293dcba3 9c0c5732”。實驗仿真結果分別如圖5~圖8所示。