五分钟了解哈希函数的特性、分类与应用

哈希函数具有单向性和抗碰撞性，被广泛应用于区块链、口令保护及软件保护。

原文标题：《【图学院】这里有哈希函数「家族」的秘密 ......》
撰文：PlatON

哈希函数是现代密码体系中的一个重要组成部分，被普遍应用在社会生产生活当中。平时大家比较感兴趣的数字货币，就使用了哈希函数。

从理论角度来看，哈希函数是以任意长度的数据为输入，输出相应固定长度的值（比如，32byte）。这个值为哈希值，又称摘要、散列、杂凑、指纹。这可能看起来很难理解，其实就是一种数学函数，输入的长度可以是任意的，但输出的长度是固定的。

密码学的很多概念是从现实世界的概念迁徙而来，比如哈希是模拟人类的指纹。因为人类的指纹始终不变，不可能跟随人的胖瘦而更改，也不可能同时代表两个人。

在网络安全协议中，哈希函数可以用来处理电子签名，将冗长的签名文件压缩为一段独特的数字信息，像指纹鉴别身份一样保证原来数字签名文件的合法性和安全性。

哈希函数的特性

哈希函数具有两大基本属性（敲黑板，这是重点）：单向性和抗碰撞性。单向性决定了哈希函数的正向计算效率高，反向计算难度非常大，几乎不可能；而抗碰撞性决定了无法找到两个不同的输入，使得其输出（即哈希值）是一致的。

接下来，让我们依次进行阐述。

单向性

哈希函数的单向性意味着，给定一个哈希值，我们无法（很难）逆向计算出其原像输入。即给定一个哈希值 y，我们无法计算出 x，使得 y=H （x）。简单来说，是无法逆向推理。

对于无法逆向推理，你可能会产生疑问：难道就不能通过不断试错的方法，碰碰运气，得到最终的 x 值吗？也就是说，尝试不同的 x 值，总有一个经过哈希后能得到正确的 y 值吧？这只能说，实践出真知。

以哈希函数 SHAI （输出为 160-bit）为例，假设计算机具备的算力为 73TH/s （即每秒可执行 73×1012 次哈希），Bitman 算力最高矿机 AntminerS17+），那么其一年可执行的哈希运算为 2×1022 次，要搜索出每一个原像大概需要 282 年，超过 100 万亿亿年。

以下是计算过程：

73TH/s=73×1012/s≈2×1022/year≈278/year

2160÷278=282year>1024year

所以，反向计算出哈希函数原像的难度太大，几乎不可能。

抗碰撞性

碰撞指的是在输入区间 D 中的任意两个不同输入 x、y，两者的哈希值是相同的。那么哈希函数的抗碰撞性意味着，找出任意两个不同的输入值 x、y，使得 H （x）= H （y）是 困难 的。（这里称为「困难」的原因，是消息空间是无穷的，而哈希值空间是有限的，因此一定会存在碰撞，只是对寻找碰撞的算力需要有难度上的约束）。

以哈希函数 SHAI （输出为 160-bit）为例：其输出空间为（0，2160），假设有一万亿个哈希值，发生碰撞的概率仅为 3×10-25。被碰撞的概率太低，几乎不可能。

因此，哈希函数的碰撞虽很难，但产生碰撞的几率并不为零。比如，我们将十只鸽子放到五个箱子里面，一定会有两只鸽子是在同一个箱子里面。

再比如下图的生日攻击问题，考虑所有人的生日都是独立均匀随机分布在 365 天内，因为第二个人不能跟第一个人有相同的生日 (概率是 364/365)，第三个人不能跟前两个人生日相同 (概率为 363/365)，依此类推，用阶乘方法计算。最终得知，当 n=23 时，概率趋于 50%，而人的出生率并不是均匀随机的，因此 23 人实际概率应该大于 50%。

因此，哈希函数的抗碰撞性依据其内部构造而定，不同的哈希函数被攻击的几率不同。

哈希函数算法「家族」

从哈希（Hash）函数这一概念诞生至今，已经提出了几十种哈希算法，每类算法对应不同的参数又会形成不同的算法实现。众多的哈希函数如同一个江湖，其中 MD 家族和 SHA 家族是「哈希江湖」中最具声望的两大家族。

国际： MD4、MD5、SHA-1、SHA-256、SHA-3 。（MD 系列、SHA-1 已被破解）

国内： 国产自主研发的商用密码哈希算法，即 SM3 。

