張文婷,龍 敏

(長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院,長(zhǎng)沙410014)

一種交叉處理的混沌多變量Hash算法構(gòu)造

張文婷,龍 敏

(長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院,長(zhǎng)沙410014)

在現(xiàn)有的并行處理模式下,Hash函數(shù)由于明文分塊之間關(guān)聯(lián)性不大從而引起安全問(wèn)題。為此,提出一種交叉處理的多變量混沌Hash算法,算法安全性基于二次多變量多項(xiàng)式方程組求解問(wèn)題(MQ問(wèn)題)的困難性和混沌理論的復(fù)雜性。其中64個(gè)壓縮函數(shù)可并行處理數(shù)據(jù),利用多變量代數(shù)理論構(gòu)造輸出函數(shù)進(jìn)一步混亂與擴(kuò)散,根據(jù)不同的需求調(diào)整Hash值的長(zhǎng)度。對(duì)算法分別進(jìn)行存儲(chǔ)空間分析、偽造攻擊分析、差分攻擊分析及統(tǒng)計(jì)實(shí)驗(yàn)分析,結(jié)果表明,該算法彌補(bǔ)了傳統(tǒng)多變量多項(xiàng)式密碼的運(yùn)行效率不足,且可以抵抗偽造攻擊、差分攻擊和統(tǒng)計(jì)攻擊。

Hash函數(shù);MQ問(wèn)題;混沌映射;交叉處理;并行模式

1 概述

Hash函數(shù),也稱散列函數(shù)、湊雜函數(shù),用于將任意長(zhǎng)度的消息壓縮為固定長(zhǎng)度的消息摘要。Hash函數(shù)廣泛應(yīng)用于數(shù)據(jù)完整性檢測(cè)、身份認(rèn)證、數(shù)字簽名等領(lǐng)域。傳統(tǒng)的Hash函數(shù)采用Merkle-Damg?rd結(jié)構(gòu),如經(jīng)典的MD5[1]和SHA-1[2]算法。然而這類Hash函數(shù)的安全性能在文獻(xiàn)[3-4]中被證實(shí)不可靠,且串行處理的結(jié)構(gòu)導(dǎo)致效率不高,研究人員不再滿足于傳統(tǒng)Hash函數(shù)。

混沌是一種復(fù)雜的非線性動(dòng)力學(xué)系統(tǒng),它具有初值敏感性、隨機(jī)性、長(zhǎng)期不可預(yù)測(cè)性等性質(zhì),與密碼學(xué)上擴(kuò)散與混亂的要求一致,因此誕生了混沌密碼學(xué)。近年來(lái)為了提高Hash算法的運(yùn)行效率,新的混沌Hash算法越來(lái)越傾向于采用并行處理的模式。文獻(xiàn)[5]提出了一種時(shí)空混沌的可并行處理Hash函數(shù),文獻(xiàn)[6]也成功地找到了該算法的碰撞。文獻(xiàn)[7]利用分段線性函數(shù)和4維貓映射構(gòu)造了一種可并行處理Hash函數(shù),但文獻(xiàn)[8]發(fā)現(xiàn)了該算法難以抵抗偽造攻擊。盡管并行處理結(jié)構(gòu)效率很高,但這種并行處理的結(jié)構(gòu)導(dǎo)致明文的各分組之間聯(lián)系不強(qiáng),很容易遭受攻擊。

有限域上MQ問(wèn)題的求解是NP難解性問(wèn)題,利用MQ問(wèn)題構(gòu)造密碼可以抵抗量子計(jì)算機(jī)的威脅。2007年Billet等人首次將MQ問(wèn)題應(yīng)用到Hash函數(shù)中,提出了MQ-Hash[9]。然而這種基于多變量多項(xiàng)式方程組求解困難性的Hash函數(shù)存儲(chǔ)空間巨大,運(yùn)行速度緩慢,實(shí)用價(jià)值不高。而文獻(xiàn)[10-11]也指出了直接利用MQ問(wèn)題構(gòu)造的多變量Hash函數(shù)的不足。

