基于時(shí)滯混沌系統(tǒng)的帶密鑰Hash函數(shù)的設(shè)計(jì)與分析

徐 杰，楊娣潔，隆克平,2

(1. 電子科技大學(xué)光互聯(lián)網(wǎng)和移動(dòng)信息網(wǎng)絡(luò)研究中心 成都 611731; 2. 北京科技大學(xué)計(jì)算機(jī)與通信工程學(xué)院 北京 海淀區(qū) 100083)

網(wǎng)絡(luò)數(shù)據(jù)的完整性時(shí)刻都會(huì)受到威脅，為了確認(rèn)收到的信息在傳輸過(guò)程中沒(méi)有被攻擊者插入、篡改或刪除，以公鑰密碼、數(shù)字簽名等為代表的加密安全技術(shù)已得到廣泛的研究和應(yīng)用。單向Hash函數(shù)作為數(shù)字簽名等安全技術(shù)中的一個(gè)關(guān)鍵環(huán)節(jié)，目前有MD2、MD5、SHA等標(biāo)準(zhǔn)。文獻(xiàn)[1-2]公布了對(duì)MD4、MD5、HAVAL-128、RIPEMD、SHA-1等Hash函數(shù)的碰撞攻擊方法，對(duì)國(guó)際上通行的Hash函數(shù)給出了快速尋找碰撞攻擊的方法，從理論上證明了基于MD5和SHA-1等算法的電子簽名有被偽造的可能性。所謂碰撞，是指不同的初始文本對(duì)應(yīng)的Hash映射結(jié)果相同，即發(fā)生了多對(duì)一映射。為了提高網(wǎng)絡(luò)信息的安全性，保證數(shù)字簽名的真實(shí)性，設(shè)計(jì)新的、更安全的單向Hash函數(shù)十分必要。

由于混沌系統(tǒng)具有初始值敏感性、遍歷性和偽隨機(jī)性等特點(diǎn)，近年來(lái)利用混沌方法構(gòu)造Hash函數(shù)迅速成為新的研究方向和熱點(diǎn)。目前國(guó)內(nèi)外主要的研究方法是在原有算法的基礎(chǔ)上，結(jié)合混沌系統(tǒng)構(gòu)造出新的高可靠性、高安全性的Hash函數(shù)。文獻(xiàn)[3]提出了基于前饋-反饋非線性數(shù)字濾波器構(gòu)建帶密鑰的Hash函數(shù)。文獻(xiàn)[4]則研究了分段線性混沌映射的Hash函數(shù)構(gòu)造方法。文獻(xiàn)[5]提出了基于RBF神經(jīng)網(wǎng)絡(luò)和混沌映射構(gòu)造Hash函數(shù)的方法。文獻(xiàn)[6]提出了利用耦合混沌映射方法構(gòu)造Hash函數(shù)。文獻(xiàn)[7]構(gòu)建了基于保守混沌系統(tǒng)的單向Hash函數(shù)。文獻(xiàn)[8]提出了基于耦合映像格子混沌模型的Hash函數(shù)算法。文獻(xiàn)[9]在對(duì)復(fù)合離散混沌系統(tǒng)和由兩個(gè)混沌映射構(gòu)成的特殊復(fù)合離散混沌系統(tǒng)分析的基礎(chǔ)上，建立了基于復(fù)合離散混沌系統(tǒng)的帶密鑰的Hash算法。文獻(xiàn)[10]提出了基于二維超混沌映射的單向散列函數(shù)構(gòu)造方法，但其抗碰撞性還不能達(dá)到較好的效果。文獻(xiàn)[11]提出了基于時(shí)空混沌系統(tǒng)構(gòu)造Hash函數(shù)的方法，但在明文填充時(shí)，僅僅填充了一些字符而并未加入明文的任何消息，仍然容易產(chǎn)生碰撞。但所有這些成果都推動(dòng)了混沌Hash函數(shù)的研究，具有積極的意義。

在對(duì)研究現(xiàn)狀深入分析的基礎(chǔ)上，本文設(shè)計(jì)了基于時(shí)滯混沌系統(tǒng)構(gòu)造帶密鑰的Hash函數(shù)算法。該算法利用時(shí)滯混沌系統(tǒng)的敏感性和遍歷性，將明文消息逐比特地調(diào)制在時(shí)滯混沌系統(tǒng)的迭代軌跡中，并以關(guān)聯(lián)了所有明文信息的一組混沌序列，結(jié)合帶密鑰的Hash函數(shù)HMAC-MD5認(rèn)證算法，計(jì)算得出單向Hash值。理論分析和仿真實(shí)驗(yàn)均表明，該算法在保證了散列值的混亂性和散布性的同時(shí)，因混沌特性的加入而增大了參數(shù)空間，并使HMAC-MD5認(rèn)證算法的抗窮舉性得到了很大的提升，進(jìn)一步增強(qiáng)了算法的安全性和抗碰撞性。

