基于分段Logistic映射的并行Hash函數構造算法

王 永，陳 燕，趙 毅

1.重慶郵電大學 計算機科學與技術學院，重慶 400065

2.重慶郵電大學 電子商務與現代物流重點實驗室，重慶 400065

1 引言

Hash函數是信息安全領域中一種被廣泛應用的基本技術。Hash函數以不同長度的消息作為輸入，并產生固定長度Hash值，將其作為信息的摘要（或信息的指紋）。近年來，對常用的Hash函數如MD5[1]、SHA-1[2]等的攻擊取得了突破性的進展。這也使得新的Hash函數的構造研究成為了當前的一個研究熱點。混沌由于天然具有初值敏感性、偽隨機性、難以預測等特性，受到研究者的青睞。當前，混沌成為構造密碼算法的一種新的技術手段，被逐步廣泛地應用于信息安全領域[3]。Liu等人利用具有魯棒性的混沌映射構造了“一次一密”加密系統[4]，在圖像加密中表現出良好的性能。將混沌映射與圖像的位排列，以及與DNA編碼結合，在圖像加密中表現出很好的應用潛力[5-6]。此外，Wang等人將數學模型與混沌映射結合提出了新型的加密方法，展現出良好的加密特性[7]。基于混沌設計Hash函數是混沌密碼中的一個研究分支。混沌Hash函數主要利用混沌迭代的不可逆性和初值敏感性來產生Hash值。與加密算法不同的是，Hash函數是利用簽名來保證明文信息的完整性，更強調在將明文信息融入混沌迭代后，混沌軌道在相空間的均勻性。因此對混沌映射自身的特性的依賴性更好。文獻[8-9]基于串行設計分別提出了時空混沌雙擾動單向Hash函數和基于變參數循環移位的Hash函數，但是串行模式處理方式不能充分發揮多核CPU的并行處理優勢。為此，研究者們提出了一些基于混沌系統的并行Hash函數設計方法[10-13]。從提高運行效率的角度出發，希望混沌映射的變換式相對簡單，如文獻[10]和[11]分別基于分段線性映射和Chebyshev映射，提出了并行Hash函數的構造算法。從提高算法安全性的角度出發，希望混沌映射的變化式相對復雜，從而保持混沌序列的高復雜性。文獻[12]和[13]正是基于這樣的思想分別基于洗牌交換網和動態混沌映射給出了相應的并行Hash函數構造算法。因此，怎樣在混沌系統的復雜性和高效性之間找到合適的契合點，成為基于混沌系統設計Hash函數的一個重要研究點。此外，已有的研究表明，在并行處理消息的過程中，如果對消息的合并處理不當，構造出的Hash函數容易產生安全性漏洞。Guo等人[14]采用偽造攻擊的方法，成功構建了文獻[15]中的碰撞對。因此，如何防止偽造攻擊成為了并行Hash函數設計中另外一個值得關注的問題。

針對上述問題，本文從兼顧效率與安全的角度出發，選取分段Logistic映射作為構造Hash函數的基礎混沌映射。基于該映射提出了一種并行的混沌Hash函數構造算法。在該算法中，初始階段利用混沌映射的迭代擴散明文消息塊之間的相互影響，從而有效地防止了偽造攻擊，保證了算法的安全性，為新型Hash函數的構造提供了參考。

2 分段Logistic映射

Logistic映射是在混沌密碼算法設計中常用的一種混沌系統，具有結構簡單運行效率高的特點，其表達式如下：

其中xj∈（0，1）為狀態值，μ為控制參數。當前已有一些針對Logistic映射弱點的密碼分析方法被提出[16]，因此提升Logistic映射的密碼學特性變得非常有必要。

對Logistic映射進行分段處理后，可以得到分段Logistic映射（PLM）如下[17]：

式中N為分段數量，當控制參數μ∈（2，4]時該映射具有很好的混沌特性。與Logistic映射相比，PLM具有更好的密碼學性質，如更大的Lyapunov指數，更好的遍歷性。已有研究表明，PLM隨著N的增大其Lyapunov指數也不斷增大。此外，PLM同樣具備一維混沌映射的高效性。這些特性使得PLM非常適合應用于混沌Hash算法的設計。