本文基于混沌映射和多變量多項(xiàng)式方程組構(gòu)造了一種交叉結(jié)構(gòu)的Hash算法,該算法利用并行Hash算法和多變量Hash算法的優(yōu)點(diǎn),抑制了兩者分別容易遭到偽造攻擊和差分攻擊的缺陷。

2 預(yù)備知識(shí)

2.1 混沌映射

混沌是一種類似無(wú)規(guī)則、隨機(jī)的運(yùn)動(dòng),它對(duì)初值以及參數(shù)極其敏感,在長(zhǎng)期內(nèi)不可預(yù)測(cè)。這些性質(zhì)都滿足密碼學(xué)中混亂與擴(kuò)散的要求相符。本文采用Henon映射和分段線性映射來(lái)構(gòu)造Hash算法。

(1)Henon映射

其中,當(dāng)α=1.4,β=0.3時(shí)為典型Henon映射,典型Henon映射是混沌映射。Henon映射是二維混沌映射,它由xi,yi共同確定迭代方程,本文算法選擇Henon映射生成密鑰流,加大了算法的密鑰空間。

(2)分段線性映射PLCM

當(dāng)x∈[0,1],Q∈(0,0.5)時(shí),系統(tǒng)處于混沌狀態(tài)。分段線性映射的分布均勻,且輸出軌道的自相關(guān)函數(shù)是δ形的。同時(shí)它的形式簡(jiǎn)單,只有一個(gè)控制參數(shù),易于實(shí)現(xiàn)且速度上有優(yōu)勢(shì)。本算法選擇PLCM映射作為壓縮函數(shù)。

2.2 MQ問(wèn)題

給定一個(gè)有限域F=GF(q)上n個(gè)變量m個(gè)方程二次多項(xiàng)式方程組可以表示為:

其中,1≤i≤m,ai,j,k,bi,j,ci∈GF(q)。則MQ問(wèn)題為如下所述,給定方程組f=(f1,f2,…,fm),每個(gè)分量fi都是有限域GF(q)上隨機(jī)選擇的n個(gè)變量的二次方程。對(duì)于已知的y∈Fm,求解一個(gè)x∈Fn,滿足y=(f1(x),f2(x),…,fm(x)),叫做MQ問(wèn)題。

MQ問(wèn)題是NP難解性問(wèn)題[12]。本文算法用二次多變量多項(xiàng)式結(jié)構(gòu)作為輸出函數(shù),將前面并行的壓縮函數(shù)隱藏起來(lái),從而達(dá)到抵御偽造攻擊的目的。

3 Hash函數(shù)的構(gòu)造

3.1 消息填充

設(shè)明文的長(zhǎng)度為m,Hash值的長(zhǎng)度為n,明文被填充為512 bit的整數(shù)倍:在明文相應(yīng)的二進(jìn)制形式之后補(bǔ)充一個(gè)1,再補(bǔ)充若干個(gè)0。這段(100…0)2串的長(zhǎng)度為l,滿足(m+l)mod 512=512-16-64=432。然后在右邊添加16 bit的Hash值長(zhǎng)度n,最后再添加64 bit的消息明文長(zhǎng)度m,如果m＞264,則取mmod 264。

消息填充結(jié)構(gòu)如圖1所示。

圖1 消息填充結(jié)構(gòu)

3.2 算法描述

算法運(yùn)算在由不可約多項(xiàng)式y(tǒng)8+y4+y3+1定義的GF(28)上,Hash值長(zhǎng)度可取192 bit,224 bit, 256 bit,384 bit等。為描述方便,下文輸出Hash值長(zhǎng)度默認(rèn)為192 bit。

(1)填充后的明文可分成s個(gè)512 bit的消息塊M1,M2,…,Ms。對(duì)于每個(gè)消息塊Mi(i=1,2,…,s)再分為64個(gè)子塊Mi=block1,i,block2,i,…,block64,i,其中每個(gè)blockj.i為8 bit。對(duì)于所有blockj,i(j=1, 2,…,64)經(jīng)下式線性變換后映射得到PLCM映射的參數(shù)Qj,i。

