无可抵赖地打赌——哈希函数漫谈

欢迎大家来到IT世界,在知识的湖畔探索吧!

聊一个计算机科学和密码学里经常出现的一个概念：哈希函数。2019年有这样一条新闻：

首个由中国民间发起的“未来科学大奖”，迎来了首位女性得主——今年53岁的清华大学高等研究院杨振宁讲座教授王小云。她获得了“数学与计算机科学奖”，因为她“在密码学中的开创性贡献，她的创新性密码分析方式揭示了被广泛使用的密码哈希函数的弱点，促进了新一代密码哈希函数标准”。

（上图：王小云教授。现任山东大学网络空间安全学院院长、清华大学高等研究院“杨振宁讲座”教授）

那就来看看哈希函数到底是啥？王小云教授又揭示了什么样的哈希函数的弱点。

首先，哈希是个音译，英语原文是“Hash”。音译的术语比较讨厌，它不提供这个术语的实际意义。但它还有两个意译：“散列函数”和“杂凑函数”。而这两个名称恰好对应了哈希函数的两种主要应用场景，我们来分别看一下。

第一个场景，我用一个故事解释一下。

你是学校的老师，你需要给全校学生分发最新定制的校服。这批校服不光尺寸不同，每件校服上都印有学生的名字，不能随意分发。如果让学生自己来领的话，排队就太久了，而且找衣服也很麻烦。

现在你可以调动10个老师帮你分发，要如何把这些校服分配给这些老师，才能使每个老师拿到差不多数量的校服，并且学生也能方便地知道该去哪个老师那里领校服，使得排队时间能大大缩短呢？

相信你稍加思索，就能想到如下方案：

根据学生姓名姓氏拼音的首字母，分配到不同的老师那里，每个老师负责分配2到3个字母即可。比如第一个老师分发姓氏首字母A、B、C，第二个老师负责D和E，….., 一直到第十个老师负责x、y、z等等。

为什么说这个方案好呢？首先是分发衣服是便捷的，因为姓名已经印在衣服上了，看一下就明白了。这个要比去查学生学号、生日、星座啥的方便太多了。

其次，每个老师可以负责差不多的衣服。诚然，有些姓氏特别多，会造成某个字母下的校服特别多。但可以先把所有衣服按字母分成26堆，然后再看怎么均匀组合成十堆。这样，可以使每个老师负责分发的数量差不多。

最后，这个方案对学生也是很方便的。学生只要根据自己的姓氏首字母，直接找到对应的队伍排队取就行了。

以上过程中，我们其实定义了一个把学生映射到某个字母上，再进一步映射到1到10之间某个数字的函数。我们说这个函数就是一种“哈希函数”。

它有一个特点：比较大的定义域和比较小的值域。我们的例子中，定义域是全体学生，可以有成百上千名学生，最后映射为10个数字。

另外还有一个潜在要求是：映射过程是简便的，映射计算时间不随运算规模增大（比如说学生人数的增加）而增大。哈希函数不能搞太复杂，太复杂就不好用。

以上这种哈希函数在编程领域经常会用到。比如有很多数据要处理，那么为了加速处理，就想搞并行处理对吧。这是就需要把待处理的任务合理划分成若干组，然后分发到不同的队列等待处理。这个过程是不是很像之前分发校服的过程。实际应用中，如果待处理的数据是均匀分布的随机数的话，那么最简单的哈希函数就是模取余的过程。

这也是为什么哈希函数的一种中文翻译是散列函数的原因。我猜翻译者的想法就是把一个队列打散成多个队列，所以叫“散列”。

以上就是一种简单的哈希函数：它的基本要求就是定义域大，值域小，计算简便。

哈希函数在密码学领域里也有非常重要的应用，而在密码学中，对哈希函数的要求严格了许多，除了以上特点外，主要还增加了以下两个要求：

求逆运算困难。也就是，已知一个哈希函数的函数值，要找到是哪个元素映射成这个函数值是困难的。我们已经看到，哈希函数总是定义域比值域大，也就是它是多对一的函数。现在要求，哪怕是多对一，要找到任何一个函数值的逆都是困难的。这个要求其实隐含了两个要求：

