國(guó)家無(wú)線電監(jiān)測(cè)中心 霍 甲 劉 蓉 任培明

一、引言

哈希算法是把任意長(zhǎng)度的輸入，通過(guò)散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。不同的輸入通過(guò)散列變換成相同的輸出，并且從輸出得到的散列值是惟一的。換言之就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的算法。如果得到的散列值不同，那么散列值的原始輸入也是不相同的。利用哈希算法的良好特性，哈希算法在數(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)換部份差了一個(gè)比特的循環(huán)位移。SHA-0和SHA-1可將一個(gè)最大264比特的信息，轉(zhuǎn)換成一串160位的信息摘要。但是很快SHA-0就遭到了破解。

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

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

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

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

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

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

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

表2 吞吐量對(duì)比

四、結(jié)束語(yǔ)

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