基于细胞自动机的Hash函数方法

1、2010年第12期,第43卷 通 信 技 术 Vol.43,No.12,2010 总第228期 Communications Technology No.228,Totally基于细胞自动机的Hash函数方法张传武(西南民族大学 电气信息工程学院,四川 成都 610041【摘 要】Hash函数的设计中,不仅要求Hash算法具有较好的混乱和扩散性、弱碰撞性,而且要求算法实现的高速性。提出了一种基于规则90细胞自动机的Hash函数方法,采用具有二叉树型状态转移的规则90细胞自动机作为Hash函数方法的迭代函数。实验与分析表明,这种构造方法在具有一般Hash函数较好混乱和扩散性、较安全的碰撞性,同时

2、由于细胞自动机结构内在适合于VLSI的结构和并行的信息处理机制而具有其他Hash方法无法比拟的速度优势。【关键词】Hash函数;细胞自动机;二叉树型状态转移【中图分类号】TN918 【文献标识码】A【文章编号】1002-0802(201012-0123-03 Hash Function based on Cellular AutomataZHANG Chuan-wu(CEIE, Southwest University for Nationalities, Chengdu Sichuan 610041, China【Abstract】In the design of an efficient

3、Hash function, it is required that the Hash function must have fairly good confusion, diffuse, low collision, and high-speed implementation as well. This paper proposes a cellular automata-based Hash function, which adopts rule 90 cellular automata with binary tree state transition as the iteration

4、function of the Hash. Simulation results indicate that this method has the characteristics of good confusion, diffuse and low collision, including the advantages of high-speed implementation.【Key words】Hash function;cellular automata;binary tree state transition0 引言Hash函数是在20世纪50年代引入的技术,它将一个任意长度的消息映

5、射为一个固定长度的消息摘要。Hash函数最早用于检测消息传输中由于噪声而发生的随机错误,后来主要用于检测消息传输中人为的错误或杜撰的消息。基于Hash 函数消息认证应用迅速发展,广泛用于包括消息认证、口令检查、软件保护、构造加密算法等领域。目前应用广泛的MD5、SHA-1函数是基于复杂度假设而设计的,需要进行大量的异或等逻辑运算或采用分组加密方法多次迭代1,从而具有运算量大、实现复杂的缺点。同时在新兴的基于混沌映射的Hash函数构造中2,由于采用基于浮点运算的算法,大大增加了实现的复杂度,从而影响了Hash函数的速度。所以,如何从结构上来提高Hash 函数实现速度已成为Hash函数设计需要解决

6、的一个重要问题,即解决Hash函数的高速实现问题3。针对上述问题,提出了一种基于二叉树型状态转移结构的细胞自动机的Hash函数方法。1 基于细胞自动机的高速Hash函数细胞自动机具有组成单元结构的简单规则性、单元之间作用的局部互连性和信息处理的高度并行性等优点,并表现出复杂的功能。细胞自动机的这些特点使其尤其适合于VLSI 的高速实现。实际中的Hash函数是建立在压缩函数上,在细胞自动机中,有一类能系统构造的具有二叉树型状态转移的细胞自动机4可以用于Hash函数的构造(这里讨论无密钥Hash函数。由于二叉树型状态转移结构的细胞自动机在每一步状态迭代都具有信息损失,使得原始序列的信息在迭代过程中

7、逐渐减少,但由于实际消息的迭代次数不可能为无穷大,因此获得的Hash函数值在保留一定信息量的同时具备了无法通过反向计算获得其原始信息固有特性。同时,由于细胞自动机所特有的基于比特的、适合于VLSI实现的并行处理结构5,所以具有比基于混沌迭代和基于移位寄存器的传统方法来构造Hash函数更具有优势。目前传统的Hash函数构造方法为:分段(输入数据以收稿日期:2010-02-22。作者简介:张传武(1971-,男,博士,教授,主要研究方向为信息处理、细胞自动机、计算机通信网。123某种特定的方式进行补位后分成多个长度相同的数据段、初始化(Hash中间值的初始值以某种方式事先确定、迭代(,i nf函数

8、作用于第i个分段数据和得到的Hash中间值,一般每个数据段只使用一次、结果(将最后一次的迭代结果作为Hash值输出,但有时也可以使用一定的数据压缩方法,即只将其中部分或其变换作为最后的Hash值输出。利用能产生二叉树型状态转移的规则90细胞自动机作为Hash函数 图1 Hash函数构造方法其算法描述如下:取2N-1个单元的具有二叉树型状态转移结构的规则90细胞自动机,并将信息的奇偶计数位补充为Hash函数的值,即构成2N位的Hash输出值(其插值的位置可以由一初始值给定;输入数据和密钥,并将其进行分组和填充,其中密钥为输入的重复,而数据的填充可以采用不同方法(本例采用简单的在后附加“ABC”等

9、ASCII码;对数据进行交织处理,以便于信息的散布;数据与上一组的迭代值异或后进行迭代运算;迭代中需要比较迭代值是否为迭代函数的奇异点(如线性规则的细胞自动机为全0状态,如果是则加载进行重新迭代;进行相应组数的迭代运算后的迭代值与数据的奇偶校验位组合得到Hash函数值。2 性能分析与算法仿真2.1 文本Hash结果对上述单向Hash函数构造算法中确定N=8的规则90细胞自动机作为迭代函数进行计算机仿真,取文本为“In the 1980s, S. Wolfram simplified its architecture and resulted the characteristics of sim

10、ple structure of elements, local interaction of elements, parallel processing of information, and complex global properties 1,2.”。当密钥为“firste”时的Hash函数值为“0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0

11、 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 10 0 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1

12、1 0 0 1 0 1 1 0 0 0 1 11 0 0 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0”。情况一,将初始文本中的开始字母“I”改为“H”即改变一个比特数据,其他条件不变时其Hash函数值为“0 1 1 10 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 01 0 0 1 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1

13、0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 10 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 0 11 1 0 1 0 1 1 0 1 1 1 0 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 10 1 0 0 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 11 1 0 1

14、0 1 1 1 1 0 1 1 1 0”。其输出的Hash函数值与原Hash 函数值相比有116 bit的变化。情况二,将初始文本中的“simple”中的字母“s”改为“r”,其他条件不变时其Hash函数值为“1 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 0 0 0

15、 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 10 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 11 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0

16、 1 0 1 0 1 0 0”。其输出的Hash函数值与原Hash函数值相比有114 bit的变化。情况三,在原文本的末尾加一个空格,其他条件不变时其Hash函数值为“1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 10 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 01 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1

17、1 1 1 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 10 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0 11 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1”。其输出的Has

18、h函数值与原Hash函数值相比有131 bit的变化。情况四,当密钥的字母“e”变为“d”,其他条件不变时的Hash函数值为“1 1 1 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 1 1

19、 0 1 1 1 00 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 0 11 1 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 11241 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0”。其输出的Hash函数值与原Hash函数值相比有1

20、14 bit的变化。从上面的数据可知,初值比特变动,结果具有很大的概率发生较大的变化,可见算法具有较好的单向性,具有较高的初值敏感性。2.2 混乱与扩散性质统计分析为了隐藏明文信息的冗余度,Shannon提出了混乱与扩散的概念,即加密体制要求充分均匀的利用密文空间。要尽量做到明文对应的Hash值不相关,而对于信息的二进制表示,每比特只能为0或1两种可能,因此理想Hash的扩散效应是初值细微变化导致Hash值50%的变换。从上面的文本的Hash实验可以看出,在文本或密钥改变一个比特的信息时,其Hash值的变化为44.531-51.171,接近于50%,具有较好的混乱和扩散性。2.3 算法的速度和

21、碰撞分析从上述Hash方法可知,算法的速度与原始消息长度有关,由于采用的是基于规则90的线性细胞自动机结构,其一次迭代只用到2次比特异或运算即模二加运算,所以对于长度为L×N(其中N为细胞自动机的单元数即对消息的分组长度比特的消息,那总共只用到2L次模二加运算,速度远远快于基于浮点数的算法。基于细胞自动机的Hash算法的高速性在于细胞自动机内在的并行处理机制和适合于VLSI实现的物理结构,采用VLSI和FPGA/CPLD的实现结构中,基于细胞自动机的方法与基于移位寄存器的方法相比具有数倍的速度优势。碰撞是指对不同的初值其Hash值相同即发生一对多映射的情况,但目前对Hash函数的碰撞

22、特性进行较系统的理论分析具有较大的难度。由于Hash函数本身是将一个不定长度的值映射为等长的值(且实际情况往往是将一个较长序列映射为较短的定长序列,所以实际关心的是Hash函数在混乱和扩散基础上对输出Hash值的分布均匀性。对于由具有二叉树型的规则90细胞自动机构造的迭代函数而言,由于二叉树型状态转移的对称性(即有一半的状态在迭代到循环点的步长是一致的最长,如果Hash函数的输入序列是均匀的话,其在轮函数的迭代下也是相对均匀的分布于这些迭代的位置,即所有的状态都相对等可能的作为Hash函数的输出值。3 结语研究了一种基于规则90的细胞自动机的Hash函数的构造方法,这种方法建立在将具有2N-1

23、个单元的二叉树型状态转移的细胞自动机作为Hash函数的迭代函数,并结合序列的奇偶校验位构成2N位Hash值输出的方法。研究表明:细胞自动机固有的适合于VLSI实现的特性和并行信息处理机制,使该方法具有其他方法无法比拟的速度优势;同时,二叉树型状态转移的细胞自动机作为Hash函数的迭代函数在一定程度上保障了该方法的安全性。参考文献1 张瀚,王秀峰,李朝晖,等.基于时空混沌系统的单项Hash函数构造J.物理学报,2005,54(09:4006-4010.2 王小敏,张家树,张文芳.基于广义混沌映射切换的单向Hash函数构造J.物理学报,2003,52(11:2737-2742.3 TOUCH J

24、D. Performance Analysis of MD5C/ACM. ACM SpecialInterest Group in Communication. Cambridge, MA, USA: ACM, 1995: 77-86.4 张传武.二叉树型结构的细胞自动机同构性构造J.计算机科学,2008,35(40:184-185/189.5 ZHANG C W. Performance Analysis of the CPLD/FPGAImplementation of Cellular AutomataC/ IEEE Computer Society. The 2008 International Conference on Embedded Software and Systems Symposia. Washington, DC, USA: The IEEE C