0 引言

    集成電路和信息技術(shù)的日益發(fā)展，支付寶、淘寶、網(wǎng)銀以及微信等互聯(lián)網(wǎng)應(yīng)用的迅速普及，為人們?nèi)粘Ｉ?、學(xué)習(xí)和工作帶來(lái)極大便利。大量的信息共享帶來(lái)方便的同時(shí)，也出現(xiàn)信息泄露與被篡改的威脅，如網(wǎng)上銀行賬戶(hù)被盜、個(gè)人隱私泄露以及棱鏡門(mén)事件等。因此如何保證數(shù)據(jù)信息的安全在密碼學(xué)中顯得尤為突出。Hash函數(shù)又稱(chēng)哈希函數(shù)或者雜湊函數(shù)，是現(xiàn)代密碼學(xué)中最基本的模塊之一，以任意長(zhǎng)度的消息值作為輸入，生成固定長(zhǎng)度的輸出數(shù)據(jù)。Hash函數(shù)在數(shù)字簽名、文件校驗(yàn)、鑒權(quán)協(xié)議以及流密鑰產(chǎn)生、偽隨機(jī)序列生成、流密碼等方面有著廣泛的應(yīng)用。自從2004年密碼學(xué)家王小云教授宣布攻破常用的MD5雜湊算法以來(lái)，網(wǎng)絡(luò)信息安全問(wèn)題進(jìn)一步凸顯。美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所(NIST)于2007年宣布一項(xiàng)公開(kāi)征集雜湊函數(shù)新標(biāo)準(zhǔn)(SHA-3算法)的活動(dòng)，于2012年10月2日Keccak雜湊算法憑借著其新穎的Sponge結(jié)構(gòu)迭代設(shè)計(jì)方法、較強(qiáng)的安全性能以及良好的實(shí)現(xiàn)方法成為新一代雜湊函數(shù)標(biāo)準(zhǔn)。

    作為當(dāng)前雜湊算法標(biāo)準(zhǔn)的SHA-3算法，與以往哈希算法相比呈現(xiàn)出良好的安全性和工作效率，但其物理實(shí)現(xiàn)還不太成熟。首先，算法的電路實(shí)現(xiàn)所占用的硬件資源仍相對(duì)較多；其次，算法實(shí)現(xiàn)所能達(dá)到的處理速度雖已較快，但實(shí)際應(yīng)用空間仍有限；最后，隨著攻擊方式的進(jìn)化，SHA-3算法被攻擊的輪數(shù)會(huì)越來(lái)越多，其安全性也可能隨之降低。因此，SHA-3算法本身存在一定的優(yōu)化空間。本文在研究查找表（Look-Up-Table，LUT)方法的基礎(chǔ)上，針對(duì)算法在實(shí)際應(yīng)用中速度慢與占用資源大的問(wèn)題進(jìn)行改進(jìn)，提出一種基于LUT的高速低硬件開(kāi)銷(xiāo)SHA-3算法。將其運(yùn)行的中間結(jié)果先寫(xiě)入RAM中，每輪運(yùn)算只需輸入地址信息就能實(shí)現(xiàn)具體邏輯運(yùn)算，同時(shí)利用硬件共用的方式提高硬件利用率。改進(jìn)后的算法進(jìn)一步提高SHA-3算法的適用性，具有廣闊的應(yīng)用前景。

1 SHA-3算法

    2012年10月NIST宣布Keccak算法為SHA-3競(jìng)選的最終獲勝者，該算法方案的提供者主要包括Guido Bertoni，Joan Daemen(AES加密算法的發(fā)明者之一)，Michael Peeters以及Gilles Van Assche。所提供標(biāo)準(zhǔn)的Keccak方案整體結(jié)構(gòu)采用海綿結(jié)構(gòu)(sponge construction)。海綿結(jié)構(gòu)的工作過(guò)程主要分成兩個(gè)階段：吸收階段和擠壓階段。在吸收階段，在保存內(nèi)部狀態(tài)不變的前提下將輸入信息與輸入狀態(tài)進(jìn)行異或操作，異或的結(jié)果作為吸收階段的輸入數(shù)據(jù)；在擠壓階段，根據(jù)輸出數(shù)據(jù)位寬要求，從N輪置換運(yùn)算的結(jié)果中交替取出所需數(shù)據(jù)，最后拼接成輸出數(shù)據(jù)。Keccak算法所采用的海綿結(jié)構(gòu)模型。其中，壓縮函數(shù)為Keccak-f[x]，x是輪函數(shù)的置換寬度，長(zhǎng)度決定迭代函數(shù)的輪數(shù)，具體根據(jù)公式x=25×2l進(jìn)行計(jì)算。即nr=12+2l，在壓縮函數(shù)處理時(shí)，每一輪置換函數(shù)f作用在一個(gè)三維矩陣的五步迭代置換。

