一种基于变参级联混沌的Hash函数算法

吴　涛　金建国　魏明军

1(华北理工大学现代技术教育中心　河北唐山　063009)

2(华北理工大学理学院　河北唐山　063009)

3　　　(华北理工大学信息工程学院　河北唐山　063009)

(happynat@163.com)



一种基于变参级联混沌的Hash函数算法

吴涛1金建国2魏明军3

1(华北理工大学现代技术教育中心河北唐山063009)

2(华北理工大学理学院河北唐山063009)

3(华北理工大学信息工程学院河北唐山063009)

(happynat@163.com)

A Hash Function Algorithm Based on Variable Parameter Cascade Chaos

Wu Tao1, Jin Jianguo2, and Wei Mingjun3

1(ModemTechnologyEducationCenter,NorthChinaUniversityofScienceandTechnology,Tangshan,Hebei063009)

2(CollegeofSciences,NorthChinaUniversityofScienceandTechnology,Tangshan,Hebei063009)

3(CollegeofInformationEngineering,NorthChinaUniversityofScienceandTechnology,Tangshan,Hebei063009)

AbstractA Hash function algorithm based on variable parameter cascade chaos is put forward aiming at the possible risk on the letting out of cascade chaos key and the deficiency of present Hash function. That is the status variable of another chaos system as the parameter perturbation is introduced to a Hash function cascade driving system, and the safe variable parameter cascade chaos system is realized with the control of turbulence intensity. The Hash function composed in this way not only obeys the variable parameter characteristic of chaos rules, but also possesses the feature of crosstalk step by step between the cascade subsystems. It can effectively reduce the risk of short period behavior caused by the finite computer precision and digital quantization possible, and it has great significance to improve the complexity and strong collision resistance of the compression function’s internal structure. The experimental results show that compared with other chaotic Hash algorithm and SHA-3 algorithm, this algorithm has high sensitivity to initial conditions, nice chaos and diffusion ability, strong collision resistance, simple and flexible algorithm, and strong controllability of variable parameter system; and it has a favorable prospect in the field of chaos secure communication, digital signature, etc.

Key wordscascade chaos; Hash function; parameter perturbation; Lyapunov index; anti collision

摘要针对级联混沌可能存在的密钥泄漏风险以及当前Hash函数的不足，提出了一种基于变参级联混沌的Hash函数算法，即在构成Hash函数的级联驱动系统中，引入了另一混沌系统的状态变量作为参数扰动，并在扰动强度的控制下实现安全的变参级联系统.由此构成的Hash函数不仅具有符合混沌规律的变参特性，同时还具有级联子系统间逐级串扰的性质，能有效降低由计算机有限精度和数字量化可能造成的短周期行为风险，对提高压缩函数内部结构的复杂度和抗碰撞性有着显著意义.实验结果表明：与其他混沌Hash算法和SHA-3算法相比，该算法具有高度的初值敏感性和良好的混乱与扩散性能，抗碰撞能力强，算法实现简单灵活，变参系统可控性强，在混沌保密通信、数字签名等领域具有良好的推广前景.

关键词级联混沌；Hash函数；参数扰动；Lyapunov指数；抗碰撞性

Hash函数作为数字签名等安全技术中的一个关键环节，其安全性历来广受关注.特别是2004年以来，对传统Hash函数的攻击取得了突破性的进展，MD5，SHA-1，DHA-256等Hash函数的安全缺陷被陆续公布，设计新的Hash函数成为各界广泛关注的问题.由于混沌具有高度的敏感性、遍历性和内随机性等密码学特点，因此结合混沌系统构造出高可靠性、高安全性的Hash函数，成为近年来新的研究方向和热点，并取得了一些研究成果.

