劉 慧趙 耿白 健

1(西安電子科技大學(xué)通信工程學(xué)院 西安 710071)2(北京電子科技學(xué)院 北京 100070)

基于神經(jīng)網(wǎng)絡(luò)模型的雙混沌 Hash 函數(shù)構(gòu)造

劉 慧1,2趙 耿1,2白 健1,2

1(西安電子科技大學(xué)通信工程學(xué)院 西安 710071)2(北京電子科技學(xué)院 北京 100070)

高效快速的單向 Hash 函數(shù)是當(dāng)前安全技術(shù)研究的熱點。文章采用神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)造了一種 Hash 函數(shù)，由 Logistic 映射和 Chebyshev 映射結(jié)合起來的雙混沌系統(tǒng)產(chǎn)生該神經(jīng)網(wǎng)絡(luò)的參數(shù)，將明文信息逐塊進行處理，并最終通過異或產(chǎn)生 128 bit 的 Hash 值。經(jīng)實驗數(shù)據(jù)和仿真分析可知：文章提出的方案滿足單向 Hash 函數(shù)所要求的混亂和置換特性，并且具有很好的弱碰撞性和初值敏感性；另外，該方案結(jié)構(gòu)簡單容易實現(xiàn)。

雙混沌系統(tǒng)；Hash 函數(shù)；神經(jīng)網(wǎng)絡(luò)；Logistic 映射；Chebyshev 映射

1 引 言

隨著電子商務(wù)的迅速發(fā)展，單向 Hash 函數(shù)在以公鑰密碼技術(shù)、數(shù)字簽名、完整性驗證、身份認證和動態(tài)口令鑒別等為代表的安全技術(shù)中得到了廣泛的應(yīng)用[1,2]。傳統(tǒng)的單向 Hash 方法有MD2、MD5 和 SHA 等標(biāo)準(zhǔn)[3,4]，但它們多數(shù)基于復(fù)雜度假設(shè)，需要進行大量復(fù)雜的異或等邏輯運算[5,6]。近年來，利用混沌系統(tǒng)的確定性和對初值的敏感性來構(gòu)造密碼算法已經(jīng)成為國內(nèi)外研究的熱點[7-9]。其中，基于混沌的 Hash 函數(shù)能很好地解決傳統(tǒng) Hash 函數(shù)運算量的問題，但是基于單一混沌系統(tǒng)的 Hash 函數(shù)構(gòu)造的方案還存在一些不足：基于某些特定混沌系統(tǒng)來實現(xiàn)的 Hash 函數(shù)的構(gòu)造可以利用各種混沌預(yù)測技術(shù)成功地破譯和提取信號[10]，保密性能并非完美，而且在實際實現(xiàn)過程中受處理器字長精度的限制，混沌映射本身所產(chǎn)生的混沌序列也會退化為周期序列[11]。為了避免出現(xiàn)上述弊端，充分發(fā)揮混沌映射的優(yōu)點，本文采取將兩種混沌映射結(jié)合在一起產(chǎn)生系統(tǒng)參數(shù)的構(gòu)造方法，并且將混沌系統(tǒng)產(chǎn)生的參數(shù)在使用中與明文相結(jié)合進行不斷地更新，避免出現(xiàn)混沌映射逐漸退化成為周期序列的弊端。理論分析和實驗仿真證明，本文提出的方案具有很好的混亂置換特性和弱碰撞性，具有擴展研究的實際意義。

2 預(yù)備知識

在本節(jié)中就本文所用到的基本知識進行介紹，以便在下述小節(jié)中進行 Hash 函數(shù)的構(gòu)造。

2.1 Logistic 映射

一維 Logistic 映射從數(shù)學(xué)形式上來看是一個非常簡單的混沌映射，它具有極其復(fù)雜的動力學(xué)行為，運算速度快，方程反復(fù)迭代可以產(chǎn)生較好的混沌序列，而產(chǎn)生的混沌序列對初始狀態(tài)和系統(tǒng)參數(shù)極其敏感，在保密通信領(lǐng)域中的應(yīng)用十分廣泛，其數(shù)學(xué)表達公式如下：