3 混沌Hash函數的構造

本文提出的基于混沌的并行Hash函數構造過程分三個部分：明文預處理、消息塊處理、產生Hash值。明文預處理是將消息值經迭代后再分塊以增強消息塊間的擴散效果。消息塊處理是對分塊后的消息做并行處理，生成相應消息塊的中間Hash值。產生Hash值是將每個消息塊的中間Hash值經異或操作后獲得最終Hash值。

3.1 明文預處理

（1）劃分明文消息與補齊。設原始明文M的字節數為L，將M分割成128 Byte的消息塊G1,G2,…,GR。若L不是128的整數倍，則對最后一個塊進行填充。填充規則為：GR=*…*00…0length(M)，length(M)=Lmod255。將消息塊依次存儲在數組P中，每個元素P[i](i=1，2，…，128R）的長度為8 bit。如式（3）所示：

（2）增加明文字節間的關聯。設置PLM中的N=64，x0=0.123 456 789，μ=4，將PLM迭代n0次以消除初始值的影響。然后，繼續迭代產生狀態值xs，將xs按式（4）轉換為一個8 bit的整數 ks，并根據式（5）替換數組P中的每個元素值。

其中i=1,2,…,128R；s=1,2,…,128R。 P[i]是當前處理的明文值，P′[i]是P[i]替換后的值，且設置P′[0]=P[128R]。

（3）調整每個塊中的首元素的值。將數組P′中的最后一個元素P′[128R]作為反饋值與每個消息塊Gm（m=1，2，…，R）中的第一個元素 P′[128(m-1)+1]進行異或運算，如表達式（6）所示：

（4）迭代產生并行處理的初始參數。將首元素值調整后的消息塊記為G′m，繼續迭代PLM映射，迭代m次產生序列{gm}，分別將gm作為處理第m個消息塊G′m(m=1,2,…,R)的初始參數。

3.2 消息塊處理

預處理后的各明文消息塊采用并行模式進行處理。對任一消息塊G′m(m=1,2,…,R)，其處理流程圖如圖1所示。選取消息塊G′m作為輸入值，參數gm為初始參數，通過二輪迭代PLM映射，產生nbit的中間結果。參數qj∈（0，1），用于改變控制參數μ的值。yj表示一個二進制數，取值0或1。由序列{yj}構成的nbit值即為消息塊G′m的中間結果。處理消息塊的具體過程如下所示：

Let x0=gm,l=128,n=128

For j=1 to n

qj=P′[(m-1)l+j]255

μ=qj+xj-1+2

xj=PLM((qj+xj-1)2)

End

For j=n+1 to 2n

qj=P′[(m-1)l+2n-j+1]255

μ=qj+xj-1+2

xj=PLM((qj+xj-1)2)

If xj＞0&&xj＜=0.5

then yi=0

End If

If xj＞0.5&&xj＜=1

Then yi=1

End If

End

Return the middle hash value

H(m)=yn+1,yn+2,…,y2n

3.3 產生Hash值

消息塊G′m經并行化處理后的輸出值為H(m)，m=1,2,…,R。通過異或運算將所有消息塊的輸出合并到一起，即得到最后的Hash值H ，如式（7）所示：

圖1 消息塊處理流程圖

4 混沌Hash函數的性能分析

4.1 Hash值分布

對一個安全可靠的Hash算法而言，由該算法產生的Hash值是均勻分布的。本文隨意選取一段消息“Hash function is one of the major tools in cryptography，which is usually used for integrity protection in conjunction with message authentication and digital signature schemes.Chaotic dynamical systems possess the following main characteristics：sensitivity to tiny changes in initial conditions，unstable periodic orbits，desired diffusion and confusion properties，and oneway property.Due to these properties，chaotic systems have become a very good candidate for use in the field of cryptography.”統計該消息中ASCII碼值的分布情況，以及由本文Hash算法所產生的Hash值（十六進制數）的分布情況，分別如圖2和圖3所示。

圖2 明文消息ASCII碼值分布圖

從圖中可以看出，明文消息的ASCII碼值大多集中分布在100到130之間，其對應的十六進制的Hash值均勻地分布在整個區域，表明Hash值未暴露出任何與明文消息相關的統計信息。

圖3 十六進制Hash值分布圖

4.2 敏感性分析

Hash算法應滿足對明文消息的敏感依賴性，即明文信息發生微小變化，其對應的Hash值均能產生類似雪崩效應的輸出結果。在本文的算法中，與敏感性相關的操作主要有兩個方面：其一是在明文預處理中，利用PLM映射的迭代來增強字節之間的關聯，再通過調整每個塊中首元素的值，保證對明文任何位置的改變，都能傳遞到所有的塊中；其二是在消息塊處理部分，通過PLM狀態值與消息塊值之間的融合和迭代，來強化擴散的效果。由于PLM映射為混沌系統，天然具有初值的敏感依賴性，且通過分段處理增大了映射的Lyapunov指數，擴散性得到了增強。故本文算法能更好地保證Hash值對明文消息的敏感依賴。

本文在明文信息微小改變的條件下測試Hash值的變化情況，具體如下：

條件1同4.1節中的原始明文。

條件2將原始明文的首字母“H”改為“h”。

條件3 將原始明文的末尾“.”改為“，”。

條件4將原始明文的末尾加上1個空格。

條件5將原始明文中的單詞“function”改為“functions”。

得到的Hash值（十六進制）如下，對應二進制序列如圖4所示。

條件1 E9 A6 C5 0B 0F 1F D4 0F 2A F3 42 E1 76 BB 82 F4。

條件2 5D 0A BC 31 4A 54 84 A3 EF F0 22 4E E4 76 58 72（60）。

條件3 F1 FB B0 7C 1A F4 D3 46 55 05 63 CA 38 8D EF AC（68）。

條件4 30 43 4F 2A 75 1C 0C 96 5A 4F 9D C5 36 20 68 22（63）。

條件5 9C D9 99 F0 1E 63 18 34 41 CE 06 A3 52 01 57 97（69）。

圖4 不同條件下Hash值比較

從實驗結果可以看出，明文消息的細微改變都能引起Hash值發生巨大的變化，所以本文算法具有良好消息敏感性。

4.3 混亂與擴散分析

Hash函數的混亂與擴散特性主要是從統計的角度使得原始明文和Hash值之間的關系變得更復雜，且使明文的每一位均能影響Hash值。通常采用如下指標測量Hash函數的混亂與擴散性能：

P的均方差：

式中T為測試的總次數，Bi表示第i次測試時變化的比特數。

任意選取一段明文消息，產生其Hash值。然后，隨機改變消息中某個比特的值，求得新的Hash值，比較兩個Hash值的差異。分別重復上述操作256、512、1 024、2 048和10 000次，得到 Bˉ、P 、ΔB、ΔP 值如表1所示。

表1 實驗結果統計

重復10 000次操作時得到的Hash值變化比特數的統計結果如圖5和圖6所示。實驗結果表明，該算法的平均變化比特數Bˉ為64.01，每比特平均變化概率P為50.02%，接近理論值64和50%。ΔB與ΔP的值分別為5.50和4.28，都非常得小，這表明該算法的混亂和擴散性很穩定，能夠抵抗統計攻擊和差分攻擊。

圖5 Bˉ的分布圖

圖6 變化比特數B的直方圖

4.4 抗碰撞性分析

4.4.1 抗生日攻擊分析

碰撞指隨機給定兩個不同的輸入數據，而Hash值卻相同，即發生了多對一映射。生日攻擊與碰撞本質上是一樣的，生日攻擊指隨機選取兩個不同的明文消息計算各自的Hash值，比較它們的Hash值相同的概率。本文算法的Hash值長度為128 bit，且輸出分布均勻，故生日攻擊的復雜度為264，滿足安全性的要求。

4.4.2 抗中間碰撞攻擊分析

中間碰撞攻擊的對象為Hash函數構造中的中間結果。在本文的算法中，每個消息塊的輸出是其中的一個中間結果。在中間結果的產生過程中，本文基于的是迭代PLM映射(N=64)的方式。就該映射而言，若已知其當前的狀態值，推測其前一狀態值，有128種可能性。在模塊的處理過程中，總共迭代PLM的次數為256次。所以，在已知消息塊輸出結果的情況下，預測輸入值計算量為128256，滿足安全性的要求。

4.4.3 抗偽造攻擊分析

偽造攻擊指攻擊者在已知幾對明文和Hash值情況下，通過對這些消息進行組合和排列以實現碰撞。在文獻[14]中，采用偽造攻擊的方式，實現了對一些基于混沌的并行Hash函數的碰撞。這些基于混沌的Hash函數[15，18]之所以被破解，主要的原因為各明文塊之間是相互獨立的，沒有考慮它們之間的關聯與影響。在本文算法中，預處理階段采取了兩個方式來彌補：其一是通過鏈式結構，借助混沌映射的迭代實現各明文比特之間的關聯與擴散；其二是通過最后一個字節的反饋來調整每個塊的首字節值，從而強化擴散的效果。所以，本文算法能有效防止偽造攻擊。

4.4.4 抗碰撞實驗

混沌系統通常定義在實數域，對基于混沌映射的Hash函數，很難從數學上證明它的抗碰撞性。因此，本文根據文獻[19]的方法定量分析該算法的抗碰撞性，通過式（14）計算T次實驗中相鄰Hash值的絕對差異度：

d=∑i=1

T

|t(ei)-t(e′i) （14）其中ei和e′i分別是原消息Hash值和修改消息后Hash值中的第i個ASCII碼字符，函數t()將ASCII碼字符轉換為對應的十進制數值。

以4.3節中的10 000次實驗數據作為樣例，求得最大、最小絕對差異度如表2所示，以及在相同位置上有相同ASCII碼值的個數分布如圖7所示。本文算法的平均字符差異度為85.31，非常接近理想狀態下[19]的理論值85.33，并且最大的相同字符數為2，說明該算法具有很好的抗碰撞性。

|602 1 365 85.31

表2 兩個Hash值之間的絕對差異度d

相同ASCII碼值的個數

圖7 Hash值中有相同值的ASCII碼字符的分布圖

4.5 效率分析

在配置為Intel core i3 2120 3.30 GHz，8 GB RAM的計算機中，采用Visual C++6.0實現了本文算法。采用不同的線程數量，對長度不同的明文消息產生其對應的Hash值，測量算法的執行時間，結果如圖8所示。計算結果表明，隨著線程數量的增加，算法的執行效率明顯提高。當線程為4個時，算法的處理速度為102 Mb/s。這表明該算法具有較高的執行效率，能夠滿足實際應用的需要。

圖8 算法的運行時間

4.6 對比分析

從當前國內外發表的文獻中，選取類似的采用并行結構的Hash函數算法[12-13，19-21]與本文的算法進行比較。對比的結果如表3所示。

表3 隨機測試T次的比較

從表3中可以看出，上述基于混沌的并行Hash函數均具有不錯的統計性能和良好的抗碰撞性。與其他算法相比，本文算法的平均字符差異度為85.31，非常接近理論值85.33。在統計指標方面，本文算法的 Bˉ為63.99，P為49.99%與文獻[21]中的結果相同，比其他算法更接近理論值64和50%。ΔB與ΔP的值分別為5.57和4.25，在所比較的算法中最小，表明該算法具有更好的混亂和擴散性。

5 結束語

本文利用分段Logistic映射運算速度快且具有良好密碼學屬性的特點，提出了一種新的并行混沌Hash函數構造算法。在明文預處理過程中，通過對每個消息值做鏈式變換操作以增強消息塊間的擴散效果，從而提高該算法的抗碰撞性。在消息塊的處理過程中采用了并行操作，消息塊輸出結果的合并為簡單的異或運算，有效地減少了運算量，使算法在滿足安全性的同時，具有很好的運行效率。理論分析與計算機仿真實驗的結果表明，該算法能滿足Hash函數的各項性能要求，具有良好的應用潛力。