如文献[1]利用斜帐篷映射在特定参数下的混沌行为构建Hash函数算法，通过多次迭代混沌方程来扩散消息变化对Hash值的影响；文献[2-3]则利用高维混沌映射的不变测度、遍历性和无倍周期分岔等特性构建安全的Hash函数，通过非线性耦合作用显著增强了消息块值对混沌状态值的扩散效应，但因算法复杂导致运算效率较低[4].除了将消息映射到相空间的方法外，文献[5]提出了一种简单的可变参混沌Hash算法，通过μ=3.9999995-ki×0.00001将明文消息调制到Logistic映射的参数空间，利用混沌系统对参数极度敏感的特性达到很好的扩散效应；文献[6]则进一步基于切比雪夫多项式算法提出了一种变参数的并行混沌Hash算法，该算法从相应消息块中动态获取可变参数，最终通过一维Logistic映射的状态值来构建Hash值；为了克服单一迭代系统可能存在的碰撞缺陷，文献[7]提出了基于复合混沌动力系统的Hash函数算法，利用二维Logistic映射的输出作为分段线性映射的分段参数，最终通过分段线性映射的多次迭代构造Hash值.文献[8-10]结合时空混沌的特性，利用其格点间耦合项的扰动作用，使系统具有更好的随机性态和扩散能力.相对于简单混沌映射的Hash函数，基于时空混沌构造的Hash函数是一个格子之间存在相互耦合作用的复杂高维混沌系统，在带来安全性的同时，也提高了算法的复杂性.上述研究对Hash函数的改进作出了重大的贡献，但仍存在一些局限.例如基于离散混沌映射的方案，存在着Lyapunov指数小、初值条件和系统参数有限等缺陷，而基于连续混沌和高维混沌映射的方案，由于其算法复杂导致产生的序列码率较低.为此，文献[4]提出了离散混沌的一种级联方案，详细研究了级联对动力学性能的改善，证明了混沌级联是改善系统随机性和复杂性的一种简单实用的方法.级联驱动的方法虽具有序列产生率高、安全性能好的一面，但也存在着潜在的安全威胁.文献[11]就指出由于构成级联系统的子系统间存在着逐级串扰，即使构成级联的各个子系统均是混沌的，但由它们构成的级联系统也有不是混沌的情况，而且级联后的系统是否混沌与构成它的子系统的序有关.

为了克服级联混沌系统可能存在的安全风险，本文提出了一种利用参数扰动项[12]改进级联混沌性能的方案，并以此构建安全可靠的Hash函数，即在构成Hash函数的级联驱动系统中引入另一混沌系统的状态变量作为参数扰动，并在扰动强度的控制下实现安全的变参级联方案.该方案的优点在于：1)构成Hash函数的级联混沌系统为混沌变参系统，Hash函数内部结构更加难以预测；2)利用逐级串扰特性增强了压缩函数各轮计算之间位模式的安全性，提高了相空间重构、回归映射及碰撞攻击的难度；3)通过参数扰动强度控制变参系统，改善了系统参数的可用空间.

1参数扰动下的变参级联混沌

1.1参数扰动下的变参级联混沌方程

以Logistic映射构成的级联混沌为驱动系统，一维ICMIC映射[13]为扰动系统构造变参级联混沌系统，系统状态方程如下：

(1)

(2)

其中，x为式(1)的变量，μ1,μ2,μ3,…,μm为式(1)的参量，σzj为参数扰动项，zj的值由式(2)获得，σ值作为扰动强度.当j=1,2,…,m时，式(1)中上一级(第j-1级)子系统的输出xj-1将作为下一级(第j级)子系统的输入，并通过式(2)的输出值zj和扰动强度σ的乘积对参数进行扰动；直到j=m时，最后一级子系统的输出xm将作为系统下一次循环的初始值，从而实现m级子系统的闭环级联驱动.

1.2扰动强度σ与Lyapunov指数分析

Fig. 1　The relationship between σ and Lyapunov index.图1　σ-Lyapunov指数关系图(a=2)

为保证式(1)不会产生溢出，规定μ∈(1.5,1.99],σ∈[-9,9]，并选取适当的σ值使式(1)在式(2)的扰动下依然保持混沌状态.以文献[11]表3,4,7提供的级联系统为例，设式(1)的初值x0=0.8，式(2)的初值z0=0.6，参数a=2，采用文献[14-15]提出的方法计算式(1)在式(2)的扰动下，其Lyapunov指数随扰动强度σ值的变化情况，如图1所示.

