OHNN新的分組Hash算法

李國剛，鐘超林，藺小梅（華僑大學信息科學與工程學院，福建廈門361021）

?

OHNN新的分組Hash算法

李國剛，鐘超林，藺小梅
（華僑大學信息科學與工程學院，福建廈門361021）

摘要：在Hash函數算法的研究設計過程中，引入混沌系統理論，探索研究基于混沌動力學的Hash函數算法.將分段線性混沌映射和過飽和的Hopfield神經網絡（OHNN）進行結合，提出一種基于混沌動力理論的單向Hash函數構造方法.對算法進行仿真和測試，從不同方面分析驗證所提新的算法滿足Hash算法的性能指標.安全性分析表明：該算法能抵抗多種碰撞和統計分析的攻擊，具有很好的安全性能.

關鍵詞：Hopfield神經網絡；混沌吸引子；分段線性映射；Hash算法

采用大量邏輯運算的Hash函數的方法已不具備所需的安全特性［1－6］，當經典Hash函數被攻破后尋找一個更安全的算法就變得不再那么簡單.于是，在Hash函數算法的研究設計過程中，引入混沌系統理論［3］，探索基于混沌動力學的Hash函數算法，成了密碼學領域研究的新思路.本文將分段線性混沌映射和過飽和Hopfield神經網絡（OHNN）進行結合，提出一種基于混沌動力理論的單向Hash函數構造方法.

1　分段線性映射

選擇的混沌映射是一維分段線性映射，它從標準帳篷映射和斜帳篷映射推廣演化而來，函數為

xn/q，0≤xn＜q，

（xn－q）/（0.5－q），q≤xn＜0.5，（1

（1－x－q）/（0.5－q），0.5≤x＜1－q，

（1－xn）/q，1－q≤xn＜1.

式（1）中：x取值范圍為［0，1］；控制參數q取值范圍為（0，0.5）.當q在（0，0.5）的范圍內時，會產生混沌現象，其函數圖形，如圖1所示.由文獻［6］可知：該分段線性映射的輸出序列在（0，1）是遍歷的，有著很好的數學統計特性.系統的不變分布函數f＊（x）的算子［5］為

Psf＊（x）＝Pf＊（xP）＋（0.5－P）f＊（P＋x（0.5－P）＋（0.5－P）f＊（0.5＋（1－x）（0.5－P））＋Pf＊（1－xP）.（2）

f（x）＝1表明系統在（0，1）上是均勻分布的.

圖1　分段線性映射Fig.1　Piecewise linear mapping

2　OHNN吸引子的混沌特性

在OHNN中吸引子［4］在每個穩定狀態時候的收斂域是混沌的，其與神經網絡的初始狀態之間表現出一種不規則的關系，稱之為混沌性［5］.假設Hopfield神經網絡有N個神經元，算法中取N＝16.引入一隨機變換矩陣H，原始狀態Su和吸引域中各元素組成的矩陣S的演變規律為式（3）～（4）中：＾S是S的更新狀態；＾Su是Su的更新狀態.

神經網絡新的權值聯結矩陣T為式（5）中：H′為H的轉置矩陣.

網絡運行后，按式（2），（3）的變化規律，當改變混沌神經網絡的初值，即T發生改變時，其對應的吸引子和吸引域都都將發生非常明顯的改變.基于離散的Hopfield神經網絡的統計概率問題，如果要有較多的不可預測的吸引子，則要求網絡中興奮性的突觸連接和抑制性的突觸連接的數目要盡可能地相等.算法選取N＝16，也是基于此考慮.

設OHNN網絡的初始聯結矩陣T0與N階非奇異隨機變換矩陣H分別為

3　算法設計

Hash算法結構上一般分為壓縮函數和運算迭代.壓縮函數承擔Hash算法最關鍵的功能，即如何將任意長度明文序列單向壓縮映射成固定長度的輸出，設計了一種新的單向分組Hash函數算法.算法的基本思想如下：將OHNN的收斂域中的吸引子元素x0作為密鑰，同原始文本比特、分段線性映射（式（4））的上一次迭代結果的值結合一起，共同運算得出對應的Hash值.設計的Hash函數生成的函數值長度（K）為128b.整個算法的結構框圖，如圖2所示.

圖2　算法結構框圖Fig.2　Block diagram of the algorithm

1）明文擴展.明文消息是一段任意長字符，每一個明文字符數值ASCII變換后，轉換為［0，1］之間的浮點數.將轉換后的數值存儲在數組D中.擴展方法如下：設消息明文為m，該消息明文的長度設為s，再添加nb的（101010…）2，使得（m＋n）mod 1 024＝1 024－s成立.s的取值一般為64，0≤n≤Kl.添加后的待處理消息變成M，可分為l個1 024b的子模塊，M＝（M1，M2，…，Ml），m＋n＋s＝1 024l.

