哈希函数的应用辨析

摘要：分析和对比了哈希函数在信息安全、数据结构和数据挖掘等领域的应用，找出了它在不同领域里所呈现的特点和要求：信息安全领域里的单向性、随机性和无碰撞性，数据结构里尽可能减少碰撞、但不能避免碰撞，而数据挖掘里用于任务分配时则要求均匀碰撞。这为相关课程的教学提供了一些有益的参考，便于澄清一些模糊、混淆的认识。

关键词：哈希函数；信息安全；数据结构；数据挖掘

中图分类号：TP309 文献标识码：A 文章编号：1009-3044（2013）34-7741-02

哈希函数是把任意长度的输入通过一定的算法，变换成固定长度的输出，该输出就是哈希值。哈希函数在信息技术领域得到了广泛的应用，在信息安全、数据结构和数据挖掘类课程都涉及到了哈希函数。由于应用领域的不同，哈希函数呈现出了不同的特性和使用方法，但相关课程在讲述哈希函数时，常常只分析哈希函数在本类课程中的特点和应用，而对其在其他领域里的应用情况闭口不谈，以至于学生们常常感觉很困惑，不知道这门课的哈希函数和那门课的哈希函数之间到底有什么关系，是否相同或者不同之处在于什么地方。该文将结合哈希函数在信息安全、数据结构和数据挖掘等领域的应用来分析它所表现出的不同特征及其原因，以便能更好地理解和掌握哈希函数。

1 哈希函数在信息安全技术中的应用

在信息安全技术领域，哈希算法是现代密码体系中的一个重要组成部分，特别是在数字签名技术中得到广泛应用。在数字签名协议中，哈希函数扮演了一个非常重要的角色。假定A要向B发送一个签名的消息，签名发送方A首先利用哈希函数H计算出消息M的哈希值H（M），然后用自己的私钥Kd对哈希值H（M）进行加密，就得到数字签名Sig=EKd（H（M））；随后把数字签名Sig连同消息M一起，发送出去。签名接收方B收到复合的消息之后，把签名Sig提取出来，然后用A的公钥Ke对签名解密得到一个哈希值H”=DKe（Sig）；同时B还利用哈希函数H计算所收到消息的哈希值H’=H（M’）。如果H’=H”，则证明消息确实是A产生的，并且在传送过程中未被篡改。

从上面的分析中可以看出，哈希函数实际上把对大量数据的保护和认证问题转换成为对一小段固定长度的数据，即哈希值的保护和认证。因此，哈希值必需和所发送的消息之间建立一一对应的关系，而且这种关系应该是无法预测，这样才能和公钥算法一块实现数字签名的身份认证和防篡改的功能。这实际上就是对哈希函数提出了单向性、随机性和无碰撞的要求。在这里单向性和随机性都是为了防止攻击者有目的地利用消息的哈希值去寻找另一个不同的消息、但却具有相同的哈希值，从而达到篡改消息而不被发现的效果，也就是说故意制造碰撞。哈希函数实际上可以看成是一个原像集合到像集合的一个映射，由于原像集合的数据可以是任意长度，而像集合的哈希值却是固定长度的，所以这肯定是多对一的映射，即便单向性和随机性都得到了满足，碰撞在理论上仍就是不可避免的，这将严重危及数字签名的合理性。因此用于信息安全领域的哈希函数值都必需满足一定的长度，如MD5和SHA-1，其哈希值长度分别为128位和160位，这样像集合的大小将分别达到2128和2160；采用生日攻击，找到一对碰撞的计算量分别达到O（264） 和O（280），这对现有的计算能力来说在合理的时间内是难以实现的。即便这样，MD5由于其哈希值长度相对较短，已经被认为是不安全的而逐渐被淘汰，新的哈希函数也在陆续推出中，其哈希值更长，找到碰撞的难度会更大。由此可见，在信息安全技术领域，利用哈希函数对消息进行映射得到的哈希值概要地反映了该消息的某种唯一特性，这也是为什么哈希值在信息安全领域也被称为消息摘要的原因；相应地，对哈希函数的无碰撞性有非常严格的要求，因此所采用的哈希值长度也较长。

2 哈希函数在数据结构中的应用

在讲数据结构中的哈希函数的应用时，就必须提到哈希表。哈希表是一种数据结构，它可以提供快速的插入操作和查找操作。哈希表是根据关键码值（Key value）而直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数就是哈希函数，存放记录的数组叫做哈希表。由于数组容量有限，因此由哈希函数定义的从关键码值构成的原像集合到像集合，亦即哈希表的映射也是多对一的映射，而且发生碰撞的可能性很大——此时的像集合的大小远远小于前面提到的应用在信息安全领域的哈希函数像集合的大小，如MD5的2128和SHA-1的2160。这样一来，对不同的关键词可能得到同一哈希地址，这将影响哈希表的查找效率。图1很清楚地表明了这一现象，从中可以看到在这个哈希表里，对于0、1、10、11、12以及15这几个位置，每个位置都装了多个数据，即这几个位置都发生了碰撞。

