新一代哈希算法

國家無線電監(jiān)測中心 霍 甲 劉 蓉 任培明

一、引言

哈希算法是把任意長度的輸入，通過散列算法，變換成固定長度的輸出，該輸出就是散列值。不同的輸入通過散列變換成相同的輸出，并且從輸出得到的散列值是惟一的。換言之就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的算法。如果得到的散列值不同，那么散列值的原始輸入也是不相同的。利用哈希算法的良好特性，哈希算法在數(shù)字認(rèn)證，數(shù)字簽名領(lǐng)域有著廣泛的應(yīng)用。

二、新一代算法的產(chǎn)生

SHA-算法是屬于哈希算法的一種，其他如 MD4，MD5，SHA-0，SHA-1，RIPENMD 等也都屬于哈希算法。

1993年第一代SHA-算法頒布，被稱為SHA-0。它在發(fā)布之后很快就被NSA撤回，并且由1995年發(fā)布的修訂版本FIPS PUB 180-1(通常稱為SHA-1)取代。SHA-1和SHA-0的算法只在壓縮算法的信息轉(zhuǎn)換部份差了一個比特的循環(huán)位移。SHA-0和SHA-1可將一個最大264比特的信息，轉(zhuǎn)換成一串160位的信息摘要。但是很快SHA-0就遭到了破解。

2001年，NIST即宣布他們將逐漸減少使用SHA-1，改以SHA-2取而代之。NIST發(fā)布了共計4款不同的SHA-算法，分別為 SHA-256/224 ，SHA-512/384。但是隨著第二代SHA-算法的應(yīng)用越來越廣泛，第二代SHA-也面臨著諸多的問題，雖然第二代SHA-算法目前沒有找到破解的可能性，但是由于MD5的成功破解，使得NIST不得不再推出一個更加安全更加效率的新算法。

美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）在2005年、2006年分別舉行了2屆密碼Hash 研討會；同時于2007年正式宣布在全球范圍內(nèi)征集新的下一代密碼Hash算法，舉行SHA-3競賽。新的Hash算法將被稱為SHA-3，并且作為新的安全Hash標(biāo)準(zhǔn)。算法提交已于2008年10月結(jié)束，NIST通過2輪的篩選選出進(jìn)入最終輪（final round）的算法。公開競賽的整個進(jìn)程仿照高級加密標(biāo)準(zhǔn)AES的征集過程。2012年10月2日，Keccak被選為NIST競賽的勝利者，成為SHA-3.。

三、新一代哈希算法SHA-3技術(shù)對比

Keccak算法是由ST微電子公司的BERTONI等和NXP半導(dǎo)體公司的PEETERS等共同設(shè)計提交的Hash算法。它基于sponge結(jié)構(gòu)，其中的壓縮算法是作用在一個三維數(shù)組上的5步置換操作。對于輸出為256位Hash算法應(yīng)用，r取1088位，c取512位，全部輸入為1600位，組成一個25×8字節(jié)的三維矩陣。Keccak算法的消息填充方式比較復(fù)雜，首先將消息填充值8位的整數(shù)倍，填充方式為最低位為1，其他位為0；然后添加上8位無符號整數(shù)d。

表1是三代SHA-算法基本參數(shù)對比，從表中我們看到，新一代SHA-算法支持更長的信息輸入長度，循環(huán)次數(shù)要少于SHA-1和SHA-2。SHA-3使用的是海綿算法，在最大的版本，算法使用的內(nèi)存狀態(tài)是使用一個5×5的二維陣列，資料型態(tài)是64位元的字節(jié)，總計1600位元。縮版的算法使用比較小的，以2為冪次的字節(jié)大小w為1位元，總計使用25位元。除了使用較小的版本來研究加密分析攻擊，比較適中的大小（例如從w=4使用100位元，到w=32使用800位元）則提供了比較實(shí)際且輕量的替代方案。

表1 三代SHA算法基本參數(shù)

對于硬件實(shí)現(xiàn)的效率問題，我們選取了在同等硬件消耗下進(jìn)行對三代算法的對比。我們基于Xilinx公司出品的Virtex-5xc5vlx220芯片，使用ISE硬件仿真工具對電路進(jìn)行FPGA硬件評估。由于不同硬件實(shí)現(xiàn)的硬件消耗不同，目前主流的有兩種方向，一種是用最少的器件完成效率最高的吞吐量，另外一種是以器件消耗為代價完成最大的吞吐量。我們這里是以硬件器件消耗大體一致的前提下，對三代SHA-算法做了對比。表2給出了在同等硬件消耗下的吞吐量對比?？梢钥吹?，新一代SHA-3算法在同等硬件消耗的前提下完成了最大的吞吐量。

表2 吞吐量對比

四、結(jié)束語

我們在比較三代SHA-算法中發(fā)現(xiàn)，SHA-3算法結(jié)構(gòu)有利用并行化設(shè)計，并且消息塊大，消息處理能力強(qiáng)，因此有著非常高的數(shù)據(jù)吞吐率。同時，SHA-3算法運(yùn)算單元僅為Xor，AND，Not運(yùn)算，邏輯單元硬件消耗不大，因此SHA-3算法在速度導(dǎo)向設(shè)計中性能更加突出。再加上SHA-3算法迭代次數(shù)都遠(yuǎn)小于SHA-1和SHA-2，因此在運(yùn)算復(fù)雜度上，SHA-3算法遠(yuǎn)小于SHA-1和SHA-2，這說明三種算法在同等硬件消耗情況下，SHA-3有著絕對的優(yōu)勢。