圖 1 Logistic 映射的分叉圖Fig. 1. The diagram of Logistic map bifurcation

2.2 Chebyshev 映射

Chebyshev 映射是一種簡單卻十分有效的以階數(shù)為參數(shù)的混沌序列映射。令 Tn(x)＝cos(n. cos—1(x))，則 Tn(x)稱為 n 階第一切比雪夫多項式(Chebyshev)。它有下列性質(zhì)：

圖 2 Chebyshev 多項式(T0—T4)的圖象Fig. 2. The diagram of Chebyshev polynomials

3 雙混沌系統(tǒng) Hash 函數(shù)的構(gòu)造方法

3.1 雙混沌系統(tǒng)的構(gòu)造方法

從混沌映射中生成的混沌序列有實值序列和二值序列兩種。前者是混沌映射軌跡點集合的子集形成的序列。后者通過定義一個閾值，從實數(shù)值的混沌序列中得到。本文的雙混沌系統(tǒng)產(chǎn)生的混沌序列是一個實值序列。

分別用 Logistic 映射與 Chebyshev 映射，各自通過迭代得到一組混沌實值序列，將這兩個新序列按位異或，形成一組新的序列。新序列也是一個實值序列，也具有相應(yīng)的混沌特性[12]?；煦缧蛄挟a(chǎn)生的原理圖如圖 3。

3.2 單向 Hash 函數(shù)的整體構(gòu)造

本文設(shè)計的 Hash 函數(shù)方案首先將明文進行填充并分塊，每次處理明文的256 比特，將每次得到的 Hash 值迭代到系統(tǒng)神經(jīng)網(wǎng)絡(luò)的參數(shù)矩陣中，從而保證每塊明文得到的 Hash 值都能與前面所有的參數(shù)和明文相關(guān)，以保持系統(tǒng)的初值敏感特性。最終的 Hash 值則是所有明文塊 Hash 值的異或。本算法的整體框架圖如圖 4 所示。

本方案的具體設(shè)計步驟：

圖 3 雙混沌系統(tǒng)的構(gòu)造原理圖Fig. 3. The construction of double chaotic maps

圖 4 本文 Hash 算法的整體設(shè)計框架Fig. 4. The construction of our Hash function

(1)首先選取適當(dāng)?shù)膮?shù)，通過雙混沌系統(tǒng)進行迭代(注意該參數(shù)必須滿足使得迭代后產(chǎn)生的值滿足混沌特性)，從至少 500 次以后開始取出迭代值記為 X1, X2,…, X512，將這 512 個迭代值按順序排列作為神經(jīng)網(wǎng)絡(luò)中的參數(shù)。其中X1, X2,…, X256作為第一個矩陣 A 的初始值，X257, X258,…, X512作為第二個矩陣 B 的初始值。其中， A 矩陣需要不斷的通過輸出進行更新，在第四步中我們將會給出詳細的更新規(guī)則。

(2)將待 Hash 的明文進行填充，將其填充成 256 bit 的整數(shù)倍，填充方法和現(xiàn)行的 SHA-3 類似，主要是為了方便明文塊處理，每次均以256 bit 進行處理。將填充后的明文進行分組 M1, M2,…, MN, Mi為 256 bit。

(3)輸入 256 bit 作為一塊明文 Mi。將其分為m1, m2,…, m16，mi(i＝1,2,…,16)，每一個 mi是 16 bit，將其除以 216，變成 0～1 之間的小數(shù)，記為。

(4)將明文塊 Mi進入神經(jīng)網(wǎng)絡(luò)的單元，即對進行如下操作：

