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

文章正文
发布时间:2024-07-17 15:19

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)。