基于时滞混沌系统的带密钥Hash函数的设计与分析

徐 杰，杨娣洁，隆克平,2

(1. 电子科技大学光互联网和移动信息网络研究中心 成都 611731; 2. 北京科技大学计算机与通信工程学院 北京 海淀区 100083)

网络数据的完整性时刻都会受到威胁，为了确认收到的信息在传输过程中没有被攻击者插入、篡改或删除，以公钥密码、数字签名等为代表的加密安全技术已得到广泛的研究和应用。单向Hash函数作为数字签名等安全技术中的一个关键环节，目前有MD2、MD5、SHA等标准。文献[1-2]公布了对MD4、MD5、HAVAL-128、RIPEMD、SHA-1等Hash函数的碰撞攻击方法，对国际上通行的Hash函数给出了快速寻找碰撞攻击的方法，从理论上证明了基于MD5和SHA-1等算法的电子签名有被伪造的可能性。所谓碰撞，是指不同的初始文本对应的Hash映射结果相同，即发生了多对一映射。为了提高网络信息的安全性，保证数字签名的真实性，设计新的、更安全的单向Hash函数十分必要。

由于混沌系统具有初始值敏感性、遍历性和伪随机性等特点，近年来利用混沌方法构造Hash函数迅速成为新的研究方向和热点。目前国内外主要的研究方法是在原有算法的基础上，结合混沌系统构造出新的高可靠性、高安全性的Hash函数。文献[3]提出了基于前馈-反馈非线性数字滤波器构建带密钥的Hash函数。文献[4]则研究了分段线性混沌映射的Hash函数构造方法。文献[5]提出了基于RBF神经网络和混沌映射构造Hash函数的方法。文献[6]提出了利用耦合混沌映射方法构造Hash函数。文献[7]构建了基于保守混沌系统的单向Hash函数。文献[8]提出了基于耦合映像格子混沌模型的Hash函数算法。文献[9]在对复合离散混沌系统和由两个混沌映射构成的特殊复合离散混沌系统分析的基础上，建立了基于复合离散混沌系统的带密钥的Hash算法。文献[10]提出了基于二维超混沌映射的单向散列函数构造方法，但其抗碰撞性还不能达到较好的效果。文献[11]提出了基于时空混沌系统构造Hash函数的方法，但在明文填充时，仅仅填充了一些字符而并未加入明文的任何消息，仍然容易产生碰撞。但所有这些成果都推动了混沌Hash函数的研究，具有积极的意义。

在对研究现状深入分析的基础上，本文设计了基于时滞混沌系统构造带密钥的Hash函数算法。该算法利用时滞混沌系统的敏感性和遍历性，将明文消息逐比特地调制在时滞混沌系统的迭代轨迹中，并以关联了所有明文信息的一组混沌序列，结合带密钥的Hash函数HMAC-MD5认证算法，计算得出单向Hash值。理论分析和仿真实验均表明，该算法在保证了散列值的混乱性和散布性的同时，因混沌特性的加入而增大了参数空间，并使HMAC-MD5认证算法的抗穷举性得到了很大的提升，进一步增强了算法的安全性和抗碰撞性。

1 时滞混沌的系统研究

本文基于时滞混沌系统的非线性动力学特性设计Hash函数算法，该混沌系统根据时延系数的不同可以表达为不同维数的映射，系统方程表示为：

式中，a和b是实参数；un是系统n时刻的状态，其状态集合称为状态空间；u0是初始状态；N是系统维数。

系统(1)可通过如下变量转换为：

得到的N维系统方程为：

由式(3)可知系统在参数空间内具有对称性和周期性：

因此，根据该混沌系统的对称和周期特性，将研究的区域仅限制在参数空间(a,b)的a>0且b∈[0,a]的范围内。

同时，从系统方程式(3)的sin函数性质可知，该系统还具备有界性：

可见，在任何参数和任何初始条件下，系统的所有状态轨迹都是有界的，对于混沌特性的控制和应用非常有利。