由此可见，在数据结构里，由于哈希函数的像集合相对较小，导致碰撞是非常可能发生的。在数据查找过程中，关键码的比较次数，取决于产生碰撞的多少：产生的碰撞少，查找效率就高；产生的碰撞多，查找效率就低。因此，影响产生碰撞多少的因素，也就是影响查找效率的因素。影响碰撞多少的因素主要包括哈希函数的随机性、处理碰撞的方法以及哈希表的装填因子等。因此，在数据结构里，对于哈希函数本身而言，由于其生成的哈希值长度较短，并不能保证无碰撞性；而且由于哈希表是为了方便存储和操作，对哈希函数的单向性也没有什么太严格的要求，主要是要保证其良好的随机性——这也是为了减少碰撞。这显然和信息安全领域里所用到的哈希函数有共同的地方，如对随机性的要求；但也有不同的地方，如对单向性和无碰撞性要求的严格程度是完全不一样的。另外在数据结构里，哈希值主要和存储地址相关联，此时显然就不能再把哈希值称为消息摘要或者数据摘要了。

3 哈希函数在数据挖掘中的应用

Map-reduce是Google提出的一个软件架构，用于大规模数据集（大于1TB）的并行运算。在数据挖掘特别是大数据的分析处理中，Map-reduce正得到了越来越广泛的应用。用户需要编写两个函数：Map函数和Reduce函数，而系统将管理并行运算，协调负责执行Map或者Reduce的任务，同时也处理可能发生的任务节点的宕机。

Map-reduce运行的步骤是：

1） 各个Map任务从一个分布式文件系统中获得一个或者多个数据块，这些任务再利用用户编写的代码把数据块映射成一系列的（key，value）对；

2） 一个主控制器收集从各个任务输出的（key，value）对并且按key值进行排序；然后把这些key在所有的Reduce任务中进行分配，具有相同key值得（key，value）对就会被分配到同一个Reduce任务中；

3） Reduce任务一次处理一个key值，然后把具有相同key值的输出按用户编写的代码结合在一起。

不管Map和Reduce是怎么样的任务，第（2）步实际上就是一个分组和聚合的过程。主控制器进程知道有多少Reduce任务，比如有r个（r的值通常由用户来设定）。主控制器通常利用一个哈希函数作用于key，然后产生一个从0到r-1的编号。每个key被取哈希值后，相应的（key，value）对就被输出到r个本地文件中的一个；每个文件都由一个Reduce任务来处理。由此可见，哈希函数在这里起到的是一个任务分配的作用，并且要尽可能均匀，以便实现各个Reduce节点负荷的均匀分配；这样每个Reduce节点分配的任务量都大体相当。如果key的数目小于Reduce节点的数目，就无法做到均匀分配。但实际上在大数据分析处理中，通过合理地

设计都可以让key的数量大于Reduce节点的数量。从上面的分析中可以看出，在Map-reduce中哈希函数作用于key后必然要产生碰撞，只是希望碰撞要尽量均匀分布；也就是对哈希函数的随机性有要求，而对哈希函数的单向性、无碰撞性并没有要求，和前面信息安全、数据结构中的要求明显就不一样了。显然，哈希值在这里也不应该被称为消息摘要或者数据摘要，它只是代表了进行任务分配的编号而已。

4 结束语

从以上分析可以看出，哈希函数在信息安全、数据结构以及数据挖掘等应用领域里起到的作用并不相同：或者把消息一一映射成摘要，或者把数据映射到地址，或者实现任务的均匀分配。因此信息安全领域最为严格，强调哈希函数的单向性、随机性和无碰撞性；数据结构里则主要强调尽量减少碰撞，而在数据挖掘里进行工作分配时关注的是碰撞的均匀性。所以也不能笼统地认为哈希值就是消息或者数据摘要，它在不同领域里也相应地具有不同的含义，起到不同的作用。

参考文献：

[1] 胡伟雄.电子商务安全技术[M].武汉：华中师范大学出版社， 2011.

[2] 林果园，别玉玉，刘凯.信息系统安全[M].北京：清华大学出版社， 2012.

[3] 严蔚敏，吴伟民. 数据结构（C语言版）[M].北京：清华大学出版社， 2011.

[4] Anand Rajaraman， Jeffrey David Ullman. Mining of Massive Datasets [M]. Cambridge： Cambridge University Press， 2011.