哈希算法：如何防止数据库中的用户信息被脱库？

文章来源于极客时间前google工程师−王争专栏。
2011年CSDN“脱库”事件，CSDN网站被黑客攻击，超过600万用户的注册邮箱和密码明文被泄露，很多网友对CSDN明文保存用户密码行为产生了不满。如果你是CSDN的一名工程师，你会如何存储用户密码这么重要的数据吗？仅仅MD5加密一下存储就够了吗？

实际开发中，我们该如何用哈希算法解决问题？

什么是哈希算法？

散列表也叫哈希表，散列函数也叫哈希函数、哈希算法，都源于英文Hash。

哈希算法的定义和原理：

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

一个优秀的哈希算法需要满足几点条件:

从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）
对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同
散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小
哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值

MD5的哈希值是128位的Bit长度，为了方便表示，转化为16进制编码

MD5(" 今天我来讲哈希算法 ") = bb4767201ad42c74e650c1b6c03d78fa
MD5("jiajia") = cd611a31ea969b908932d44d126d195b

尽管只有一字之差，得到的哈希值也是完全不同的

MD5(" 我今天讲哈希算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb
MD5(" 我今天讲哈希算法 ") = a1fb91ac128e6aa37fe42c663971ac3d

通过"a1fb91ac128e6aa37fe42c663971ac"很难推断出对应的文本。

对于非常长的文本，要求哈希算法的计算时间很短。比如一篇4000多个汉字的文章，用MD5计算哈希值，用不了1ms的时间。

哈希算法的应用非常非常多，最常见的7个，分别是安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。

应用一：安全加密（理解成数字签名）

最常用于安全加密的哈希算法是MD5(MD5 Message-Digest Algorithm,MD5消息摘要算法)和SHA(Secure Hash Algorithm,安全散列算法)。

除了这两个之外，还有DES(数据加密)、AES(高级加密)等。

实际上，不管是什么哈希算法，我们只能尽量减少碰撞冲突的概率，理论上是没办法做到完全不冲突的。

这里就基于组合数学中一个非常基础的理论，鸽巢原理（抽屉原理）。这个原理是说，如果有10个鸽巢，有11只鸽子，那肯定有1个鸽巢中的鸽子数量多于1个，换句话说，肯定有2只鸽子在1个鸽巢内。

有了鸽巢原理的铺垫之后，我们再来看，为什么哈希算法无法做到零突破？

哈希算法产生的哈希值的长度是固定且有限的。MD5哈希值是固定的128位二进制串，能表示的数据是有限的，最多能表示2^{128个数据，而我们要哈希的数据是无穷的。基于鸽巢原理，如果我们对2}128+1个数据求哈希值，就必然会存在哈希值相同的情况。一般情况下，哈希值越长的哈希算法，散列冲突的概率越低。

2^128=340282366920938463463374607431768211456

如下两段字符串经过MD5哈希算法加密之后，产生的哈希值是相同的。

即便哈希算法存在冲突，但是在有限的时间和资源下，哈希算法还是被很难破解的。

除此之外，没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也越长。

应用二：唯一标识

先举一个例子：如果要在海量的图库中，搜索一张图是否存在，我们不能单纯地用图片的云信息（比如图片名称）来比对，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。那我们该如何搜索呢？

任何文件在计算机中都可以表示成二进制码串，所以，比较笨的办法就是，拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。如果相同，则说明图片在图库中存在。但是，每个图片小则几十KB、大则几MB，转化成二进制是一个非常长的串，比对起来非常耗时。有没有比较快的方法呢？

我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取100个字节，从中间取100个字节，从最后再取100个字节，然后将这300个字节放到一块，通过哈希算法（比如MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样可以减少很多工作量。

如果还想继续提高哦效率，我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中的时候，我们先通过哈希算法对这个图片取唯一标识，然后再散列表中查找是否存在这个唯一标识。

如果不存在，那就说明这个图片不在图库中；如果存在，我们再通过散列表中存储的文件路径，获取到这个已经存在的图片，跟现在要插入的图片做全量的比对，看是否完全一样。如果一样，就说明已经存在；如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片。

应用三：数据校验

电驴这样的BT下载软件的原理是基于P2P协议的。我们从多个机器上并行下载一个2GB的电影，这个电影文件可能会被分割成很多文件块（比如可以分成100块，每块大约20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。

我们知道网络传输是不安全的，下载的文件块有可能是被宿主机器恶意修改过的，又或者下载过程中出现了错误，所以下载文件块可能不是完整的。如果我们没有能力检测这种恶意修改或者文件下载出错，就会导致最终合并后的电影无法观看，甚至导致电脑中毒。

问题是：如何来检验文件块的安全、正确、完整呢？

BT协议很复杂，校验方法也有很多，我们来看一种方法的思路。

我们通过哈希算法，对100个文件块分别取哈希值，并且保存在种子文件中。**哈希算法有一个特点，对数据很敏感。**只要文件块的内容有一丁点改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要重新从其他宿主机器上下载这个文件块。