摘 要: 在分析SM3算法的基礎(chǔ)上詳細介紹了目前Hash函數(shù)的4種硬件實現(xiàn)策略,同時給出了迭代方式和基于充分利用時鐘周期的循環(huán)展開方式下的FPGA實現(xiàn)。該循環(huán)展開方式有效地減少了一半的工作時鐘數(shù)和11%的運算時間,吞吐量提高了11%,且占用的硬件資源較少。
關(guān)鍵詞: SM3;迭代方式;循環(huán)展開方式;FPGA;VHDL
Hash函數(shù)是密碼學(xué)中最基本的模塊之一,在密碼學(xué)中扮演著極其重要的角色,廣泛應(yīng)用于數(shù)字簽名、消息鑒別和偽隨機數(shù)生成器等領(lǐng)域,是近幾年密碼學(xué)研究的熱點領(lǐng)域[1]。
Hash函數(shù)是將任意長度的信息通過算法變成固定長度的輸出,且這個變換過程是不可逆的。Hash函數(shù)的不可逆特性使得攻擊者不能通過Hash值推出任何部分的原始信息。因為對于原始信息中的任意一個比特數(shù)據(jù)發(fā)生改變,其Hash值都將發(fā)生明顯變化。此外,Hash函數(shù)還具有碰撞約束性,即不能找到一個輸入使其輸出結(jié)果等于一個已知的輸出結(jié)果,或者不能同時找到兩個不同的輸入使其輸出結(jié)果完全一致。正是這些特性,使得Hash值可以用來驗證信息是否被修改。
1 SM3算法簡介
為了滿足電子認證服務(wù)系統(tǒng)等應(yīng)用需求,國家密碼管理局于2010年12月發(fā)布了SM3密碼Hash算法。該算法適用于商用密碼應(yīng)用中的數(shù)字簽名和驗證、消息認證碼的生成與驗證以及隨機數(shù)的生成,可滿足多種密碼應(yīng)用的安全需求。SM3算法能夠?qū)θ魏涡∮?64 bit的數(shù)據(jù)進行計算,輸出長度為256 bit的Hash值。
SM3算法包括預(yù)處理、消息擴展和計算Hash值三部分。預(yù)處理部分由消息填充和消息分組兩部分組成。首先將接收到的消息末尾填充一個“1”,再添加k個“0”,使得填充后的數(shù)據(jù)成為滿足Length=448 mod 512 bit的數(shù)據(jù)長度,再在末尾附上64 bit消息長度的二進制表示數(shù),然后將消息分成512 bit的子塊,最后將每個512 bit的消息子塊擴展成132個字W0,W1,…,W67,W0′,W1′,…,W63′用于Hash值的計算。SM3算法計算流程圖如圖1所示。
SM3算法的Hash運算主要是在壓縮函數(shù)部分,壓縮函數(shù)共包含64輪,每輪包括12步運算,64輪循環(huán)計算結(jié)束后,再將計算結(jié)果與輸入到本輪計算的初始數(shù)據(jù)進行異或運算,即上一次Hash運算的Hash值輸出Hi與輸入到本輪計算的初始數(shù)據(jù)異或得到本次Hash值輸出Hi+1。Hn即為最終的Hash值,H0為設(shè)計者提供的初始值IV。
2 Hash算法的硬件實現(xiàn)策略
在通過FPGA編程實現(xiàn)Hash算法過程中,提高吞吐量以及減少硬件資源占用是衡量硬件實現(xiàn)算法的重要指標,高效率、低功耗以及面積優(yōu)化設(shè)計都是FPGA設(shè)計中最受關(guān)注的方面。目前為止,Hash算法的FPGA實現(xiàn)策略大致有以下4種方式[1-2],如圖2所示。
?。?)迭代方式:該方式將單步運算的結(jié)果重新反饋到輸入端,在節(jié)約硬件資源的同時造成了較大的時延,雖然效率較低,但比較實用。
?。?)循環(huán)展開方式:該方式根據(jù)算法的具體特性,將多步運算合并成單步運算,以加大并行運算規(guī)模的方式來提高單步運算的效率。
(3)流水線方式:該方式將所有單步運算全部在時鐘的控制下予以實現(xiàn),每個時鐘均有輸出。全流水線時的吞吐量達到最高,但是硬件資源消耗相當大。由于Hash函數(shù)的運算特點,該方式很少在實際中使用。
?。?)混合方式:該方式實現(xiàn)的算法能在面積和速度上取得平衡。
3 SM3算法的FPGA實現(xiàn)
由于SM3算法消息擴展部分的軟硬件實現(xiàn)的效率相差不大,因此本文著重討論該算法的計算部分在FPGA上的兩種實現(xiàn)方式。
3.1 迭代方式
由于SM3算法的每輪計算過程大致相同,因此可以采用迭代方式實現(xiàn)。實現(xiàn)過程中,將存放常數(shù)Tj和IV的常量矩陣利用ROM結(jié)構(gòu)實現(xiàn)。分析SM3算法的消息擴展和壓縮函數(shù)的計算過程與特點可以看出,預(yù)先通過組合邏輯計算全部W0,W1,…,W67,W0′,W1′,…,W63′的值需要消耗大量的硬件資源。而在每輪的壓縮函數(shù)計算過程中,只需使用相應(yīng)的一組Wj和Wj′,因此便無需預(yù)先將W0,W1,…,W67,W0′,W1′,…,W63′值全部計算出來,可以利用時鐘的控制,在每次運算壓縮函數(shù)之前,預(yù)先計算將要被使用的一組Wj和Wj′,顯然這將使獲得每輪壓縮函數(shù)運算結(jié)果消耗2個時鐘周期。加上初始值的輸入、明文輸入以及Hash結(jié)果輸出共消耗的3個時鐘周期,采用迭代方式進行一次SM3算法需要消耗1+1+1+64×2=131個時鐘周期。
3.2 循環(huán)展開方式
仔細分析SM3算法的運算過程及迭代方式實現(xiàn)SM3算法的設(shè)計過程可知,時間主要耗費在消息擴展和壓縮函數(shù)的計算上[3]。在SM3算法的迭代方式實現(xiàn)中,每輪壓縮函數(shù)的運算和消息擴展運算中均需消耗一個時鐘周期,尤其是在進行消息擴展過程中,每組Wj和Wj′計算量都比較小,利用一個時鐘周期去進行運算實在過于浪費。如果在一個時鐘周期里進行兩組Wj和Wj′的計算,同時把一個時鐘中本來只進行一輪壓縮函數(shù)的運算也增加到兩輪,這樣不僅能更充分地利用一個時鐘周期提高計算速度,而且整個SM3算法核心運算過程的時鐘消耗也將縮短到64個時鐘周期。
3.3 FPGA實現(xiàn)結(jié)果
本文采用Altera公司Stratix II系列的EP2S90F1508C3芯片,以Quartus II 8.1為開發(fā)環(huán)境[4],采用硬件描述語言VHDL進行SM3算法的FPGA實現(xiàn)。SM3算法實現(xiàn)的整體結(jié)構(gòu)可分為庫函數(shù)模塊和主程序模塊兩大模塊[1,5]。在SM3算法庫函數(shù)模塊中定義了6個左循環(huán)移位函數(shù)ROL7、ROL9、ROL12、ROL15、ROL19、ROLk和4個函數(shù)FF、GG、P0、P1,均用組合邏輯資源實現(xiàn),常數(shù)Tj和IV的常量矩陣利用ROM結(jié)構(gòu)實現(xiàn)。主程序中定義了實體端口(如圖3所示),編譯生成的模塊圖如圖4所示。用狀態(tài)機對運算過程進行控制,SM3算法的主程序中包含了s00、s01、s02、s03、s04和s05 6個狀態(tài)。
以2010年12月國家密碼管理局發(fā)布SM3算法所附錄的運算示例中提供的數(shù)據(jù)為標準,將實驗仿真所得到的計算數(shù)據(jù)與該標準進行對照,對于一個512 bit分組和兩個512 bit分組,采用迭代方式實現(xiàn)和采用循環(huán)展開方式實現(xiàn)均計算出了正確的Hash值“66c7f0f4 62eeedd9 d1f2d46b dc10e4e2 4167c487 5cf2f7a2 297da02b 8f4ba8e0”和“debe9ff9 2275b8a1 38604889 c18e5a4d 6fdb70e5 387e5765 293dcba3 9c0c5732”。實驗仿真結(jié)果分別如圖5~圖8所示。
表1比較了兩種實現(xiàn)方式下的硬件資源占用、工作主頻、所需時鐘數(shù)、計算時間及吞吐量。由表1可得,循環(huán)展開方式的吞吐量是迭代方式的1.11倍,即工作效率提高了11%,循環(huán)展開方式的計算時間為迭代方式的0.9倍,即時間消耗減少了11%。
本文成功將SM3算法進行了FPGA實現(xiàn),并將基于充分利用時鐘周期的循環(huán)展開方式與迭代方式實現(xiàn)的SM3算法相比較,雖然硬件資源占用有所增加,但其時間消耗減少了11%,吞吐量提高了11%。由此可見,對于SM3算法的實現(xiàn),采用循環(huán)展開方式比完全的迭代方式效率更高,時間消耗更少,而占用資源的增加與取得的收效相比并不算多,這對追求高效率、低資源消耗的移動設(shè)備至關(guān)重要。
參考文獻
[1] 高獻偉,路而紅.密碼算法FPGA實現(xiàn)技術(shù)[M].北京:西苑出版社,2010.
[2] RODRIGUEZ-HENRIQUEZ R. SAQIB N A, Díaz Pérez A, et al . Cryptographic Algorithms on reconfigurable hardware[M]. Springer, 2006:189-220.
[3] 曾旭,高獻偉,路而紅,等.HASH算法MD5的高速實現(xiàn)[J].成都信息工程學(xué)報,2009,24(2):129-132.
[4] 李洪偉,袁斯華.基于Quartus II的FPGA/CPLD設(shè)計[M].北京:電子工業(yè)出版社,2006.
[5] 劉欲曉,方強.EDA技術(shù)與VHDL電路開發(fā)應(yīng)用實踐[M].北京:電子工業(yè)出版社,2009.