Enews
招商

【中链知识库】一致性哈希算法(hash)是这么回事

09-15 23:22

标签    中链财经   区块链   区块链百科   区块链技术   区块链应用

文章来源: 中链财经

映射函数是从一个非常大的取值空间映射到一个非常小的取值空间,由于不是一对一的映射,HASH函数转换后不可逆,即不可能通过逆操作和HASH值还原出原始的值,受到计算能力限制(注意,不是逻辑上不可能,前面的不可能是逻辑上的)而且也无法还原出所有可能的全部原始值。

    把网址A,转换成数字1。网址B,转换成数字2。

    一个网址X,转换成数字N,根据数字N作为下标,就可以快速地查找出网址X的信息。这个转换的过程就是哈希算法。

中链财经

    比如这里有一万首歌,给你一首新的歌X,要求你确认这首歌是否在那一万首歌之内。

    无疑,将一万首歌一个一个比对非常慢。但如果存在一种方式,能将一万首歌的每首数据浓缩到一个数字(称为哈希码)中,于是得到一万个数字,那么用同样的算法计算新的歌X的编码,看看歌X的编码是否在之前那一万个数字中,就能知道歌X是否在那一万首歌中。

    作为例子,如果要你组织那一万首歌,一个简单的哈希算法就是让歌曲所占硬盘的字节数作为哈希码。这样的话,你可以让一万首歌“按照大小排序”,然后遇到一首新的歌,只要看看新的歌的字节数是否和已有的一万首歌中的某一首的字节数相同,就知道新的歌是否在那一万首歌之内了。

    当然这个简单的哈希算法很容易出现两者同样大小的歌曲,这就是发送了碰撞。而好的哈希算法发生碰撞的几率非常小。

QQ截图20180915231643.png

    空间映射函数,例如,全体的长整数的取值作为一个取值空间,映射到全部的字节整数的取值的空间,这个映射函数就是HASH函数。

 

    通常这种映射函数是从一个非常大的取值空间映射到一个非常小的取值空间,由于不是一对一的映射,HASH函数转换后不可逆,即不可能通过逆操作和HASH值还原出原始的值,受到计算能力限制(注意,不是逻辑上不可能,前面的不可能是逻辑上的)而且也无法还原出所有可能的全部原始值。

QQ截图20180915231745.png

    HASH函数运用在字典表等需要快速查找的数据结构中,他的计算复杂度几乎是O(1),不会随着数据量增加而增加。另外一种用途就是文件签名,文件内容很多,将文件内容通过HASH函数处理后得到一个HASH值,验证这个文件是否被修改过,只需要把文件内容用同样的HASH函数处理后得到HASH值再比对和文件一起传送的HASH值即可,如不公开HASH算法,那么信道是无法篡改文件内容的时候篡改文件HASH值,一般应用的时候,HASH算法是公开的,这时候会用一个非对称加密算法加密一下这个HASH值,这样即便能够计算HASH值,但没有加密密钥依然无法篡改加密后HASH值。这种算法用途很广泛,用在电子签名中。

 

    HASH算法也可进行破解,这种破解不是传统意义上的解密,而是按照已有的HASH值构造出能够计算出相同HASH值的其他原文,从而妨碍原文的不可篡改性的验证,俗称找碰撞。这种碰撞对现有的电子签名危害并不严重,主要是要能够构造出有意义的原文才有价值,否则就是构造了一个完全不可识别的原文罢了,接收系统要么无法处理报错,要么人工处理的时候发现完全不可读。理论上我们终于找到了在可计算时间内发现碰撞的算法,推算了HASH算法的逆操作的时间复杂度大概的范围。

QQ截图20180915231905.png

     HASH算法的另外一个很广泛的用途,就是很多程序员都会使用的在数据库中保存用户密码的算法,通常不会直接保存用户密码(这样DBA就能看到用户密码啦,好危险啊),而是保存密码的HASH值,验证的时候,用相同的HASH函数计算用户输入的密码得到计算HASH值然后比对数据库中存储的HASH值是否一致,从而完成验证。


QQ截图20180915232003.png

    由于用户的密码的一样的可能性是很高的,防止DBA猜测用户密码,我们还会用一种俗称“撒盐”的过程,就是计算密码的HASH值之前,把密码和另外一个会比较发散的数据拼接,通常我们会用用户创建时间的毫秒部分。这样计算的HASH值不大会都是一样的,会很发散。


QQ截图20180915232049.png

 

X
  • 打赏支付
当前账户总金币:0
请选择打赏金额:
  • 100
  • 300
  • 500
  • 1000
  • 1500
  • 2000
    收藏
文章页底部M1

关于我们

中链财经为打造区块链领域,秉承区块链社区共识的理念,为广大区块链爱好者提供客观的区块链资讯服务。 中链财经将致力推动区块链相关应用的发展,维护健康的创新发展环境,建立先进的区块链生态圈,成为区块链行业发展的风向标 。今天,各种真假区块链层出不穷,中链财经将努力帮助所有人无门槛地走入区块链领域,读懂区块链发展趋势。

合作机构

  • BITMAIN
  • BITMAIN

联系我们