函数的值域要大。像之前的哈希函数，它只有10种或26种取值，可能性就太少了。太少的话，可以通过尝试大量随机函数输入，来恰好得到所需输出。现实中哈希函数的值域一般都是128比特或更多，那么值域至少有种可能，这是远超枚举可能的。

这个要求也不与“定义域要比值域大”矛盾。密码学中的哈希函数可以接受任意长度的比特位作为输入，所以理论上，定义域中有无穷多个元素。

第二个隐含要求是：函数输入值的微小变动，都会导致函数值的巨大变动。

它的意思是，即使输入本身非常长，有几百万位，只要在输入中修改一个比特位，由0变成1，或者1变成0，都会导致输出结果的巨大的变化。这也是确保哈希函数很难求逆的一个要求。否则，可以逐渐逼近可能的逆，或者缩小可能的取值范围。这都是不允许的，都会影响哈希函数的安全性。

比如以下两个字符串的md5哈希值（md5是一种常见的哈希函数）：

 ~ echo 大老李聊数学 | md5 Aeeb9bab2b328c3304d88f691d60fe64 

欢迎大家来到IT世界,在知识的湖畔探索吧!

欢迎大家来到IT世界,在知识的湖畔探索吧!~ echo 大老王聊数学 | md5 52454cd51a108d4d79ca0a72 

可以看到，输入虽然只有一字之差，但是两者的md5值是天壤之别。你可以想象，即使有两个哈希值很接近，它们的原文也必然是天壤之别。

密码学中的哈希函数，除了求逆困难，还有一个要求：不容易找到“碰撞”。这里有个重要概念：“碰撞”。之前说了，哈希函数都多对一函数，那么如果两个不同的函数输入，得到同样的哈希结果，此时就说这两个输入发生了碰撞。

现在的要求就是，你没有方法简单地找到任何两个函数输入，使得它们的输出是相同的。基本上，之前的“不容易求逆”的要求，是这个“不容易找碰撞”的一个必要但不充分条件。

如果可以求逆的话，那可以随便取一个输入得到一个输出，再根据这个输出得到一个原值。由于是哈希函数的多对一特性，这个原值基本上不会与原值相同，那么就得到了一对“碰撞”。所以，不容易求逆，是不容易找到碰撞的一个必要条件。

但找碰撞不一定通过求逆的方式，所以我们必须单独把这个条件列出来。

根据以上哈希函数的条件，你可以想象出哈希函数的构造方式。它经常需要把输入的信息按位进行移位、异或等操作来得到最终的输出，所以哈希函数有另一个中文名称：“杂凑”函数。我想翻译者的意思就是“混杂和拼凑”的意思，这个翻译实际体现了哈希函数的计算过程。

那么来看看哈希函数到底可以用在哪些场合，只要了解了哈希函数的应用场合，你就会理解为什么哈希函数需要有以上的要求。

最常见的场合就是用来作为校验一个文件完整性。比如某些提供大文件下载的网站中，一般在下载链接附近，标明这个文件的MD5或者SHA校验码。这里的MD5和SHA是两种最常见的哈希函数。

它们的作用就是帮你校验文件完整性。当下载完这个大文件之后，你可以用本地的MD5或者SHA哈希计算工具，计算一下这个文件的哈希值，与网站上给出的值进行比对。如果一致，说明下载的文件是完好的。如果不一致，则说明文件下载过程中受损或者源文件被篡改了。无论如何，这个文件都不能用了。

a435f6f393ddaeda9f683c32ea780b5a1de422ee77d98e909 *ubuntu-22.04.3-desktop-amd64.iso a4acfda10b18da50e2ec50ccaf860d7f20b389df05c0e911d16fd *ubuntu-22.04.3-live-server-amd64.iso 

以上是Ubuntu Linux某个版本的两个iso光盘镜像的SHA256哈希值，取自Ubuntu网站。下载链接在这里。

所以这也是为什么哈希值又是被称为指纹函数或摘要函数的原因。因为这短短的一串数字，就锁定了原文的内容。你对原文进行1比特修改，都会导致哈希值的不匹配。

