[摘 要] 本文提出了一種基于位運(yùn)算乘法、加法運(yùn)算的Hash函數(shù)構(gòu)造，Hash函數(shù)通過(guò)更短的哈希值比用原始值進(jìn)行數(shù)據(jù)庫(kù)搜索更快，這種方法一般用來(lái)在數(shù)據(jù)庫(kù)中建立索引并進(jìn)行搜索，同時(shí)還用在各種加、解密算法中。Hash函數(shù)執(zhí)行速度較快，可抗生日攻擊，具有較好的雪崩效應(yīng)。可用于信息安全完整性檢驗(yàn)，檢驗(yàn)信息是否被非法更改。

[關(guān)鍵詞] Hash函數(shù) 位運(yùn)算 文本摘要 抗攻擊性

一、問題的提出

隨著Internet的普及和發(fā)展，電子商務(wù)也越來(lái)越被更多的人接受和使用，網(wǎng)絡(luò)中成千上萬(wàn)種商品，如何對(duì)商品進(jìn)行分類，如何保證商品的安全性和有效性，以及在最短的時(shí)間內(nèi)檢索出有用信息，已成為人們關(guān)注的焦點(diǎn)。網(wǎng)絡(luò)信息出于安全性考慮，常需要對(duì)網(wǎng)絡(luò)中產(chǎn)品的有效性和合法性進(jìn)行鑒別，以防止對(duì)產(chǎn)品信息的攻擊（偽造、篡改、刪除等），以公鑰密碼術(shù)、數(shù)字簽名等為代表的加密安全技術(shù)已成為研究的熱點(diǎn)。

Hash函數(shù)是將產(chǎn)品信息轉(zhuǎn)化為較短的、固定長(zhǎng)度的文字摘要的常用技術(shù)，傳統(tǒng)的哈希方法有MD2、MD5、SHA等標(biāo)準(zhǔn)，它們多是采用基于異或等邏輯運(yùn)算的方法或是用DES等分組加密方法多次迭代得到Hash結(jié)果，前者由于主要使用異或運(yùn)算，雖然每步運(yùn)算簡(jiǎn)單，但計(jì)算輪數(shù)即使在被處理的文本很短的情況下也很大；后種方法運(yùn)算量很大，難以快速得到可靠的加密結(jié)果。

針對(duì)以上問題，本文提出了一種基于位運(yùn)算乘法、加法運(yùn)算的Hash函數(shù)構(gòu)造，其表達(dá)簡(jiǎn)單，并能很好地達(dá)到Hash函數(shù)的各項(xiàng)性能，且很容易用軟硬件實(shí)現(xiàn)。該算法執(zhí)行速度較快，可抗生日攻擊，具有較好的雪崩效應(yīng)?？捎糜谛畔踩暾詸z驗(yàn)，檢驗(yàn)信息是否被非法更改。

二、Hash函數(shù)構(gòu)造

因特網(wǎng)中信息的保密、完整以及身份的驗(yàn)證成為數(shù)據(jù)安全的三大問題。其中信息完整檢驗(yàn)的核心技術(shù)是Hash函數(shù)，Hash函數(shù)是一種把任意長(zhǎng)度的輸入變換成固定輸出的一種壓縮映射算法。

位運(yùn)算是指對(duì)數(shù)據(jù)進(jìn)行二進(jìn)制位的運(yùn)算。為了保證構(gòu)造的Hash函數(shù)的安全性，對(duì)Hash函數(shù)的二進(jìn)制位數(shù)要求越來(lái)越高。