2）密鑰流生成.初始密鑰由OHNN和參數H0提供.在OHNN中隨機選取吸引域中的一個值的前一狀態，將其轉換為［0，1］間的浮點數，并將其存儲，作為選取的密鑰，賦值給xi和H0，作為分段線性映射的初始值.

3）段線性映射處理.算法對明文的迭代處理，采用分組并行處理方式.算法對每一個明文分組子模塊Mi（1，2，3，…，l）的處理，采用不同的密鑰參數，但采用同樣的迭代算法（圖2）.以第Mi個模塊為例，對于當前所選擇的子模塊mi，j（j＝1，2，3，…，128），由混沌神經網絡產生吸引子的前一個狀態作為一個密鑰，初始化為當前函數的初始值，經過混沌分段映射函數mi，j次迭代，生產當前狀態值xmi，j.然后，將當前生成的混沌狀態四舍五入為相對應的0或者1，一直到模塊中的所有值都處理完畢，得到的是由Hl 個1或者0組成的數組.通過級聯這Kl個0或者1就是第i個模塊的Hash值.

4）最終Hash值的生成.每個消息模塊Mi（i＝1，2，…，l）都會生成一個中間Hash值Hi（i＝1，2，…，l），最后按H（M）＝H（l）H（l－1）…H（1）計算，得到整個明文序列的最終Hash值.

4　算法測試及安全性能分析

4.1 Hash值分布

混沌Hash函數的主要性能分析方法：固定長度的消息經過Hash函數，通過計算，得到的Hash值能均勻反應消息中每個消息.算法輸入的明文序列為

The chip is a communications processor consisting of a reduced instruction set computer processor and a digital signal processor.This device has a rich peripheral set architected specifically for voice over internet protocol phone applications that results in a reduced bill of materials，reduced complexity，and reduced time to develop an internet protocol phone.The chip architecture uses advanced design features to provide flexibility and performance.Combined with Telogy Networks software for IP phone applications，the chip provides a complete hardware/software solution capable of reducing sys－tem design cycle times.

原始明文的ASCII碼分布，如圖3（a）所示.由圖3（a）可知：明文的ASCII都集中在一個小范圍之內.算法之后的最終散列值的分布圖，如圖3（b）所示.由圖3（b）可知：經過本Hash函數計算以后的散列值分布相當均勻.

圖3　明文信息和Hash值分布Fig.3　Plaintext and Hash value distribution

4.2 文本仿真

仿真采用Hash算法，對一段任意長的原始明文進行計算，獲取其十六進制的Hash值H0.對原始明文文本按n（n＞1）種不同的修改方法，修改成與原始明文只有微小差異的n組明文，并計算其對應的Hash值Hn.將文本相關參數做下列6種情況的改變：1）直接計算文本Hash值；2）將首字符T變為Y；3）processor變為orocessor；4）最后字符“.”變為“。”；5）最后位置添加空格符；6）密鑰0.232323更改為0.232326.分別得到的Hash值用十六進制表示如下：

1）923A0D309FCE9739325786F0D52F99BD；2）22CA1394803B775095A647053CC9B48B；3）A2647C3D6CC5CEBA28D571DAF0D0E714；4）4AFC27F2E08794EB19A45D4A752BB3C4；5）C814C819818BC3FE89B7884797D03764；6）18DA39BCEA0C8EE77D1D7533988782EF.不同條件下的Hash值，如圖4所示.由圖4可知：文中構造的Hash算法單項性能良好，任何明文或者秘鑰微小的改變都能給最終的結果帶來很大的變化，完全符合密碼學的混亂的特性.

圖4　不同條件下的Hash值Fig.4　Hash values under different conditions

4.3 混亂與擴散性質統計分析

隨機選取一段明文并計算出其Hash值H0.然后，隨機改變明文中1個比特位的值，計算出改變后的Hash值Hn，比較Hn和H0間不同的比特位個數，完成一次測試統計.重復上述過程N次，得到統計數據.文中測試的Hash算法生成的Hash值長度為128b.測試中N取1 024，如圖5所示.由圖5可知：每改變明文1b，對應輸出的Hash值較為均勻地分布在理論值64b的周邊，說明有著較強的混亂和擴散性.對128，256，512，1 024，4種不同測試次數的實驗數據進行統計分析，如表1所示.

圖5　明文敏感性測試Fig.5　Plaintext susceptibility testing

表1　統計分析測試結果Tab.1　Statistical analysis of the test results

由表1可知：明文每改變1b時，算法的平均變化比特數珚B非常接近于64b的理想值，平均變化概率P也都接近于50%的理想狀況；其對應的均方差ΔB和ΔP均非常小，說明變化幅度很小且這種變化是非常穩定的.從統計學的角度說明其具有良好的抗統計攻擊的能力.

4.4 抗碰撞分析

文中采用文獻［7］的方法，測試算法的抗碰撞能力.經過1 024次試驗，得到最大差異度為2 180，最小差異度為853，平均差異度為1 506，平均差異度/字符是88.82，非常接近理想值85.333 3，說明本算法的碰撞程度很低，完全能夠抵抗碰撞攻擊.

