带你了解区块链与密码学：哈希函数简史

PlatON 閱讀 1997 2020-9-15 16:04

本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事，从感兴趣到有乐趣，全民课堂等你来学。

这个系列中的课程内容首先从比特币着手进行入门介绍，再延伸至区块链的相关技术原理与发展趋势，然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号，持续进行学习。

【本课堂内容全部选编自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算法。

带你了解区块链与密码学：哈希函数简史