什么是哈希算法
哈希算法,又称散列算法,它是一个单向函数,可以把任意长度的输入数据转化为固定长度的输出:
h/=H(x)h=H(x)h/=H(x)
例如,对 morning
和 bitcoin
两个输入进行某种哈希运算,得到的结果是固定长度的数字:
H("morning") = c7c3169c21f1d92e9577871831d067c8
H("bitcoin") = cd5b1e4947e304476c788cd474fb579a
我们通常用十六进制表示哈希输出。
因为哈希算法是一个单向函数,要设计一个安全的哈希算法,就必须满足:通过输入可以很容易地计算输出,但是,反过来,通过输出无法反推输入,只能暴力穷举。
H("???????") = c7c3169c21f1d92e9577871831d067c8
H("???????") = cd5b1e4947e304476c788cd474fb579a
想要根据上述结果反推输入,只能由计算机暴力穷举。
哈希碰撞
一个安全的哈希算法还需要满足另一个条件:碰撞率低。
碰撞是指,如果两个输入数据不同,却恰好计算出了相同的哈希值,那么我们说发生了碰撞:
H("data-123456") = a76b1fb579a02a476c789d9115d4b201
H("data-ABCDEF") = a76b1fb579a02a476c789d9115d4b201
因为输入数据长度是不固定的,所以输入数据是一个无限大的集合,而输出数据长度是固定的,所以,输出数据是一个有限的集合。把一个无限的集合中的每个元素映射到一个有限的集合,就必然存在某些不同的输入得到了相同的输出。
哈希碰撞的本质是把无限的集合映射到有限的集合时必然会产生碰撞。我们需要计算的是碰撞的概率。很显然,碰撞的概率和输出的集合大小相关。输出位数越多,输出集合就越大,碰撞率就越低。
安全哈希算法还需要满足一个条件,就是输出无规律。输入数据任意一个bit(某个字节的某一个二进制位)的改动,会导致输出完全不同,从而让攻击者无法逐步猜测输入,只能依赖暴力穷举来破解:
H("hello-1") = 970db54ab8a93b7173cb48f55e67fd2c
H("hello-2") = 8284353b768977f05ac600baad8d3d17
哈希算法有什么作用
假设我们相信一个安全的哈希算法,那么我们认为,如果两个输入的哈希相同,我们认为两个输入是相同的。
如果输入的内容就是文件内容,而两个文件的哈希相同,说明文件没有被修改过。当我们从网站上下载一个非常大的文件时,我们如何确定下载到本地的文件和官方网站发布的原始文件是完全相同,没有经过修改的呢?
哈希算法就体现出了作用:我们只需要计算下载到本地的文件哈希,再和官方网站给出的哈希对比,如果一致,说明下载文件是正确的,没有经过篡改,如果不一致,则说明下载的文件肯定被篡改过。
大多数软件的官方下载页面会同时给出该文件的哈希值,以便让用户下载后验证文件是否被篡改:
和文件类似,如果两份数据的哈希相同,则可以100%肯定,两份数据是相同的。