商学院首页 > 比特币进阶(一) > 群人各说什么是哈希算法?

群人各说什么是哈希算法?

发布时间:2020-01-20 14:16作者:lxlmycsdnfree信息来源:CSDN阅读数:11869栏目:比特币进阶(一)

这个HASH算法不是大学里数据结构课里那个HASH表的算法。这里的HASH算法是密码学的基础,比较常用的有MD5和SHA,最重要的两条性质,就是不可逆和无冲突。

 

所谓不可逆,就是当你知道x的HASH值,无法求出x;

 

所谓无冲突,就是当你知道x,无法求出一个y, 使x与y的HASH值相同。

 

这两条性质在数学上都是不成立的。因为一个函数必然可逆,且由于HASH函数的值域有限,理论上会有无穷多个不同的原始值,它们的hash值都相同。MD5和SHA做到的,是求逆和求冲突在计算上不可能,也就是正向计算很容易,而反向计算即使穷尽人类所有的计算资源都做不到。

 

我觉得密码学的几个算法(HASH、对称加密、公私钥)是计算机科学领域最伟大的发明之一,它授予了弱小的个人在强权面前信息的安全(而且是绝对的安全)。举个例子,只要你一直使用https与国外站点通讯,并注意对方的公钥没有被篡改,G**W可以断开你的连接,但它永远不可能知道你们的传输内容是什么。

 

顺便说一下,王小云教授曾经成功制造出MD5的碰撞,即md5(a) = md5(b)。这样的碰撞只能随机生成,并不能根据一个已知的a求出b(即并没有破坏MD5的无冲突特性)。但这已经让他声名大噪了。

 


哈希算法是用来解决数据和数据之间对应关系的一种算法。它的初衷是用来加速数据存取。

 

计算机领域内的大多数查找算法都与存储数据的规模呈正相关,用于衡量查找算法效率的量我们称为平均查找长度,一般情况下,比较优秀的查找算法的平均查找长度也不会短于数据规模以2为底的对数()。

 

哈希算法中,我们把数据项中的关键字用一种特定的对应关系和存储数据项的地址或地址偏移量对应起来。注意:这种对应一般不是一一对应,因为不可能有足够多的地址对应近乎无穷多的关键字。

 

这样一来,当我们知道数据关键字的时候,在大多数情况下可以在常数时间(与数据规模无关的常数)内存取这个关键字。其他的时候,有可能发生多个关键字占据同一地址的现象,我们称之为碰撞。

 

碰撞:已知原数据和其MD5值,想找到一个具有相同MD5值的数据(即伪造数据)

 

这种情况下需要对关键字进行二次或更多次的处理(如果发生多次碰撞),所费时间在最差情况下也只与规模成正比。

 

只要这种函数的对应关系取得足够好,碰撞就会较少的发生,从而使平均查找长度在数据规模可控的情况下大幅度缩短,从而提高查找效率。

 


哈希函数除此以外,也可以用来对广义上的字符串(例如文本、视频、图片、程序等等等等)进行特征验证。常见的有CRC32(32位循环冗余校验),从MD2、MD3、MD4发展而来的MD5(消息摘要算法第五版),SHA1(安全哈希算法)等等。

 

这类哈希算法的最初用途仅仅是对这些广义字符串进行完整性校验,因为在传输中损坏的比特位往往仅仅是极少数,这些少数的错误用上述提到的算法可以得出和原本正确文件截然不同的值,这也就使得文件完整性校验的开销得以缩小。

问题中描述的用途其实并不完全适当,但是在一定程度内可行。

 

因为访问的网络地址有无穷多个,但是所有的哈希算法生成的特征值都有限,在极端情况下,很有可能会出现两个不同的网络地址具有相同特征值的情况。

 

这不仅使得在得知特征值时,反向推测网络地址具有了可行性(虽然开销可能极大,需要大量时间穷举),而且在网络地址增长速度极快的今天,安全地址可能和危险地址发生碰撞导致误杀或者错误放行的情况(现在虽然可能还没出现过,但不能排除这种可能性)。

 

简单结论:

 

这种哈希算法本身虽然在理论上是不可逆的,但是它的思想保证了它也不是绝对可靠的。


这种函数是一种摘要算法,你给他输入一个任意长的数据A他给你返回固定长度的数据B,也称B为“指纹”。
所以理论上来说你拿到一个B你是猜不出来A是什么的。因为B是固定长度的,它对应了无数个A。
举个更形象点的例子。

 

这东西其实就像字典(其实就是)。你给出来的字符串是一个单词,他在字典里面所属的条目是A-Z其中一个字母。不管你给的单词有多长,他总属于字典中某一个目录下(也就是首字母。。)。你现在有两个单词,你不知道他们都是什么,但是你知道一个在“A”里面一个在“E”里面。这样你就知道这俩肯定不是同样的单词。不过由于每个条目下都有一大堆的单词,所以你还是不知道这两个单词具体是什么。

 

当然也有很大的概率两个单词都在E里面,这种情况叫做一种“碰撞”。两个不同的东西生成了同样的结果。拿到360的例子上来说就是,你开了家网站,起了个特别诡异的名字,用奇虎的哈希算法算出来的结果和某个不良网站一样。那么你的网站就被当不良网站屏蔽掉了。

 

