哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　PGE \* MERGEFORMT PGE \* MERGEFORMT 1 哈希函数的应用辨析 XX：1009-3044（20XX）34-7741-02  哈希函数是把任意长度的输入通过一定的算法，变换成固定长度的输出，该输出就是哈希值。哈希函数在信息技术领域得到了广泛的应用，在信息安全、数据结构和数据挖掘类课程都涉及到了哈希函数。由于应用领域的不同，哈希函数呈现出了不同的特性和使用方法，但相关课程在讲述哈希函数时，常常只分析哈希函数在本类课程中的特点和应用，而对其在其他领域里的应用情况闭口不谈，以至于学生们常常感觉很困惑，不知道这门课的哈希函数和那门课的哈希函数之间到底有什么关系，是否相同或者不同之处在于什么地方。该文将结合哈希函数在信息安全、数据结构和数据挖掘等领域的应用来分析它所表现出的不同特征及其原因，以便能更好地理解和掌握哈希函数。  1 哈希函数在信息安全技术中的应用  在信息安全技术领域，哈希算法是现代密码体系中的一个重要组成部分，特别是在数字签名技术中得到广泛应用。在数字签名协议中，哈希函数扮演了一个非常重要的角色。假定要向B发送一个签名的消息，签名发送方首先利用哈希函数H计算出消息M的哈希值H（M），然后用自己的私钥Kd对哈希值H（M）进行加密，就得到数字签名Sig=EKd（H（M））；随后把数字签名Sig连同消息M一起，发送出去。签名接收方B收到复合的消息之后，把签名Sig提取出来，然后用的公钥Ke对签名解密得到一个哈希值H”=DKe（Sig）；同时B还利用哈希函数H计算所收到消息的哈希值H’=H（M’）。如果H’=H”，则证明消息确实是产生的，并且在传送过程中未被篡改。  从上面的分析中可以看出，哈希函数实际上把对大量数据的保护和认证问题转换成为对一小段固定长度的数据，即哈希值的保护和认证。因此，哈希值必需和所发送的消息之间建立一一对应的关系，而且这种关系应该是无法预测，这样才能和公钥算法一块实现数字签名的身份认证和防篡改的功能。这实际上就是对哈希函数提出了单向性、随机性和无碰撞的要求。在这里单向性和随机性都是为了防止攻击者有目的地利用消息的哈希值去寻找另一个不同的消息、但却具有相同的哈希值，从而达到篡改消息而不被发现的效果，也就是说有意制造碰撞。哈希函数实际上可以看成是一个原像集合到像集合的一个映射，由于原像集合的数据可以是任意长度，而像集合的哈希值却是固定长度的，所以这肯定是多对一的映射，即便单向性和随机性都得到了满足，碰撞在理论上仍就是不可幸免的，这将严峻危及数字签名的合理性。因此用于信息安全领域的哈希函数值都必需满足一定的长度，如MD5和SH-1，其哈希值长度分别为128位和160位，这样像集合的大小将分别达到2128和2160；采纳生日攻击，找到一对碰撞的计算量分别达到O（264） 和O（280），这对现有的计算能力来说在合理的时间内是难以实现的。即便这样，MD5由于其哈希值长度相对较短，已经被认为是不安全的而逐渐被淘汰，新的哈希函数也在陆续推出中，其哈希值更长，找到碰撞的难度会更大。由此可见，在信息安全技术领域，利用哈希函数对消息进行映射得到的哈希值概要地反映了该消息的某种唯一特性，这也是为什么哈希值在信息安全领域也被称为消息2 哈希函数在数据结构中的应用  在讲数据结构中的哈希函数的应用时，就必须提到哈希表。哈希表是一种数据结构，它可以提供快速的插入操作和查找操作。哈希表是根据关键码值（Key vlue）而直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数就是哈希函数，存放记录的数组叫做哈希表。由于数组容量有限，因此由哈希函数定义的从关键码值构成的原像集合到像集合，亦即哈希表的映射也是多对一的映射，而且发生碰撞的可能性很大——此时的像集合的大小远远小于前面提到的应用在信息安全领域的哈希函数像集合的大小，如MD5的2128和SH-1的2160。这样一来，对不同的 由此可见，在数据结构里，由于哈希函数的像集合相对较小，导致碰撞是非常可能发生的。在数据查找过程中，关键码的比较次数，取决于产生碰撞的多少：产生的碰撞少，查找效率就高；产生的碰撞多，查找效率就低。因此，影响产生碰撞多少的因素，也就是影响查找效率的因素。影响碰撞多少的因素主要包括哈希函数的随机性、处理碰撞的方法以及哈希表的装填因子等。因此，在数据结构里，对于哈希函数本身而言，由于其生成的哈希值长度较短，并不能保证无碰撞性；而且由于哈希表是为了方便存储和操作，对哈希函数的单向性也没有什么太严格的要求，主要是要保证其良好的随机性——这也是为了减少碰撞。这显然和信息安全领域里所用到的哈希函数有共同的地方，如对随机性的要求；但也有不同的地方，如对单向性和无碰撞性要求的严格程度是完全不一样的。另外在数据结构里，哈希值主要和存储地址相关联，此时显然就不能再把哈希值称为消息3 哈希函数在数据挖掘中的应用  Mp-reduce是Google提出的一个软件架构，用于大规模数据集（大于1TB）的并行运算。在数据挖掘特别是大数据的分析处理中，Mp-reduce正得到了越来越广泛的应用。用户需要编写两个函数：Mp函数和Reduce函数，而系统将治理并行运算，协调负责执行Mp或者Reduce的任务，同时也处理可能发生的任务节点的宕机。  Mp-reduce运行的步骤是：  1） 各个Mp任务从一个分布式文件系统中获得一个或者多个数据块，这些任务再利用用户编写的代码把数据块映射成一系列的（key，vlue）对；  2） 一个主操纵器收集从各个任务输出的（key，vlue）对并且按key值进行排序；然后把这些key在所有的Reduce任务中进行分配，具有相同key值得（key，vlue）对就会被分配到同一个Reduce任务中；  3） Reduce任务一次处理一个key值，然后把具有相同key值的输出按用户编写的代码结合在一起。  不管Mp和Reduce是怎么样的任务，第（2）步实际上就是一个分组和聚合的过程。主操纵器进程知道有多少Reduce任务，比如有r个（r的值通常由用户来设定）。主操纵器通常利用一个哈希函数作用于key，然后产生一个从0到r-1的编号。每个key被取哈希值后，相应的（key，vlue）对就被输出到r个本地文件中的一个；每个文件都由一个Reduce任务来处理。由此可见，哈希函数在这里起到的是一个任务分配的作用，并且要尽可能均匀，以便实现各个Reduce节点负荷的均匀分配；这样每个Reduce节点分配的任务量都大体相当。如果key的数目小于Reduce节点的数目，就无法做到均匀分配。但实际上在大数据