文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2017.04.011
中文引用格式: 張躍軍,廖澴桓,,丁代魯. 基于LUT的高速低硬件開銷SHA-3算法設計[J].電子技術(shù)應用,,2017,43(4):43-46.
英文引用格式: Zhang Yuejun,,Liao Huanhuan,,Ding Dailu. A high speed and low hardware cost SHA-3 algorithm based on LUT method[J].Application of Electronic Technique,2017,,43(4):43-46.
0 引言
集成電路和信息技術(shù)的日益發(fā)展,,支付寶、淘寶,、網(wǎng)銀以及微信等互聯(lián)網(wǎng)應用的迅速普及,,為人們?nèi)粘I睢W習和工作帶來極大便利,。大量的信息共享帶來方便的同時,,也出現(xiàn)信息泄露與被篡改的威脅,如網(wǎng)上銀行賬戶被盜,、個人隱私泄露以及棱鏡門事件等,。因此如何保證數(shù)據(jù)信息的安全在密碼學中顯得尤為突出。Hash函數(shù)又稱哈希函數(shù)或者雜湊函數(shù),,是現(xiàn)代密碼學中最基本的模塊之一,,以任意長度的消息值作為輸入,生成固定長度的輸出數(shù)據(jù)。Hash函數(shù)在數(shù)字簽名,、文件校驗,、鑒權(quán)協(xié)議以及流密鑰產(chǎn)生、偽隨機序列生成,、流密碼等方面有著廣泛的應用,。自從2004年密碼學家王小云教授宣布攻破常用的MD5雜湊算法以來,網(wǎng)絡信息安全問題進一步凸顯,。美國國家標準與技術(shù)研究所(NIST)于2007年宣布一項公開征集雜湊函數(shù)新標準(SHA-3算法)的活動,,于2012年10月2日Keccak雜湊算法憑借著其新穎的Sponge結(jié)構(gòu)迭代設計方法、較強的安全性能以及良好的實現(xiàn)方法成為新一代雜湊函數(shù)標準,。
作為當前雜湊算法標準的SHA-3算法,,與以往哈希算法相比呈現(xiàn)出良好的安全性和工作效率,但其物理實現(xiàn)還不太成熟,。首先,,算法的電路實現(xiàn)所占用的硬件資源仍相對較多;其次,,算法實現(xiàn)所能達到的處理速度雖已較快,,但實際應用空間仍有限;最后,,隨著攻擊方式的進化,,SHA-3算法被攻擊的輪數(shù)會越來越多,其安全性也可能隨之降低,。因此,,SHA-3算法本身存在一定的優(yōu)化空間。本文在研究查找表(Look-Up-Table,,LUT)方法的基礎(chǔ)上,,針對算法在實際應用中速度慢與占用資源大的問題進行改進,提出一種基于LUT的高速低硬件開銷SHA-3算法,。將其運行的中間結(jié)果先寫入RAM中,,每輪運算只需輸入地址信息就能實現(xiàn)具體邏輯運算,同時利用硬件共用的方式提高硬件利用率,。改進后的算法進一步提高SHA-3算法的適用性,,具有廣闊的應用前景。
1 SHA-3算法
2012年10月NIST宣布Keccak算法為SHA-3競選的最終獲勝者,,該算法方案的提供者主要包括Guido Bertoni,,Joan Daemen(AES加密算法的發(fā)明者之一),Michael Peeters以及Gilles Van Assche,。所提供標準的Keccak方案整體結(jié)構(gòu)采用海綿結(jié)構(gòu)(sponge construction),。海綿結(jié)構(gòu)的工作過程主要分成兩個階段:吸收階段和擠壓階段。在吸收階段,在保存內(nèi)部狀態(tài)不變的前提下將輸入信息與輸入狀態(tài)進行異或操作,,異或的結(jié)果作為吸收階段的輸入數(shù)據(jù),;在擠壓階段,根據(jù)輸出數(shù)據(jù)位寬要求,,從N輪置換運算的結(jié)果中交替取出所需數(shù)據(jù),,最后拼接成輸出數(shù)據(jù)。Keccak算法所采用的海綿結(jié)構(gòu)模型,。其中,,壓縮函數(shù)為Keccak-f[x],x是輪函數(shù)的置換寬度,,長度決定迭代函數(shù)的輪數(shù),,具體根據(jù)公式x=25×2l進行計算。即nr=12+2l,,在壓縮函數(shù)處理時,每一輪置換函數(shù)f作用在一個三維矩陣的五步迭代置換,。
1.1 SHA-3算法的三維置換矩陣
壓縮函數(shù)Keccak-f[x]的輸入數(shù)據(jù)按照坐標軸m,、n、p依次填充進5×5×64的三維比特數(shù)組a[m][n][p]中,,稱作狀態(tài)數(shù)組,。最終提交時,b=1 600,,即m=5,,n=5,p=64(l=6),,基本塊置換函數(shù)由12+2l(l=6時為24)輪迭代5個子輪,,每輪運算都各自簡單獨立。每輪迭代的輪函數(shù)由五步迭代的R運算組成,,通過對三維比特數(shù)組進行不同方向的變換達到擴散和混淆的作用,。其中,變換為非線性變換,,下文將會具體分析SHA-3算法的五步迭代函數(shù),。
1.2 SHA-3算法的五步迭代函數(shù)
目前SHA-3算法的三維矩陣主要采用l=6,即矩陣大小為5×5×64,。在m,、n軸進行模5運算,在p軸進行模64運算,。
這一變換是將每比特附近的兩列(column)比特之和迭加到該比特上(m和n的坐標都是模5的)具有良好的擴散性,。
這一變換作用于z軸上,是針對每個p方向的lane的比特循環(huán)移位。
這一變換是針對每個m-n平面的slice的比特移位,,達到長期擴散的效應,。
這是針對每個m方向的row的非線性運算,等效為5×5的S盒,。
這一變換是通過在每輪運算最后加一個輪常數(shù)RC,,逐比特進行,且每輪ir的輪常數(shù)不同,,達到破壞三維數(shù)組原有對稱性的效應,。
2 SHA-3面積優(yōu)化算法的VLSI實現(xiàn)
SHA-3算法的面積優(yōu)化的主要思路是通過使用LUT方法達到使用并行加速設計算法的效果,利用RAM寄存每次計算結(jié)果以及一些中間變量,,實現(xiàn)同時對一個分組數(shù)據(jù)進行運算處理,,從而加快SHA-3置換算法處理速度,降低算法執(zhí)行功耗,。
2.1 LUT面積優(yōu)化策略
由于在SHA-3算法中,,分組數(shù)據(jù)位寬均為64位,因而若采用并行加速的方式來設計算法,,開銷太大不能實現(xiàn)同時對一個分組數(shù)據(jù)進行運算處理,,在運算過程中只能對某一部分數(shù)據(jù)進行運算,其他數(shù)據(jù)資源處于閑置狀態(tài),,極大影響利用率和算法執(zhí)行速度,。而采用LUT方法,如圖1和圖2所示,,暫存中間數(shù)據(jù)來實現(xiàn)算法,,克服內(nèi)存開銷過大的缺點。每次將計算好的結(jié)果放在RAM中,,進行加密運算時,,直接從SRAM中取出運算結(jié)果即可。不但加快SHA-3置換算法處理速度,,而且極大降低算法設計復雜度,,進而減少實際電路資源開銷。
2.2 面積優(yōu)化算法流程
基于SHA-3標準算法和面積優(yōu)化策略,,確定SHA-3面積優(yōu)化算法的具體實現(xiàn)方案,,該算法的流程如圖3所示,該算法步驟如下:
步驟1:將算法中輸入的25位64進制數(shù)據(jù)形式的輸入數(shù)據(jù)從0地址開始存入64位64進制的RAM表中,。
步驟2:通過狀態(tài)機對輸入數(shù)據(jù)依次實現(xiàn)線性變換以及非線性變換,,每次運算的結(jié)果都存儲在RAM表中,每個狀態(tài)都會產(chǎn)生一個0~63的地址addr,、一個8位2進制的命令字command,、0~4的控制字counter_plane_to_pe和counter_sheet_to_pe,、一個0~24的輪轉(zhuǎn)數(shù)nr_round以及2個一位二進制讀寫信號enR和enW,通過地址以及讀寫信號對RAM表中對應的數(shù)據(jù)進行操作,,讀取的數(shù)據(jù)存儲在64位的二進制寄存器data_from_mem中,,要寫入RAM表中的數(shù)存儲在64位的二進制寄存器data_to_mem中。
每個狀態(tài)執(zhí)行的變換過程如圖4所示,,變換進行的運算使用了9個64位的二進制寄存器,,分別是r1_in、r1_out,、r2_in,、r2_out、r3_in,、r3_out,、rho_out、chi_out,、iota,,初值均為0x0000。變換流程圖如圖3所示,,主要分成以下兩個階段:
階段1:當enW=1時,,在執(zhí)行線性變換階段,根據(jù)command命令字各個位的值選擇data_from_mem,、r1_out、r2_out,、r3_out進行對應的與,、異或運算計算出r1_in的值,根據(jù)command命令字各個位的值選擇r1_out或r2_out賦值給r2_in,,根據(jù)command命令字各個位的值選擇r2_out或r3_out賦值給r3_in,,將r1_out、r2_out,、r3_out進行對應的與,、異或運算計算出chi_out的值;在執(zhí)行非線性變換階段,,根據(jù)counter_plane_to_pe,、counter_sheet_to_pe控制字的值將r1_out左移一定位數(shù)后賦值給rho_out,在執(zhí)行變換階段時,,根據(jù)輪轉(zhuǎn)數(shù)nr_round生成對應的輪常數(shù)iota,。
階段2:當enR=1時,根據(jù)command命令字各個位的值選擇將r1_out,、chi_out,、rho_out與iota進行異或運算后賦值給data_to_mem,。當時鐘上升沿到來時,按照五步迭代公式賦值運算,。將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算法的主要開銷在輪運算過程中,,所以處理速度的快慢由24輪運算的五步迭代所決定。因此,,考慮在硬件實現(xiàn)過程中,,在一個時鐘周期內(nèi)采用LUT的方法完成五步迭代,提高算法的效率,。同時采用硬件復用的方式,,進行面積優(yōu)化。從時間的角度,,可以提前完成各輪密匙的計算,,雜湊數(shù)據(jù)時只需要一個時鐘周期即可,所以數(shù)據(jù)計算可以盡量滿足對實時性的要求,;從硬件開銷角度看,,整套SHA-3算法采用LUT和硬件復用的方式,節(jié)省大量的存儲和邏輯運算單元,,降低系統(tǒng)功耗,。
3 實驗結(jié)果與分析
采用TSMC 65 nm CMOS工藝,實現(xiàn)基于LUT方法的SHA-3算法硬件電路,。實驗環(huán)境包括Intel Pentium(R) Dual-Core CPU 2.70 GHz,、2 G RAM計算機,DC綜合軟件,,NCverilog和Modelsim仿真軟件,。采用VHDL語言實現(xiàn)面積優(yōu)化SHA-3算法,其中表1和表2分別為部分的輸入/輸出數(shù)據(jù),,表3為DC綜合的特征總結(jié),,工作速度為150 MHz。
4 結(jié)論
本文通過對SHA-3算法的五步置換研究,,提出一種基于LUT方法的小面積算法設計方案,,并在VHDL硬件語言下實現(xiàn)。將生成數(shù)據(jù)與原有的SHA-3算法結(jié)果進行比較,,驗證其正確性,。采用利用狀態(tài)機實現(xiàn)SHA-3算法核心置換函數(shù)的輪運算,結(jié)合LUT方法處理每輪運算的數(shù)據(jù)交換和數(shù)據(jù)存儲,,對RAM表讀寫數(shù)據(jù)實現(xiàn)讀取運算與覆蓋新的運算結(jié)果,,在優(yōu)化SHA-3算法效率的同時有效降低面積開銷,。
參考文獻
[1] 王勇,蔡國永.基于隨機函數(shù)的哈希函數(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] 李倩男,,李云強,,蔣淑靜,等.Keccak類非線性變換的差分性質(zhì)[J].通信學報,,2012,,33(9):140-146.
[6] 李建瑞,汪鵬君,,張躍軍,,等.基于SHA-3算法的圖像密鑰生成方法[J].華東理工大學學報,2015,,41(5):693-697.
作者信息:
張躍軍,,廖澴桓,丁代魯
(寧波大學 電路與系統(tǒng)研究所,,浙江 寧波315211)