設(shè)Hash函數(shù)的二進(jìn)制位數(shù)為M，設(shè)介紹商品信息的文本（下簡(jiǎn)稱文本）對(duì)應(yīng)的二進(jìn)制串?dāng)?shù)為N，將其平分為t組，每組有k位二進(jìn)制數(shù)，最后一個(gè)不足k位時(shí)用前置0補(bǔ)齊，k值的大小由構(gòu)造的Hash函數(shù)二進(jìn)制位數(shù)決定。得到的分組記為n1，n2，…，nt，按順序s個(gè)相乘，再相加，s值的大小由構(gòu)造的Hash函數(shù)二進(jìn)制位數(shù)決定，但在具體設(shè)置k、s值時(shí)最好不要相差太大，例k=13，s=14。

令：A=n1·n2·…·ns+ n2·n3·…·ns+1+ nt·nt+1·…·ns-1，若A超過(guò)需要的位數(shù)M，則截取，若不足需要的位數(shù)，則用前置0補(bǔ)齊，記為n，已知N，求n時(shí)容易的，可定義Hash函數(shù)為：

Hash(N)=n。

三、構(gòu)造的Hash函數(shù)的性質(zhì)

設(shè)文本為N，長(zhǎng)度為L(zhǎng)，基于實(shí)際問題的考慮并不失一般性，設(shè)文本長(zhǎng)度L不小于1kb。

實(shí)現(xiàn)性：實(shí)際應(yīng)用中對(duì)Hash函數(shù)的一個(gè)非常重要的要求是簡(jiǎn)單易實(shí)現(xiàn)，該方法構(gòu)造的Hash函數(shù)只用到二進(jìn)制乘法和加法運(yùn)算，利用一般的程序設(shè)計(jì)語(yǔ)言即可簡(jiǎn)單實(shí)現(xiàn)，并適用于軟件和硬件實(shí)現(xiàn)。

應(yīng)用的廣泛性：從上面構(gòu)造Hash函數(shù)的過(guò)程看，這樣的Hash函數(shù)能應(yīng)用于任何大小的文本。

定長(zhǎng)輸出：將文本集合中的任意長(zhǎng)度的文本N映射為長(zhǎng)度為n的文本摘要，不論N是多少位的文本，由構(gòu)造的算法可知，一定可以取得需要的位數(shù)為M位的文本摘要，所以可以產(chǎn)生定長(zhǎng)輸出。

敏感性：敏感性要求對(duì)輸入信息某一位的變化，應(yīng)引起文本摘要平均一半的變化，經(jīng)過(guò)大量的實(shí)驗(yàn)證明，該方法構(gòu)造的Hash函數(shù)，文本中一位的改變能引起平均一半的輸出位的變化。

安全性：在很廣泛的條件下，本方法產(chǎn)生的Hash地址分布是均勻的，算法保證了帶密鑰的Hash函數(shù)的安全性完全由密鑰的安全性決定，滿足對(duì)帶密鑰的Hash函數(shù)的安全性要求。敏感性決定了帶密鑰的Hash函數(shù)的安全性要求。

單向性：?jiǎn)蜗蛐允侵附o定一個(gè)散列值，通過(guò)計(jì)算找到某個(gè)文本，使該文本的摘要等于給定的摘要在計(jì)算上是不可行的。因?yàn)闃?gòu)造的摘要涉及到整個(gè)文本，與形成摘要的文本相同位數(shù)的文本有2L個(gè)，由構(gòu)造方法可知，已知n，求得n1，n2，…，nt，在計(jì)算上是不可行的，即已知n求N在計(jì)算上是不可行的。

弱對(duì)抗性：弱對(duì)抗性是指給定x和Hash(x)，確定y使得Hash(x)= Hash(y)在計(jì)算上不可行，由摘要的構(gòu)造方法，給定x和Hash(x)，確定使得Hash(x)= Hash(y)的y，最簡(jiǎn)單的是尋找與x相同位數(shù)的y，但由敏感性可知這是不可行的。

強(qiáng)對(duì)抗性：強(qiáng)對(duì)抗性是指找不到任何兩個(gè)文本x和y，使得Hash(x)= Hash(y)。首先尋找具有相同位數(shù)的x和y，滿足Hash(x)= Hash(y)，由敏感性可知這是不可行的。尋找不同位數(shù)的x和y，滿足Hash(x)= Hash(y)，因?yàn)闄z驗(yàn)時(shí)文本與文本摘要一起使用，沒有實(shí)際意義。

