图学院第五单元开课啦！这单元我们将学习哈希函数及其在区块链中的应用。
哈希函数的定义
哈希函数(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。