1 時(shí)滯混沌的系統(tǒng)研究

本文基于時(shí)滯混沌系統(tǒng)的非線性動(dòng)力學(xué)特性設(shè)計(jì)Hash函數(shù)算法，該混沌系統(tǒng)根據(jù)時(shí)延系數(shù)的不同可以表達(dá)為不同維數(shù)的映射，系統(tǒng)方程表示為：

式中，a和b是實(shí)參數(shù)；un是系統(tǒng)n時(shí)刻的狀態(tài)，其狀態(tài)集合稱(chēng)為狀態(tài)空間；u0是初始狀態(tài)；N是系統(tǒng)維數(shù)。

系統(tǒng)(1)可通過(guò)如下變量轉(zhuǎn)換為：

得到的N維系統(tǒng)方程為：

由式(3)可知系統(tǒng)在參數(shù)空間內(nèi)具有對(duì)稱(chēng)性和周期性：

因此，根據(jù)該混沌系統(tǒng)的對(duì)稱(chēng)和周期特性，將研究的區(qū)域僅限制在參數(shù)空間(a,b)的a>0且b∈[0,a]的范圍內(nèi)。

同時(shí)，從系統(tǒng)方程式(3)的sin函數(shù)性質(zhì)可知，該系統(tǒng)還具備有界性：

可見(jiàn)，在任何參數(shù)和任何初始條件下，系統(tǒng)的所有狀態(tài)軌跡都是有界的，對(duì)于混沌特性的控制和應(yīng)用非常有利。

文獻(xiàn)[12-14]中，已對(duì)該時(shí)滯混沌系統(tǒng)的非線性動(dòng)力學(xué)特性進(jìn)行了深入研究。在系統(tǒng)參數(shù)空間內(nèi)，通過(guò)對(duì)系統(tǒng)的穩(wěn)定性研究，得到了該系統(tǒng)從穩(wěn)定狀態(tài)到混沌狀態(tài)的分岔演變過(guò)程，對(duì)系統(tǒng)的穩(wěn)定性控制和應(yīng)用中的參數(shù)選取有重要作用。在系統(tǒng)狀態(tài)空間內(nèi)，已經(jīng)研究了系統(tǒng)吸引域(或吸引盆)隨參數(shù)變化的演變過(guò)程，以及作為吸引域邊界的不變流形和作為混沌吸引子(或奇怪吸引子)邊界的臨界流形的特性。并且，由不同初始條件而引起的系統(tǒng)多穩(wěn)定態(tài)的特性也在研究中得到了驗(yàn)證。

通過(guò)上述研究，可發(fā)現(xiàn)該系統(tǒng)所產(chǎn)生的混沌吸引子始終有界，并且受參數(shù)控制，對(duì)于該系統(tǒng)的實(shí)際應(yīng)用非常有利。通過(guò)研究得到了該系統(tǒng)通向混沌的方法，對(duì)于混沌序列的選取和控制十分重要。

2 基于時(shí)滯混沌迭代的帶密鑰Hash函數(shù)設(shè)計(jì)原理

在對(duì)時(shí)滯混沌系統(tǒng)非線性動(dòng)力學(xué)研究的基礎(chǔ)上，本文設(shè)計(jì)了一種基于該混沌系統(tǒng)的帶密鑰Hash函數(shù)算法。該算法的基本思路是將明文消息M以字符為單位讀取，經(jīng)線性變換量化處理得到離散的明文序列C(k)，該明文序列C(k)通過(guò)時(shí)滯混沌系統(tǒng)進(jìn)行逐字節(jié)的迭代，從而得到一組離散時(shí)滯混沌序列，對(duì)其進(jìn)行帶密鑰Hash函數(shù)運(yùn)算，即可獲得定長(zhǎng)的時(shí)滯混沌Hash值。該算法的基本設(shè)計(jì)原理如圖1所示。

圖1 基于時(shí)滯混沌迭代的帶密鑰Hash函數(shù)構(gòu)造原理圖

該Hash算法主要分為3個(gè)步驟：