1.1 SHA-3算法的三維置換矩陣

    壓縮函數(shù)Keccak-f[x]的輸入數(shù)據(jù)按照坐標(biāo)軸m、n、p依次填充進(jìn)5×5×64的三維比特?cái)?shù)組a[m][n][p]中，稱(chēng)作狀態(tài)數(shù)組。最終提交時(shí)，b=1 600，即m=5，n=5，p=64(l=6)，基本塊置換函數(shù)由12+2l(l=6時(shí)為24)輪迭代5個(gè)子輪，每輪運(yùn)算都各自簡(jiǎn)單獨(dú)立。每輪迭代的輪函數(shù)由五步迭代的R運(yùn)算組成，通過(guò)對(duì)三維比特?cái)?shù)組進(jìn)行不同方向的變換達(dá)到擴(kuò)散和混淆的作用。其中，變換為非線(xiàn)性變換，下文將會(huì)具體分析SHA-3算法的五步迭代函數(shù)。

1.2 SHA-3算法的五步迭代函數(shù)

    目前SHA-3算法的三維矩陣主要采用l=6，即矩陣大小為5×5×64。在m、n軸進(jìn)行模5運(yùn)算，在p軸進(jìn)行模64運(yùn)算。

    這一變換是將每比特附近的兩列(column)比特之和迭加到該比特上(m和n的坐標(biāo)都是模5的)具有良好的擴(kuò)散性。

    這一變換作用于z軸上，是針對(duì)每個(gè)p方向的lane的比特循環(huán)移位。

    這一變換是針對(duì)每個(gè)m-n平面的slice的比特移位，達(dá)到長(zhǎng)期擴(kuò)散的效應(yīng)。

    這是針對(duì)每個(gè)m方向的row的非線(xiàn)性運(yùn)算，等效為5×5的S盒。

    這一變換是通過(guò)在每輪運(yùn)算最后加一個(gè)輪常數(shù)RC，逐比特進(jìn)行，且每輪i_r的輪常數(shù)不同，達(dá)到破壞三維數(shù)組原有對(duì)稱(chēng)性的效應(yīng)。

2 SHA-3面積優(yōu)化算法的VLSI實(shí)現(xiàn)

    SHA-3算法的面積優(yōu)化的主要思路是通過(guò)使用LUT方法達(dá)到使用并行加速設(shè)計(jì)算法的效果，利用RAM寄存每次計(jì)算結(jié)果以及一些中間變量，實(shí)現(xiàn)同時(shí)對(duì)一個(gè)分組數(shù)據(jù)進(jìn)行運(yùn)算處理，從而加快SHA-3置換算法處理速度，降低算法執(zhí)行功耗。

2.1 LUT面積優(yōu)化策略

    由于在SHA-3算法中，分組數(shù)據(jù)位寬均為64位，因而若采用并行加速的方式來(lái)設(shè)計(jì)算法，開(kāi)銷(xiāo)太大不能實(shí)現(xiàn)同時(shí)對(duì)一個(gè)分組數(shù)據(jù)進(jìn)行運(yùn)算處理，在運(yùn)算過(guò)程中只能對(duì)某一部分?jǐn)?shù)據(jù)進(jìn)行運(yùn)算，其他數(shù)據(jù)資源處于閑置狀態(tài)，極大影響利用率和算法執(zhí)行速度。而采用LUT方法，如圖1和圖2所示，暫存中間數(shù)據(jù)來(lái)實(shí)現(xiàn)算法，克服內(nèi)存開(kāi)銷(xiāo)過(guò)大的缺點(diǎn)。每次將計(jì)算好的結(jié)果放在RAM中，進(jìn)行加密運(yùn)算時(shí)，直接從SRAM中取出運(yùn)算結(jié)果即可。不但加快SHA-3置換算法處理速度，而且極大降低算法設(shè)計(jì)復(fù)雜度，進(jìn)而減少實(shí)際電路資源開(kāi)銷(xiāo)。