(2)算法的密鑰為Henon映射的一對(duì)初值(xx,yy)。迭代Henon映射50次后選取后32對(duì)迭代值(xxη,yyη)(η=19,20,21,…,50)進(jìn)行下式變換得到PLCM映射的初值。

這 64個(gè) PLCM 映射的初值分別為key1,key2,…,key64,而系統(tǒng)參數(shù)是變化的,每輪系統(tǒng)參數(shù)取相應(yīng)的Qj,i,(j=1,2,…,64;i=1,2,…,s),共迭代2s次。因這64個(gè)PLCM是并行處理的,所以每一路的操作一樣,以PLCM1為例:PLCM1前s次迭代,參數(shù)依次為Q1,1,Q1,2,…,Q1,s;PLCM1后s次迭代,參數(shù)依次為Q1,s,Q2,s-1,…,Q1,1。這64個(gè) PLCM構(gòu)成交叉結(jié)構(gòu),即每一輪PLCMj生成的迭代值作為下一輪PLCMj+1的初值,而PLCM64的迭代值則作為下一輪PLCM1的初值。最后這64個(gè)PLCM同時(shí)得到64個(gè)終值,作為二次多變量多項(xiàng)式結(jié)構(gòu)的輸入。2s輪迭代之間的交叉結(jié)構(gòu)如圖2所示。

圖2 壓縮函數(shù)的交叉結(jié)構(gòu)

(3)64個(gè)PLCM映射的終值作為二次多變量多項(xiàng)式方程組的 64個(gè)變量x1,x2,…,x64。此時(shí)GF(28)上64個(gè)變量24個(gè)方程的二次多變量多項(xiàng)式結(jié)構(gòu)可表示為:

每個(gè)fk(k=1,2,…,24)都為如下形式:

其中,ak,p,q,bk,p,ck都是從GF(28)上隨機(jī)選擇的元素。

這個(gè)二次多變量多項(xiàng)式結(jié)構(gòu)將64個(gè)變量壓縮為24個(gè)變量,而這24個(gè)變量級(jí)聯(lián)起來(lái)得到最終192 bit的Hash值。算法的整體結(jié)構(gòu)如圖3所示。

圖3 算法整體結(jié)構(gòu)

4 性能分析與仿真結(jié)果

算法的壓縮函數(shù)可定義為C=F(P(key,M)),其中,F為多變量多項(xiàng)式方程組;P為64路混沌映射;key為密鑰;M為消息明文。設(shè)每輪函數(shù)Pi的結(jié)果為ρi=(ρ1i,ρ2i,…,ρ64i),要找到一對(duì)M≠M(fèi)′,使得C(M)=C(M′),做如下證明:設(shè)第i輪時(shí)ρi=ρi′,i-1是滿足ρi-1≠ρi-1′最大的情況,對(duì)于任意的ρi-1′計(jì)算得到ρi′=Pi(ρi-1′,Qi′),可推出Qi≠Q(mào)i′。假設(shè)第i輪后消息分組的值完全相同,則此后的迭代軌跡完全一致,在反向迭代至2s-i次時(shí),再次使用Qi′作為參數(shù)計(jì)算得到 ρ2s-i+1′=P2s-i(ρ2s-i′,Qi′),由于Qi≠Q(mào)i′,ρ2s-i=ρ2s-i′而可推出 ρ2s-i+1≠ρ2s-i+1′。 那么對(duì)于往后2s-i+1至2s輪迭代,根據(jù)混沌的性質(zhì),其軌跡仍然將會(huì)截然不同,從而導(dǎo)致F的計(jì)算結(jié)果不同,即C(M)≠C(M′),因此可以認(rèn)為算法是無(wú)碰撞的。混沌的運(yùn)動(dòng)十分復(fù)雜,對(duì)初值極其敏感,對(duì)明文任意微小的改變都會(huì)導(dǎo)致迭代值極大的變化,即使在攻擊者已知P2s的最壞情況下,求解F也是不可行的,因?yàn)镕是個(gè)NP難解性問(wèn)題,從而保證了算法的單向性。

4.1 存儲(chǔ)空間