1) 進(jìn)行明文線性變換量化處理。具體方法為：對(duì)明文信息M(k)以字符為單位進(jìn)行ASCII編碼，得到明文信息M(k)的ASCII編碼序列Asc(M(k))，其中k=1,2,…, K，K為M(k)的長(zhǎng)度。由于ASCII碼序列的值域范圍為[0,255]，因此通過(guò)ASCII編碼，明文消息M(k)的值域量化至[0,255]之間，利用線性公式C(k)=g+0.001Asc(M(k))對(duì)Asc(M(k))進(jìn)行線性變換，g為取值范圍在[12,12.545]之間的一個(gè)常數(shù)，于是得到符合時(shí)滯混沌迭代參數(shù)所要求的值域范圍[12,12.8]的離散序列C(k)。

2) 對(duì)離散序列C(k)進(jìn)行時(shí)滯混沌迭代，計(jì)算離散時(shí)滯混沌序列。時(shí)滯混沌系統(tǒng)(1)的一維系統(tǒng)為：

表1 離散時(shí)滯混沌序列

3) 對(duì)離散時(shí)滯混沌序列(xiK－1)(i∈[1,N+1])進(jìn)行HMAC-MD5運(yùn)算，獲得定長(zhǎng)的混沌Hash值。具體方法為：① 令離散時(shí)滯混沌序列(xiK－1)為HMAC-MD5算法的輸入消息，即M=(xiK－1)，其中i∈[1,N+1]；② 采用列為“00110110”重復(fù)排列任意次的ipad序列與通信雙方約定的密鑰Key進(jìn)行異或運(yùn)算，得到序列S0，并采用序列為“01011100”重復(fù)排列任意次所構(gòu)成的opad序列與通信雙方約定的密鑰Key進(jìn)行異或運(yùn)算，得到序列S1；③ 將序列S0與輸入消息M拼接構(gòu)成離散序列G0=(M|S0)，對(duì)G0進(jìn)行MD5運(yùn)算，得到長(zhǎng)度為128 bit的Hash值H0=H[G0]MD5；④ 將序列S1與所得的Hash值H0拼接構(gòu)成離散序列G1=(H0|S1)，對(duì)G1進(jìn)行MD5運(yùn)算，得到長(zhǎng)度為128 bit的Hash值H1=H[G1]MD5。H1即為最終的時(shí)滯混沌Hash值。

3 混沌Hash函數(shù)性能分析

3.1 密鑰敏感性分析

為了分析基于所設(shè)計(jì)的Hash函數(shù)算法對(duì)密鑰的敏感性，針對(duì)文本信息進(jìn)行Matlab仿真實(shí)驗(yàn)，并將密鑰僅做10－6的改動(dòng)，分析所得的Hash值的差異。取初始文本信息為：

As a phenomenon of culture, festivals bear the weight of human civilization. China makes no exception. Chinese traditional festivals contain and incarnate the distillation of Chinese traditional culture.However, since the Opening and Reform, Chinese traditional festival culture has encountered w ith an unprecedented challenge. Through analyzing the phenomenon of the invasion, the thesis reveals the econom ic and ideological reasons for its birth and development in China and summarizes its great effects on Chinese society. Meanwhile, the thesis also points out the limits of the invasion by exploring its reasons from the historical and realistic aspects. Thus it can be seen that the western festival culture cannot replace the status of Chinese traditional festival culture in China for ever.

基于初始密鑰和經(jīng)10－6改動(dòng)后的密鑰，分別進(jìn)行本文設(shè)計(jì)的時(shí)滯混沌Hash函數(shù)運(yùn)算，所得Hash值用十六進(jìn)制表示如下。

初始密鑰的Hash值為：

eb953cd6dda22d7e3af675d594fa8bd4

改動(dòng)后密鑰的Hash值為：

a46dbf8679e198cc2853ba5c68f3e336

將上述Hash值用二進(jìn)制序列圖形化表示，如圖2所示。

以上仿真結(jié)果表明，本文所設(shè)計(jì)的Hash函數(shù)算法對(duì)密鑰具有很高的敏感性，即使密鑰存在微小的差異，也會(huì)產(chǎn)生截然不同的Hash值。

圖2 密鑰存在10-6差異時(shí)的Hash值二進(jìn)制對(duì)比結(jié)果

3.2 混亂與散布性質(zhì)統(tǒng)計(jì)分析

Hash函數(shù)的設(shè)計(jì)必須遵循混亂和散布兩個(gè)重要原則，盡量做到相關(guān)明文對(duì)應(yīng)的Hash值不相關(guān)。對(duì)于結(jié)果的二進(jìn)制表示，每比特只有0或者1兩種可能，所以理想Hash值的散布效果應(yīng)該是，初值的微小變化將導(dǎo)致結(jié)果的每比特都以50%的概率變化。因此，考察Hash認(rèn)證函數(shù)的混亂與散布性質(zhì)，即考察算法明文發(fā)生l bit變化情況所引起Hash密文結(jié)果變化的比特?cái)?shù)。