一个好的哈希算法要保证尽可能的少产生碰撞。还是说你之前查字典的例子。这次你把字典拆了。给里面每个首字母下面又加了26个条目,分别是A-Z,里面装着以这些当结尾的单词。这样你随便挑两个单词是一个坑里出来的概率就小多了。

 

设计一个哈希算法要考虑的有很多。比如你不知道一个单词具体是什么,但知道首字母是A,但是你也不知道首字母A的单词都是什么,你得找一堆单词挨个试。要是算法复杂点你得试个几十年才能找到符合条件的单词,虽然可能不是你原来找的那个,但是看起来差不多。那么这算法就成功了。人家拖了你几十年。

 

然后突然你有一天觉醒了。感觉就差俩单词太费劲了。所以你买了本空字典,把天下单词挨个试一遍,终于把所有目录里面都填满了。然后你以后找单词就很方便了。别人给你一个单词首字母是A,你就随便从A里面找个应附上。虽然不知道是不是他说的那个,但至少看起来是一个坑里出来的就过关了。这字典就叫彩虹表。这东西写起来比较耗时。没准你算了二十年发现试过的那些单词首字母全是XYZ,但是人家每次给的都是ETA,那之前的活都白干了。

 

虽然这种方法得到的不是原始记录,而仅仅是与之具有相同特征的记录。而且有这个特征的记录可能有一大堆。有的时候你碰巧拿到的就是原来的那个,但大多数拿到的都是垃圾。如果你的表很全的话,那很有可能一堆记录里面有个和原来的那条一模一样的。这时候你可以根据别的什么信息猜猜找的是什么。比如你俩正打架,然后找出来他给你的单词是F开头的,那基本上就能猜出来了。

 

这就是哈希算法。一个好的哈希算法仅仅知道结果的话是极难反算出原始数据来的,特别是有意义的原始数据。

 

至于周老板怎么用我倒是不知道。不过他既然知道那些网址是非法的,那么肯定得有个小本,记录着谁都干过坏事。然后想想之前的彩虹表(你懂的)。

 


就是空间映射函数,例如,全体的长整数的取值作为一个取值空间,映射到全部的字节整数的取值的空间,这个映射函数就是HASH函数。通常这种映射函数是从一个非常大的取值空间映射到一个非常小的取值空间,由于不是一对一的映射,HASH函数转换后不可逆,即不可能通过逆操作和HASH值还原出原始的值,受到计算能力限制(注意,不是逻辑上不可能,前面的不可能是逻辑上的)而且也无法还原出所有可能的全部原始值。HASH函数运用在字典表等需要快速查找的数据结构中,他的计算复杂度几乎是O(1),不会随着数据量增加而增加。另外一种用途就是文件签名,文件内容很多,将文件内容通过HASH函数处理后得到一个HASH值,验证这个文件是否被修改过,只需要把文件内容用同样的HASH函数处理后得到HASH值再比对和文件一起传送的HASH值即可,如不公开HASH算法,那么信道是无法篡改文件内容的时候篡改文件HASH值,一般应用的时候,HASH算法是公开的,这时候会用一个非对称加密算法加密一下这个HASH值,这样即便能够计算HASH值,但没有加密密钥依然无法篡改加密后HASH值。这种算法用途很广泛,用在电子签名中。HASH算法也可进行破解,这种破解不是传统意义上的解密,而是按照已有的HASH值构造出能够计算出相同HASH值的其他原文,从而妨碍原文的不可篡改性的验证,俗称找碰撞。这种碰撞对现有的电子签名危害并不严重,主要是要能够构造出有意义的原文才有价值,否则就是构造了一个完全不可识别的原文罢了,接收系统要么无法处理报错,要么人工处理的时候发现完全不可读。理论上我们终于找到了在可计算时间内发现碰撞的算法,推算了HASH算法的逆操作的时间复杂度大概的范围。
HASH算法的另外一个很广泛的用途,就是很多程序员都会使用的在数据库中保存用户密码的算法,通常不会直接保存用户密码(这样DBA就能看到用户密码啦,好危险啊),而是保存密码的HASH值,验证的时候,用相同的HASH函数计算用户输入的密码得到计算HASH值然后比对数据库中存储的HASH值是否一致,从而完成验证。由于用户的密码的一样的可能性是很高的,防止DBA猜测用户密码,我们还会用一种俗称“撒盐”的过程,就是计算密码的HASH值之前,把密码和另外一个会比较发散的数据拼接,通常我们会用用户创建时间的毫秒部分。这样计算的HASH值不大会都是一样的,会很发散。最后,作为一个老程序员,我会把用户的HASH值保存好,然后把我自己密码的HASH值保存到数据库里面,然后用我自己的密码和其他用户的用户名去登录,然后再改回来解决我看不到用户密码而又要“偷窥”用户的需要。最大的好处是,数据库泄露后,得到用户数据库的黑客看着一大堆HASH值会翻白眼。

 

比特币:https://peixun.btcmoney.cc/post/d370a8fcad1d09b0

关键字: btc
免责声明:作为区块链信息平台,本站所提供的资讯信息不代表任何投资暗示,本站所发布文章仅代表个人观点,与比特财经网官方立场无关。投资有风险,入市须谨慎。

2019-2020 Copyright © 比特财经商学院 版权所有