作者吴彦冰：清华大学高等研究院数学博士，师从著名中国密码学家、中国科学院院士王小云。破解韩国标准加密算法LEA 、POP共识算法发明人。
策划/Jacky
编辑/文炳
在OK区块链工程院技术交流活动上，邀请了清华大学密码学研究中心吴彦冰博士前来讨论，并整理了其中一些精彩观点，以飨读者。
01
什么是Hash函数？
Hash函数是密码学的基本工具，Hash函数可以用在数字签名中，通过后面的介绍我们可以知道数字签名使用的是椭圆曲线，计算复杂度十分高，在签名之前，我们通常都将要签名的文件或者信息经过Hash函数压缩之后再进行签名。
哈希函数还可以用在数据完整性的检测当中，例如说我们经常会看到网站上下载软件时会在旁边给出Hash值，这个Hash值就是用来判断文件是否完整，是否在下载时被别人篡改了。我们从网站上下载了一个文件，我们怎么判断我们下载的文件是完整的呢？我们可以将文件经过Hash函数之后得到的值与网站上的进行对比，看是否相同，相同则代表文件网站，不相同则代表不网站或者被篡改。
Hash函数还可以用于可证明安全密码体制当中，这个之后我们会讲到。其次Hsah函数还可以检测传输中消息是否被篡改，防止伪造电子签名和消息认证码，作为安全组件设计多种密码体制和安全通信协议，比特币和区块链的核心技术。
Hash函数又称杂凑函数、散列函数、数字指纹等，将任意长的消息压缩为一个固定长度的摘要。如下图，我们可以看到Hash函数可以将任意大小的文件压缩成n比特的一个01串，n可以是128、160、192、256、384或512。
我们可以看到Hash函数的数学表达式是Y=H(M) , {0,1}*®{0,1}n，H代表一个Hash函数，M代表一个输入信息，Y是一个输出，可以看到，Hash函数的输入可以是任意位数的，但是输出是定长位数的，为n。计算机中使用的Hash表主要用于存储和查找，是源于1953年IBM的历史性讨论所得到的。
密码学中的Hash函数与计算机中使用的Hash函数略有不同，密码学中使用的Hash函数具有特定的安全属性。之后我们会具体介绍它的安全属性。
我们之前介绍的Hash函数是不带密钥的，直接对消息进行压缩。我们可以在Hash函数中引入密钥，使它变成可以进行身份验证的MAC算法。我们可以看到下图的表示，是把密钥和消息同时作为Hash函数的输入。MAC函数具有消息完整性检测和通信双方的身份认证功能。Hash函数广泛应用于各类Internet协议，如IPsec、SSL/TLS、SSH、SNMP等，还有金融安全：银行，电子钱币等。
02
Hash函数的五大安全特性
再来说一下Hash函数的5大安全特性。首先，Hash函数具有抗原像攻击的安全属性。抗原像攻击是指给定任意Hash值Y，恢复消息M 是困难的。抗第二原像攻击和抗碰撞性是相似的，抗第二原像攻击指的是对于给定的消息M1 ，计算另一个消息M2 使H(M1)=H(M2)是困难的。
而抗碰撞性则是指找到不同的消息(M1, M2) 有相同的指纹，即H(M1)=H(M2)是困难的。这两个安全属性的不同点在于一个是给定M1，一个是M1可以自己选择。
抗长度扩展攻击指的是给定消息M的长度和H(M)，不知道M的情况下，计算H(M||M’)是困难的。抗二次碰撞攻击：给定一对碰撞消息M和M’，对于任意消息N，消息M||N和M’||N也形成碰撞。
Hash函数主要有6种，分别是MD5，SHA-1，SHA-2，SHA-3，Whirlpool，SHA-3，SM3。MD5已经是很传统的hash函数了，是在1992年由Rivest设计提出的，输出长度为128比特。Rivest也是公钥加密算法RSA的设计者之一，是其中的R，Rivest在2002年的时候得到了图灵奖。
我的导师王小云教授在Crypto 2004上提出一种能成功攻破MD5的算法。SHA-1是1995年由NIST（美国国家标准与技术研究院）提出，输出长度160比特。SHA-2是2002年由NIST提出，输出长度256，384，512比特。Whirlpool是2000年由Rijmen等设计，输出长度512比特。KECCAK在SHA-3标准竞赛中胜出，成为SHA-3标准算法，是2007年由Daemen等设计，输出长度256，384，512比特。Hash函数也有由中国人自己设计实现的算法，SM3，是在2010年由我的导师王小云院士等设计，输出长度256比特。
其次王老师还攻破过SHA-1，SHA-2。王老师最推荐看的一本密码学入门书籍是《码书》。我是通过看《欺骗的艺术》说到MD5时有标注，MD5已被中国科学家王小云破解了解到王老师的，之后对王老师十分敬佩，并且成为她的研究生。
03
Hash函数的应用
Hash可以应用在登陆认证中。用户提供用户名和密码，服务器在数据库中查找用户名，获取salt值，计算Hash(salt+password)与数据库中比对，相同则通过认证。这样可以防止密码直接存在数据库中，黑客/管理员可以直接查看到用户密码。加salt的目的是防止两个用户密码相同在服务器中可以直接查看到。
Hash可以用在密钥衍生中。我们可以看到银行使用的U盾所产生的随机数就是通过Hash函数产生的。其次Hash函数也广泛应用于RFID、卫星通讯等密码系统中。
Hash函数也在数字签名中有应用。如果学习完下一节的知识之后，我们就会知道，数字签名使用的是椭圆曲线签名，在计算上十分慢，要签的数据量越大签名速度就会越慢，所以一般采用的办法是，在签名前先将要签名的信息进行Hash压缩，得到一个很短的比特串，之后再进行签名运算。我们看下图是一个金融安全的模型。
Hash函数还在比特币以及区块链中有很好的应用。比特币挖矿，其实就是在找一个随机数n，使得n拼接上交易信息的Hash值前m位为零。前m位为零，代表的是挖矿的计算复杂度，假设要寻找前60比特为0的Hash值，那么他的计算复杂度就是260次运算。电子货币：一种代替货币的电子签名，通过用户的公钥（数字证书）可验证货币的合法性。
来源：OK区块链工程院