注意：為了避免混沌序列由于計算機精度的影響進入周期循環(huán)，在此對矩陣 A 進行不斷地更新。更新方法是將每次第二步產(chǎn)生的結(jié)果 y1, y2,…, y16代入 A 中，使得 A 中所有的列均向右移動一列，最右邊一列舍棄，這樣 A 矩陣的第一列便被替換為 {y1, y2,…, y16}T。

4 對于 Hash 函數(shù)的有效性分析

4.1 文本 Hash 結(jié)果

取初始文本為“If I were a boy again and gentle as courage, nothing so cruel and pitiless as cowardice,” says a wise author. We too often borrow trouble, and anticipate that may never appear.” He fear of ill exceeds the ill we fear.”dangers will arise in any career, but presence of mind will often conquer the worst of them. Be prepared for any fate, and there is no harm to be feared. If I were a boy again, I would look on the cheerful side, life is very much like a mirror if you smile upon it, it smiles back upon you; but if you frown and look doubtful on it, you will get a similar look in return.”文本 1 將文本中的 If 變成 1f，文本 2 將文本中的 feared 改成 freaed，文本 3 將文本 again后面的“,”改成“.”。文本 4 將文本中的 upon改成 on。5 個文本的 Hash 結(jié)果用 16 進制表示結(jié)果如下：

原文本：81CAFD161CEDFDE44D3D7BB40A2E FD17

文本 1：1B2FC1BE6B94AFBD4740D76D9F9B8449

文本 2：98B8C56C7B33F8153A4C06E6A173669F

文本 3：50EFD2AC96C78A123E52538A4429E49B

文本 4：B82FFFDCEC4097556998B0ABC8A08563

用 0,1 序列的圖形化表示，如圖 5 所示。

圖 5 5 次 Hash 值的 0,1 序列圖形Fig. 5. The fi ve Hash values of sequence on 0 bit and 1bit

4.2 Hash 值的混亂與擴散性質(zhì)的統(tǒng)計分析

為了隱藏明文消息的冗余度，Shannon 提出了混亂與擴散的概念，加密體制中要求充分且均勻的利用密文空間，Hash 函數(shù)同樣要盡量做到相應(yīng)明文對應(yīng)的 Hash 密文不相關(guān)。因為結(jié)果用二進制表示，每比特只有 1 或 0 兩種可能，因此理想的 Hash 的擴散效果應(yīng)該是初值的細微變化將導(dǎo)致結(jié)果的每比特都以 50% 的概率變化。

我們采用的測試方法是：在明文空間中隨機地選取一段明文求其 Hash 值，然后改變明文 1比特的值得到另一 Hash 結(jié)果，比較兩個 Hash 結(jié)果求出變化的比特數(shù) Bi。一共進行 N 次類似的測試，可畫出相應(yīng)的比特變化數(shù)分布圖：圖 6 表示N 為 2048 次時相應(yīng)的比特變化數(shù)分布圖。

圖 6 2048 次 bit 變化數(shù)的分布圖Fig. 6. The distribution of 2048 bits

從圖 6 可以看出，明文 1 比特變化所引起的Hash 值實際變化的比特數(shù)非常集中地分布在理想狀態(tài)的變化數(shù) 64 比特附近，表明該算法具備很強的混亂與擴散能力。為了進一步闡明該算法的功能，我們定義以下的四個統(tǒng)計量。

分別經(jīng) N＝128, 256, 512, 1024, 2048 次測試，得到本算法的實驗數(shù)據(jù)如表 1 所示。

從表 1 中的數(shù)據(jù)可以看出，本算法的平均變化比特數(shù)和每比特平均變化概率都非常接近理想狀態(tài)下的 64 比特和 50%，相當(dāng)充分和均勻地利用了密文空間，從統(tǒng)計效果上保證了攻擊者無法在已知一些明文密文對的情況下偽造或反推出其他的明文密文。另外，和很小，表明本算法 Hash 的混亂和擴散性能相當(dāng)穩(wěn)定。

4.3 抵抗碰撞和生日攻擊性分析