文献[12-14]中，已对该时滞混沌系统的非线性动力学特性进行了深入研究。在系统参数空间内，通过对系统的稳定性研究，得到了该系统从稳定状态到混沌状态的分岔演变过程，对系统的稳定性控制和应用中的参数选取有重要作用。在系统状态空间内，已经研究了系统吸引域(或吸引盆)随参数变化的演变过程，以及作为吸引域边界的不变流形和作为混沌吸引子(或奇怪吸引子)边界的临界流形的特性。并且，由不同初始条件而引起的系统多稳定态的特性也在研究中得到了验证。

通过上述研究，可发现该系统所产生的混沌吸引子始终有界，并且受参数控制，对于该系统的实际应用非常有利。通过研究得到了该系统通向混沌的方法，对于混沌序列的选取和控制十分重要。

2 基于时滞混沌迭代的带密钥Hash函数设计原理

在对时滞混沌系统非线性动力学研究的基础上，本文设计了一种基于该混沌系统的带密钥Hash函数算法。该算法的基本思路是将明文消息M以字符为单位读取，经线性变换量化处理得到离散的明文序列C(k)，该明文序列C(k)通过时滞混沌系统进行逐字节的迭代，从而得到一组离散时滞混沌序列，对其进行带密钥Hash函数运算，即可获得定长的时滞混沌Hash值。该算法的基本设计原理如图1所示。

图1 基于时滞混沌迭代的带密钥Hash函数构造原理图

该Hash算法主要分为3个步骤：

1) 进行明文线性变换量化处理。具体方法为：对明文信息M(k)以字符为单位进行ASCII编码，得到明文信息M(k)的ASCII编码序列Asc(M(k))，其中k=1,2,…, K，K为M(k)的长度。由于ASCII码序列的值域范围为[0,255]，因此通过ASCII编码，明文消息M(k)的值域量化至[0,255]之间，利用线性公式C(k)=g+0.001Asc(M(k))对Asc(M(k))进行线性变换，g为取值范围在[12,12.545]之间的一个常数，于是得到符合时滞混沌迭代参数所要求的值域范围[12,12.8]的离散序列C(k)。

2) 对离散序列C(k)进行时滞混沌迭代，计算离散时滞混沌序列。时滞混沌系统(1)的一维系统为：

表1 离散时滞混沌序列

3) 对离散时滞混沌序列(xiK－1)(i∈[1,N+1])进行HMAC-MD5运算，获得定长的混沌Hash值。具体方法为：① 令离散时滞混沌序列(xiK－1)为HMAC-MD5算法的输入消息，即M=(xiK－1)，其中i∈[1,N+1]；② 采用列为“00110110”重复排列任意次的ipad序列与通信双方约定的密钥Key进行异或运算，得到序列S0，并采用序列为“01011100”重复排列任意次所构成的opad序列与通信双方约定的密钥Key进行异或运算，得到序列S1；③ 将序列S0与输入消息M拼接构成离散序列G0=(M|S0)，对G0进行MD5运算，得到长度为128 bit的Hash值H0=H[G0]MD5；④ 将序列S1与所得的Hash值H0拼接构成离散序列G1=(H0|S1)，对G1进行MD5运算，得到长度为128 bit的Hash值H1=H[G1]MD5。H1即为最终的时滞混沌Hash值。

3 混沌Hash函数性能分析

3.1 密钥敏感性分析

为了分析基于所设计的Hash函数算法对密钥的敏感性，针对文本信息进行Matlab仿真实验，并将密钥仅做10－6的改动，分析所得的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.

基于初始密钥和经10－6改动后的密钥，分别进行本文设计的时滞混沌Hash函数运算，所得Hash值用十六进制表示如下。

初始密钥的Hash值为：

eb953cd6dda22d7e3af675d594fa8bd4

改动后密钥的Hash值为：

a46dbf8679e198cc2853ba5c68f3e336

将上述Hash值用二进制序列图形化表示，如图2所示。

以上仿真结果表明，本文所设计的Hash函数算法对密钥具有很高的敏感性，即使密钥存在微小的差异，也会产生截然不同的Hash值。

图2 密钥存在10-6差异时的Hash值二进制对比结果

3.2 混乱与散布性质统计分析

