【密码学】杂（瞎）谈（聊）哈希函数

哈希函数

本文依然是闲聊，不讲具体的算法内容，来一个小总结，相信大家看过我写过的文章之后，应该对于md系列算法 sha系列算法 sm3等哈希函数比较熟悉了，不熟悉的读者，我再来安利一下我之前写过的文章或者大家也可以去查阅相关的资料，在这里不再重复描述算法的具体内容了，本文呢，针对哈希函数来一个小小的总结，来看一下哈希函数有哪些公共的特性。

什么是哈希函数？

「哈希函数」H使用变长的数据分组M作为输入，生成固定长度的结果h = H(M)这一值也称为哈希值或者散列值。对于广义上的哈希函数而言，这个实际上就是把某个任意大小的集合映射到某个固定长度的集合里面，就好比我们编程语言经常会用到的哈希表，里面也是用到了哈希函数。

哈希函数

可能对于上面的描述，读者看起来还是不太好理解，下面我来举一个简单的例子，相信大家都用过电话本，没用过实体的电话本相信大家手机大概率是有通讯录的，可能手机上没有存通讯录的习惯，那么相信能够看到这篇文章的读者，大概率是一个微信用户，微信里面同样会有联系人，我们来定义一个简单的哈希函数，这个哈希函数呢，就是把联系人的拼音的首字母取出来，当做最新的哈希值，这里我们再来简化一下，假设联系人的名称都可以抽象为3个字（不要问为什么要这么做，上面说了，哈希函数要映射到固定长度的大小）。

我们来看下面的通讯录，如下的人名均为我虚拟出来的，如有雷同纯属巧合。

• 张三一(zsy)
• 张三二(zsr)
• 张三三(zss)
• 张三四(zss)

这里，我们发现，最后两个名字所对应的哈希值是一样的，这其实就是哈希冲突，也就说明，我这个定义的哈希函数是比较差的，比较容易的去找到一组冲突。不过虽然我这个哈希函数质量比较差，不影响他看做是一个哈希函数。

非密码学的哈希函数

之前我们提到的md5 sha1 sm3之类的，其实都是密码学安全的哈希函数（虽然某些已经发现不安全因素，不推荐使用了），但是对于哈希函数大家庭来说，不仅仅有密码学安全的哈希函数，还有非密码学安全的哈希函数，这些函数呢，其实不太追求在密码学当中的安全性，但是在某些场景下，也有他独特的优势。

举一个简单的例子，我们常见的短网址应用，我们需要把一个不定长的网址URI转换成为一个比较短的，固定长度的值，对于这个需求，哈希函数的定义太贴合了，那么我们是不是可以使用md5 sha1 sm3之类的来实现呢，这实际上是可以的，但是呢，对于短网址来说，我们需要的是更快的计算，较少的冲突，我们不需要他符合密码学哈希函数的所有特性（有关密码学哈希函数的特性，接下来的章节在讲）对于密码学安全的哈希函数来说，他的计算相对来说是比较慢的，可能大家没有体会，大家思考一下是不是就突然火一把的btc，他的pow就是基于密码学安全的哈希函数，如果这种哈希函数可以被非常快速计算，那么就没有矿工什么事儿了。

对于短网址来说，我们希望它计算的越快越好，可以满足这个需求的算法也比较多，比如说MurmurHash算法，这个算法在2008年被发明出来，在很多软件比如Redis，openresty，LevelDB，MemCache等等都有应用，这个算法有两种长度的哈希值（这里指的v2/v3，这里给自己挖个坑，请叫我挖坑小能手，后面具体聊一聊这个算法的具体结构，这里就不展开讲了）分别是32bits和128bits对于短网址而言，我们采用32bits的结果就可以了。当然对于短网址生成来说，也有不基于哈希函数来实现的，可以采用分布式发号器（Distributed ID Generator）来实现，这里也不过多去描述了。对于MurmurHash和md5计算速度的比较，可以参考文末的参考资料，这里对于Lua的实现来说前者的速度是后者的将近10倍。

密码学的哈希函数

这里，我们来聊一下有关密码学哈希函数的特征，对于密码学哈希函数来说，我们不仅仅需要只是让一个值变为另一个值的映射，而且还需要保持一定的安全特性。

抗原像性

先来回顾一下之前学过的什么是原像，原像是数学当中函数的一个概念，函数h的输出h(x)通常称为x的像，因此x被称为h(x)的原像。哈希函数应该是抗原像的，说人话就是哈希函数的逆运算是困难的，也就是对于一个哈希值，我们想找到是哪个值计算而来的这个是十分困难的。

抗第二原像性

这个和抗原像性类似，这个是指，对于一个哈希函数h, 给定一个输入值x, 以及他输出的哈希值h(x) 很难找到一个不等于x的y 使得h(y) = h(x) 。换句话就是，给定一个输入值以及一个哈希值，很难找具有相同哈希值的另一个不同的输入值。

这两个安全属性的差异在于，前一个是根据哈希值，攻击者无法推断计算哈希值之前的内容，后一个是指，即时攻击者拿到了哈希前和哈希后的内容，很难找到另一个其他的值，使得哈希之后的内容相同。

抗碰撞性

之前我们提到的哈希冲突，也就是发生了碰撞，这个是指，我们很难找到两个不同的x和y使得h(x) = h(y)，看起来这个和上面所提到到的抗第二原像性有些类似（这条约束比上一条要强，有些地方吧抗第二原像性也叫做抗弱碰撞性，而后者称之为抗强碰撞性，换句话说，也就是如果一个函数是抗碰撞的，那么他一定是抗第二原像的），只不过这里没有给定的哈希值了，而是针对所有的输入，都很难找到两个一样的值。

这里后面两个所说的都是十分困难，而不是绝不可能，对于现代密码学来说，保证在有限的算力和时间下不可能就足够了，因为哈希函数是从无穷集合到有限集合的一个映射，因此根据鸽巢原理我们必定能找到一组冲突的值，只不过找到这组冲突的值，可能消耗的算力或者时间是我们现在无法接受的。

哈希函数安全特性

小结

本文主要介绍了一下什么是哈希函数，以及密码学哈希函数需要满足那些特性，对于一般的哈希函数来说，我们不一定要去追求他的安全特性，比如说字典的实现，短网址，或者说是图片名称保存这些，我们只是要他冲突小，速度快就够了，而对于密码学来说，我们是需要保证他的安全特性的，比如数字签名，密码的存储，我们可能要牺牲一部分的性能来换回更加的安全。举个简单的例子，比如说我们拿到一个密码的哈希值，那么我们希望去找到这个原来密码的明文，这里我们只能去通过不断的穷举实现，假设两个哈希算法的抗碰撞性程度相似，那么如果一个哈希算法的计算时间要更长，那么对应的穷举时间也会相应的增加，因此这就更加能保护我们密码的安全，还是那句话，安全和效率其实不太好做到双赢，我们只能在安全和效率中间取得一个trade off。