4.5 生日攻擊

生日攻擊的原理不使用Hash函數和任意代數性質，只決定于消息摘要的長度.為了抵抗生日攻擊，通常把消息摘要的長度取為至少128b，對于MD5的生日攻擊需要約264次哈希運算，SHA－1輸出長度選擇的160b也是出于這樣的考慮.算法最終的哈希值為128b.

4.6 算法的比較

選取具有代表性的算法［6，8－10］與所提算法進行對比分析，從相關統計數據得出基于混沌的Hash函數均具有很好的統計性能，平均變化比特數達到64b，而同時每比特的平均變化概率50%以上，接近Hash函數算法理論上的理想水平.文中算法與文獻［8，10］的算法均具有良好的統計性能，在抗碰撞攻擊方面，文中算法在抗碰撞分析中的平均差異度是88.82，而文獻［8］所提算法是97.5，明顯優于文獻［8］所提算法.同文獻［6，9］中的平均變化比特數和每比特平均變化概率相比，所設計的算法具有較好的統計性能指標.

5　結束語

提出的基于OHNN的新的分組Hash算法采用并行運算思維，提升了算法執行效率.OHNN的結構和性質滿足混沌密碼系統的要求，與單純引入一個混沌系統相比，具有更好的安全性能.即使消息明文的長度相同，只要改H，其對應的吸引子和產生的吸引域則會完全不同.這使分段映射的輸入控制參數不一樣，引入了擾動，避免混沌動力學特性退化，并確保了最終散列值完全不相同.消息的擴展這一步驟，即把消息長度也作為一個參數項，增加了攻擊的難度，使算法的安全性能有了進一步的保障.最后，從不同方面分析驗證了所提新的算法滿足Hash算法的性能指標.安全性分析表明：本算法能抵抗多種碰撞和統計分析的攻擊，具有很好的安全性能.

參考文獻：

［1］WANG Xiao－yun，YAO Fang.Cryptanalysis of SHA－l hash function［C］∥Proceedings of Crypto 2005.Berlin：Springer－Verlag，2005：19－35.

［2］XIAO Di，LIAO Xiao－feng，WANG Yong.Improving the security of a parallel keyed hash function based on chaotic maps［J］.Phys Lett A，2009，373（47）：4346－4353.

［3］YANG Gang，YI Jun－yan.Dynamic characteristic of a multiple chaotic neural network and its application［J］.Soft Computing，2013，17（5）：783－792.

［4］LI Guo－gang，GUO Dong－hui.One－way property proof in public key cryptography based on OHNN［J］.Procedia Engineering，2011，15（1/2）：1812－1816.

［5］LASOTA A，MACKEY M C.Probabilistic properties of deterministic systems［M］.Cambridge：Cambridge University Press，1985：1.

［6］XIAO Di，LIAO Xiao－feng.One－way Hash function construction based on the chaotic maps with changeable－parameter［J］.Chaos Solitons and Fractais，2005，24（1）：65－71.

［7］WONG K W.A combined chaotic cryptographic and hashing scheme［J］.Physics Letters A，2003，307（5/6）：292－298.

［8］李永華.混沌加密算法與Hash函數構造研究［D］.大連：大連大學，2012：45.

［9］WANG Yong，LIAO Xiao－feng，XIAO Di，et al.One－way hash function construction based on 2Dcoupled map lattices［J］.Information Sciences，2008，178（5）：1391－1406.

［10］XIAO Di，LIAO Xiao－feng，DENG Shao－jiang.Parallel keyed hash function construction based on chaotic maps［J］.Phys Lett A，2008，372（26）：4682－4688.

（責任編輯：陳志賢 英文審校：吳逢鐵）

New Gouping Hash Agorithm Based on OHNN

LI Guo－gang，ZHONG Chao－lin，LIN Xiao－mei
（College of Information Science and Engineering，Huaqiao University，Xiamen 361021，China）

Abstract：In the design process of the Hash function algorithm study，the chaotic systems theory，is introduced to investigate the Hash Function Algorithm Based on Chaos Dynamics.Combining the piecewise linear chaotic map and oversaturated Hopfield neural network（OHNN）.An unidirectional Hash function construction method based on chaotic dynamical theory is proposed.The new algorithm is verified to meet the performance index of Hash algorithm from different aspects by simulation and testing.Security analysis shows that the proposed algorithm can resist many kinds of attacks，and has good security performance.

Keywords：hopfield neural；the chaotic attractor；piecewise linear mapping；Hash algorithm

通信作者：李國剛（1973－），男，教授，博士，主要從事集成電路設計與信息安全的研究.E－mail：lgg＠hqu.edu.cn.

中圖分類號：TN 918.4

文獻標志碼：A

文章編號：1000－5013（2015）04－0393－06

doi：10.11830/ISSN.1000－5013.2015.04.0393

收稿日期：2014－12－29

基金項目：國家自然科學基金資助項目（61370007）；華僑大學科研基金資助項目（14BS115）