我們將任意改變 1 比特得到的 2048 個 Hash值進行統(tǒng)計分析，其中這 2048 個值都以 16 進制保存。我們統(tǒng)計其在相同位置上對應(yīng)的字符相等的個數(shù)，經(jīng)仿真，統(tǒng)計結(jié)果的分布為：n(0)＝258，n(1)＝553，n(2)＝613，n(3)＝369， n(4)＝174，n(5)＝75，n(6)＝19，n(7)＝7，n(8)＝0，并且超過 8 個字符相等的 Hash 值數(shù)目均為0，其具體的字符統(tǒng)計分布圖如圖 7 所示。

圖 7 相同位置有相同字符的 Hash 值統(tǒng)計Fig. 7. The Hash value of the same char in the same location

我們通過以下的實驗來定量地測試本算法的抗碰撞能力[13]：在明文空間中隨機地選取一段明文求出并以 ASCII 碼形式存儲其 Hash 值，然后隨機地選擇并改變明文中 1比特的值得到另一新的 Hash 結(jié)果，同樣以 ASCII 碼形式存儲其 Hash值。比較兩個 Hash 結(jié)果，記錄在相同位置上有相同值得 ASCII 碼字符的數(shù)目，并且利用公式計算兩個 Hash 值的絕對差異度。其中，和分別是原始 Hash 和新的 Hash值的第 i 個 ASCII 碼字符，而函數(shù) t(*)將 ASCII碼字符轉(zhuǎn)化為它們相應(yīng)的十進制數(shù)值。我們在Logistic 映射 μ＝3.7 初始值 x0＝0.5，Chebyshev映射初始值為 x0＝0.2 的參數(shù)下，做了 2048 次實驗，得到 d 的最大值、最小值、平均值和平均每個字符的差異度列于表 2 中。由表可得，該算法的抗碰撞性能良好。

表 1 混亂與擴散性能實驗Table 1. The result of experiment on diffusion and confussion

表 2 兩個 Hash 值的絕對差異度Table 2. The absolute difference degree of two Hash values

4.4 與 SHA-3 算法的性能比較

通過上述小節(jié)的分析，我們可以看出本算法與 SHA-3 算法類似，均可以滿足 Hash 函數(shù)的基本特征，同時相對于 SHA-3 算法，該算法主要優(yōu)點體現(xiàn)在以下兩點：第一，本算法引入了混沌映射，具有更好的混亂和擴散特性；第二，目前還沒有很好的針對于混沌映射的量子攻擊算法，而該算法可以抵抗量子攻擊。但由于該算法在參數(shù)生成過程中加入了混沌映射，使其與 SHA-3算法的效率相比還有一定差距，因此我們下一步工作的重點就是針對算法的效率問題做進一步的改進。

5 小 結(jié)

本文提出了一種基于神經(jīng)網(wǎng)絡(luò)的雙混沌Hash 函數(shù)的構(gòu)造方法，其中神經(jīng)網(wǎng)絡(luò)的參數(shù)由Logistic 映射和 Chebyshev 映射結(jié)合起來的雙混沌系統(tǒng)產(chǎn)生，具有更加廣泛的密鑰空間，并且混沌特性更好。將初始值通過這種雙混沌系統(tǒng)進行迭代產(chǎn)生神經(jīng)網(wǎng)絡(luò)的參數(shù)，明文以 512 比特分塊讀入，使用每次產(chǎn)生的 Hash 值去逐步更新神經(jīng)網(wǎng)絡(luò)的參數(shù)，從而使每次的 Hash 結(jié)果都與前面所有的明文和參數(shù)相關(guān)，這一特點使得本方案的系統(tǒng)具有天生強化雪崩效應(yīng)的能力，更加確保了最終 Hash 值的每一比特都與消息的所有比特相關(guān)，消息或者初始值的微小變化，通過迭代過程不斷的擴散放大，最終導(dǎo)致完全不同的 Hash 結(jié)果。經(jīng)過理論分析和實際仿真驗證，本方案構(gòu)造的單向 Hash 算法滿足 Hash 算法要求的初值敏感性、不可逆性和弱碰撞性等特點。并且采用分塊執(zhí)行的方案能保證迭代步數(shù)與初始文本長度基本是成正比關(guān)系，具有較高的效率，具有成為一種快速使用的單向 Hash算法的潛力。

