摘  要： 在分析SM3算法的基礎(chǔ)上詳細(xì)介紹了目前Hash函數(shù)的4種硬件實(shí)現(xiàn)策略，同時(shí)給出了迭代方式和基于充分利用時(shí)鐘周期的循環(huán)展開(kāi)方式下的FPGA實(shí)現(xiàn),。該循環(huán)展開(kāi)方式有效地減少了一半的工作時(shí)鐘數(shù)和11%的運(yùn)算時(shí)間,，吞吐量提高了11%,，且占用的硬件資源較少。
關(guān)鍵詞： SM3,；迭代方式,；循環(huán)展開(kāi)方式；FPGA,；VHDL

　Hash函數(shù)是密碼學(xué)中最基本的模塊之一,，在密碼學(xué)中扮演著極其重要的角色，廣泛應(yīng)用于數(shù)字簽名,、消息鑒別和偽隨機(jī)數(shù)生成器等領(lǐng)域,，是近幾年密碼學(xué)研究的熱點(diǎn)領(lǐng)域[1]。
Hash函數(shù)是將任意長(zhǎng)度的信息通過(guò)算法變成固定長(zhǎng)度的輸出,，且這個(gè)變換過(guò)程是不可逆的,。Hash函數(shù)的不可逆特性使得攻擊者不能通過(guò)Hash值推出任何部分的原始信息。因?yàn)閷?duì)于原始信息中的任意一個(gè)比特?cái)?shù)據(jù)發(fā)生改變,，其Hash值都將發(fā)生明顯變化,。此外，Hash函數(shù)還具有碰撞約束性,，即不能找到一個(gè)輸入使其輸出結(jié)果等于一個(gè)已知的輸出結(jié)果,，或者不能同時(shí)找到兩個(gè)不同的輸入使其輸出結(jié)果完全一致。正是這些特性,，使得Hash值可以用來(lái)驗(yàn)證信息是否被修改,。
1 SM3算法簡(jiǎn)介
　為了滿足電子認(rèn)證服務(wù)系統(tǒng)等應(yīng)用需求，國(guó)家密碼管理局于2010年12月發(fā)布了SM3密碼Hash算法,。該算法適用于商用密碼應(yīng)用中的數(shù)字簽名和驗(yàn)證,、消息認(rèn)證碼的生成與驗(yàn)證以及隨機(jī)數(shù)的生成，可滿足多種密碼應(yīng)用的安全需求,。SM3算法能夠?qū)θ魏涡∮?64 bit的數(shù)據(jù)進(jìn)行計(jì)算,，輸出長(zhǎng)度為256 bit的Hash值。
SM3算法包括預(yù)處理,、消息擴(kuò)展和計(jì)算Hash值三部分,。預(yù)處理部分由消息填充和消息分組兩部分組成。首先將接收到的消息末尾填充一個(gè)“1”,，再添加k個(gè)“0”,，使得填充后的數(shù)據(jù)成為滿足Length=448 mod 512 bit的數(shù)據(jù)長(zhǎng)度，再在末尾附上64 bit消息長(zhǎng)度的二進(jìn)制表示數(shù),，然后將消息分成512 bit的子塊,，最后將每個(gè)512 bit的消息子塊擴(kuò)展成132個(gè)字W0，W1,，…,，W67,，W0′，W1′,，…,，W63′用于Hash值的計(jì)算。SM3算法計(jì)算流程圖如圖1所示,。

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