当σ=0时，式(1)退化为常参数级联混沌系统，其Lyapunov指数约等于-0.020 834 249 7，与文献[11]的结果一致.但随着扰动强度σ的增强，当|σ|>2后，式(1)的Lyapunov指数持续大于0，并最终稳定到1.902 368 348附近.经研究发现，只要σ的取值范围适当，经扰动后的级联系统正Lyapunov指数通常会高于或近似于未经扰动的原始级联系统(即σ=0时)，如图1所示；此外，在其他参数不变的情况下，改变扰动系统的参数a对σ-Lyapunov指数图的基本形态影响不大，但会影响正负Lyapunov指数出现时σ的取值范围，如图2～3所示:

Fig. 2　Effects of positive and negative regions of the Lyapunov index (a=0.05).图2　σ对Lyapunov指数正负区域的影响(a=0.05)

Fig. 3　Effects of positive and negative regions of the Lyapunov index (a=0.001).图3　σ对Lyapunov指数正负区域的影响(a=0.001)

可见，参数扰动项σz对级联混沌系统的动力学特性具有显著的影响.由于级联混沌存在显著的子系统间串扰特性，即使各独立子系统的Lyapunov指数均为正，整个系统最终的Lyapunov指数仍有可能出现负值[11].如果此时只对级联系统的原始参数μ1,μ2,μ3,…,μm做混沌值zj的线性叠加(即σ=1)，如图2,3所示，系统的Lyapunov指数仍会是负值，从而易造成密钥窗口的泄漏.因此，在对级联混沌系统施以变参时，应充分考虑扰动强度σ对系统动力特性的影响，选择合适范围内的值，使系统始终保持在混沌状态；同时，上述研究表明可用σ值的选取范围远比一般级联系统的原始参数μm要大得多，因此将消息明文调制到扰动强度σ上远比其调制到系统的原始参数上更有优势，相对于文献[5-7]具有更好的变参级联效果.

2Hash函数的构造

2.1压缩函数方程

设Hash值长度为LH(b)，式(1)是一个6级级联混沌，其初始参数为μ1=1.986 2,μ2=1.901,μ3=1.801,μ4=1.701,μ5=1.601,μ6=1.501；式(2)的初值和参数设为z0=0.6，a=2；由图2可知，扰动强度σ在区间[-9,9]内均可满足式(1)的Lyapunov指数大于0.以式(1)为驱动系统，式(2)为扰动系统构造基于变参级联混沌的Hash函数，其压缩函数方程为

(3)

输入：4个输入分量，依次为CVp-1，σp，χp,0，jp，其代表的物理含义分别为上一轮输出的链接变量、本轮迭代的扰动强度、式 (1)的迭代初值以及迭代起始位置；

输出：长度为LH(b)的中间链接变量CVp；最后一轮输出的链接变量CVt即为消息M的最终散列值H(M).

2.2算法描述

算法1 .变参扰动级联的混沌Hash函数算法.

Step1. 消息预处理.

将任意长度的消息明文M分割成长度为L(b)的消息块M0,M1,M2,…,Mt，分割前按文献[16]的方法对明文M进行填充，填充后M=*…*100…0Length(M)，其中*…*表示原始明文部分，Length(M)表示64 b的原始明文长度，在二者之间可填充长度为r的“100…0”位串，r的值为满足M被整数分割的最小正整数解.

Step2. 初始化赋值.

以L=8为例，将第1个消息块M0转换为对应的十进制数值D0，则χ0,0=D028，χ0,0∈[0,1).以χ0,0作为式(1)的第1轮迭代初值，令σ0=9(D0+1)28作为本轮迭代的扰动强度，式(1)在式(2)的扰动下开始迭代Y次，由于明文消息已调制到级联混沌的参数空间，此处Y=N+Nk为一常数，其中N≥300用于满足变参后的轨道分离，Nk=LH4用于产生链接变量的4 b二进制码元.此时得到消息块M0对应的Y个迭代值为

将最后Nk个输出值依次代入函数G得到对应的4 b二进制码元，即：

(4)

函数G的定义如下：

定义1. 设函数G:A→H，A={aj|j=1,2,…,Nk}，其中aj是属于[-1,1]区间的实小数；H={hj|j=1,2,…,Nk}，其中hj是4b码元对应的十进制数值.若|aj|=1，则hj=15；否则易知，总能找到一个正整数z∈[1,16]，使得(z-1)16≤|aj|

将式(4)中各码元合并成一个二进制序列CV0，即得到压缩函数的初值IV：