整個(gè)算法由混沌迭代和多變量多項(xiàng)式計(jì)算2個(gè)部分組成。第一部分所需存儲(chǔ)空間主要是PLCM映射的狀態(tài)值和系統(tǒng)參數(shù),而迭代64個(gè)PLCM映射2s次需64×2s×(2×8)bit。第二部分為有限域GF(28)上的二次多變量多項(xiàng)式方程組,其所需存儲(chǔ)空間主要是有限域GF(28)的乘法表和隨機(jī)系數(shù)。GF(28)有256個(gè)元素,每個(gè)元素8 bits,則乘法表需要256×256×8 bit。多變量多項(xiàng)式方程組有nm(n+l)/2個(gè)二次項(xiàng),nm個(gè)一次項(xiàng)和m個(gè)常數(shù)項(xiàng)。表1列出不同Hash值長(zhǎng)度情況下MQ部分所占存儲(chǔ)空間。

表1 二次多變量多項(xiàng)式結(jié)構(gòu)所占存儲(chǔ)空間

混沌部分所占空間由明文大小決定,多變量多項(xiàng)式部分的存儲(chǔ)空間則是固定的。因迭代Henon映射50次產(chǎn)生的密鑰流所占空間極小,此處計(jì)算忽略。因此,算法的存儲(chǔ)空間主要由明文大小和多變量多項(xiàng)式的隨機(jī)數(shù)決定。一段大小為512sbit(s為明文分組數(shù))的明文在Hash值長(zhǎng)度為192 bit的情況下,多變量多項(xiàng)式結(jié)構(gòu)占114.27 KB混沌部分占0.25sKB,共計(jì)114.27+0.25sKB。顯然,與占用將近3.5 MB的MQ-Hash[9],本算法在存儲(chǔ)空間上具有明顯優(yōu)勢(shì)。這是因?yàn)镸Q-Hash的采用的傳統(tǒng)的串行處理結(jié)構(gòu),每個(gè)壓縮函數(shù)中都要對(duì)當(dāng)前明文分組進(jìn)行一次多變量多項(xiàng)式計(jì)算,而本文的壓縮函數(shù)為并行的混沌映射而多變量多項(xiàng)式方程組為輸出函數(shù),對(duì)于任意長(zhǎng)度的明文僅作一次多變量多項(xiàng)式計(jì)算。

4.2 抗偽造攻擊性

偽造攻擊是指給定一段消息,攻擊者不知其密鑰的情況下根據(jù)該消息的Hash值來(lái)構(gòu)造明文,從而達(dá)到攻擊的目的。文獻(xiàn)[6,8]中指出并行處理的結(jié)構(gòu)導(dǎo)致明文的各分組之間聯(lián)系不緊密,因而無(wú)法抵御偽造攻擊。因此,本算法在并行運(yùn)算前,對(duì)明文的每個(gè)分組做了如下線性變化來(lái)加強(qiáng)各分組的聯(lián)系:

該變換由3個(gè)位置因素決定:當(dāng)前消息塊的橫向坐標(biāo)i、當(dāng)前消息塊的縱向坐標(biāo)j和消息塊的總數(shù)s,增減修改明文的任何數(shù)據(jù)都會(huì)不同程度地改變i,j,s,從而改變了Qi,j的值。同時(shí)算法又引進(jìn)了交叉處理,當(dāng)前混沌映射處理后得到的迭代值在下一輪中并不由自身處理,而是送給相鄰的混沌映射處理,這樣大大加強(qiáng)了明文不同分組之間的聯(lián)系,中間值微小的變化會(huì)在最終的Hash中放大,使得明文充分混淆。此外算法在并行的壓縮函數(shù)之后,用二次多變量多項(xiàng)式結(jié)構(gòu)作為輸出函數(shù)。對(duì)于文獻(xiàn)[6,8]中提出的將上下兩行Hash值交換后進(jìn)行異或運(yùn)算而產(chǎn)生相同結(jié)果的攻擊方法,由于本算法中多變量多項(xiàng)式結(jié)構(gòu)進(jìn)一步對(duì)并行處理結(jié)構(gòu)的結(jié)果充分置亂,隱藏起壓并行處理結(jié)構(gòu)的內(nèi)部狀態(tài),從而不再可行。

