OHNN新的分組Hash算法

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

?

OHNN新的分組Hash算法

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

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

關(guān)鍵詞：Hopfield神經(jīng)網(wǎng)絡(luò)；混沌吸引子；分段線性映射；Hash算法

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

1　分段線性映射

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

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］；控制參數(shù)q取值范圍為（0，0.5）.當q在（0，0.5）的范圍內(nèi)時，會產(chǎn)生混沌現(xiàn)象，其函數(shù)圖形，如圖1所示.由文獻［6］可知：該分段線性映射的輸出序列在（0，1）是遍歷的，有著很好的數(shù)學統(tǒng)計特性.系統(tǒng)的不變分布函數(shù)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表明系統(tǒng)在（0，1）上是均勻分布的.

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

2　OHNN吸引子的混沌特性

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

神經(jīng)網(wǎng)絡(luò)新的權(quán)值聯(lián)結(jié)矩陣T為式（5）中：H′為H的轉(zhuǎn)置矩陣.

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

設(shè)OHNN網(wǎng)絡(luò)的初始聯(lián)結(jié)矩陣T0與N階非奇異隨機變換矩陣H分別為

3　算法設(shè)計

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

圖2　算法結(jié)構(gòu)框圖Fig.2　Block diagram of the algorithm

1）明文擴展.明文消息是一段任意長字符，每一個明文字符數(shù)值A(chǔ)SCII變換后，轉(zhuǎn)換為［0，1］之間的浮點數(shù).將轉(zhuǎn)換后的數(shù)值存儲在數(shù)組D中.擴展方法如下：設(shè)消息明文為m，該消息明文的長度設(shè)為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和參數(shù)H0提供.在OHNN中隨機選取吸引域中的一個值的前一狀態(tài)，將其轉(zhuǎn)換為［0，1］間的浮點數(shù)，并將其存儲，作為選取的密鑰，賦值給xi和H0，作為分段線性映射的初始值.

3）段線性映射處理.算法對明文的迭代處理，采用分組并行處理方式.算法對每一個明文分組子模塊Mi（1，2，3，…，l）的處理，采用不同的密鑰參數(shù)，但采用同樣的迭代算法（圖2）.以第Mi個模塊為例，對于當前所選擇的子模塊mi，j（j＝1，2，3，…，128），由混沌神經(jīng)網(wǎng)絡(luò)產(chǎn)生吸引子的前一個狀態(tài)作為一個密鑰，初始化為當前函數(shù)的初始值，經(jīng)過混沌分段映射函數(shù)mi，j次迭代，生產(chǎn)當前狀態(tài)值xmi，j.然后，將當前生成的混沌狀態(tài)四舍五入為相對應的0或者1，一直到模塊中的所有值都處理完畢，得到的是由Hl 個1或者0組成的數(shù)組.通過級聯(lián)這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函數(shù)的主要性能分析方法：固定長度的消息經(jīng)過Hash函數(shù)，通過計算，得到的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都集中在一個小范圍之內(nèi).算法之后的最終散列值的分布圖，如圖3（b）所示.由圖3（b）可知：經(jīng)過本Hash函數(shù)計算以后的散列值分布相當均勻.

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

4.2 文本仿真

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

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

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

4.3 混亂與擴散性質(zhì)統(tǒng)計分析

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

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

表1　統(tǒng)計分析測試結(jié)果Tab.1　Statistical analysis of the test results

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

4.4 抗碰撞分析

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

4.5 生日攻擊

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

4.6 算法的比較

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

5　結(jié)束語

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

參考文獻：

［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－h(huán)ui.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函數(shù)構(gòu)造研究［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－），男，教授，博士，主要從事集成電路設(shè)計與信息安全的研究.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）