Comunion 区块链深度学习系列｜哈希碰撞原理

Comunion 是一个去中心化的(DAO) 组织协作网络，提供面向数字时代的全新商业基础设施和价值转化机制，致力于让劳动价值 像 资本一样自由流通、交易和积累。

本系列内容包含：基本概念及原理、密码学、共识算法、钱包及节点原理、挖矿原理及实现。

本篇专门讲解哈希碰撞原理，这对于哈希算法的理解是非常重要的。如果把这个理解透了，那么哈希算法里面的很多特点，包括区块链当中为什么使用哈希算法，那么基本上就完全通透了。

定义

摘要函数（哈希函数），其实是一个安全性定义。

抗原像碰撞

什么是原像？函数有定义域，有词语，有对应关系。那么类比到这里，原像是指定义域里面的一些未知数。

引用哈希算法应用中挖矿的例子来说，X是定义域，里面的部分就是原像，Y就是一个值域。

我们来看其定义，几乎所有消息摘要，都难以用ppn算法计算出一个原像。

这句话的意思是，假如确定了一个对应关系，或者确定了一个哈希函数，这时对定义域里面某一个元素，比如X1，进行哈希之后，产生了一个哈希值，比如Y1。

假设这个时候产生了Y1，但是并没有告诉任何人。那么这里就有一个问题：这个Y1的原像是谁呢？

这是很难找出来的，也就是提供一个像：Y1，很难找出其对应的原像：X1，这也就是抗原像碰撞的意思。

抗第二原像碰撞

通过字面意思来解释是，存在两个原像，这两个原像是很难找到碰撞的。

给定一个摘要函数h，消息m1，任何ppn算法都难以计算出一个m2使得m1≠m2并且h（m1）=h（m2）。

意思是，给定一个哈希函数，通过任何ppn算法，很难找出一个m2，但这个m2和m1不相同，然后使得原像m2和m1，里面的像也相同，这是很难做到的。

抗碰撞

给定一个摘要函数，任意ppn算法，难以找到m1，m2，使得h（m1）=h（m2）。

意思是，给定一个哈希函数，使用任意ppn算法，难以找到两个消息（原像），使得它们的像相同。

强抗碰撞的意思是，给定一个哈希函数，从定义域（原像）里面随便找两个数，并且这两个数的像是相同的，这样的数是很难找到的。

抗第二原像碰撞和抗碰撞之间的区别是：

抗第二原像碰撞是抗碰撞里面的一个特殊问题。抗碰撞的条件更加强一些，因为是任意取的两个原像，想得到的像是相同的。而抗第二原像碰撞是给定了一个固定的原像，让再找一个原像，使得这两个原像里面的像相同。所以说抗第二原像碰撞是弱抗碰撞。

在区块链中，如果一个哈希函数满足上述三个安全性定义，即：抗原相碰撞、抗第二原像碰撞、抗碰撞，那么这个函数就可以使用，比如SHA-256就满足这三点。

应用

通过安全性定义，其实我们能发现一个特点：这种函数能进行一个数据的完整性认证。

为什么这么说呢？

举个例子，特工A发了一段消息，内容是：使用任意函数H。并用SHA-256对这段话进行哈希，假设其哈希值全部是0，那么就产生了256个0。

特工A把这段消息发给特工B，特工B收到之后，也对其内容“使用任意函数H”进行哈希，假如产生的值是256个0的话，那么就说明这个消息在传播的过程当中没有被篡改。

发送方将完整的传输传输给了接收方，完成了发送方的目的，同时接受方也可以对数据的完整性进行验证。

这里有的朋友就有疑问了，那么对于消息：使用任意函数X，经过哈希之后，会不会也产生256个0呢？

我可以负责的告诉你，如果对消息进行哈希使用的函数，满足上述三个安全性定义的话，那么是不会产生这种情况的。所以，在进行区块链开发选用函数的时候，可以不必须用SHA-256，但是一定要满足这三个安全条件。

其实讲到这里，有很多朋友会产生一个问题：假如我采用的是SHA-256算法，其原像是任意的字符串，像是固定的，那么这个像的空间有多大呢？

答案是：2的256次方的像，也就是总共可以容纳这么多像。

安全级别

还有一个问题是：一个任意多的原像和一个固定空间大的像，那么肯定会通过一定的概率找到两个原像一样的像，也就是产生了碰撞，那么这个碰撞的概率是多大呢？

这个问题很好理解，像是固定的，但是原线有很多，在一个固定的空间内肯定会有碰撞的概率，就比如之前讲过的粒子对撞机一样的原理。

很多朋友都会对这个问题困扰很久。

其实在密码学里面专门有个悖论来解释这个问题，我们一起来用“生日悖论”来解释一下这个问题。

生日悖论

上述的成功概率与下述的问题相关。

问题：要使得教室里的学生中有两个人的生日相同的概率大于0.5（也就是50%），那么教室里至少需要有多少学生？

从直观上来看，可能至少需要2/365≈183个人才行。但是大家仔细分析一下，回顾一下之前学过的概率论的一些知识，会发现这个问题其实并不容易回答。

我们另外一个角度，从反面来解决这个问题，可能会更好一点。

这个问题的反面事件可以理解为：教室里的学生，任意两个人的生日，不相同的概率大于50%。

如果我们能把反面事件的概率求出来，那么用1减去求得概率就是原题目的答案。

所以这个问题我们转换成：求这个教室里面任意两个人的生日，不相同的概率大于50%的人数。

那么到底有多少个人不相同，概率才大于50%呢？

我们做两个假设：

假设1，每个学生的生日在某个特定一天的概率是1/365；

假设2，n个学生的生日都互不相同的概率大于50%。

这里就转换成了求n是什么。

我们首先来来分析一下，n 个人里面，2个人生日不相同的概率是多大？也就是从教室里面任意选出2个人，那他们生日不相同的概率是多少？

答案是：364/365。

也就是把两个人标记为A和B，A的生日是365天中的某一天，那么B的生日和A不同，就有364种可能。

我们继续，如果3个人不相同的概率是多大呢？那么就是：364/365 * 363/365 。

……

那么n个人不相同的概率应该是：363/365 * 364/365 * ……*（365-n+1）/365

这个时候呢，n个人生日不相同的概率，我们已经求出来了。如果要求这个概率大于50%，则可以写成：pro[363/365 * 364/365 * ……*（365-n+1）/365] >

0.5，这就是反面事件的解。

那正面事件就可以写成：1-{ pro[363/365

* 364/365 * ……*（365-n+1）/365] > 0.5} > 0.5

算式列出来之后，对n求解，得出n≥23，也就是说，只要不少于23个人，就至少有两人生日相同的概率大于50%。

这看起来很不可思议，但通过计算却是：一个 30 人的班级中，存在两人生日相同的概率为 70%；对于 60 人的班级中，这种概率要大于 99%。

从引起逻辑矛盾的角度来说，生日悖论并不是一种“悖论”。但这个数学事实十分反直觉，故称之为一个悖论。

通过这个问题，我们回来看哈希函数的碰撞问题：假如使用的哈希函数是SHA-256，那么它的安全级别是多少呢？

或者说，假如使用的哈希函数是SHA-256，任意找两个原像，要使这两个原像产生碰撞的概率大于50%，需要做多少次计算呢？

通过生日悖论，我们可以理解到，SHA-256的安全级别不是2^256（2的256次方），而是：2^（256/2），也就是2的256/2次方。

引申一下，其实在密码学里面，对哈希函数有一个专门的安全性界定，它是跟哈希函数的尾缀有关系的，所以假如使用的是SHA-n，那么其安全级别就是：2^（n/2）。