2.2 面積優(yōu)化算法流程

    基于SHA-3標(biāo)準(zhǔn)算法和面積優(yōu)化策略，確定SHA-3面積優(yōu)化算法的具體實(shí)現(xiàn)方案，該算法的流程如圖3所示，該算法步驟如下：

    步驟1：將算法中輸入的25位64進(jìn)制數(shù)據(jù)形式的輸入數(shù)據(jù)從0地址開(kāi)始存入64位64進(jìn)制的RAM表中。

    步驟2：通過(guò)狀態(tài)機(jī)對(duì)輸入數(shù)據(jù)依次實(shí)現(xiàn)線(xiàn)性變換以及非線(xiàn)性變換，每次運(yùn)算的結(jié)果都存儲(chǔ)在RAM表中，每個(gè)狀態(tài)都會(huì)產(chǎn)生一個(gè)0~63的地址addr、一個(gè)8位2進(jìn)制的命令字command、0~4的控制字counter_plane_to_pe和counter_sheet_to_pe、一個(gè)0~24的輪轉(zhuǎn)數(shù)nr_round以及2個(gè)一位二進(jìn)制讀寫(xiě)信號(hào)enR和enW，通過(guò)地址以及讀寫(xiě)信號(hào)對(duì)RAM表中對(duì)應(yīng)的數(shù)據(jù)進(jìn)行操作，讀取的數(shù)據(jù)存儲(chǔ)在64位的二進(jìn)制寄存器data_from_mem中，要寫(xiě)入RAM表中的數(shù)存儲(chǔ)在64位的二進(jìn)制寄存器data_to_mem中。

    每個(gè)狀態(tài)執(zhí)行的變換過(guò)程如圖4所示，變換進(jìn)行的運(yùn)算使用了9個(gè)64位的二進(jìn)制寄存器，分別是r1_in、r1_out、r2_in、r2_out、r3_in、r3_out、rho_out、chi_out、iota，初值均為0x0000。變換流程圖如圖3所示，主要分成以下兩個(gè)階段：

    階段1：當(dāng)enW=1時(shí)，在執(zhí)行線(xiàn)性變換階段，根據(jù)command命令字各個(gè)位的值選擇data_from_mem、r1_out、r2_out、r3_out進(jìn)行對(duì)應(yīng)的與、異或運(yùn)算計(jì)算出r1_in的值，根據(jù)command命令字各個(gè)位的值選擇r1_out或r2_out賦值給r2_in，根據(jù)command命令字各個(gè)位的值選擇r2_out或r3_out賦值給r3_in，將r1_out、r2_out、r3_out進(jìn)行對(duì)應(yīng)的與、異或運(yùn)算計(jì)算出chi_out的值；在執(zhí)行非線(xiàn)性變換階段，根據(jù)counter_plane_to_pe、counter_sheet_to_pe控制字的值將r1_out左移一定位數(shù)后賦值給rho_out，在執(zhí)行變換階段時(shí)，根據(jù)輪轉(zhuǎn)數(shù)nr_round生成對(duì)應(yīng)的輪常數(shù)iota。

    階段2：當(dāng)enR=1時(shí)，根據(jù)command命令字各個(gè)位的值選擇將r1_out、chi_out、rho_out與iota進(jìn)行異或運(yùn)算后賦值給data_to_mem。當(dāng)時(shí)鐘上升沿到來(lái)時(shí)，按照五步迭代公式賦值運(yùn)算。將RAM表中地址0~24的數(shù)據(jù)輸出，得到最終SHA-3數(shù)據(jù)。

