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