4.3 抗差分攻擊性

MQ問(wèn)題是NP難解性問(wèn)題。但是解決MQ問(wèn)題的復(fù)雜度取決于方程數(shù)m,變量數(shù)n和有限域的階q?，F(xiàn)已存在有效地解決超定多變量多項(xiàng)式方程(n＜m)的方法和置換多變量多項(xiàng)式方程(n=m)的方法,因此在利用多變量多項(xiàng)式構(gòu)造密碼時(shí)通常使用不定方程(n＞m)。本算法在選擇Hash值長(zhǎng)度為192 bit,224 bit,256 bit,384 bit時(shí),多變量多項(xiàng)式結(jié)構(gòu)均可表示為F64→F24,F64→F28,F64→F32和F64→F48的不定方程形式。相比求解復(fù)雜度為O(qm)的窮舉攻擊,文獻(xiàn)[13]中提出一種復(fù)雜度大大降低的解決不定方程系統(tǒng)的算法:設(shè),當(dāng)k滿足2k2＞m-2k時(shí),該算法的復(fù)雜度為O(qm-k)。可見(jiàn)利用該算法有效求解二次多變量不定方程,對(duì)不定方程的取值要嚴(yán)格的限定,該算法僅適用于q,n,m很小的情況。按照文獻(xiàn)[13]的求解方法在不同的Hash值長(zhǎng)度情況下解決本算法MQ問(wèn)題部分的復(fù)雜度在表2列出,可見(jiàn)本文算法的二次多變量多項(xiàng)式結(jié)構(gòu)理論上不可解。

表2 二次多變量多項(xiàng)式結(jié)構(gòu)的求解復(fù)雜度

設(shè)Q為有限域F上m個(gè)方程n個(gè)變量的二次方程組為f1,f2,…,fm。對(duì)于任意給定的 δ=(δ1, δ2,…,δn)可在多項(xiàng)式時(shí)間O(mn2)內(nèi)找到一對(duì)輸入x=(x1,x2,…,xn),y=(y1,y2,…,yn)發(fā)生碰撞,其中,(x,y)=(x,x+δ)[9]。單獨(dú)使用二次多變量多項(xiàng)式來(lái)構(gòu)造密碼是不安全的,無(wú)法抵御差分攻擊。

差分攻擊的是針對(duì)分組通過(guò)分析明文對(duì)的差值對(duì)密文對(duì)的影響來(lái)恢復(fù)部分密鑰,而本文算法中明文的各分組在經(jīng)多變量多項(xiàng)式結(jié)構(gòu)處理前先經(jīng)過(guò)交叉的64組混沌映射處理,經(jīng)多輪迭代將初始值擴(kuò)散到整個(gè)相空間,這種對(duì)明文充分的置亂很難從最終的迭代值中推算原始消息。而要在本文算法的二次多變量多項(xiàng)式結(jié)構(gòu)部分發(fā)現(xiàn)碰撞,必須要求前面的壓縮函數(shù)部分可逆,而壓縮函數(shù)采用的混沌映射的性質(zhì)確保了在輸入差分經(jīng)過(guò)數(shù)次迭代已均勻分布到所有比特位,因此,在二次多變量多項(xiàng)式結(jié)構(gòu)尋找碰撞是不可行的。

4.4 統(tǒng)計(jì)分析

4.4.1 擴(kuò)散與混亂性質(zhì)測(cè)試

Shannon引入了擴(kuò)散與混亂2個(gè)概念來(lái)評(píng)估密碼系統(tǒng)的性能。對(duì)于用二進(jìn)制表示的Hash值,每1 bit只有0或者1兩種可能,因此理想的Hash值擴(kuò)散效果應(yīng)該是明文中1 bit變化會(huì)引起Hash值50%的變化。

其中,N為統(tǒng)計(jì)次數(shù);Bi為第i次測(cè)試變化的位數(shù);h為Hash值的長(zhǎng)度。