Step3. 生成Hash值.

从第2个消息分组M1开始，到最后1个消息分组Mt作同样的处理.以消息分组Mp为例，首先将其转换为对应的十进制数值Dp，然后需要确定本轮压缩函数的4个输入分量：

CVp-1：上一轮压缩函数的输出；

σp：作为扰动强度，σp=9(Dp+1)28，σp∈(0,9]；

χp,0：式(1)上一轮的迭代终值，即χp,0=χp-1,Y；

jp：式(1)上一轮迭代终止位置的下一级.

将CVp-1，σp，χp,0，jp代入式(3)后，以χp,0为初值、σp为扰动强度从式(1)的第jp个子系统处开始迭代，在式(2)的扰动下迭代Y次，得到消息块Mp对应的Y个迭代值如下：

同理，将最后Nk个输出值依次代入函数G得到对应的4 b二进制码元，即:

(5)

将式(5)代入式(6)，得到本轮输出的链接变量CVp.

(6)

其中XOR代表按位异或运算.至此，本轮的压缩函数计算完成.

循环重复上述过程，直到处理完最后1个分组：

(7)

则CVt即为消息最终的单向散列值.

3实验结果与分析

3.1Hash函数算例及敏感性分析

以英文版《双城记》开篇第1段为文本范例，取LH=128计算其Hash值，则Nk=32.实验通过微小改变消息内容产生新的Hash值，并与原Hash值进行比较来验证算法的敏感性，结果如表1所示.经过计算发现Hash值二进制位上1的个数在128 b散列值中占到的位数平均值为52.66%，均超过总位数的一半.同时相对于每次条件的改变，所得Hash值平均变化位数为65.5个，可见明文的每位微小变化都可以导致散列值50%以上的位值发生变化，说明算法具有高度的初值敏感性.

Table 1　The Simulation Results of Hash Function Example

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

使用文献[6]中定义的统计测试方法，通过6个统计指标Q=(H,ΔH,B,ΔB,P,ΔP)来衡量算法的混乱与扩散性质，计算方法如下：

其中，H和ΔH表示平均位分布及其均方差，B和ΔB表示平均变化位数及其均方差，P和ΔP表示平均变化概率及其均方差，N为统计次数.分别对128 b,256 b,512 b的Hash值进行混乱与扩散性质实验，每项实验又分别经过N=128,256,512,1024,2048次统计后，得到的统计结果如表2～4所示.

表2～4的测试结果表明：该算法在产生不同长度Hash值时，位分布均匀，H值均接近理想状态的50%；平均变化位数B分别为64.058，128.396，256.194，均超过Hash值长度的一半，说明消息的每位变化均可导致Hash值一半以上的位值发生变化；此外，每位平均变化概率P分别为50.054，50.156，50.038，非常接近雪崩效应的理想值50%；同时随着Hash值长度的增加，可以看到ΔH和ΔP的平均值逐渐减少，说明这2个统计量的稳定性逐渐增强，ΔB的值虽略有升高，但升幅比例较低，ΔH，ΔB，ΔP统计量的上述特征反映了Hash值性质的稳定性.

Table 2　Statistics of Hash Value (LH=128)

Table 3　Statistics of Hash Value (LH=256)

Table 4 Statistics of Hash Value (LH=512)

3.3抗碰撞性测试

抗碰撞能力是评价Hash函数安全性的另一个重要指标[3].采用文献[3]的测试方法，通过式(8)～(10)计算N次实验中相邻Hash值的单位字符平均差异度:

(8)

其中，e和e′分别对应变化前后Hash值第i个位置的字节码，函数t(e)将该字节码e转换为对应的十进制数值.

(9)

(10)

式(9)(10)中，N为统计次数，di为第i次实验结果与第i-1次实验结果比较的绝对差异度，D为相邻2个Hash值的单位字符平均差异度.实验分别对128 b,256 b,512 b的Hash值进行N=10 000次碰撞测试，得到的统计结果如表5所示：

Table 5　The Test of Anti Collision Performance(N=10 000)

表5的结果表明：在该算法下不同长度Hash值的单位字符平均差异度D分别为85.31，85.30，85.31，均接近理想状态[10]下的理论值85.333，说明算法对不同长度Hash值都具有较强的抗碰撞性.同时，其均方差值较小且彼此间相差不大，说明算法的抗碰撞性比较稳定[3].

