字符串哈希(hash)算法梳理

什么是哈希(Hash)？

Hash，一般翻译做散列，也有直接音译为哈希，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。

数学表述为：h = H(M) ，其中H()–单向散列函数，M–任意长度明文，h–固定长度散列值。

在信息安全领域中应用的Hash算法，还需要满足其他关键特性：

单向性(one-way)，从预映射，能够简单迅速的得到散列值，而在计算上不可能构造一个预映射，使其散列结果等于某个特定的散列值，即构造相应的M=H-1(h)不可行。这样，散列值就能在统计上唯一的表征输入值，因此，密码学上的 Hash 又被称为”消息摘要(message digest)”，就是要求能方便的将”消息”进行”摘要”，但在”摘要”中无法得到比”摘要”本身更多的关于”消息”的信息。
抗冲突性(collision-resistant)，即在统计上无法产生2个散列值相同的预映射。给定M，计算上无法找到M’，满足H(M)=H(M’) ，此谓弱抗冲突性；计算上也难以寻找一对任意的M和M’，使满足H(M)=H(M’) ，此谓强抗冲突性。要求”强抗冲突性”主要是为了防范所谓”生日攻击(birthday attack)”，在一个10人的团体中，你能找到和你生日相同的人的概率是4%，而在同一团体中，有2人生日相同的概率是7%。类似的，当预映射的空间很大的情况下，算法必须有足够的强度来保证不能轻易找到”相同生日”的人。
映射分布均匀性和差分分布均匀性，散列结果中，为 0 的 bit 和为 1 的 bit ，其总数应该大致相等；输入中一个 bit 的变化，散列结果中将有一半以上的 bit 改变，这又叫做”雪崩效应(avalanche effect)”；要实现使散列结果中出现 1bit 的变化，则输入中至少有一半以上的 bit 必须发生变化。其实质是必须使输入中每一个 bit 的信息，尽量均匀的反映到输出的每一个 bit 上去；输出中的每一个 bit，都是输入中尽可能多 bit 的信息一起作用的结果。

Damgard 和 Merkle 定义了所谓“压缩函数(compression function)”，就是将一个固定长度输入，变换成较短的固定长度的输出，这对密码学实践上 Hash 函数的设计产生了很大的影响。Hash函数就是被设计为基于通过特定压缩函数的不断重复“压缩”输入的分组和前一次压缩处理的结果的过程，直到整个消息都被压缩完毕，最后的输出作为整个消息的散列值。尽管还缺乏严格的证明，但绝大多数业界的研究者都同意，如果压缩函数是安全的，那么以上述形式散列任意长度的消息也将是安全的。

哈希（Hash）和加密（Encrypt）的区别

概括来说，哈希（Hash）是将目标文本转换成具有相同长度的、不可逆的杂凑字符串（或叫做消息摘要），而加密（Encrypt）是将目标文本转换成具有不同长度的、可逆的密文。

从数学角度讲，哈希和加密都是一个映射。下面正式定义两者：

一个哈希算法$R=H(S)$是一个多对一映射，给定目标文本S，H可以将其唯一映射为R，并且对于所有S，R具有相同的长度。由于是多对一映射，所以H不存在逆映射$S=H^{-1}(R)$使得R转换为唯一的S。
一个加密算法$R=E(S,K_E)$是一个一一映射，其中第二个参数叫做加密密钥，E可以将给定的明文S结合加密密钥$K_E$唯一映射为密文R，并且存在另一个一一映射$S=D(R,K_D)$，可以结合$K_D$将密文R唯一映射为对应明文S，其中$K_D$叫做解密密钥。

下图是哈希和加密过程的图示：

Hash函数的应用

错误校正

使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方，对将要发送的数据应用散列函数，并将计算的结果同原始数据一同发送。在数据的接收方，同样的散列函数被再一次应用到接收到的数据上，如果两次散列函数计算出来的结果不一致，那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验。

语音识别