另外，当你使用网盘服务时，经常会发现，有时上传一个很大的文件，似乎一瞬间就完成了。那就是因为这个网盘服务提供者已经计算并索引了它已经存储过的所有文件的哈希值。

当你再一次上传某个文件，如果与已有的文件具有相同哈希值，网盘服务商就知道它已经存储过你所要上传的文件了，所以不用重复上传了。网盘服务商只要把已经存储过的文件显示给你就好了，就是这个简单的原理。

哈希函数另一个作用是安全地存储密码。你有没有想过，当你注册某个网站，设置了某个密码时，网站会如何存储你的密码？

其实多数网站不会存储你的密码的原文，而是存储你的密码的哈希值。因为存储密码的原文对网站的管理者的要求太高了，密码数据库泄露就不得了了。改为存储哈希值就好很多。每当登录的时，网站只是比对你输入的密码的哈希值是否与数据库里的哈希值匹配。

如果黑客获取了密码数据，那么他只是拿到密码的哈希值。因为哈希函数不容易求逆，所以黑客并不能很容易地找到密码的原文。但这里要提醒各位的是，不要使用常见密码或者弱密码。

因为哈希函数的正向操作不难，所以早就有被称为“彩虹表”的数据库，它存储了常见密码和弱密码的各种哈希值。当黑客拿到你的密码的哈希值之后，只要去数据库里比对一下，如果你的密码是弱密码，数据库里一比对就出来了。

(上图：一个在线MD5数据库，弱密码“Password123”的MD5值已经存在于数据库中，所以很容易被“还原”出来)

当然，更好的方法是使用专业的密码管理工具。现在，基本上所有主流浏览器都能帮你在不同的网站生成不同的强密码，并且帮你记住密码。其实这是最安全的。像大老李现在99%的密码都在浏览器里，我根本不知道那些网站的密码，严刑拷打我也没用。而一旦网站泄露密码，也只泄露我在一个网站的密码，损失可以控制在最小程度。

现在可以说说王小云教授揭示了什么样的哈希函数的弱点。早在2004年，王小云教授就找到了相对简单的方法，可以寻找md5和SHA-0哈希函数的碰撞。 第二年，她又联合其他同事发表了一个方法，可以相对简单地寻找SHA-1哈希函数的碰撞。

一对著名的MD5碰撞：

它们的MD5值都是：

fb1a26e4bc422aef54eb4

注意，以上两串数字都是16进制数值，不能以字符串类型作为输入求MD5，否则得不到以上结果。

当然，这是很了不起的成就，这里面用到的数学方法非常复杂。所以现在需要严格安全的场合，都不推荐使用MD5或者SHA-0、SHA-1哈希函数，因为它们的安全性是被证明有弱点的。

而有些媒体说王小云教授“激活成功教程了MD5，SHA算法”，这种说法是不准确的。首先，哈希算法不是加密算法，难以使用“激活成功教程”一词。一定要说“激活成功教程”的话，那我觉得只有能够快速求逆才能算是激活成功教程。而现在对MD5还是不能快速求逆的，所以，MD5用在文件完整性的校验上还是完全可以的。

那么以上就是哈希函数的几个重要的应用，因为它具有防篡改的特性，它在网络安全领域可谓无处不在。不管是网络数字证书，还是电子签名或者加密货币领域等等，哈希函数基本上无处不在。

那以下，我再介绍两个关于哈希函数比较搞笑的，但确实很实用的两个场景。

第一个场景：防抵赖。有些朋友可能会经常私下打赌，为了防止抵赖，最好的方法就是把打赌内容公之于众，发个朋友圈让大家都知道，这是最好的防抵赖的方法。

但也可能有这种情况，打赌的内容不方便公开，那怎么能够防止抵赖呢？这时，哈希函数就能发挥作用了。可以做的是，打赌双方把打赌内容写在某个文件里，比文件里写：

xxx与xxx打赌如下如果xxx则xxx。打赌人xxx和xxx，身份证号是xxx和xxxx。

把以上内容写在某个文件里。

然后，双方各自拿到这个文件的一个副本。此时，双方都计算一下这个文件的md5哈希值，理论上计算结果应该是一样的。