取密鑰 xx=1.17,yy=-0.28。對(duì)初始文本“Hash function is an algorithm converts variable length message to a fixed length of digest,which is called hash value.Hash function has a wide range of application in information security,such as data integrity authentication, identity authentication and digitalsignature.”進(jìn) 行1 000次測(cè)試,每次隨機(jī)改變文本中1 bit的值,并比較改變后的Hash值和原始文本的Hash值。不同Hash值長(zhǎng)度下1 000次測(cè)試相應(yīng)的平均變化比特?cái)?shù)、平均變化概率P、均方差ΔB、均方差ΔP在表3中列出。

表3 雪崩測(cè)試統(tǒng)計(jì)結(jié)果

4.4.2 Hash值分布

安全的Hash算法的一個(gè)重要要求是Hash值均勻分布。本文對(duì)以下消息進(jìn)行仿真實(shí)驗(yàn):“Hash function is an algorithm converts variable length message to a fixed length of digest,which is called hash value.Hash function has a wide range of application in information security, such as data integrity authentication,identity authentication and digital signature.”密鑰取 xx=1.17,yy=-0.28。通過(guò)仿真結(jié)果可以看到明文與Hash值的分布:圖4(a)為明文的ASCII碼值分布圖,ASCII碼值集中地分布在90～120這個(gè)范圍內(nèi);而圖4(b)為十六進(jìn)制Hash值的分布圖,Hash值分布十分分散。由此可知,本文算法得到的Hash值有良好的擴(kuò)散與混亂性能。

圖4 明文和Hash值的分布

4.4.3 敏感性分析

為測(cè)試本文算法對(duì)于明文和密鑰的敏感程度,在7種不同條件下對(duì)4.5.1中的文本進(jìn)行仿真實(shí)驗(yàn)。

文本1:原文。

文本2:將原文首字母H改為G。

文本3:將原文中as一詞改為is。

文本4:將原文末尾處句點(diǎn)改為逗號(hào)。

文本5:在原文末尾添加一位空格。

文本6:將 密 鑰yy取 值 由 -0.28改 為-0.280 000 000 000 000 1。

文本7:將 密 鑰xx取 值 由 1.17 改 為1.170 000 000 000 000 1。

仿真所得192 bit的Hash值長(zhǎng)度的十六進(jìn)制形式如下:

文本1:BAD4A890BF7240044C22B58E0A45A1C598 6D2E67E65A9939

文本2:27F08D4ECBC371221D35193A4D797391E4 CE56077B0A26D5(改變94位)

文本3:0BC2E9D74577C01E611F6480C51C63F43E CCC5DD136CFB7F(改變91位)

文本4:0F034E33295F561EF088BFF984B55ED96989 CC988750FE02(改變106位)

文本5:CEE066D48D20D8F2DA3C1924A69539735 C39FC711CA64547(改變96位)

文本6:400543850934F5EB02D3797DB6BB53CBE2 F06E62CF721A02(改變104位)

文本7:F093000A8363508DD75F621B782CEA4A6C 6D6397C30A546D(改變88位)

圖5所示為相應(yīng)的Hash值二進(jìn)制形式的圖形分布,可以看出對(duì)明文和密鑰的任何細(xì)微改變都會(huì)對(duì)Hash值產(chǎn)生巨大的影響,證明算法對(duì)明文和密鑰的敏感程度良好。

圖5 7種條件下二進(jìn)制Hash值比較

5 結(jié)束語(yǔ)

本文結(jié)合混沌理論的復(fù)雜性和MQ問(wèn)題的難解性,提出一種新的交叉迭代的Hash算法,算法占用空間小、處理速度快,另外,可根據(jù)不同需求調(diào)節(jié)Hash值長(zhǎng)度。仿真實(shí)驗(yàn)和理論分析證明本文算法滿足Hash算法的安全要求,且具有處理大容量數(shù)據(jù)的潛力。今后的工作重點(diǎn)是以該算法為基礎(chǔ)研究在云端進(jìn)行消息認(rèn)證的方法。

[1] Rivest L.The MD5 Message digest Algorithm[S]. RFC 1321,1992.

[2] NIST.FIPS PUB 180-2-1993 SecureHash Standard[Z].1993.

[3] Wang Xiaoyun,Yu Hongbo.How to Break MD5 and Other Hash Functions[C]//Proceedings of EUROCRYPT’05. Berlin,Germany:Springer-Verlag,2005:19-35.