对于像从一个已知列表中匹配一个MP3文件这样的应用，一种可能的方案是使用传统的散列函数——例如MD5，但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同（从音频文件的二进制数据来看）的音频文件，但是要找到全部相同（从音频文件的内容来看）的音频文件就需要使用其他更高级的算法了。

信息安全

Hash算法在信息安全方面的应用主要体现在以下的3个方面：

文件校验

我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。MD5 Hash算法的”数字指纹”特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法。

数字签名

Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称”数字摘要”进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

鉴权协议

鉴权协议又被称作挑战–认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

常见Hash函数介绍

MD5 和 SHA1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。

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

现代化的Hash算法

Jenkins Hash

1997年Bob Jenkins在《 Dr. Dobbs Journal》杂志上发表了一片关于散列函数的文章《A hash function for hash Table lookup》，这篇文章自从发表以后现在网上有更多的扩展内容。这篇文章中，Bob广泛收录了很多已有的散列函数，这其中也包括了他自己所谓的“lookup2”。随后在2006年，Bob发布了lookup3，由于它即快速（Bob自称，0.5 bytes/cycle）又无严重缺陷，被广泛使用。lookup3即为Jenkins Hash。更多有关Bob’s散列函数的内容请参阅维基百科：Jenkins hash function。memcached的hash算法，支持两种算法：jenkins, murmur3，默认是jenkins。

MurmurHash

Austin Appleby在2008年发布了一个新的散列函数：MurmurHash。其最新版本大约是lookup3速度的2倍（大约为1 byte/cycle），它有32位和64位两个版本。32位版本只使用32位数学函数并给出一个32位的哈希值，而64位版本使用了64位的数学函数，并给出64位哈希值。根据Austin的分析，MurmurHash具有优异的性能，虽然Bob Jenkins 在《Dr. Dobbs article》杂志上声称“我预测MurmurHash比起lookup3要弱，但是我不知道具体值，因为我还没测试过它”。MurmurHash能够迅速走红得益于其出色的速度和统计特性。当前的版本是MurmurHash3，Redis、Memcached、Cassandra、HBase、Lucene都在使用它。

CityHash

CityHash是2011年Google发布的字符串散列算法，和murmurhash一样，属于非加密型hash算法。CityHash算法的开发是受到了 MurmurHash的启发。其主要优点是大部分步骤包含了至少两步独立的数学运算。现代 CPU 通常能从这种代码获得最佳性能。CityHash 也有其缺点：代码较同类流行算法复杂。Google 希望为速度而不是为了简单而优化，因此没有照顾较短输入的特例。Google发布的有两种算法：cityhash64 与 cityhash128。它们分别根据字串计算 64 和 128 位的散列值。这些算法不适用于加密，但适合用在散列表等处。CityHash的速度取决于CRC32 指令，目前为SSE 4.2（Intel Nehalem及以后版本）。

SpookyHash

2011年Bob Jenkins发布了他自己的一个新散列函数SpookyHash（这样命名是因为它是在万圣节发布的）。它们都拥有2倍于MurmurHash的速度，但他们都只使用了64位数学函数而没有32位版本，SpookyHash给出128位输出。

FramHash

2014年Google发布了FarmHash，一个新的用于字符串的哈希函数系列。FarmHash从CityHash继承了许多技巧和技术，是它的后继。FarmHash有多个目标，声称从多个方面改进了CityHash。与CityHash相比，FarmHash的另一项改进是在多个特定于平台的实现之上提供了一个接口。这样，当开发人员只是想要一个用于哈希表的、快速健壮的哈希函数，而不需要在每个平台上都一样时，FarmHash也能满足要求。目前，FarmHash只包含在32、64和128位平台上用于字节数组的哈希函数。未来开发计划包含了对整数、元组和其它数据的支持。

其他Hash算法

XXHash：https://github.com/Cyan4973/xxHash

SuperFastHash：http://www.azillionmonkeys.com/qed/hash.html

该选用哪个Hash函数？

当然，发布时间更晚的，功能方面可能更优，但是也有可能存在某种限制。如果是32位的机器，建议使用MurmurHash，他要比lookup3的32位更快些。

参考链接：