然接着，双方就可以各自发布这样一条朋友圈：

如此就起到了防抵赖的作用。为什么呢？如果一方抵赖，那么另一方就可以公开展示这个文件，并且任何人都可以用哈希校验工具，计算这个文件哈希值，与当初的数值比对。

如果一致，那么就足以使众人相信，这两个人确实有过这场打赌。因为哈希函数的特性，要伪造出一份有打赌内容的文件，并且其哈希值恰好是当初公告的那个，是不可能的。所以，人们就会相信，这个文件就是当初公开宣布时所宣称的那个文件。这就是哈希函数的防抵赖作用。

哈希函数还有一个另类应用场景，可以叫做“拥有权声明”。它的意思是，当你需要让别人相信你拥有某个信息，但又不能直接公布这个信息的时候，你可以用哈希函数。

比如，你要在微信群里搞个数学竞赛，你把题目公布在群里，最早提交正确答案的前三名有奖，截止某某时间。

问题在于大家不信任你这个群主。有人提出质疑：我怎么相信你给出的获奖者的名次？你说xx人是第一名，你怎么证明他就是第一个提交答案的呢？

那么，这时候哈希函数又可以发挥作用了。你可以说，请做出答案的人，把解题过程和自己的名字写在某个文件里，最好再追加一些其他无关信息。最后计算一下此文件的哈希值，公布在微信群里。

事后，请所有获奖的人，把解答文件转发到群里。那么所有人都可以打开这些文件检查内容是否包含解答，并且再计算一下哈希值，与其当初公布在群里的哈希值比对。如果相同，那么所有人应该没话说了。

这就是哈希函数的另一个妙用，当有任何需要延后公布的信息，但你又必须在此时此刻证明你有这个信息的时候，就可以改用展示这个信息的哈希值来代替。

最后，说几个关于哈希值的趣味思考问题：

第一：有没有某个数字的哈希值是自身？这个问题很有意思，这种数字在数学上就叫做不动点。而且对所有各类哈希算法，基本上都可以估算出存在不动点的概率约为1-1/e≈63%。

但目前，没有找到任何主流哈希函数的不动点，甚至连像a->b->c->a这样循环链条都没有找到。所以你不要看MD5，虽然有弱点了，但是我们对它的掌握还是很弱的。

第二：有没有可能构造一个字符串，它包含自身的md5值。这也很难，但是已经能做出来了，只是这个输入字符串比较长。以下这张动画GIF显示的内容就是自身的MD5值：

欢迎大家来到IT世界,在知识的湖畔探索吧!$md5 md5.gif MD5 (md5.gif) = f5ca4f935d44b85c431a8bf788c0eaca 

另外，还有人制作出了包含文件本身md5值的pdf文件。就是这个pdf文件里有一句话，我的md5值是xxx。然后你去检查这个文件的md5值，真的就是那个数字。

这是挺酷的，甚至有人在简历中写入了简历文件的md5:

（来源：https://www.zhihu.com/question//answer/）

但是制作这样的文件并不简单。你不能先写好文件，然后算一下文件的哈希值，再写回到文件里。因为一旦你改变了文件，那么它的哈希值也改变了。所以得用非常技术化的方法，利用已知的md5的漏洞，才能做到，控制一个文件大部分的内容，通过改写文件的局部内容，使得文件的md5值恰好是写在文件里的那个。

如果你想制作这样的文件，可以参考：https://github.com/corkami/collisions

总结：我们了解了两种哈希函数。一种是条件比较简单的，用来分流队列的哈希函数。一种是条件更为严格的，用在密码学中的哈希函数。

密码学中的哈希函数非常有用，基本上在所有需要延迟发送信息，但又必须在当下锁定信息内容的场合，都可以考虑使用哈希函数。如果你有任何关于可以使用哈希函数的好的场合和情形，也欢迎留言告诉我。

最后出一道思考题：

有人认为哈希函数是单向函数，不能求逆运算。所以我可以公开我的身份证号码的哈希值，不用担心别人能反推出我的身份证号。这句话对不对？公开自己身份证号的哈希值，到底安不安全？为什么？

参考链接：

https://www.zhihu.com/question/