【区块链与密码学】第5-1讲：哈希函数简史_hash函数的定义

 

【本课堂内容全部选编自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条是安全性要求。

1. 单向性：即给定消息可以产生一个哈希值，而给定哈希值不可能产生对应的消息；否则, 设传送数据C=<M, H(M‖K)>，K是密钥。攻击者可以截获C，求出哈希函数的逆，从而得出H-1(C)，然后从M和M‖K即可得出K。
2. 弱抗碰撞性：是保证一个给定的消息的哈希值不能找到与之相同的另外的消息，即防止伪造。否则，攻击者可以截获报文M及其哈希函数值H(M)，并找出另一报文M’使得H(M’)=H(M)。这样攻击者可用M’去冒充M，而收方不能发现。
3. 强抗碰撞性：是对已知的生日攻击方法的防御能力，强抗碰撞自然包含弱抗碰撞。

密码学上安全的杂凑函数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。

哈希函数碰撞攻击复杂度示意图

【区块链与密码学】第五单元的第一课今天就结束啦！这一单元我们将深入探讨哈希函数。敬请期待啦~