混亂與散布性質(zhì)的統(tǒng)計(jì)數(shù)字特征可由以下數(shù)據(jù)描述：

其中，N為統(tǒng)計(jì)次數(shù)；Bn為第n次測(cè)試時(shí)的變換比特?cái)?shù)。

基于上述思想，本文設(shè)計(jì)的基于時(shí)滯混沌系統(tǒng)的Hash函數(shù)的混亂與散布性的分析統(tǒng)計(jì)數(shù)據(jù)計(jì)算方法為：1) 取一段長(zhǎng)度為K的原始明文，通過(guò)Hash函數(shù)，計(jì)算出該段明文的Hash值H；2) 在該段明文的第一個(gè)字符的ASCII碼上加1，得到一段新的明文，計(jì)算出新明文的Hash值H'，并比較H與H'的變換比特?cái)?shù)，得到B1；3) 在原始明文的第2個(gè)字符的ASCII碼上加1，得到一段新的明文，計(jì)算出新明文的Hash值H''，并比較H與H''的變換比特?cái)?shù)，得到B2；4) 以此類(lèi)推，最終得到B1，B2，B3，…，Bn-2，Bn-1，Bn；5) 得到Bn序列后，計(jì)算出上述描述混亂與散布性質(zhì)的統(tǒng)計(jì)數(shù)據(jù)。

本文分別對(duì)明文長(zhǎng)度K為250、500、1 000、6 500個(gè)字符的文字信息進(jìn)行Hash函數(shù)性能統(tǒng)計(jì)數(shù)據(jù)運(yùn)算，結(jié)果如表2所示。

表2 混沌Hash函數(shù)混亂與散布性質(zhì)的統(tǒng)計(jì)數(shù)據(jù)

從表2可知，即使初始明文有微小的變化，本文設(shè)計(jì)的時(shí)滯混沌Hash函數(shù)算法，都將導(dǎo)致Hash值有將近一半的位變化。平均變化比特?cái)?shù)和每比特平均變化率都分別趨近于理想狀態(tài)下的64 bit和50%。可見(jiàn)，本文算法相當(dāng)充分和均勻地利用了明文空間，明文的任何擾動(dòng)，使得密文在統(tǒng)計(jì)上產(chǎn)生接近等概率的均勻分布，從統(tǒng)計(jì)效果上保證了攻擊者無(wú)法在已知一些明文密文對(duì)的情況下偽造其他的明文密文。并且，△B與△P都很小，表明算法對(duì)明文的混亂與散布能力強(qiáng)而穩(wěn)定。

4.3 抗碰撞性分析

抗碰撞性是衡量Hash函數(shù)性能的又一重要指標(biāo)。對(duì)Hash函數(shù)的碰撞分析，可以通過(guò)每次改變明文的任何一個(gè)比特位，對(duì)得到的Hash值在相同位置出現(xiàn)相同十六進(jìn)制值的情況進(jìn)行統(tǒng)計(jì)分析，從而計(jì)算其碰撞率。本文分別對(duì)250、500、1 000和6 500次明文比特位的改變進(jìn)行測(cè)試，得到Hash值在相同位置出現(xiàn)相同十六進(jìn)制值的碰撞概率，如表3所示?？偲骄鲎猜蕿?.45%，可見(jiàn)，多次測(cè)試的碰撞率都非常低，說(shuō)明本文算法具有很強(qiáng)的抗碰撞性。

表3 混沌Hash函數(shù)碰撞率

4 結(jié) 論

本文所設(shè)計(jì)的基于時(shí)滯混沌系統(tǒng)的帶密鑰Hash函數(shù)算法，利用時(shí)滯混沌系統(tǒng)的非線性動(dòng)力學(xué)特性，將需要傳送的明文信息逐字節(jié)地調(diào)制在時(shí)滯混沌迭代的軌跡中，使產(chǎn)生的Hash值的每個(gè)比特都與需要傳送的明文信息相關(guān)。在帶密鑰的Hash函數(shù)運(yùn)算過(guò)程中，采用HMAC-MD5算法，對(duì)密鑰進(jìn)行兩次異或運(yùn)算，加深了攻擊者破譯的難度。