3.4与其他典型Hash算法的比较

首先，选取近年来一些典型的混沌Hash算法作对比，表6描述了该算法与其他文献算法在同一统计量方面的性能对比.

Table 6Confusion and Diffusion of the Contrast of the Hash

Algorithms (N=10 000，LH=128)

表6Hash算法的混乱与扩散统计性能对比(N=10 000，LH=128)

从表6可以看出，在10 000次测试中， 除文献[1]外，本文算法的B值最大，即对于每位明文变化，本文算法产生的Hash值具有更好的敏感性；且每位平均变化概率为50.054%，非常接近理想状态下的50%，与文献[2-3,6]的结果比较接近，优于文献[1]和文献[10]的结果；在抗碰撞性方面，本文算法的平均差异度均值D=85.31，最接近理论值85.333.通过比较发现，本文算法体现出了较好的混乱与扩散性能，且具有很强的抗碰撞性.

其次，选取新一代Hash函数标准SHA3-512算法作为对比研究对象，表7描述了本文算法与SHA3算法的性能对比数据.

Table 7Comparison with the Performance of SHA3

Algorithm(N=10000，LH=512)

表7　与SHA3算法的性能对比(N=10000，LH=512)

从表7可以看出，本文算法在每位明文变化、平均变化概率和抗碰撞性方面比SHA-3算法更接近理想值.在运行位测试[17]方面，SHA-3算法的位分布更加平衡，略向左倾斜；而本文算法略向右倾斜，二者相差不大.在算法结构上，SHA-3算法采用了创新的“海绵引擎”[17]，计算方法上仅使用了AND，XOR，NOT等位操作模式，因此更加快速，适合于各种硬件实现；而本文算法引入了浮点运算，因此在移动终端上的计算性能略逊于SHA3算法，但本文算法充分利用了初始敏感性、内在随机性等混沌系统的固有性质，算法朴素简单，抗碰撞性更强，此外由于引入了混沌参数扰动的方法，增加了系统的复杂性，减少了由计算机有限精度而产生短周期行为的风险[18].

4结束语

本文将级联混沌技术与参数扰动方法相结合，提出了一种基于变参级联混沌的Hash函数设计方案.通过对其Lyapunov指数的分析发现，经过参数扰动后的级联混沌系统，只要扰动强度σ的取值范围适当，总可以使系统保持混沌状态，从而避免了级联混沌可能带来的密钥窗口泄漏问题[11]；同时相对于原有级联混沌的复杂参数组合，扰动强度σ不仅具有更大的取值范围，也更加易于控制.因此，将消息明文调制到扰动强度σ上远比其调制到系统的原始参数上更有优势.此外，与现有典型混沌Hash函数[1-10]相比，由于构成Hash函数的级联系统不但存在着子系统间的逐级串扰，且其参数的变化也符合混沌特性，从而使Hash函数的内部结构更加难以预测，压缩函数各轮计算之间位模式的安全性得以显著增强，为抵御现有的暴力攻击和统计分析攻击提供了保障.实验与分析结果表明，算法具有高度的单向性和初值敏感性、良好的混乱与扩散性能，抗碰撞能力强；同时算法实现简单灵活、扩展性强，具有良好的推广前景.

如何将参数扰动方法与高维级联混沌技术相结合是下一步值得深入研究的课题，此外该方法在实际应用中还有若干问题有待解决，如扰动系统本身的安全性和同步性、扰动后系统相空间的概率密度分布规律等都有待进一步研究.

参考文献

[1]Kanso A, Yahyaoui H, Almulla M. Keyed hash function based on a chaotic map [J]. Information Sciences, 2012, 186(1): 249-264

[2]Akhavan A, Samsudin A, Akhshani A. A novel parallel hash function based on 3D chaotic map [J]. EURASIP Journal on Advances in Signal Processing, 2013, 2013(1): 1-12

[3]Kanso A, Ghebleh M. A fast and efficient chaos-based keyed hash function [J]. Communications in Nonlinear Science and Numerical Simulation, 2013, 18(1): 109-123

