2022年2022年哈希算法散列 .pdf

《2022年2022年哈希算法散列 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年哈希算法散列 .pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、计算机算法领域基本知识Hash，一般翻译做 “ 散列 ” ，也有直接音译为” 哈希 “ 的，就是把任意长度的输入（又叫做预映射，pre-image） ，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是， 散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出， 而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要 的函数。HASH 主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里 ,叫做 HASH 值 . 也可以说， hash 就是找到一种数据内容和数据存放地址之间的映

2、射关系基本概念* 若结构中存在关键字和K 相等的记录，则必定在f(K) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f 为散列函数 (Hash function) ，按这个思想建立的表为 散列表 。* 对不同的关键字可能得到同一散列地址，即key1key2 ，而 f(key1)=f(key2) ，这种现象称冲突。 具有相同函数值的关键字对该散列函数来说称做同义词。综上所述， 根据散列函数 H(key) 和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“ 象 ” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或

3、散列，所得的存储位置称散列地址。* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的， 则称此类散列函数为均匀散列函数(Uniform Hash function) ，这就是使关键字经过散列函数得到一个“ 随机的地址 ” ，从而减少冲突。常用的构造散列函数的方法散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数， 数据元素将被更快地定位1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b ，其中 a 和 b 为常数（这种散列函数叫做自身函数）2. 数字分析法3. 平方取中法4

4、. 折叠法5. 随机数法6. 除留余数法：取关键字被某个不大于散列表表长m 的数 p 除后所得的余数为散列地址。即H(key) = key MOD p, p=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p 的选择很重要，一般取素数或m，若 p 选的不好，容易产生同义词。处理冲突的方法1. 开放寻址法； Hi=(H(key) + di) MOD m, i=1,2, k(k=m -1)，其中 H(key)为散列函数，m 为散列表长， di 为增量序列，可有下列三种取法：1. di=1,2,3, m-1，称线性探测再散列；2. di=12, (-1)2, 22,(- 2)2,

5、 (3)2, , (k)2,(k=m/2)称二次探测再散列; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 3. di=伪随机数序列，称伪随机探测再散列。= 2. 再散列法： Hi=RHi(key), i=1,2,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“ 聚集 ” ，但增加了计算时间。3. 链地址法 (拉链法 ) 4. 建立一个公共溢出区查找的性能分析散

6、列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：1. 散列函数是否均匀；2. 处理冲突的方法；3. 散列表的装填因子。散列表的装填因子定义为：= 填入表中的元

7、素个数/ 散列表的长度 是散列表装满程度的标志因子。由于表长是定值，与“ 填入表中的元素个数” 成正比，所以， 越大，填入表中的元素较多，产生冲突的可能性就越大；越小，填入表中的元素较少，产生冲突的可能性就越小。实际上， 散列表的平均查找长度是装填因子的函数， 只是不同处理冲突的方法有不同的函数。了解了 hash 基本定义，就不能不提到一些著名的hash 算法， MD5和 SHA-1 可以说是目前应用最广泛的Hash 算法，而它们都是以MD4为基础设计的。那么他们都是什么意思呢 ? 这里简单说一下：（1) MD4MD4(RFC 1320)是MIT 的Ronald L. Rivest 在 199

8、0 年设计的，MD 是Message Digest 的缩写。 它适用在 32位字长的处理器上用高速软件实现-它是基于32 位操作数的位操作来实现的。（2) MD5 MD5(RFC 1321)是 Rivest 于1991年对 MD4 的改进版本。它对输入仍以512位分组，其输出是 4个32位字的级联，与MD4 相同。 MD5 比 MD4 来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好（3) SHA-1 及其他SHA1是由 NIST NSA设计为同 DSA 一起使用的，它对长度小于264的输入，产生长度为160bit 的散列值，因此抗穷举(brute-force) 性更好。

9、 SHA-1 设计时基于和MD4 相同原理 ,并且模仿了该算法。那么这些 Hash 算法到底有什么用呢?Hash算法在信息安全方面的应用主要体现在以下的3个方面：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - （1) 文件校验我们比较熟悉的校验算法有奇偶校验和CRC 校验，这 2种校验并没有抗数据篡改的能力， 它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。MD5 Hash 算法的 数字指纹 特性，

