哈希函数简史

图学院第五单元开课啦!这单元我们将学习哈希函数及其在区块链中的应用

哈希函数的定义

哈希函数(Hash Function)是一个公开函数,用于将任意长的消息M映射为较短的、固定长度的一个值H(M),又称为散列函数、杂凑函数。我们称函数值H(M)为哈希值、杂凑值、杂凑码、或消息摘要。

杂凑值是消息中所有比特的函数,因此提供了一种错误检测能力,即改变消息中任何一个比特或几个比特都会使杂凑值发生改变。

哈希函数的性质    

哈希函数具有如下性质:

· H可以作用于一个任意长度的数据块(实际上是不是任意,比如SHA-1要求不超过264)。

· H产生一个固定长度的输出(比如SHA-1的输出是160比特,SHA-256的输出是256比特)。

· 对任意给定的x,H(x)计算相对容易,无论是软件还是硬件实现。

· 单向性(抗原像)(One-Way):对于任意给定的消息,计算其哈希值容易。但是,对于给定的哈希值h,要找到M使得H(M)=h在计算上是不可行的。

其中前3条是实用性要求,后3条是安全性要求。

单向性:即给定消息可以产生一个哈希值,而给定哈希值不可能产生对应的消息;否则, 设传送数据C=<M, H(M‖K)>,K是密钥。攻击者可以截获C,求出哈希函数的逆,从而得出H-1(C),然后从M和M‖K即可得出K。

弱抗碰撞性:是保证一个给定的消息的哈希值不能找到与之相同的另外的消息,即防止伪造。否则,攻击者可以截获报文M及其哈希函数值H(M),并找出另一报文M’使得H(M’)=H(M)。这样攻击者可用M’去冒充M,而收方不能发现。

强抗碰撞性:是对已知的生日攻击方法的防御能力,强抗碰撞自然包含弱抗碰撞。

密码学上安全的杂凑函数H应具有以下性质:

· 对于任意的消息x,计算H(x)是容易的
· H是单向的
· H是强抗碰撞的

哈希函数的发展

1978年,Merkle和Damagad设计MD迭代结构。

1993年,来学嘉和Messay改进加强MD结构。

在90年代初MIT Laboratory for Computer Science和RSA数据安全公司的Rivest设计了散列算法MD族,MD代表消息摘要。

MD族中的MD2、MD4和MD5都产生一个128位的信息摘要。

MD2(1989年)、MD4(1990年)、MD5(1991年):由美国密码学家罗纳德·李维斯特(Ronald Linn Rivest)设计,经MD2、MD3和MD4发展而来,输出的是128位固定长度的字符串。

RIPEMD-128/160/320:国际著名密码学Hans Dobbertin在1996年攻破了MD4算法的同时,也对MD5的安全性产生了质疑,从而促使他设计了一个类MD5的RIPEMD-160。在结构上,RIPEMD-160可以视为两个并行的类MD5算法,这使得RIPEMD-160的安全性大大提高。

值得注意的是,MD4、 MD5已经在2004年8月Crypto2004 上,被我国密码学者王小云等破译,即在有效的时间内找到了它们的大量碰撞。

SHA系列算法是美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)根据Rivest设计的MD4和MD5开发的算法. 美国国家安全局(National Security Agency,NSA)发布SHA作为美国政府标准。

SHA-0-SHA-0正式地称作SHA,这个版本在发行后不久被指出存在弱点.

SHA-1-SHA-1是NIST于1994年发布的,它与MD4和MD5算法非常相似,被认为是MD4和MD5的后继者.

SHA-2-SHA-2实际上分为SHA-224、SHA-256、SHA-384和SHA-512算法。


2017年2月23日谷歌宣布,谷歌研究人员和阿姆斯特丹CWI研究所合作发布了一项新的研究,详细描述了成功的SHA1碰撞攻击。

NESSIE工程推荐使用的哈希算法有SHA-256/384/512和Whirlpool (Vincent Rijmen和Paulo S. L. M. Barreto在2000年设计,入选国际标准ISO/IEC 10118-3)。(NESSIE是欧洲一项为期三年的密码标准计划, 详见: http://www.nessieproject.com/)

日本密码研究与评估委员会推荐使用的算法有RIPEMD-160、SHA-256/384/512。

此外,NIST于2008年启动新的哈希标准的征集活动。

· 除迭代结构以外的结构
· 适用于任何平台的压缩函数

2008年10月提交文档,收到64个算法,公开56个,51个进入第一轮评估。2009年10月,第二轮评估开始,剩余14个算法。第三轮剩余五个算法,2012年10月2日, Keccak被选为SHA-3。


来源:区块网

发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

分享:

支付宝

微信