[1] Kou WD. Network Security and Standards [M]. Boston: Kluwer Academic Publishers, 1997.

[2] Pieprzyh J, Sadeghiyan B. Design of Hashing Algorithm [M]. Berlin: Springer-verlag, 1993.

[3] Rivest R. The MD5 Message-Digest Algorithm [Z]. MIT Laboratory for Computer Science and RSA Data Security, Inc.

[4] FIPS PUB 180-1. SHA-1 Standard, Secure Hash Standard [S].

[5] Wang SH, Li D, Zhou H. Collision analysis of a chaos-based hash function with both modification detection and localization capability [J]. Communications in Nonlinear Science and Numerical Simulation, 2012, 17(2): 780-784.

[6] Wang SH, Hu G. Coupled map lattice based hash function with collision resistance in single-iteration computation [J]. Information Sciences, 2012, 195: 266-276.

[7] Wang Y, Liao XF, Xiao D, et al. One-way hash function construction based on 2D coupled map lattices [J]. Information Sciences, 2008, 178(5): 1391-406.

[8] Akhavan A, Samsudin A, Akhshani A. Hash function based on piecewise nonlinear chaotic map [J]. Chaos, Solitons & Fractals, 2009, 42(2): 1046-1053.

[9] Xiao D, Shih FY, Liao XF. A chaos-based hash function with both modification detection and localization capabilities [J]. Communications in Nonlinear Science and Numerical Simulation, 2010, 15(9): 2254-2261.

[10] 韓敏. 混沌時間序列預(yù)測理論與方法 [M]. 北京:中國水利水電出版社, 2007.

[11] 張家樹, 肖先賜. 用于混沌時間序列自使用預(yù)測的一種少參數(shù)二階 Volterra 濾波器 [J]. 物理學(xué)報, 2001, 50(7): 1248-1254.

[12] 趙芮, 王慶生, 溫會平. 基于二維 Logistic 與Chebyshev 映射 AES 混沌加密算法 [J]. 信息安全, 2008, 24(11): 43-45.

[13] Wong KW. A combined chaotic cryptographic and hashing scheme [J]. Physics Letters A, 2003, 307(5-6): 292-298.

A Dual Chaotic Hash Function Based on Cellular Neural Network

LIU Hui1,2ZHAO Geng1,2BAI Jian1,2

1( School of Telecommunications Engineering, Xidian University, Xi’an 710071, China )2( Beijing Electronic Science and Technology Institute, Beijing 100070, China )

The Hash function with hig h speed and ef fi ciency has been a hotspot of security. In this paper, a new Hash function based on cellular neural network was proposed. The parameters of the cellular neural network were produced by a unique system which combined the Logistic map with the Chebyshev map. The function can handle the plaintext by the block, and the fi nal 128 Hash value is the xor of every block’s Hash value. The experimental data and simulated analysis show that the proposed algorithm can satisfy the requirements of a secure hash function, and it has some good properties such as diffusion, confusion, weak collision and sensitivity to initial conditions. What’s more, the construction of the scheme can be achieved easily.

double chaos system; Hash function; cellular neural network; Logistic map; Chebyshev map

TN 918

A

2013-10-12

國家自然科學(xué)基金(NO61170037)。

劉慧，碩士研究生，研究方向為混沌公鑰和信息安全；趙耿(通訊作者)，教授，研究方向為混沌密碼理論及其應(yīng)用和計算機信息安全及保密，E-mail：zg@besti.edu.cn；白健，碩士研究生，研究方向為密碼學(xué)和格理論。