理論分析和仿真結(jié)果表明，本文設(shè)計(jì)的Hash函數(shù)算法對(duì)密鑰有高度的敏感性，即使密鑰的微小變化都將導(dǎo)致所得到的Hash值產(chǎn)生巨大的變化?？梢?jiàn)該算法能有效地抵御線性分析，并具有更大的密鑰空間和更高的安全性。并且，在混亂與散布統(tǒng)計(jì)分析以及抗碰撞性分析中，各項(xiàng)性能測(cè)試結(jié)果都趨近于理想值，表明該算法對(duì)明文的混亂與散布能力強(qiáng)而穩(wěn)定，且具有很強(qiáng)的抗碰撞性。因此，本文設(shè)計(jì)的基于時(shí)滯混沌系統(tǒng)的Hash函數(shù)算法具有很好的安全性和抗碰撞性，在數(shù)字簽名、數(shù)字水印等認(rèn)證技術(shù)中具有很好的應(yīng)用前景。

本文研究工作得到電子科技大學(xué)青年基金(L080101jx0815)的資助，在此表示感謝。

[1] WANG Xiao-yun, FENG Deng-guo, LAI Xue-jia, et al.Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD[C]//Rump Session of Crypto’04, California:Cryptology ePrint Archive, 2004.

[2] WANG Xiao-yun, FENG Deng-guo , LAI Xue-jia, et al.How to break MD5 and other Hash functions[C]//EUROCRYPT 2005. Aarhus, Denmark: Springer-Verlag,2005: 19-35

[3] ZHANG Jias-hu, WANG Xiao-min, ZHANG Weng-fang.Chaotic keyed Hash function based on feed forward feed back nonlinear digital filter[J]. Phys Lett, 2007, 362 A:439-448.

[4] XIAO Di, LIAO Xiao-feng, DENG Shao-jiang. One-way Hash function construction based on the chaotic map w ith changeable-parameter[J]. Chaos, Solitons and Fractals, 2005,24: 65-71.

[5] WEI Peng-cheng, ZHANG Wei, YANG Hua-qian, et al.Combining RBF neural network and chaotic map to construct Hash function[J]. Lecture Notes on Computer Science, 2006, 3973: 332-339.

[6] SONG Yu-rong, JIANG Guo-ping. Hash function construction based on chaotic coupled map network[C]//The 9th International Conference for Young Computer Scientists (ICYCS 2008). ChangSha, China: Inst of Elec,2008: 2753-2758.

[7] ZHANG Qing-hua, ZHANG Han, LI Zhao-hui. One-way Hash function construction based on conservative chaotic systems[C]//Fifth International Conference on Information Assurance and Security 2009 (IAS ’09). Xi’an, China: IEEE Computer, 2009: 402-405.

[8] YANG Bo, LI Zhi-min, ZHENG Shi-hui, et al. Hash function construction based on coupled map lattice for communication security[C]//Global Mobile Congress 2009.Shanghai, China: IEEE Computer Society, 2009: 1-7.

[9] 李紅達(dá), 馮登國(guó). 復(fù)合離散混沌動(dòng)力系統(tǒng)與Hash函數(shù)[J].計(jì)算機(jī)學(xué)報(bào), 2003, 26(4): 460-464

LI Hong-da, FENG Deng-guo. Composite nonlinare discrete chaotic dynamical systemsand keyed Hash functions[J].Chinese Journal of Computers, 2003, 26(4): 460-464.

[10] 彭飛, 丘水生. 基于二維超混沌映射的單向散列函數(shù)構(gòu)造[J]. 物理學(xué)報(bào), 2005, 54(10): 4562-4568.

PENG Fei, QIU Shui-sheng. One-way Hash function construction based on two-dimensional hyper-chaotic mappings[J]. Acta Phys Sin, 2005, 54(10): 4562-4568.

[11] 劉光杰, 單梁. 基于時(shí)空混沌系統(tǒng)構(gòu)造Hash函數(shù)[J]. 控制與決策, 2006 , 21(11):1244-1248.

LIU Guang-jie, Shan Liang. Construction of Hash function based on spatiotemporal chaotic systems[J]. Control and Decision, 2006, 21(11): 1244-1248.

[12] XU Jie, CHARGé P, FOURNIER P D, et al. Chaos generator for secure transm ission using a sine map and an RLC series circuit[J]. Science in China Series F:Information Sciences, 2010, 53(1): 129-136.

[13] XU Jie, LONG Ke-ping, FOURNIER P D, et al. Analysis of chaotic dynamics in two-dimensional sine square map[J].Chinese Physics Letters, 2010, 27(2): 020504.

[14] XU Jie, LONG Ke-Ping, FOURNIER P D. Chaotic dynamics in a sine square map: High-dimensional case (N≥3)[J]. Chinese Physics Letters, 2010, 27(8): 080506.

編 輯 漆 蓉