Hash函数的设计必须遵循混乱和散布两个重要原则，尽量做到相关明文对应的Hash值不相关。对于结果的二进制表示，每比特只有0或者1两种可能，所以理想Hash值的散布效果应该是，初值的微小变化将导致结果的每比特都以50%的概率变化。因此，考察Hash认证函数的混乱与散布性质，即考察算法明文发生l bit变化情况所引起Hash密文结果变化的比特数。

混乱与散布性质的统计数字特征可由以下数据描述：

其中，N为统计次数；Bn为第n次测试时的变换比特数。

基于上述思想，本文设计的基于时滞混沌系统的Hash函数的混乱与散布性的分析统计数据计算方法为：1) 取一段长度为K的原始明文，通过Hash函数，计算出该段明文的Hash值H；2) 在该段明文的第一个字符的ASCII码上加1，得到一段新的明文，计算出新明文的Hash值H'，并比较H与H'的变换比特数，得到B1；3) 在原始明文的第2个字符的ASCII码上加1，得到一段新的明文，计算出新明文的Hash值H''，并比较H与H''的变换比特数，得到B2；4) 以此类推，最终得到B1，B2，B3，…，Bn-2，Bn-1，Bn；5) 得到Bn序列后，计算出上述描述混乱与散布性质的统计数据。

本文分别对明文长度K为250、500、1 000、6 500个字符的文字信息进行Hash函数性能统计数据运算，结果如表2所示。

表2 混沌Hash函数混乱与散布性质的统计数据

从表2可知，即使初始明文有微小的变化，本文设计的时滞混沌Hash函数算法，都将导致Hash值有将近一半的位变化。平均变化比特数和每比特平均变化率都分别趋近于理想状态下的64 bit和50%。可见，本文算法相当充分和均匀地利用了明文空间，明文的任何扰动，使得密文在统计上产生接近等概率的均匀分布，从统计效果上保证了攻击者无法在已知一些明文密文对的情况下伪造其他的明文密文。并且，△B与△P都很小，表明算法对明文的混乱与散布能力强而稳定。

4.3 抗碰撞性分析

抗碰撞性是衡量Hash函数性能的又一重要指标。对Hash函数的碰撞分析，可以通过每次改变明文的任何一个比特位，对得到的Hash值在相同位置出现相同十六进制值的情况进行统计分析，从而计算其碰撞率。本文分别对250、500、1 000和6 500次明文比特位的改变进行测试，得到Hash值在相同位置出现相同十六进制值的碰撞概率，如表3所示。总平均碰撞率为6.45%，可见，多次测试的碰撞率都非常低，说明本文算法具有很强的抗碰撞性。

表3 混沌Hash函数碰撞率

4 结 论

本文所设计的基于时滞混沌系统的带密钥Hash函数算法，利用时滞混沌系统的非线性动力学特性，将需要传送的明文信息逐字节地调制在时滞混沌迭代的轨迹中，使产生的Hash值的每个比特都与需要传送的明文信息相关。在带密钥的Hash函数运算过程中，采用HMAC-MD5算法，对密钥进行两次异或运算，加深了攻击者破译的难度。

理论分析和仿真结果表明，本文设计的Hash函数算法对密钥有高度的敏感性，即使密钥的微小变化都将导致所得到的Hash值产生巨大的变化。可见该算法能有效地抵御线性分析，并具有更大的密钥空间和更高的安全性。并且，在混乱与散布统计分析以及抗碰撞性分析中，各项性能测试结果都趋近于理想值，表明该算法对明文的混乱与散布能力强而稳定，且具有很强的抗碰撞性。因此，本文设计的基于时滞混沌系统的Hash函数算法具有很好的安全性和抗碰撞性，在数字签名、数字水印等认证技术中具有很好的应用前景。

本文研究工作得到电子科技大学青年基金(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] 李红达, 冯登国. 复合离散混沌动力系统与Hash函数[J].计算机学报, 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] 彭飞, 丘水生. 基于二维超混沌映射的单向散列函数构造[J]. 物理学报, 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] 刘光杰, 单梁. 基于时空混沌系统构造Hash函数[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.

编 辑 漆 蓉