2.3 面積優(yōu)化算法的硬件結(jié)構(gòu)

    面積優(yōu)化SHA-3算法的具體結(jié)構(gòu)如圖5所示， HA-3算法的主要開(kāi)銷(xiāo)在輪運(yùn)算過(guò)程中，所以處理速度的快慢由24輪運(yùn)算的五步迭代所決定。因此，考慮在硬件實(shí)現(xiàn)過(guò)程中，在一個(gè)時(shí)鐘周期內(nèi)采用LUT的方法完成五步迭代，提高算法的效率。同時(shí)采用硬件復(fù)用的方式，進(jìn)行面積優(yōu)化。從時(shí)間的角度，可以提前完成各輪密匙的計(jì)算，雜湊數(shù)據(jù)時(shí)只需要一個(gè)時(shí)鐘周期即可，所以數(shù)據(jù)計(jì)算可以盡量滿(mǎn)足對(duì)實(shí)時(shí)性的要求；從硬件開(kāi)銷(xiāo)角度看，整套SHA-3算法采用LUT和硬件復(fù)用的方式，節(jié)省大量的存儲(chǔ)和邏輯運(yùn)算單元，降低系統(tǒng)功耗。

3 實(shí)驗(yàn)結(jié)果與分析

    采用TSMC 65 nm CMOS工藝，實(shí)現(xiàn)基于LUT方法的SHA-3算法硬件電路。實(shí)驗(yàn)環(huán)境包括Intel Pentium(R) Dual-Core CPU 2.70 GHz、2 G RAM計(jì)算機(jī)，DC綜合軟件，NCverilog和Modelsim仿真軟件。采用VHDL語(yǔ)言實(shí)現(xiàn)面積優(yōu)化SHA-3算法，其中表1和表2分別為部分的輸入/輸出數(shù)據(jù)，表3為DC綜合的特征總結(jié)，工作速度為150 MHz。

4 結(jié)論

    本文通過(guò)對(duì)SHA-3算法的五步置換研究，提出一種基于LUT方法的小面積算法設(shè)計(jì)方案，并在VHDL硬件語(yǔ)言下實(shí)現(xiàn)。將生成數(shù)據(jù)與原有的SHA-3算法結(jié)果進(jìn)行比較，驗(yàn)證其正確性。采用利用狀態(tài)機(jī)實(shí)現(xiàn)SHA-3算法核心置換函數(shù)的輪運(yùn)算，結(jié)合LUT方法處理每輪運(yùn)算的數(shù)據(jù)交換和數(shù)據(jù)存儲(chǔ)，對(duì)RAM表讀寫(xiě)數(shù)據(jù)實(shí)現(xiàn)讀取運(yùn)算與覆蓋新的運(yùn)算結(jié)果，在優(yōu)化SHA-3算法效率的同時(shí)有效降低面積開(kāi)銷(xiāo)。

參考文獻(xiàn)

[1] 王勇，蔡國(guó)永.基于隨機(jī)函數(shù)的哈希函數(shù)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015，34(10)：2679-2683.

[2] ZHANG H，HAN W，LAI X，et al.Survey on cyberspace security[J].Science China(Information Sciences)，2015，58(11)；5-47.

[3] MALIK A，AZIZ A，KUNDI D，et al.Software implementation of standard hash algorithm(SHA-3) Keccak on Intel core-i5 and cavium networks octeon plus embedded platform[C].2nd Mediterranean Conference on Embedded Computing (MECO)，2013：79-83.

[4] Hash function[OL].http：//en.wikipedia.org/wiki/Hash function.(2015.11.30).

[5] 李倩男，李云強(qiáng)，蔣淑靜，等.Keccak類(lèi)非線(xiàn)性變換的差分性質(zhì)[J].通信學(xué)報(bào)，2012，33(9)：140-146.

[6] 李建瑞，汪鵬君，張躍軍，等.基于SHA-3算法的圖像密鑰生成方法[J].華東理工大學(xué)學(xué)報(bào)，2015，41(5)：693-697.

作者信息:

張躍軍，廖澴桓，丁代魯

（寧波大學(xué) 電路與系統(tǒng)研究所，浙江 寧波315211）