00.什么是哈希算法

　　‍

哈希算法（Hash）又称摘要算法（Digest），它的作用是：对任意一组输入数据进行计算，得到一个固定长度的输出摘要。

哈希算法最重要的特点就是：

• 相同的输入一定得到相同的输出；
• 不同的输入大概率得到不同的输出。

‍

哈希算法有什么用

哈希算法的目的就是为了验证原始数据是否被篡改。

举个例子，你写了一封邮件给别人，并且算出了哈希是1234；

如果邮件在传输的过程中，被人截取并篡改了里面的内容，那么算出的哈希大概率就不是1234了。这样别人在和你检查哈希是否一致的时候，就会发现哈希不一样，从而知道原始数据被篡改过了。

这里的原始数据不仅仅指邮件这种文本类的数据，还可以是二进制文件，例如软件的安装包。我们在网站上下载软件的时候，经常看到下载页显示的哈希：

​​

截图来自 MySQL :: Download MySQL Community Server (opens new window)，MD5也是一种哈希算法，我们后续会讲。

我们下载软件安装包后，可以检查下载后的文件的哈希，是否对的上官网的哈希，哈希一致则说明下载的过程中，原始数据没有被人篡改，从而避免下载到一些恶意的软件或者病毒等。

‍

Java中的hash

Java字符串的hashCode()​就是一个哈希算法，它的输入是任意字符串，输出是固定的int​整数：

System.out.println("hello".hashCode()); //99162322
System.out.println("hello, java".hashCode()); //2057144552
System.out.println("hello, peter".hashCode());  //-647369722

两个相同的字符串永远会计算出相同的hashCode​​，否则基于hashCode​​定位的HashMap​​就无法正常工作。这也是为什么当我们自定义一个class时，覆写equals()​​方法时我们必须正确覆写hashCode()​​方法。

如果你还不知道HashMap​是什么，也没关系，学HashMap​的时候还会提到这一节的知识点

‍

哈希算法的碰撞

哈希碰撞是指，两个不同的输入得到了相同的输出：

System.out.println("AaAaAa".hashCode());  //1952508096
System.out.println("BBAaBB".hashCode());  //1952508096

前面我们说过，哈希算法的最重要的特点是：

• 相同的输入一定得到相同的输出；
• 不同的输入大概率得到不同的输出。

注意，只是大概率得到不同的输出，不是百分百不同。输出的字节长度是固定的，String​的hashCode()​输出是int整数，只有4个字节，最多只有4294967296种输出，但输入的数据长度是不固定的，有无数种输入。所以，哈希算法是把一个无限的输入集合映射到一个有限的输出集合，必然会产生碰撞。

碰撞不可怕，我们担心的不是碰撞，而是碰撞的概率，因为碰撞概率的高低关系到哈希算法的安全性。为了保证哈希算法的安全性，必须得让碰撞的概率低，并且不能随意猜测输出。

‍

不能猜测输出是指，输入的任意一个bit的变化会造成输出完全不同，这样就很难从输出反推输入（只能依靠暴力穷举）。假设一种哈希算法有如下规律：

hashA("java001") = "123456"
hashA("java002") = "123457"
hashA("java003") = "123458"

那么很容易从输出123459​反推输入，这种哈希算法就不安全。安全的哈希算法从输出是看不出任何规律的：

hashB("java001") = "123456"
hashB("java002") = "580271"
hashB("java003") = ???

‍

‍

‍

‍

常见的哈希算法

目前市面上比较常见的哈希算法有：

算法	输出长度（位）	输出长度（字节）
MD5	128 bits	16 bytes
SHA-1	160 bits	20 bytes
RipeMD-160	160 bits	20 bytes
SHA-256	256 bits	32 bytes
SHA-512	512 bits	64 bytes

‍

根据碰撞概率，哈希算法的输出长度越长，就越难产生碰撞，也就越安全。Java标准库提供了常用的哈希算法，并且有一套统一的接口。

‍

类似的，计算SHA-256，我们需要传入名称"SHA-256"​，计算SHA-512，我们需要传入名称"SHA-512"​。Java标准库支持的所有哈希算法可以在这里 (opens new window)查到。

‍

MD5算法

MD5即Message-Digest Algorithm 5（信息-摘要算法5），早期使用还是很广泛的，主流的编程语言普遍实现了MD5。MD5的前身有MD2、MD3和MD4。但随着时间的推移，16Bit不太够看了，MD5因为输出长度较短，短时间内破解是可能的，目前已经不推荐使用。

Java标准库提供了常用的哈希算法，并且有一套统一的接口。我们以MD5算法为例，看看如何对输入计算哈希：

import java.math.BigInteger;
import java.security.MessageDigest;

public class Hash2MD5 {
  public static void main(String[] args) throws Exception{
    MessageDigest md = MessageDigest.getInstance("MD5");
    md.update("Hello".getBytes("UTF-8"));
    md.update("World".getBytes("UTF-8"));
    byte[] result = md.digest();
    System.out.println(new BigInteger(1, result).toString(16));
    // output: 68e109f0f40ca72a15e05cc22786f8e6
  }
}

‍

使用MessageDigest​​时，我们首先根据哈希算法获取一个MessageDigest​​实例，然后，反复调用update(byte[])​​输入数据。

当输入结束后，调用digest()​方法获得byte[]​数组表示的摘要，最后，把它转换为十六进制的字符串。

