带你了解区块链与密码学:哈希函数简史
本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事,从感兴趣到有乐趣,全民课堂等你来学。
这个系列中的课程内容首先从比特币着手进行入门介绍,再延伸至区块链的相关技术原理与发展趋势,然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号,持续进行学习。
【本课堂内容全部选编自PlatON首席密码学家、武汉大学国家网络安全学院教授、博士生导师何德彪教授的《区块链与密码学》授课讲义、教材及互联网,版权归属其原作者所有,如有侵权请立即与我们联系,我们将及时处理。】
5.1
哈希函数的定义与性质
图学院第五单元开课啦!这单元我们将学习哈希函数及其在区块链中的应用。
哈希函数的定义
哈希函数(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=,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是强抗碰撞的
5.2
哈希函数的发展
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算法。
SHA系列哈希函数相关参数比较
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。
哈希函数碰撞攻击复杂度示意图
图学院第五单元的第一课今天就结束啦!这一单元我们将深入探讨哈希函数。敬请期待啦~
微信扫描关注公众号,及时掌握新动向
2.本文版权归属原作所有,仅代表作者本人观点,不代表比特范的观点或立场
2.本文版权归属原作所有,仅代表作者本人观点,不代表比特范的观点或立场