[4]Wang Guangyi, Yuan Fang. Cascade chaos and its dynamic characteristics[J]. Acta Physica Sinica, 2013, 62(2): 111-120 (in Chinese)(王光义, 袁方. 级联混沌及其动力学特性研究[J].物理学报, 2013, 62(2): 111-120)

[5]He Tingting, Luo Xiaoshu, Liao Zhixian, et al. A new chaos mapping hash function structural method and its application[J].Acta Physica Sinica, 2012, 61(11): 164-170 (in Chinese)(何婷婷, 罗晓曙, 廖志贤, 等. 一种新的混沌映射散列函数构造方法及应用[J]. 物理学报, 2012, 61(11): 164-170)

[6]Nouri M, Safarinia M, Pourmahdi P, et al. The parallel one-way Hash function based on Chebyshev-Halley methods with variable parameter[J]. International Journal of Computers Communications & Control, 2014, 9(1): 24-36

[7]Wang Liyan, Li Zhanmei, Liu Zixin. One-way Hash function construction based on composite chaotic map[J]. Journal of Dalian University of Technology, 2013, 53(5): 742-748 (in Chinese)(王丽燕, 李占梅, 刘自新. 一种基于复合混沌映射的单向Hash函数构造[J]. 大连理工大学学报, 2013, 53(5): 742-748)

[8]Liu Jiandong. One-way Hash function based on integer coupled Tent maps and its performance analysis[J]. Journal of Computer Research and Development, 2008, 45(3): 563-569 (in Chinese)(刘建东. 基于整数耦合帐篷映射的单向Hash函数及其性能分析[J]. 计算机研究与发展, 2008, 45(3): 563-569)

[9]Xu Jie, Yang Dijie, Long Keping. Design and analysis of a cryptographic Hash function based on Time-delay chaotic system[J]. Journal of University of Electronic Science and Technology of China, 2011, 40(3): 451-455 (in Chinese)(徐杰, 杨娣洁, 隆克平. 基于时滞混沌系统的带密钥Hash函数的设计与分析[J]. 电子科技大学学报, 2011, 40(3): 451-455)

[10]Liao Dong, Wang Xiaomin, Zhang Jiashu, et al.The chaotic Hash function based on spatial expansion construction with controllable parameters [J]. Acta Physica Sinica, 2012, 61(23): 103-112 (in Chinese)(廖东, 王小敏, 张家树, 等. 基于空间伸缩结构的参数可控的混沌Hash函数[J]. 物理学报, 2012, 61(23): 103-112)

[11]Jin Jianguo, Di Zhigang, Wei Mingjun. Potential risk of variable parameter cascade chaos system[J]. Acta Physica Sinica, 2014, 63(12): 88-100 (in Chinese)(金建国, 邸志刚, 魏明军. 变参级联混沌系统中的潜在风险[J]. 物理学报, 2014, 63(12): 88-100)

[12]Li Zhenbo, Tang Jiashi. Chaotic synchronization with parameter perturbation andits secure communication scheme[J].Control Theory & Applications, 2014, 31(5): 592-600 (in Chinese)(李震波, 唐驾时. 参数扰动下的混沌同步控制及其保密通信方案[J]. 控制理论与应用, 2014, 31(5): 592-600)

[13]He Chen, He Di, Jiang Lingge, et al. A chaotic map with infinite collapses[C]Proc of IEEE TENCON 2000. Piscataway, NJ: IEEE, 2000: 95-99

[14]Wolf A, Swift J B, Swinney H L, et al. Determining Lyapunov exponents from a time series [J]. Physica D: Nonlinear Phenomena, 1985, 16(3): 285-317

[15]Briggs K. An improved method for estimating Liapunov exponents of chaotic time series[J]. Physics Letters A, 1990, 151(12): 27-32

中图法分类号TP309

通信作者：金建国(jjg1956@126.com)

基金项目：河北省自然科学基金项目(F2014209108)；河北省科技支撑计划基金项目(13210706)；唐山市科技计划基金项目(13130208z)

收稿日期：2014-10-30；修回日期：2015-04-16

This work was supported by the Natural Science Foundation of Hebei Province of China (F2014209108), the Key Technology Research and Development Program of Hebei Province of China (13210706), and the Science and Technology Project of Tangshan of Hebei Province of China (13130208z).