抗沖突性：由構(gòu)造的Hash函數(shù)滿足獨(dú)立性可知，也就是說(shuō)文本鑒別碼的值n對(duì)文本N高度敏感，所以找到兩個(gè)相同位數(shù)文本x和y，使得Hash(x)= Hash(y)間的差很小，在計(jì)算上是不可能的。而兩個(gè)不同位數(shù)的文本x和y，使得Hash(x)= Hash(y) 間的差很小，沒有實(shí)際意義。

四、抗攻擊性分析

抵抗生日攻擊的能力：生日問題的標(biāo)準(zhǔn)近似值是，給定x個(gè)可能中的k個(gè)截然不同的隨機(jī)數(shù)，發(fā)生沖突的可能性是，一個(gè)x位的散列函數(shù)有x/2位的安全性，所以構(gòu)造的Hash函數(shù)的抗生日攻擊的能力取決于Hash函數(shù)的二進(jìn)制位數(shù)M，但M值可以由實(shí)際決定，取較大的值。

抵抗字典攻擊的能力：字典攻擊的原理是對(duì)每一個(gè)可能的輸入，預(yù)先求出它們對(duì)應(yīng)的文本鑒別碼，即n，當(dāng)攻擊者看到某個(gè)文本鑒別碼時(shí)，只要查看所編輯的散列字典，便可知輸入值N。由構(gòu)造的Hash函數(shù)可知，與N相同位數(shù)的不同文本有2L個(gè)，而由假設(shè)L>1kb，即2L>21024，如果再考慮與N不同位數(shù)的不同文本，則需要編輯的散列字典在計(jì)算上不可能，所以能很好抵御字典攻擊。

抵抗統(tǒng)計(jì)攻擊：對(duì)任意的二元序列的文本N，不失一般性可以認(rèn)為0與1的分布是均勻的，故對(duì)全體文本集合，Hash地址Hash(N)具有均勻分布，這可以有效地抵抗統(tǒng)計(jì)攻擊。

五、結(jié)論

由Hash函數(shù)的構(gòu)造、性質(zhì)、抗攻擊性分析，可以看出，本文構(gòu)造的Hash函數(shù)具有較好的性質(zhì)。由于通過(guò)更短的哈希值比用原始值進(jìn)行數(shù)據(jù)庫(kù)搜索更快，這種方法一般用來(lái)在數(shù)據(jù)庫(kù)中建立索引并進(jìn)行搜索，同時(shí)還用在各種加解密算法中。

參考文獻(xiàn)：

[1]葛 輝:一種256位hash函數(shù)算法.《大眾科技》，2005年05期

[2]陳華等:密碼算法的安全性檢測(cè)及關(guān)鍵組件的設(shè)計(jì) 中國(guó)科學(xué)院研究生院，2005年

[3]徐吉斌等:一種基于HASH函數(shù)的密鑰管理方案.安徽師范大學(xué)學(xué)報(bào)(自然科學(xué)版) ，2006年04期

[4]黎耀等 基于Hash函數(shù)改進(jìn)遺傳算法的IPv6下模糊異常檢測(cè)模型.武漢大學(xué)學(xué)報(bào)(理學(xué)版) ，2006年05期

[5]石少儉等:一種基于二進(jìn)制運(yùn)算的HASH函數(shù)構(gòu)造.山東省計(jì)算機(jī)學(xué)會(huì)2005年信息技術(shù)與信息化研討會(huì)論文集（二），2005年

[6]陳軍:基于RBF神經(jīng)網(wǎng)絡(luò)和混沌映射的Hash函數(shù)構(gòu)造.計(jì)算機(jī)科學(xué)，2006.8