MD5 由美国密码学家罗纳德·李维斯特（Ronald Linn Rivest）设计，经 MD2、MD3 和 MD4 发展而来，输出的是 128 位固定长度的字符串。主要用于增强算法复杂度和不可逆性，因其普遍、稳定、快速的特点，仍广泛应用于普通数据的加密保护领域。

SHA-1 由美国国家安全局（NSA）提出，输出的是 160 位固定长度的字符串，在 MD5 的基础上提高输出的长度，单向操作的数量以及单向操作的复杂性，但未做任何根本改进来使其能够抵御更强大的机器。

SHA-3 是由美国国家标准与技术研究所（NIST）发布的，采用了不同于 MD 算法 (如 MD5) 结构的海绵结构，是目前较为安全的哈希函数。

国内的哈希算法有国产自主研发的商用密码算法 SM3，由国家密码管理局于 2010 年发布，主要用于数字签名及验证、消息认证码生成及验证、随机数生成等，其算法是公开的。据国家密码管理局表示，其安全性及效率与 SHA-256 相当。

每个算法都是有生命周期，不可能永远被使用。 比如曾在商业市场广泛运用的 MD5 算法，被中国科学院院士、清华大学王小云教授攻破，造成密码学界的轰动。

王小云教授给出了首个在 MD5 算法上的碰撞例子，并且该碰撞案例是通过 IBM P690 计算机约 1 小时左右即可寻找到，从而证实了 MD5 算法无法防止碰撞，不适用于安全性认证。

王小云教授对 MD5 防碰撞性的攻击表现在：

能够在较短时间内计算找到消息 M1 和 M2，使得 M2 产生的哈希值与 M1 产生的哈希值相同。如此，MD5 的抗碰撞性就已不满足，使得 MD5 不再是安全的哈希算法。

因此，某个单一的哈希算法可能在十年甚至三十年内保证是安全的，能被大家放心地使用。一旦被攻破，大家只能开始换用另一种算法。当然，这个过程是非常漫长的。

哈希函数的应用

哈希函数具有单向性和抗碰撞性，即使仅仅改变输入信息的一个字符也会产生一个完全不同的哈希值，该特性帮助我们防止数据被篡改。

我们可以将原始数据和经过哈希算法得到的数据一块发送给对方，对方收到数据之后，对数据使用相同的哈希算法进行计算，如果得到的哈希值和对方发过来的相同，那么就说明数据没有经过篡改。

哈希函数的应用非常广泛，例如以下几种：

1. 口令保护：在现代 web 应用中，账户系统的口令通过哈希函数处理后，再存储于服务器上，使得口令只对用户自己可知；
2. 软件保护：对外发布软件时，同时使用哈希函数计算出软件的哈希值，与软件一起发布，防止用户下载假冒软件；
3. 区块链：在区块链中，账户与交易都涉及哈希函数的使用。

在区块链中，哈希函数的主要价值是防篡改。每一个区块都存有前一个区块的哈希值，前一个区块叫做当前区块的父区块。当修改当前区块的任意值，都会对父区块产生影响。

前面我们提到，每个算法都是有生命周期，不可能永远被使用。如果 SHA-256 算法被攻破，是不是意味着区块链就挂了？是的，除非全网升级新的哈希算法。SHA-256 算法可能被使用 30 多年或者更长时间，这都很难被确定。

值得一提的是，比特币使用 SHA-256 来转换数据的方式非常有趣，它将算法在协议中连续执行了两次。注意，这并不是为了抵御生日攻击。显然如果 Hash(x) = Hash(y)，那么也有 Hash(Hash(x)) = Hash(Hash(y))，为了缓解长度扩展攻击。

从本质上说，这种攻击需要恶意攻击者知道哈希输入值的长度，在这个已知的长度上再加上一个秘密的字符串，就可以发动哈希函数内部的一部分，从而扰乱哈希函数。由于 SHA-256 是 SHA-2 算法家族的成员，它有这一类的短板，而比特币通过将哈希函数连续运行两次来缓解这个缺陷。

总的来说，哈希函数在生活当中无处不在，包括我们平常在网络上输入的口令，背后都是哈希函数在起作用。不仅如此，它在区块链中的应用和价值也是显而易见的，通过提高其内部操作的复杂性或输出长度，使得被运用的哈希函数在一定时间内足够安全。

如同哈希函数的发展史，当有旧的算法被攻破，就有新的算法被发明。我们一直在尽全力探寻一个计算更高效的未来，不断挑选最好的工具，经得起时间的考验！

来源链接： mp.weixin.qq.com