10、使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix 系统有提供计算md5 checksum 的命令。（2) 数字签名Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称 数字摘要 进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。（3) 鉴权协议如下的鉴权协议又被称作挑战-认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。以上就是一些关于hash 以及其相关的一些基本预备知识。那么在

11、emule 里面他具体起到什么作用呢? MD5 、SHA1的破解年月17 日，在美国加州圣芭芭拉召开的国际密码大会上，山东大学王小云教授在国际会议上首次宣布了她及她的研究小组近年来的研究成果对、和等四个著名密码算法的破译结果。次年二月宣布破解SHA-1 密码。散列函数的性质所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面， 散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的， 但并不能绝对肯定二者一定相等。输入一些数据计算出散列值，然后部分改变输入值，

12、一个具有强混淆特性的散列函数会产生一个完全不同的散列值。典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域,比如固定长度的比特串。 在某些情况下， 散列函数可以设计成具有相同大小的定义域和值域间的一一对应。 一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“ 混合 ” 运算而得到。求。到2007 年为止，第三版还未完备。散列函数的应用由于散列函数的应用的多样性，它们经常是专为某一应用而设计的。例如，加密散列函数假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个 “ 单向 ” 操作：对于给定的散列值，没有实用的方法可以计算

13、出一个原始输入，也就是说很难伪造。为加密散列为目的设计的函数，如MD5 ，被广泛的用作检验散列函数。这样软件下载的时候， 就会对照验证代码之后才下载正确的文件部分。此代码有可能因为环境因素的变化，如机器配置或者IP 地址的改变而有变动。以保证源文件的安全性。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 错误监测和修复函数主要用于辨别数据被随机的过程所扰乱的事例。当散列函数被用于校验和的时候，可以用相对较短的散列值来验证任意长度

14、的数据是否被更改过。散列表散列表是散列函数的一个主要应用，使用散列表能够快速的按照关键字查找数据记录。（注意： 关键字不是像在加密中所使用的那样是秘密的，但它们都是用来“ 解锁” 或者访问数据的。 ）例如， 在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下， 散列函数必须把按照字母顺序排列的字符串映射到为散列表的内部数组所创建的索引上。散列表散列函数的几乎不可能/不切实际的理想是把每个关键字映射到唯一的索引上（参考完美散列） ，因为这样能够保证直接访问表中的每一个数据。一个好的散列函数（包括大多数加密散列函数）具有均匀的真正随机输出，因而平均只需要一两次探测 （

15、依赖于装填因子）就能找到目标。同样重要的是，随机散列函数几乎不可能出现非常高的冲突率。但是， 少量的可以估计的冲突在实际状况下是不可避免的（参考生日悖论）。在很多情况下，heuristic 散列函数所产生的冲突比随机散列函数少的多。Heuristic 函数利用了相似关键字的相似性。例如，可以设计一个heuristic 函数使得像FILE0000.CHK, FILE0001.CHK, FILE0002.CHK, 等等这样的文件名映射到表的连续指针上，也就是说这样的序列不会发生冲突。相比之下， 对于一组好的关键字性能出色的随机散列函数，对于一组坏的关键字经常性能很差，这种坏的关键字会自然产生而不仅

16、仅在攻击中才出现。性能不佳的散列函数表意味着查找操作会退化为费时的线性搜索。错误校正使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方， 对将要发送的数据应用散列函数，并将计算的结果同原始数据一同发送。在数据的接收方，同样的散列函数被再一次应用到接收到的数据上，如果两次散列函数计算出来的结果不一致，那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验。对于错误校正，假设相似扰动的分布接近最小(a distribution of likely perturbations is assumed at least approximately)。对于一个信息串的微扰可以被分为两类，大的（不可能的）错误和小的（可能的）错误。我们对于第二类错误重新定义如下，假如给定H(x) 和 x+s，那么只要 s 足够小，我们就能有效的计算出x。那样的散列函数被称作错误校正编码。这些错误校正编码有两个重要的分类：循环冗余校验和里德所罗门码。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -