科普 | Emoji 表情带你秒懂哈希函数

Ajian   |     |   1738 次阅读

1

区块链的发展史本质上是技术人员和哈希函数之间长达十年的缠绵情史。

事实上,如果你了解哈希函数,那么理解区块链的挖矿模式和不可篡改性还不是小菜一碟!(文末还有更多内容)

Git 是一种版本控制代码库系统,几乎覆盖到了所有开发者。连这种革命性的开源工具都离不开哈希函数。

电子签名软件 Docusign 同样基于哈希函数。

你每次在网站输入密码之时背后都有哈希函数在作用。

哈希函数虽然用起来非常简单,但是性能非常强大,普遍应用于各种软件,以实现版本控制、安全性和真实性

什么是哈希函数?

哈希函数在近年来的技术进步中发挥着非常重要的作用。那么,哈希函数是什么?它的工作原理是什么样的?我觉得大家至少应该对它有个基本了解。

哈希函数或许不对你的胃口,所以我也只是想解释下它为什么如此强大,不会涉及太多细节……所以别弃文好嘛😉!

网上很多关于哈希函数的解释都过于直白,要么晦涩难懂,要么枯燥无聊……要么二者兼具。因此,在本文中,我将通过 emoji 解释哈希函数,让一向暗淡的密码学世界变得鲜活起来。(虽然可能会起反效果,但……我们继续吧!)

哈希函数简介

不妨把哈希函数想象成一个 emoji 表情工厂,接受一行行 emoji ,不过仅限于猕猴桃、菠萝、茄子、辣椒、胡萝卜和玉米这 6 种。

-工厂接收并输出这 6 种 emoji 。-

工厂处理完输入之后,得到的输出也只会由上述 emoji 组成。

校对注:这里的意思就是,输入哈希函数的是数据,输出的也是数据。输入和输出的基本组成部分都是一样的,就是字符。

这个 emoji 表情工厂的特别之处在于:

1. 这个工厂输出的 emoji 数量少于输入的 emoji 数量

这家工厂每次接受一行 8 个 emoji (仅选取自上述 6 种 emoji ,其中每种 emoji 都可重复出现)。这行 emoji 经过处理之后,会返回一行 3 个 emoji 的输出,同样选取自上述 6 种 emoji 。

重点是,它输出的 emoji 比接收到的少(8 个变成 3 个)。

- Emoji 哈希工厂-

2. 相同的输入进入工厂一定会产生相同的输出

如果你两次都将相同顺序的 8 个 emoji 表情送入工厂,它每次都会返回相同顺序的 3 个 emoji 表情。

即,这个工厂具有 确定性

你可以从上面的 gif 动图中看出,对于相同的输入,工厂每次都会返回相同的输出。

校对注:这个大家可以自己验证一下:https://1024tools.com/hash

这是一个在线计算哈希值的网站。你会发现,不管你今天还是明天,放“ethfans”这段字符进去,得出的 SHA256 值一定是:

1a64ed5b74670156e60e10d8b4f94b02347169cda06b6f1493f80db0c24f2d6c

(注意输入是全小写哦!)

3. Emoji 表情工厂是一条单向通道

如果你输入一行 8 个 emoji ,工厂会立刻返回一个输出。就这么简单!

然而,如果我将工厂输出的 3 个 emoji 告诉你,但是不告诉你对应的输入是什么,你是无法通过分析工厂和输出来倒推出输入的。实际上,要想找出输入,试错已经是最快的办法了。

换句话说,要想找出某个输出对应的输入,最快的方式就是随机输入不同的 emoji 表情组,直到找到正确的那组。

更重要的是,你甚至可以在工厂里走一走,观察它的实际运作情况,却依然不能根据输出求解或逆向倒推输入!它是一个完全的单向工厂

我知道这个比喻或许还不够接地气,所以我还准备了一个更日常的比喻。

这个工厂的运作方式不就像是烤蛋糕吗!(破音)

如果我给你制作一个蛋糕所需的配料和一个详细的配方,你只要依照配方操作这些配料,立马就能做出一个蛋糕。

如果我让你用同样的配料和配方再做一次,你很快就会做出一个相同的蛋糕。烘焙同样具有确定性(理论上是这样的!)。

但是……如果我给你的是蛋糕和配方(配方不包含配料用量,只包括混制和烘培步骤),那就很难计算出这个蛋糕的确切配料用量。

这个时候,通过改变蛋糕配料比进行试错或许是最好的方法。(在这一点上,专业厨师可能另有高见!)

接下来再说回 emoji 表情工厂的属性。

4. 哪怕只改变输入中的一个 emoji 表情,也会得到完全不同的输出

就蛋糕烘焙一例而言,你可能通过一次又一次的试错,越来越近正确的配料用量。但是对于 emoji 表情工厂来说,哪怕只对输入作出细微的改变(仅改变一个 emoji 表情),得到的输出都是八竿子打不着的

以上面的 gif 动图为例,如果将输入中第一个茄子换成胡萝卜,得到的输出会是完全不同的 3 个 emoji 表情。

这就意味着在给定输出的情况下,你无法通过不断试错“逐步接近”正确的输入。你只能随机尝试不同的 emoji 表情组,直到无意中发现了正确的输入为止。

区块链挖矿本质上就是通过计算机不断进行试错来找到一类输入,经过 emoji 表情工厂的处理能够返回带有某个特性的输出,例如,以两个茄子开头的输出。

校对注:先给大家几个例子感受一下:

SHA256(ethfans) = '1a64ed5b74670156e60e10d8b4f94b02347169cda06b6f1493f80db0c24f2d6c'

SHA256(ethFans) = 'a59b6016fb422d7f41d58e16c76e570ff98830c85dc805b1d857fbf6c8173b8f'

SHA256(12345678) = 'ef797c8118f02dfb649607dd5d3f8c7623048c9c063d532cc95c5ed7a898a64f'

SHA256(24691356) = '89c3a10b69ffebfeb45eb70c183823a02cf1277250bdfc03179eb58e779c5fc3'

上面这个输入是恰好是上一个输入的两倍,但是输出值没有任何关联。其实第三点跟第四点是相通的。那么我问你:如果我要你找到一个输入,使得 SHA256 输出值以 4 个 A 开头,你有什么好办法来找?

看第五点。

5. 要找到一个输出对应的两个输入,最快的方法就是试错

你现在一定有个疑惑……

“等等,如果输出比输入短,每个输出肯定会对应多个输入吧?”

……你是对的。如果你将 8 个 emoji 放入工厂,只得到 3 个 emoji ,那么一个输出必定对应多个输入。

然而,emoji 表情工厂的设计太妙了,即使你知道某个输出对应的输入之一,可惜找出其余输入的最快方法依旧是试错。

换句话说,要找到一个输出对应的两个输入,最快的方法就是试错,直到发生“碰撞”为止。

现在是时候总结一下这个 emoji 工厂所有的神奇特性了!

小结

  1. 工厂接收 8 个 emoji 表情并且返回 3 个 emoji 表情。(压缩性

  2. 相同的输入总是返回相同的输出。(确定性

  3. 输入的毫厘之差都会导致输出的千里之谬。(漫射性

  4. 给定一个输出,试错是计算对应输入的最快方法。(单向性

  5. 试错是找到同一个输出对应的两个不同输入的最快方法。(抗碰撞

有趣归有趣,这些特性为何如此重要呢?

现在,让我们一起来看看这个工厂的实际应用。

想象一下,你的密码由 8 个 emoji 表情组成。每次你把密码输入一个网站,网站存储的不是你的密码,而是你的密码的 “哈希值”(你的密码经过 emoji 表情工厂处理之后,会输出 3 个 emoji 表情)。

这样一来,如果出现数据泄露或者有人窃取到该网站的个人数据,那么窃取者得到的只是一堆哈希值,而非实际的密码!

由于工厂是 单向 的,如果窃取者要根据哈希值逆向计算出实际的密码,唯一方法就是试错。

在当前情境下,由于你只能从 6 种 emoji 表情中选出 8 个作为密码,窃取者可能不用花很长时间便可破解。

但在实际生活中,可选作密码的字符串集合要大得多,这就意味着可能的输入范围也要大的多。与此同时,实际生活中哈希工厂/函数的输出长度也远远大于 3 个字符

因此在现实中,窃取者要花费很多很多年的时间才能根据 哈希值 算出对应的密码!

在此期间,虽然存在数据泄露的问题,却不影响你重新登录网站,反正你知道自己的密码,直接输入就好。

这时,你输入的密码会立即经由哈希工厂转化成一个哈希值。网站可以立刻检查这个哈希值是否与你的账户名所对应的哈希值匹配,因为哈希工厂总是返回相同的输出(确定性),并允许你登陆。

但是密码长度不一定都是 8 个 emoji 表情那么长,如果我想对一行更长的 emoji 表情进行哈希计算呢?

你可以的!惊不惊喜!意不意外!通过这项由 Ralph Merkle 和 Ivan Damgård 两位密码学专家提出的简单技术,任意长度的 emoji 表情都可被转化成仅由 3 个 emoji 表情组成的哈希值。

- Merkle-Damgård 架构-

我们要怎么做呢?

如果增加 emoji 表情组的长度,我们就会创建一组工厂来处理它。具体步骤如下。

  1. 先对一行较长的 emoji 表情组进行分段,前 8 个 emoji 作为第一段,之后以 5 个 emoji 为一段。(如果最后一段不足 5 个 emoji ,可以使用额外的 emoji 进行填充,不过这个额外步骤技术含量太高,这里就不做解释了。我们就假设这行 emoji 表情组是可以完美分段的!)

  2. 将第一段 emoji 输入第一个工厂。

  3. 得到一个由 3 个 emoji 表情组成的输出,将这个输出与第二段表情一起输入第二个工厂。

  4. 不断重复这个过程,直到这行 emoji 表情组全部经过工厂处理。

  5. 将最后一个工厂得到的输出返回。

所以现在我们可以把更长的 emoji 表情组转化成 3 个 emoji 的哈希值了!

等等……

既然现在输入的长度问题解决了,那么找到输出相同(一次碰撞)的两行输入会容易得多吗?

你的直觉可能会这么认为。不过出乎意料的是,这就像在一家工厂找到 “一次碰撞” 一样困难。以下是推理过程。

推理开始

假设除了试错之外,还有某种方法可以找到一个输出对应的两个较长的 emoji 表情组输入(一次碰撞)。

那么,在某个实行 Merkle-Damgård 架构的工厂中,你输入两行不同的 emoji 表情组,这个工厂将返回相同的输出。

但是,这意味着你已经使用试错之外的方法找到了一次碰撞,这就与上文提出的抗碰撞性相矛盾了!

所以……

通过增设工厂和数学推理,我们创造了一种方法,可以将任意长度的 emoji 表情组转化成由 3 个 emoji 组成的哈希值。

更重要的是,如果有人得到了一个由 3 个 emoji 组成的输出,也没有比试错更快的方法计算出任意长度的对应输入。鉴于现实世界的哈希计算存在太多组合方式,试错可能会花费许多年!

有了这个简单的技巧,假设一个 emoji 表情工厂是抗碰撞的,你就可以将自己的 emoji 表情密码设置成任意长度,其安全性依然不受影响。

那么区块链呢?

想象你有一个文档(满是 emoji 表情),里面可能是关于一笔金融交易的描述。你要向人们证明这个文档在某个确切的时刻处于某个确切的状态(截止到最后一个 emoji 表情)。

然后,你可以将整个文档放入使用 Merkle-Damgard 架构的哈希工厂中,将输出结果通过电子邮件发送给 100 个人。

因为工厂是单向的,所以邮件接收者无法弄清楚文档的原始内容。如果未来有人污蔑你的文档是假的,或者你已经篡改了它,你就可以证实在某个确切的时刻(当你把这个文档发送给去中心化网络的其它人之时),这个文档处于某个确切的状态(截止到最后一个 emoji /字母)。

既然哈希工厂是抗碰撞的,其他人自然会相信你不是骗子!

总之

哈希函数的单向性和抗碰撞性是非常强大的,它们正在改变整个技术世界。

但是 emoji 表情工厂/哈希函数内部到底是如何运作呢?

这就要涉及到很多技术细节了,实际上,如果你确信上述特性成立,那么工厂的内部运作就无关紧要了。哈希函数的特性比它们的内部运作更有趣(除非你是数学家或密码学家!)。

真正的哈希函数接受的是十六进制字符串(并不是 6 进制 emoji 表情字符串)。十六进制字符串仅由 “0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f” 十六个字符组成。哈希函数接受任意长度的输入,并且返回 64 个十六进制字符(或者为了增强安全性,返回 128 个十六进制字符)。

一种普遍使用的哈希函数是 SHA-256。如果你对本博客有任何想法,请发邮件给我,不过你要先从下方的哈希值算出我的邮箱地址!(提示:在这种情况下,可能有比试错更巧妙的方法噢!)(校对注:从密码学上来说,因为我们知道了输入必然具备的一些条件,比如里面要有个“@”。从社会工程学上来说,我们可以直接翻推特和领英 : ) )

我的邮箱地址的哈希值是:8d935def1f9e0353b0f19f3c765bdeec151862a199084ae4f4b417ca42608914


原文链接: https://medium.com/swlh/this-simple-yet-powerful-invention-is-changing-the-world-d04688c25f13
作者: Patrick Woodhead
翻译&校对: stormpang & 闵敏


你可能还会喜欢:

干货 | 基于哈希函数的签名,Part-1
科普 | 区块链是什么鬼?
观点 | 剖析工作量证明

 
0 人喜欢