散列函式 Hash _生活百科

文章插图
Hash(散列函式)【散列函式 Hash】Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的讯息压缩到某一固定长度的讯息摘要的函式。
基本介绍中文名：散列、杂凑
外文名：Hash
音译：哈希
表示：任意长度的输入
基本概念若结构中存在和关键字K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关係f为散列函式(Hash function)，按这个事先建立的表为散列表。对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称碰撞。具有相同函式值的关键字对该散列函式来说称做同义词。综上所述，根据散列函式H(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。若对于关键字集合中的任一个关键字，经散列函式映象到地址集合中任何一个地址的机率是相等的，则称此类散列函式为均匀散列函式(Uniform Hash function)，这就是使关键字经过散列函式得到一个“随机的地址”，从而减少冲突。性质所有散列函式都有如下一个基本特性：如果两个散列值是不相同的（根据同一函式），那幺这两个散列值的原始输入也是不相同的。这个特性是散列函式具有确定性的结果。但另一方面，散列函式的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但不绝对肯定二者一定相等（可能出现哈希碰撞）。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函式会产生一个完全不同的散列值。典型的散列函式都有无限定义域，比如任意长度的位元组字元串，和有限的值域，比如固定长度的比特串。在某些情况下，散列函式可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函式也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。常用HASH函式散列函式能使对一个数据序列的访问过程更加迅速有效，通过散列函式，数据元素将被更快地定位。常用Hash函式有：1．直接定址法。取关键字或关键字的某个线性函式值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函式叫做自身函式）2．数字分析法。分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，儘可能利用这些数据来构造冲突几率较低的散列地址。3．平方取中法。取关键字平方后的中间几位作为散列地址。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=1^2,-1^2,2^2,-2^2,3^2,…，±k^2,(k<=m/2)称二次探测再散列；3)． di=伪随机数序列，称伪随机探测再散列。2．再散列法：Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函式，即在同义词产生地址冲突时计算另一个散列函式地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。3．链地址法(拉链法)4．建立一个公共溢出区查找性能分析散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函式转换的地址直接找到，另一些关键码在散列函式得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：1．散列函式是否均匀；2. 处理冲突的方法；3．散列表的装填因子。散列表的装填因子定义为：α= 填入表中的元素个数/散列表的长度α是散列表装满程度的标誌因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是装填因子α的函式，只是不同处理冲突的方法有不同的函式。了解了hash基本定义，就不能不提到一些着名的hash算法，MD5和SHA-1可以说是套用最广泛的Hash算法，而它们都是以MD4为基础设计的。常用hash算法的介绍：（1)MD4MD4(RFC 1320)是 MIT 的Ronald L. Rivest在 1990 年设计的，MD 是 Message Digest（讯息摘要）的缩写。它适用在32位字长的处理器上用高速软体实现——它是基于 32位操作数的位操作来实现的。（2)MD5MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得複杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。（3)SHA-1及其他SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于2^64的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。散列函式套用由于散列函式的套用的多样性，它们经常是专为某一套用而设计的。例如，加密散列函式假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函式是一个“单向”操作：对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。为加密散列为目的设计的函式，如MD5，被广泛的用作检验散列函式。这样软体下载的时候，就会对照验证代码之后才下载正确的档案部分。此代码有可能因为环境因素的变化，如机器配置或者IP位址的改变而有变动。以保证源档案的安全性。错误监测和修複函数主要用于辨别数据被随机的过程所扰乱的事例。当散列函式被用于校验和的时候，可以用相对较短的散列值来验证任意长度的数据是否被更改过。错误校正使用一个散列函式可以很直观的检测出数据在传输时发生的错误。在数据的传送方，对将要传送的数据套用散列函式，并将计算的结果同原始数据一同传送。在数据的接收方，同样的散列函式被再一次套用到接收到的数据上，如果两次散列函式计算出来的结果不一致，那幺就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验。对于错误校正，假设相似扰动的分布接近最小(a distribution of likely perturbations is assumed at least approximately) 。对于一个信息串的微扰可以被分为两类，大的（不可能的）错误和小的（可能的）错误。我们对于第二类错误重新定义如下，假如给定 H(x) 和 x+s，那幺只要s足够小，我们就能有效的计算出x 。那样的散列函式被称作错误校正编码。这些错误校正编码有两个重要的分类：循环冗余校验和里德所罗门码。语音识别对于像从一个已知列表中匹配一个MP3档案这样的套用，一种可能的方案是使用传统的散列函式——例如MD5，但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同（从音频档案的二进制数据来看）的音频档案，但是要找到全部相同（从音频档案的内容来看）的音频档案就需要使用其他更高级的算法了。那些并不紧随IT工业潮流的人往往能反其道而行之，对于那些微小差异足够鲁棒的散列函式确实存在。现存的绝大多数散列算法都是不够鲁棒的，但是有少数散列算法能够达到辨别从嘈杂房间里的扬声器里播放出来的音乐的鲁棒性。有一个实际的例子是Shazam[1]服务。用户可以用电话机拨打一个特定的号码，并将电话机的话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐，并将它于存储在资料库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名（需要收取一定的费用）信息安全Hash算法在信息安全方面的套用主要体以下的3个方面：（1)档案校验我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。MD5 Hash算法的"数字指纹"特性，使它成为套用最广泛的一种档案完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。（2)数字签名Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协定中，单向散列函式扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对档案本身进行数字签名是等效的。而且这样的协定还有其他的优点。（3) 鑒权协定如下的鑒权协定又被称作挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。以上就是一些关于hash以及其相关的一些基本预备知识。哈希函式(1)余数法:先估计整个哈希表中的表项目数目大小。然后用这个估计值作为除数去除每个原始值，得到商和余数。用余数作为哈希值。因为这种方法产生冲突的可能性相当大，因此任何搜寻算法都应该能够判断冲突是否发生并提出取代算法。(2)摺叠法:这种方法是针对原始值为数字时使用，将原始值分为若干部分，然后将各部分叠加，得到的最后四个数字(或者取其他位数的数字都可以)来作为哈希值。(3)基数转换法:当原始值是数字时，可以将原始值的数制基数转为一个不同的数字。例如，可以将十进制的原始值转为十六进制的哈希值。为了使哈希值的长度相同，可以省略高位数字。(4)数据重排法:这种方法只是简单的将原始值中的数据打乱排序。比如可以将第三位到第六位的数字逆序排列，然后利用重排后的数字作为哈希值。哈希函式并不通用，比如在资料库中用能够获得很好效果的哈希函式，用在密码学或错误校验方面就未必可行。在密码学领域有几个着名的哈希函式。这些函式包括MD2、MD4以及MD5，利用散列法将数字签名转换成的哈希值称为信息摘要(message-digest)，另外还有安全散列算法(SHA)，这是一种标準算法，能够生成更大的(60bit)的信息摘要，有点儿类似于MD4算法。档案的hash值大家都知道emule是基于P2P （Peer-to-peer的缩写，指的是对等体网路下客户到客户档案传输的软体），它採用了"多源档案传输协定”(MFTP，the Multisource FileTransfer Protocol) 。在协定中，定义了一系列传输、压缩和打包还有积分的标準，emule 对于每个档案都有md5-hash的算法设定，这使得该档案，并且在整个网路上都可以追蹤得到。MD5-Hash-档案的数字文摘通过Hash函式计算得到。不管档案长度如何，它的Hash函式计算结果是一个固定长度的数字。与加密算法不同，这一个Hash算法是一个不可逆的单向函式。採用安全性高的Hash算法，如MD5、SHA时，两个不同的档案几乎不可能得到相同的Hash结果。因此，一旦档案被修改，就可检测出来。当我们的档案放到emule里面进行共享发布的时候，emule会根据hash算法自动生成这个档案的hash值，他就是这个档案的身份标誌，它包含了这个档案的基本信息，然后把它提交到所连线的伺服器。当有他人想对这个档案提出下载请求的时候，这个hash值可以让他人知道他正在下载的档案是不是就是他所想要的。尤其是在档案的其他属性被更改之后（如名称等）这个值就更显得重要。而且伺服器还提供了,这个档案当前所在的用户的地址，连线埠等信息,这样emule就知道到哪里去下载了。一般来讲我们要搜寻一个档案，emule在得到了这个信息后，会向被添加的伺服器发出请求，要求得到有相同hash值的档案。而伺服器则返回持有这个档案的用户信息。这样我们的客户端就可以直接的和拥有那个档案的用户沟通，看看是不是可以从他那里下载所需的档案。对于emule中档案的hash值是固定的，也是的，它就相当于这个档案的信息摘要，无论这个档案在谁的机器上，他的hash值都是不变的，无论过了多长时间，这个值始终如一，当我们在进行档案的下载上传过程中，emule都是通过这个值来确定档案。hash档案我们经常在emule日誌里面看到，emule正在hash档案，这里就是利用了hash算法的档案校验性这个功能了，文章前面已经说了一些这些功能，其实这部分是一个非常複杂的过程，在ftp,bt等软体里面都是用的这个基本原理，emule里面是採用档案分块传输，这样传输的每一块都要进行对比校验，如果错误则要进行重新下载，这期间这些相关信息写入met档案，直到整个任务完成，这个时候part档案进行重新命名，然后使用move命令，把它传送到incoming档案里面，然后met档案自动删除，所以我们有的时候会遇到hash档案失败，就是指的是met里面的信息出了错误不能够和part档案匹配，另外有的时候开机也要疯狂hash，有两种情况一种是你在第一次使用，这个时候要hash提取所有档案信息，还有一种情况就是上一次你非法关机，那幺这个时候就是要进行排错校验了。关于hash的算法研究，一直是信息科学里面的一个前沿，尤其在网路技术普及的，他的重要性越来越突出，其实我们每天在网上进行的信息交流安全验证，我们在使用的作业系统密钥原理，里面都有它的身影，特别对于那些研究信息安全有兴趣的朋友，这更是一个打开信息世界的钥匙，他在hack世界里面也是一个研究的焦点。userhash道理同上，当我们在第一次使用emule的时候，emule会自动生成一个值，这个值也是的，它是我们在emule世界里面的标誌，只要你不卸载，不删除config，你的userhash值也就永远不变，积分制度就是通过这个值在起作用，emule里面的积分保存，身份识别，都是使用这个值，而和你的id和你的用户名无关，你随便怎幺改这些东西，你的userhash值都是不变的，这也充分保证了公平性。其实他也是一个信息摘要，只不过保存的不是档案信息，而是我们每个人的信息。散列表散列表是散列函式的一个主要套用，使用散列表能够快速的按照关键字查找数据记录。（注意：关键字不是像在加密中所使用的那样是秘密的，但它们都是用来“解锁”或者访问数据的。）例如，在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下，散列函式必须把按照字母顺序排列的字元串映射到为散列表的内部数组所创建的索引上。散列表散列函式的几乎不可能/不切实际的理想是把每个关键字映射到的索引上（参考散列），因为这样能够保证直接访问表中的每一个数据。一个好的散列函式（包括大多数加密散列函式）具有均匀的真正随机输出，因而平均只需要一两次探测（依赖于装填因子）就能找到目标。同样重要的是，随机散列函式几乎不可能出现非常高的冲突率。但是，少量的可以估计的冲突在实际状况下是不可避免的（参考生日悖论）。在很多情况下，heuristic散列函式所产生的冲突比随机散列函式少的多。Heuristic函式利用了相似关键字的相似性。例如，可以设计一个heuristic函式使得像FILE0000.CHK,FILE0001.CHK,FILE0002.CHK,等等这样的档案名称映射到表的连续指针上，也就是说这样的序列不会发生冲突。相比之下，对于一组好的关键字性能出色的随机散列函式，对于一组坏的关键字经常性能很差，这种坏的关键字会自然产生而不仅仅在攻击中才出现。性能不佳的散列函式表意味着查找操作会退化为费时的线性搜寻。扩展MD5、SHA1的破解2004年8月17日，在美国加州圣芭芭拉召开的国际密码大会上，山东大学王小云教授在国际会议上首次宣布了她及她的研究小组的研究成果——对MD5、HAVAL－128、MD4和RIPEMD四个着名密码算法的破译结果。次年二月宣布破解SHA-1密码。命令描述Linux命令——hashhash命令用来显示、添加和清除哈希表。该命令的语法格式如下所示。语法hash [-l] [-r] [-p <path> <name>] [-t <command>]选项说明选项说明-l显示哈希表，包括路径-r清除哈希表-p <path> <name>向哈希表中增加内容-t <command>显示指定命令的完整路径HASH命令hash 每次传输完数据缓冲区中的数据后就显示一个#号