[4] Wang Xiaoyun,Yu Hongbo.Finding Collisions in the Full SHA-1[C]//Proceedings of EUROCRYPT’05. Berlin,Germany:Springer-Verlag,2005:17-36.

[5] 趙 耿,徐 剛,閔樂(lè)泉.一種并行時(shí)空混沌單向Hash函數(shù)的構(gòu)造[J].微計(jì)算機(jī)信息,2011,27(5):232-236.

[6] 王 浩.混沌單向Hash函數(shù)的安全性分析研究[D].長(zhǎng)沙:長(zhǎng)沙理工大學(xué),2013.

[7] Xiao Di,Liao Xiaofeng,Dong Shaojiang.Parallel Keyd Hash Function Construction Based on Chaotic Maps[J]. Physic Letters A,2008,17(7):2388-2393.

[8] Xiao Di,Liao Xiaofeng,Wang Yong.Improving the Sec Urity of a Parallel Keyd Hash Function Based on Chaotic Maps[J].Physic Letters A,2009,373(36):4346-4353.

[9] Olivier B,Matt R,Homas P.On Building Hash Functions from Multivariate Quadratic Equations[C]//Proceedings of ACISP’07.Berlin,Germany:Springer-Verlag,2007: 82-95.

[10] Ding Jintai,Yang Boyin.Multivariates Polynomials for Hashing[EB/OL].(2007-10-21).http://eprint.iacr. org/2007/137.pdf.

[11] Pierre-Alain F,Louis G,Jacques S.Differential CryptanaLysis for Multivariate Schemes[C]//Proceedings of EUROCRYPT’05.Berlin,Germany:Springer-Verlag,2005: 341-353.

[12] Garey T,Johnson D.Computers and Intractability,A Guide to the Theory of NP-completeness[M].New York,USA: [s.n.],1979:128-130.

[13] Nicolas C,Louis G,Jean-Daniel T.Solving Underdefined Systems ofMultivariate Quadratic Equations[C]// Proceedings of PKC’02.Berlin,Germany:Springer-Verlag, 2002:211-227.

編輯 索書志

Chaos Multivariate Hash Algorithm Construction of Cross Processing

ZHANG Wenting,LONG Min
(College of Computer and Communication Engineering,Changsha University of Science and Technology,Changsha 410014,China)

Aiming at the defects of security in the existed parallel Hash funtions which are caused by the weak correlations between the plaintext block,a novel Hash function algorithm based on the difficulty of solving MQ problem and the complexity of chaotic theory is proposed.The algorithm works in a parallel and cross processing mode.The output function is constructed by multivariate polynomials equations to confuse the plaintext sufficiently.The output Hash size can be adjusted according to different requirements.Storage analysis,forge attack analysis,differential attack analysis and statistic analysis are carried on algorithm.Theoretical analysis and experimental results show that the parallel structure of the algorithm compensates the inefficiency of traditional multivariate polynomial cryptosystems,and it can resist forge attack,differential attack and statistic attack.

Hash function;MQ problem;chaotic mapping;cross processing;parallel mode

1000-3428(2015)01-0130-05

A

TP309

10.3969/j.issn.1000-3428.2015.01.024

國(guó)家自然科學(xué)基金資助項(xiàng)目(61001004);湖南省教育廳基金資助項(xiàng)目(11B002);湖南省海外名師基金資助項(xiàng)目(2013008);湖南省研究生科研創(chuàng)新基金資助項(xiàng)目(CX2013B376)。

張文婷(1989-),女,碩士研究生,主研方向:單向Hash函數(shù);龍 敏,教授、博士。

2014-03-03

2014-04-03 E-mail:yesterdayjuly@qq.com

中文引用格式:張文婷,龍 敏.一種交叉處理的混沌多變量Hash算法構(gòu)造[J].計(jì)算機(jī)工程,2015,41(1):130-134.

英文引用格式:Zhang Wenting,Long Min.Chaos Multivariate Hash Algorithm Construction of Cross Processing[J]. Computer Engineering,2015,41(1):130-134.