　（1）迭代方式：該方式將單步運(yùn)算的結(jié)果重新反饋到輸入端,，在節(jié)約硬件資源的同時(shí)造成了較大的時(shí)延,，雖然效率較低，但比較實(shí)用,。
?。?）循環(huán)展開(kāi)方式：該方式根據(jù)算法的具體特性，將多步運(yùn)算合并成單步運(yùn)算,，以加大并行運(yùn)算規(guī)模的方式來(lái)提高單步運(yùn)算的效率,。
　（3）流水線方式：該方式將所有單步運(yùn)算全部在時(shí)鐘的控制下予以實(shí)現(xiàn),，每個(gè)時(shí)鐘均有輸出,。全流水線時(shí)的吞吐量達(dá)到最高，但是硬件資源消耗相當(dāng)大,。由于Hash函數(shù)的運(yùn)算特點(diǎn),，該方式很少在實(shí)際中使用。
?。?）混合方式：該方式實(shí)現(xiàn)的算法能在面積和速度上取得平衡,。
3 SM3算法的FPGA實(shí)現(xiàn)
　由于SM3算法消息擴(kuò)展部分的軟硬件實(shí)現(xiàn)的效率相差不大,，因此本文著重討論該算法的計(jì)算部分在FPGA上的兩種實(shí)現(xiàn)方式。
3.1 迭代方式
　由于SM3算法的每輪計(jì)算過(guò)程大致相同,，因此可以采用迭代方式實(shí)現(xiàn),。實(shí)現(xiàn)過(guò)程中，將存放常數(shù)Tj和IV的常量矩陣?yán)肦OM結(jié)構(gòu)實(shí)現(xiàn),。分析SM3算法的消息擴(kuò)展和壓縮函數(shù)的計(jì)算過(guò)程與特點(diǎn)可以看出,，預(yù)先通過(guò)組合邏輯計(jì)算全部W0，W1,，…,，W67，W0′,，W1′,，…，W63′的值需要消耗大量的硬件資源,。而在每輪的壓縮函數(shù)計(jì)算過(guò)程中,，只需使用相應(yīng)的一組Wj和Wj′，因此便無(wú)需預(yù)先將W0,，W1,，…，W67,，W0′,，W1′，…,，W63′值全部計(jì)算出來(lái),，可以利用時(shí)鐘的控制，在每次運(yùn)算壓縮函數(shù)之前,，預(yù)先計(jì)算將要被使用的一組Wj和Wj′,，顯然這將使獲得每輪壓縮函數(shù)運(yùn)算結(jié)果消耗2個(gè)時(shí)鐘周期。加上初始值的輸入,、明文輸入以及Hash結(jié)果輸出共消耗的3個(gè)時(shí)鐘周期,，采用迭代方式進(jìn)行一次SM3算法需要消耗1+1+1+64×2=131個(gè)時(shí)鐘周期。
3.2 循環(huán)展開(kāi)方式
　仔細(xì)分析SM3算法的運(yùn)算過(guò)程及迭代方式實(shí)現(xiàn)SM3算法的設(shè)計(jì)過(guò)程可知,，時(shí)間主要耗費(fèi)在消息擴(kuò)展和壓縮函數(shù)的計(jì)算上[3],。在SM3算法的迭代方式實(shí)現(xiàn)中，每輪壓縮函數(shù)的運(yùn)算和消息擴(kuò)展運(yùn)算中均需消耗一個(gè)時(shí)鐘周期,，尤其是在進(jìn)行消息擴(kuò)展過(guò)程中,，每組Wj和Wj′計(jì)算量都比較小，利用一個(gè)時(shí)鐘周期去進(jìn)行運(yùn)算實(shí)在過(guò)于浪費(fèi)。如果在一個(gè)時(shí)鐘周期里進(jìn)行兩組Wj和Wj′的計(jì)算,，同時(shí)把一個(gè)時(shí)鐘中本來(lái)只進(jìn)行一輪壓縮函數(shù)的運(yùn)算也增加到兩輪,，這樣不僅能更充分地利用一個(gè)時(shí)鐘周期提高計(jì)算速度，而且整個(gè)SM3算法核心運(yùn)算過(guò)程的時(shí)鐘消耗也將縮短到64個(gè)時(shí)鐘周期,。
3.3 FPGA實(shí)現(xiàn)結(jié)果
　本文采用Altera公司Stratix II系列的EP2S90F1508C3芯片,，以Quartus II 8.1為開(kāi)發(fā)環(huán)境[4]，采用硬件描述語(yǔ)言VHDL進(jìn)行SM3算法的FPGA實(shí)現(xiàn),。SM3算法實(shí)現(xiàn)的整體結(jié)構(gòu)可分為庫(kù)函數(shù)模塊和主程序模塊兩大模塊[1,，5]。在SM3算法庫(kù)函數(shù)模塊中定義了6個(gè)左循環(huán)移位函數(shù)ROL7,、ROL9,、ROL12、ROL15,、ROL19,、ROLk和4個(gè)函數(shù)FF、GG,、P0,、P1，均用組合邏輯資源實(shí)現(xiàn),，常數(shù)Tj和IV的常量矩陣?yán)肦OM結(jié)構(gòu)實(shí)現(xiàn),。主程序中定義了實(shí)體端口（如圖3所示），編譯生成的模塊圖如圖4所示,。用狀態(tài)機(jī)對(duì)運(yùn)算過(guò)程進(jìn)行控制，SM3算法的主程序中包含了s00,、s01,、s02、s03,、s04和s05 6個(gè)狀態(tài),。

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

　表1比較了兩種實(shí)現(xiàn)方式下的硬件資源占用,、工作主頻、所需時(shí)鐘數(shù),、計(jì)算時(shí)間及吞吐量,。由表1可得，循環(huán)展開(kāi)方式的吞吐量是迭代方式的1.11倍,，即工作效率提高了11%,，循環(huán)展開(kāi)方式的計(jì)算時(shí)間為迭代方式的0.9倍,，即時(shí)間消耗減少了11%。

　本文成功將SM3算法進(jìn)行了FPGA實(shí)現(xiàn),，并將基于充分利用時(shí)鐘周期的循環(huán)展開(kāi)方式與迭代方式實(shí)現(xiàn)的SM3算法相比較,，雖然硬件資源占用有所增加，但其時(shí)間消耗減少了11%,，吞吐量提高了11%,。由此可見(jiàn)，對(duì)于SM3算法的實(shí)現(xiàn),，采用循環(huán)展開(kāi)方式比完全的迭代方式效率更高,，時(shí)間消耗更少，而占用資源的增加與取得的收效相比并不算多,，這對(duì)追求高效率,、低資源消耗的移動(dòng)設(shè)備至關(guān)重要。
參考文獻(xiàn)
[1] 高獻(xiàn)偉,，路而紅.密碼算法FPGA實(shí)現(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] 曾旭，高獻(xiàn)偉,，路而紅,，等.HASH算法MD5的高速實(shí)現(xiàn)[J].成都信息工程學(xué)報(bào)，2009,，24（2）：129-132.
[4] 李洪偉,，袁斯華.基于Quartus II的FPGA/CPLD設(shè)計(jì)[M].北京：電子工業(yè)出版社，2006.
[5] 劉欲曉,，方強(qiáng).EDA技術(shù)與VHDL電路開(kāi)發(fā)應(yīng)用實(shí)踐[M].北京：電子工業(yè)出版社,，2009.