散列算法和Hash函数

1、赵润晓,男,1995年生,本科,E-mail:578562554 第1作者手机号码:180*,E-mail:578562554散列算法和Hash 函数赵润晓11(华中科技大学物理学院应用物理学1401班,武汉市中国430074摘要中本文介绍了散列算法和Hash 函数的原理、应用,尤其是在网络安全方面,着重研究了报文摘要方法、报文完整性确认方法。关键词散列算法;Hash 函数;报文摘要;MD5;1数据的散列1.1报文摘要网络安全是网络技术重要的一环,随着网络进入人们的日常生活,一方面淘宝等网上购物极大地改变了传统生活,另一方面货币的虚拟化也让不少犯罪分子有了可乘之机。网络安全是大学网络通识课的重

2、要一章,其中现代密码学的种种精妙展现让不少读者激动万分,秘钥算法、报文摘要和数字签名既是网络安全问题下的产物,也体现了人类理性的智慧1。报文摘要要求数据接受者可以较容易的核实报文是否被篡改。因此我们强烈要求一种映射(函数F ,对源报文M ,它应该具有如下特质2:1报文摘要F(M由映射和报文唯一给出,它应到长度小、能反映报文M 的全部信息。2当M 改变时,F(M也一定发生变化。3在计算上找不到以M,使得F(M=F(M.这样一来,满足上述要求的映射F 一旦被找到,那么数据接收方拿到M 和F(M就可以轻易地知道M 是否遭到了篡改。可是上述要求存在一些疑问,因为报文M 长度,是大大超过报文摘要的;那么

3、根据抽屉原理,一定可以找到两个不同的报文,使得它们各自的报文摘要相同。其二,“计算上”得不到F(M=F(M,具体含义是什么?该怎么实现?实际使用的报文摘要算法,散列函数到底是怎么满足上述要求的。1.2巨量数据的排序和检索3百度公司招聘时,曾有一道这样的面试题:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。,请你统计最热门的10个查询串,要求使用的内存不能超过1G 。当我们使用传统的排

4、序时,会发现要经行如此巨量的数据处理,占用内存会达到2.8G 。如果可以运用某种关键词,将查询串映射为关键词,那么资源的利用率就会大大增加。在最佳解答中,程序建立了一个哈希表,这是一个根据关键码值(Key value而直接进行访问的数据结构。数组的特点是寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。而哈希表综合两者的特性,做出了一种寻址容易,插入删除也容易的数据结构。这是怎么做到的呢?1.3散列函数事实上以上两个应用都运用了数据的散列,这是通过散列算法实现的4。简单的散列算法很容易理解,例如:有5个数12,25,30,45,50,这几个数有个规律,就是十位数都不相同。如果

5、我设置一个散列函数f (value =value/10;这样一来平常的时候,我们查找50,要比较5次(其他算法可能不同,这里用散列算法只需要1次,就是解散列函数,key=50/10=5,要找的数就在第5个位子。但是上面散列的问题还是很多的,比如说查找55呢?就会出错“因为55解散列函数之后,也是在第5个位子”,这就叫做一个冲突。当你把散列函数设置好了后,由于数据的庞大,冲突很有可能产生,那么就需要我们来处理冲突了。1.3.1除法散列法 图1余数法散列图1是以除16的余数当作关键词所做的散列,可以看到有些关键词没有放入数据,而有的关键词又集中了多个数据,说明除法散列法“散列能力”不强。1.3.2

6、斐波那契(Fibonacci散列法让数据先乘上一个与之数位相对应的斐波那契数,在进行散列,那么结果会好一些。如图2所示。 图2斐波那契散列1.3.3平方取值散列法以上的散列法都很容易构造冲突,也就是说,很容易找到一对数,他们的散列是相同的。而平方取值散列,找到的难度就提升了。我们对于一个五位数,取其平方后的第4、5、6位的值,例如594262=3531449476,取144作为特征值或者摘要。这是因为平方后的数,中间几位的数值和源数字的每一位都相关,所以当源数据有改动时,特征值总会变化。那59426为例。每一数位变化1后的特征值如图表1,可以发现任何一个微小的变化都对摘要产生了极大的变化。这就

7、得“计算上不可行”成为可行。源数据源数据平方摘要594263531449476144594273531568329156594363532638096263595263543344676334504262542781476278694264819969476996图表1微小的改变和极大地变化2Hash 函数2.1函数的特点Hash 函数是一类比较成熟的散列函数,例如MD5。Hash 函数主要用于完整性校验和提高数字签名的有效性,目前已有很多方案。这些算法都是伪随机函数,任何杂凑值都是等可能的。输出并不以可辨别的方式依赖于输入;在任何输入串中单个比特的变化,将会导致输出比特串中大约一半的比特发生

8、变化。在实际运用中,H 函数满足一下特点5:l 广适性。H 能够应用到大小不一的数据上。2规范性。H 能够生成大小固定的输出。3可操作性。对于任意给定的x ,H (x 的计算相对简单。4单向性。对于任意给定的代码h ,要发现满足H (x =h 的x 在计算上是不可行的。5抗撞击性。对于任意给定的块x ,要发现满足H (y =H (x 而y=x 在计算上是不可行的。一旦这样的Hash 被找到,那么网络安全中的完整性认证就不再是问题。2.2MD5下面介绍一种非常著名应用广泛的Hash 函数。Message Digest Algorithm MD56(消息摘要算法第五版为计算机安全领域广泛使用的一种

9、散列函数,用以提供消息的完整性保护,是计算机广泛使用的杂凑算法之一,主流编程语言普遍已有MD5实现。将数据(如汉字运算为另一固定长度值,是杂凑算法的基础原理,MD5的前身有MD2、MD3和MD4。MD5算法具有以下特点:1压缩性:任意长度的数据,算出的MD5值长度都是固定的。2容易计算:从原数据计算出MD5值很容易。3抗修改性:对原数据进行任何改动,哪怕只修改1个字节,所得到的MD5值都有很大区别。4强抗碰撞:已知原数据和其MD5值,想找到一个具有相同MD5值的数据(即伪造数据是非常困难的。MD5可以让大容量信息在用数字签名软件签署私人密钥前被"压缩"成一种保密的格式(就是

10、把一个任意长度的字节串变换成一定长的十六进制数字串。除了MD5以外,其中比较有名的还有sha-1、RIPEMD以及Haval等。2.3主流散列算法“破译”成功7MD5、SHA-1是当前国际通行的两大密码标准。据了解,MD5由国际著名密码学家图灵奖获得者兼公钥加密算法RSA的创始人Ronald L.Rivest 设计,SHA-1是由美国专门制定密码算法的标准机构美国国家标准技术研究院(NIST与美国国家安全局(NSA设计。两大算法是国际电子签名及许多其它密码应用领域的关键技术,广泛应用于金融、证券等电子商务领域。其中,SHA-1早在1994年便为美国政府采纳,是美国政府广泛应用的计算机密码系统。

11、但是这两项散列技术被中国科学家王小云相继“破译”。2004年8月,在美国加州圣芭芭拉召开的国际密码大会上,并没有被安排发言的王小云教授拿着自己的研究成果找到会议主席,要求进行大会发言。就这样,王小云在国际会议上首次宣布了她及她的研究小组的研究成果对MD5、HAV AL-128、MD4和RIPEMD等四个著名密码算法的破译结果。王小云的研究成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准MD5大厦轰然倒塌,引发了密码学界的轩然大波。这次会议的总结报告这样写道:“我们该怎么办? MD5被重创了,它即将从应用中淘汰。SHA-1仍然活着,但也见到了它的末日。现在就得开始更换SHA-1了。”

12、2005年2月7日,美国国家标准技术研究院发表申明,SHA-1没有被攻破,并且没有足够的理由怀疑它会很快被攻破,开发人员在2010年前应该转向更为安全的SHA-256和SHA-512算法。而仅仅在一周之后,王小云就宣布了破译SHA-1的消息。因为SHA-1在美国等国家有更加广泛的应用,密码被破的消息一出,在国际社会的反响可谓石破天惊。换句话说,王小云的研究成果表明了从理论上讲电子签名可以伪造,必须及时添加限制条件,或者重新选用更为安全的密码标准,以保证电子商务的安全。国际密码学家Lenstra利用王小云提供的MD5碰撞,伪造了符合X.509标准的数字证书,这就说明了MD5的破译已经不仅仅是理论

13、破译结果,而是可以导致实际的攻击,MD5的撤出迫在眉睫。王小云说,SHA-1在理论上已经被破译,离实际应用也为期不远。3展望随着主流Hash函数的“破译”成功,报文完整性确认的研究似乎陷入了瓶颈,我认为这其中有两个出路。一是改进散列算法,加强抗冲击性,比如说将多个Hash函数的优点集中;二是放弃散列算法,转而开发更先进的完整性确认方法。致谢感谢李老师的课程,把我带入了计算机网络的世界。参考文献1Hu Bing,Jiang Min,Wu Xia.Basic introduction about NetworkTechnology for college students.Publishing H

14、ouse of Electronics Industry,2013,9(in China(胡兵,江敏,吴霞.大学网络技术基础教程,20132James F.Kurose,Keith W.Ross.Computer Networking A Top-DownApproach(4th Edition.China Machine Press,2009.3Ma Rulin,Jiang Hua,Zhang Qinghua,An Improving Approach forHash-Table Fast Search.Computer Engineering and Science.2008,30(9:6

15、6-68(马如林,蒋华,张庆霞.一种哈希表快速查找的改进方法.计算机工程与科学.2008,30(9:66-684Luo Jianfeng.Hash-Table and Comparison of General SearchMechanism and Collision Solution.Shiyan Vocational Institute of Technology Journal.2007,20(5:96-98(骆剑锋.哈希表与一般查找方法的比较及冲突的解决.十堰职业技术学院学报,2007,20(5:96-985James F.Kurose,Keith W.Ross.Computer Networking A Top-DownApproach(4th Edition.China Mac