散列算法和Hash函數(shù)

1、散列算法和Hash 函數(shù)趙潤(rùn)曉11(華中科技大學(xué)物理學(xué)院應(yīng)用物理學(xué)1401班,武漢市中國(guó)430074摘要中本文介紹了散列算法和Hash 函數(shù)的原理、應(yīng)用,尤其是在網(wǎng)絡(luò)安全方面,著重研究了報(bào)文摘要方法、報(bào)文完整性確認(rèn)方法。關(guān)鍵詞散列算法;Hash 函數(shù);報(bào)文摘要;MD5;1數(shù)據(jù)的散列1.1報(bào)文摘要網(wǎng)絡(luò)安全是網(wǎng)絡(luò)技術(shù)重要的一環(huán),隨著網(wǎng)絡(luò)進(jìn)入人們的日常生活,一方面淘寶等網(wǎng)上購(gòu)物極大地改變了傳統(tǒng)生活,另一方面貨幣的虛擬化也讓不少犯罪分子有了可乘之機(jī)。網(wǎng)絡(luò)安全是大學(xué)網(wǎng)絡(luò)通識(shí)課的重要一章,其中現(xiàn)代密碼學(xué)的種種精妙展現(xiàn)讓不少讀者激動(dòng)萬(wàn)分,秘鑰算法、報(bào)文摘要和數(shù)字簽名既是網(wǎng)絡(luò)安全問(wèn)題下的產(chǎn)物,也體現(xiàn)了人類理性

2、的智慧1。報(bào)文摘要要求數(shù)據(jù)接受者可以較容易的核實(shí)報(bào)文是否被篡改。因此我們強(qiáng)烈要求一種映射(函數(shù)F ,對(duì)源報(bào)文M ,它應(yīng)該具有如下特質(zhì)2:1報(bào)文摘要F(M由映射和報(bào)文唯一給出,它應(yīng)到長(zhǎng)度小、能反映報(bào)文M 的全部信息。2當(dāng)M 改變時(shí),F(M也一定發(fā)生變化。3在計(jì)算上找不到以M,使得F(M=F(M.這樣一來(lái),滿足上述要求的映射F 一旦被找到,那么數(shù)據(jù)接收方拿到M 和F(M就可以輕易地知道M 是否遭到了篡改?？墒巧鲜鲆蟠嬖谝恍┮蓡?wèn),因?yàn)閳?bào)文M 長(zhǎng)度,是大大超過(guò)報(bào)文摘要的;那么根據(jù)抽屜原理,一定可以找到兩個(gè)不同的報(bào)文,使得它們各自的報(bào)文摘要相同。其二,“計(jì)算上”得不到F(M=F(M,具體含義是什么?該

3、怎么實(shí)現(xiàn)?實(shí)際使用的報(bào)文摘要算法,散列函數(shù)到底是怎么滿足上述要求的。1.2巨量數(shù)據(jù)的排序和檢索3百度公司招聘時(shí),曾有一道這樣的面試題:搜索引擎會(huì)通過(guò)日志文件把用戶每次檢索使用的所有檢索串都記錄下來(lái),每個(gè)查詢串的長(zhǎng)度為1-255字節(jié)。假設(shè)目前有一千萬(wàn)個(gè)記錄(這些查詢串的重復(fù)度比較高,雖然總數(shù)是1千萬(wàn),但如果除去重復(fù)后,不超過(guò)3百萬(wàn)個(gè)。一個(gè)查詢串的重復(fù)度越高,說(shuō)明查詢它的用戶越多,也就是越熱門(mén)。,請(qǐng)你統(tǒng)計(jì)最熱門(mén)的10個(gè)查詢串,要求使用的內(nèi)存不能超過(guò)1G 。當(dāng)我們使用傳統(tǒng)的排序時(shí),會(huì)發(fā)現(xiàn)要經(jīng)行如此巨量的數(shù)據(jù)處理,占用內(nèi)存會(huì)達(dá)到2.8G 。如果可以運(yùn)用某種關(guān)鍵詞,將查詢串映射為關(guān)鍵詞,那么資源的利用率

4、就會(huì)大大增加。在最佳解答中,程序建立了一個(gè)哈希表,這是一個(gè)根據(jù)關(guān)鍵碼值(Key value而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。數(shù)組的特點(diǎn)是尋址容易,插入和刪除困難;而鏈表的特點(diǎn)是:尋址困難,插入和刪除容易。而哈希表綜合兩者的特性,做出了一種尋址容易,插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)。這是怎么做到的呢?1.3散列函數(shù)事實(shí)上以上兩個(gè)應(yīng)用都運(yùn)用了數(shù)據(jù)的散列,這是通過(guò)散列算法實(shí)現(xiàn)的4。簡(jiǎn)單的散列算法很容易理解,例如:有5個(gè)數(shù)12,25,30,45,50,這幾個(gè)數(shù)有個(gè)規(guī)律,就是十位數(shù)都不相同。如果我設(shè)置一個(gè)散列函數(shù)f (value =value/10;這樣一來(lái)平常的時(shí)候,我們查找50,要比較5次(其他算法可能不同,這里用

5、散列算法只需要1次,就是解散列函數(shù),key=50/10=5,要找的數(shù)就在第5個(gè)位子。但是上面散列的問(wèn)題還是很多的,比如說(shuō)查找55呢?就會(huì)出錯(cuò)“因?yàn)?5解散列函數(shù)之后,也是在第5個(gè)位子”,這就叫做一個(gè)沖突。當(dāng)你把散列函除法散列法 圖1余數(shù)法散列圖1是以除16的余數(shù)當(dāng)作關(guān)鍵詞所做的散列,可以看到有些關(guān)鍵詞沒(méi)有放入數(shù)據(jù),而有的關(guān)鍵詞又集中了多個(gè)數(shù)據(jù),說(shuō)明除法散列法“散列能力”不強(qiáng)。讓數(shù)據(jù)先乘上一個(gè)與之?dāng)?shù)位相對(duì)應(yīng)的斐波那契數(shù),在進(jìn)行散列,那么結(jié)果會(huì)好一些。如圖2所示。 圖2斐波那契散列以上的散列法都很容易構(gòu)造沖突,也就是說(shuō),很容易找到一對(duì)數(shù),他們的散列是相同的。而平方取值散列,找到的難度就提升了。我們

6、對(duì)于一個(gè)五位數(shù),取其平方后的第4、5、6位的值,例如594262=3531449476,取144作為特征值或者摘要。這是因?yàn)槠椒胶蟮臄?shù),中間幾位的數(shù)值和源數(shù)字的每一位都相關(guān),所以當(dāng)源數(shù)據(jù)有改動(dòng)時(shí),特征值總會(huì)變化。那59426為例。每一數(shù)位變化1后的特征值如圖表1,可以發(fā)現(xiàn)任何一個(gè)微小的變化都對(duì)摘要產(chǎn)生了極大的變化。這就得“計(jì)算上不可行”成為可行。4819969476996圖表1微小的改變和極大地變化2Hash 函數(shù)2.1函數(shù)的特點(diǎn)Hash 函數(shù)是一類比較成熟的散列函數(shù),例如MD5。Hash 函數(shù)主要用于完整性校驗(yàn)和提高數(shù)字簽名的有效性,目前已有很多方案。這些算法都是偽隨機(jī)函數(shù),任何雜湊值都是等

7、可能的。輸出并不以可辨別的方式依賴于輸入;在任何輸入串中單個(gè)比特的變化,將會(huì)導(dǎo)致輸出比特串中大約一半的比特發(fā)生變化。在實(shí)際運(yùn)用中,H 函數(shù)滿足一下特點(diǎn)5:l 廣適性。H 能夠應(yīng)用到大小不一的數(shù)據(jù)上。2規(guī)范性。H 能夠生成大小固定的輸出。3可操作性。對(duì)于任意給定的x ,H (x 的計(jì)算相對(duì)簡(jiǎn)單。4單向性。對(duì)于任意給定的代碼h ,要發(fā)現(xiàn)滿足H (x =h 的x 在計(jì)算上是不可行的。5抗撞擊性。對(duì)于任意給定的塊x ,要發(fā)現(xiàn)滿足H (y =H (x 而y=x 在計(jì)算上是不可行的。一旦這樣的Hash 被找到,那么網(wǎng)絡(luò)安全中的完整性認(rèn)證就不再是問(wèn)題。2.2MD5下面介紹一種非常著名應(yīng)用廣泛的Hash 函數(shù)

8、。Message Digest Algorithm MD56(消息摘要算法第五版為計(jì)算機(jī)安全領(lǐng)域廣泛使用的一種散列函數(shù),用以提供消息的完整性保護(hù),是計(jì)算機(jī)廣泛使用的雜湊算法之一,主流編程語(yǔ)言普遍已有MD5實(shí)現(xiàn)。將數(shù)據(jù)(如漢字運(yùn)算為另一固定長(zhǎng)度值,是雜湊算法的基礎(chǔ)原理,MD5的前身有MD2、MD3和MD4。MD5算法具有以下特點(diǎn):1壓縮性:任意長(zhǎng)度的數(shù)據(jù),算出的MD5值長(zhǎng)度都是固定的。2容易計(jì)算:從原數(shù)據(jù)計(jì)算出MD5值很容易。3抗修改性:對(duì)原數(shù)據(jù)進(jìn)行任何改動(dòng),哪怕只修改1個(gè)字節(jié),所得到的MD5值都有很大區(qū)別。4強(qiáng)抗碰撞:已知原數(shù)據(jù)和其MD5值,想找到一個(gè)具有相同MD5值的數(shù)據(jù)(即偽造數(shù)據(jù)是非常困

9、難的。MD5可以讓大容量信息在用數(shù)字簽名軟件簽署私人密鑰前被"壓縮"成一種保密的格式(就是把一個(gè)任意長(zhǎng)度的字節(jié)串變換成一定長(zhǎng)的十六進(jìn)制數(shù)字串。除了MD5以外,其中比較有名的還有sha-1、RIPEMD以及Haval等。2.3主流散列算法“破譯”成功7MD5、SHA-1是當(dāng)前國(guó)際通行的兩大密碼標(biāo)準(zhǔn)。據(jù)了解,MD5由國(guó)際著名密碼學(xué)家圖靈獎(jiǎng)獲得者兼公鑰加密算法RSA的創(chuàng)始人Ronald L.Rivest 設(shè)計(jì),SHA-1是由美國(guó)專門(mén)制定密碼算法的標(biāo)準(zhǔn)機(jī)構(gòu)美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院(NIST與美國(guó)國(guó)家安全局(NSA設(shè)計(jì)。兩大算法是國(guó)際電子簽名及許多其它密碼應(yīng)用領(lǐng)域的關(guān)鍵技術(shù),廣泛應(yīng)用于

10、金融、證券等電子商務(wù)領(lǐng)域。其中,SHA-1早在1994年便為美國(guó)政府采納,是美國(guó)政府廣泛應(yīng)用的計(jì)算機(jī)密碼系統(tǒng)。但是這兩項(xiàng)散列技術(shù)被中國(guó)科學(xué)家王小云相繼“破譯”。2004年8月,在美國(guó)加州圣芭芭拉召開(kāi)的國(guó)際密碼大會(huì)上,并沒(méi)有被安排發(fā)言的王小云教授拿著自己的研究成果找到會(huì)議主席,要求進(jìn)行大會(huì)發(fā)言。就這樣,王小云在國(guó)際會(huì)議上首次宣布了她及她的研究小組的研究成果對(duì)MD5、HAV AL-128、MD4和RIPEMD等四個(gè)著名密碼算法的破譯結(jié)果。王小云的研究成果作為密碼學(xué)領(lǐng)域的重大發(fā)現(xiàn)宣告了固若金湯的世界通行密碼標(biāo)準(zhǔn)MD5大廈轟然倒塌,引發(fā)了密碼學(xué)界的軒然大波。這次會(huì)議的總結(jié)報(bào)告這樣寫(xiě)道:“我們?cè)撛趺崔k?

11、 MD5被重創(chuàng)了,它即將從應(yīng)用中淘汰。SHA-1仍然活著,但也見(jiàn)到了它的末日。現(xiàn)在就得開(kāi)始更換SHA-1了。”2005年2月7日,美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院發(fā)表申明,SHA-1沒(méi)有被攻破,并且沒(méi)有足夠的理由懷疑它會(huì)很快被攻破,開(kāi)發(fā)人員在2010年前應(yīng)該轉(zhuǎn)向更為安全的SHA-256和SHA-512算法。而僅僅在一周之后,王小云就宣布了破譯SHA-1的消息。因?yàn)镾HA-1在美國(guó)等國(guó)家有更加廣泛的應(yīng)用,密碼被破的消息一出,在國(guó)際社會(huì)的反響可謂石破天驚。換句話說(shuō),王小云的研究成果表明了從理論上講電子簽名可以偽造,必須及時(shí)添加限制條件,或者重新選用更為安全的密碼標(biāo)準(zhǔn),以保證電子商務(wù)的安全。國(guó)際密碼學(xué)家Len

12、stra利用王小云提供的MD5碰撞,偽造了符合X.509標(biāo)準(zhǔn)的數(shù)字證書(shū),這就說(shuō)明了MD5的破譯已經(jīng)不僅僅是理論破譯結(jié)果,而是可以導(dǎo)致實(shí)際的攻擊,MD5的撤出迫在眉睫。王小云說(shuō),SHA-1在理論上已經(jīng)被破譯,離實(shí)際應(yīng)用也為期不遠(yuǎn)。3展望隨著主流Hash函數(shù)的“破譯”成功,報(bào)文完整性確認(rèn)的研究似乎陷入了瓶頸,我認(rèn)為這其中有兩個(gè)出路。一是改進(jìn)散列算法,加強(qiáng)抗沖擊性,比如說(shuō)將多個(gè)Hash函數(shù)的優(yōu)點(diǎn)集中;二是放棄散列算法,轉(zhuǎn)而開(kāi)發(fā)更先進(jìn)的完整性確認(rèn)方法。致謝感謝李老師的課程,把我?guī)肓擞?jì)算機(jī)網(wǎng)絡(luò)的世界。參考文獻(xiàn)1Hu Bing,Jiang Min,Wu Xia.Basic introduction ab

13、out NetworkTechnology for college students.Publishing House of Electronics Industry,2013,9(in China(胡兵,江敏,吳霞.大學(xué)網(wǎng)絡(luò)技術(shù)基礎(chǔ)教程,2013Approach(4th Edition.China Machine Press,2009.3Ma Rulin,Jiang Hua,Zhang Qinghua,An Improving Approach forHash-Table Fast Search.Computer Engineering and Science.2008,30(9:66-684Luo Jianfeng.Hash-Table and Comparison of General SearchMechanism and Collision Solution.Shiyan Vocational Institute of Technology Journal.2007,20(5:96-98Approach(4th Edition.China Machine Press,2009.6R Rive