运行上述代码，可以得到输入HelloWorld​的MD5是68e109f0f40ca72a15e05cc22786f8e6​。

‍

SHA-1

SHA-1也是一种哈希算法，它的输出是160 bits，即20字节。SHA-1是由美国国家安全局开发的，SHA算法实际上是一个系列，包括SHA-0（已废弃）、SHA-1、SHA-256、SHA-512等。

在Java中使用SHA-1，和MD5完全一样，只需要把算法名称改为"SHA-1"​：

    MessageDigest md = MessageDigest.getInstance("SHA-1");
    md.update("Hello".getBytes("UTF-8"));
    md.update("World".getBytes("UTF-8"));
    byte[] result = md.digest();
    System.out.println(new BigInteger(1, result).toString(16));
    // output: db8ac1c259eb89d4a131b253bacfca5f319d54f2

‍

哈希与存储密码

哈希算法的另一个重要用途是存储用户口令。如果直接将用户的原始口令存放到数据库中，会产生极大的安全风险：

• 数据库管理员能够看到用户明文口令；
• 数据库数据一旦泄漏，黑客即可获取用户明文口令

‍

已有不少公司因为明文存储密码，导致数据库泄漏后造成重大问题：

2011年12月，CSDN的安全系统遭到黑客攻击，600万用户的登录名、密码及邮箱遭到泄漏。随后，CSDN"密码外泄门"持续发酵，天涯、世纪佳缘等网站相继被曝用户数据遭泄密。天涯网于12月25日发布致歉信，称天涯4000万用户隐私遭到黑客泄露。此次失窃的只是密码集，用户只要及时修改密码即可避免隐私失窃，因此不用恐慌。但用户修改密码只是“治标”，网站改变数据存放策略才是“治本”。

密码外泄门_百度百科 (opens new window)

‍

那如果我们存储密码的哈希呢？用户在注册的时候，输入密码，我们不直接存储密码，而是存储哈希；而当用户登录时，在用户输入原始口令后，计算用户输入的原始口令的MD5并与数据库存储的MD5对比，如果一致，说明口令正确，否则，口令错误。

因此，数据库存储用户名和口令的表内容应该像下面这样：

username	password
bob	f30aa7a662c728b7407c54ae6bfd27d1
alice	25d55ad283aa400af464c76d713c07ad
tim	bed128365216c019988915ed3add75fb

‍

这样一来有几个好处：

1. 数据库管理员看不到用户的原始口令。
2. 即使数据库泄漏，黑客也无法拿到用户的原始口令。想要拿到用户的原始口令，必须用暴力穷举的方法，一个口令一个口令地试，直到某个口令计算的MD5恰好等于指定值。

这种存储方式也是目前主流的存储敏感信息的措施。

‍

重复输入密码

在设置密码的时候，通常屏幕上不会直接显示明文，防止密码被人看到；但这样有个缺点，万一用户输错了，就会导致登录失败。例如用户想输入的是 Abc123，但用户错输入成了abc123，这样用户以为密码是Abc123，导致后续登录用的密码也是Abc123，最后登录不了。

因此，现在通常要用户输入两次密码的，两次都输入错了概率较低，能保证用户输入的密码，和想要输入的密码，是一致的：

​​

‍

再举个例子延伸下：笔者所在的公司里，数据库密码是分两个人保管的，每个人只知道一半的密码。有一份需求中，我需要用到数据库密码生成的密文，对数据库进行操作；此时可以生成密文后，再生成一次密文，比较两者是否一致，这样能避免输入密码的时候输入错误了，导致生成的密文也是错的。

‍

彩虹表

黑客并不笨，暴力穷举会消耗大量的算力和时间。但是，如果有一个预先计算好的常用口令和它们的MD5的对照表：

常用口令	MD5
hello123	f30aa7a662c728b7407c54ae6bfd27d1
12345678	25d55ad283aa400af464c76d713c07ad
passw0rd	bed128365216c019988915ed3add75fb
19700101	570da6d5277a646f6552b8832012f5dc
…	…
20201231	6879c0ae9117b50074ce0a0d4c843060

这个表就是彩虹表。如果用户使用了常用口令，黑客从MD5一下就能反查到原始口令：

用户bob的密码MD5：f30aa7a662c728b7407c54ae6bfd27d1​，原始口令：hello123​；

用户alice的密码MD5：25d55ad283aa400af464c76d713c07ad​，原始口令：12345678​；

用户tim的密码MD5：bed128365216c019988915ed3add75fb​，原始口令：passw0rd​。

这就是为什么不要使用弱密码，以及不要使用生日作为密码的原因。

‍

‍

‍

加盐

即使用户使用了常用密码，我们也可以采取措施来抵御彩虹表攻击，方法是对每个口令额外添加随机数（称为盐），然后加密整个字符串，这个方法称之为加盐（salt），伪代码如下：

digest = md5(salt+inputPassword)

当用户登录的时候，将用户输入的密码和盐一起计算哈希值，然后和数据库中存储的密码进行比较。盐的目的在于使黑客的彩虹表失效，即使用户使用常用口令，也无法从MD5反推原始口令。

‍

小结

哈希算法可用于验证数据完整性，具有防篡改检测的功能；

常用的哈希算法有MD5、SHA-1等；

用哈希存储口令时要考虑加盐防止彩虹表攻击。

‍