密码学之Hash函数

白云上不知道谁贴了一篇很老的新闻 ，说的是王小云教授破译密码的事情。这是去年的新闻了。我当时刚看到的时候也是很不相信，觉得以中国这样浮躁的空气，不太可能有这样的事情。而且现在的安全体系结构，本来就已经经受了很多年的考验了。不过，庆幸的是，我还是一定程度上错了。王小云教授的确做了很优秀的工作。只是媒体有很大的误导，把这个工作吹到了神乎其神（现在的记者是越来越不敬业了，当年徐迟写《哥德巴赫猜想》虽然客观上夸大了哥德巴赫猜想在数学界的地位，可是徐迟在专业上是一丝不苟，数学不是他的专业，可是也一点不敢马虎，生怕报道出现什么硬伤）。白云上的那篇帖子上了十大，可是我在旁边的一篇关于王小云相关工作的科普居然只有几个人关注，其中有一个还是我的一个好朋友友情支持的。我怕媒体把这些学子也误导了，就在贴到这里，作为科普。好了，言归正传。

王小云的主要工作是密码学中的hash函数。

在现在的密码学体系结构中，hash函数是一个很重要的部分。通常用来生成数字摘要。（就基本的安全体系结构，一般认为对称密钥，非对称密钥，数字摘要和数字签名是最基础的，很多安全策略都基于此。本文只说数字摘要，其余者不表）

数字摘要是干什么的呢？我举一个例子。如果我给一个朋友写了一封信，内容为：

寄10000人民币到工商银行帐号123456

而这封信被人截获，截获人把信的内容改为：

寄20000人民币到工商银行帐号654321

再把这个信投递到原收信人。

收信人不知道这个信的内容已经改动。就按信的内容执行。那么攻击人完成攻击。

这个时候，我作为发件人如何避免这个情况再发生呢。（假设我们这里不加密信件）

我会在给人发送信件的时候，先对信件使用一个hash函数生成一个摘要。再用一个比较安全的方式告诉收件人说：如果你收到的信的用和我相同的hash函数相同的生成的摘要是XXXXXXXXXXXXXXX这样的数的话，那这个信的内容没有被改动过。

这样即使攻击者可以看到信的内容，但是如果改动了信的内容，就无法产生相同的摘要，收件人就不会相信。

下面说说hash函数。

简单的说，hash函数就是把任意长的输入字符串变化成固定长的输出字符串的一种函数。输出字符串的长度称为hash函数的位数。即使两个串只有很少的不同，他们的Hash值也会有很大的不同。hash函数要保证输入串和输出串没有统计上的相关性。也无法从hash值得到原串。

目前比较广泛的使用的hash函数是sha-1和md5。很多下载网站在给一个下载文件的时候会同时给一个下载文件的md5码。用来给下载者验证下载文件在下载中有没有出现错误。

既然任意长度的字符串都产生一个相同长度的串，那么，这个hash函数就一定会有冲突，而这个冲突很难有现成的算法找到。通常都是通过强力攻击来枚举。比如sha-1算法是160位的。这样如果我用sha-1算法来验证2^160+1个字符串，根据鸽笼原理，会有至少两个串的校验码是一样的。这样就找到了一个冲撞。一个有个恶意的攻击者为了找到这样个冲撞，可能要死而不已了。（其实，因为算法的特殊性，概率上只需要2^80次计算）。而且，也很难正好可以凑出一个有用的串，其hash值和原串相同。

王小云的主要工作是给出了MD5，SHA-0的碰撞，以及SHA-1的理论破解，她证明了160位SHA-1，只需要大约2^69次计算就能找出来，而理论值是2^80次。其实这个次数还是很高。攻击者对于比较强的hash算法用这样的算法来攻击，也是很辛苦的，基本没有什么可行的办法。而MD5基本已经被弃用。

其实在很多p2p文件共享软件中，如amule，bt等都用了hash算法来确定文件是否相同。

PS:
1.上面公布的帐号并非实有，想汇钱给我，请谨慎操作或和我联系 ：）
2.广义上的hash函数是计算机程序设计和算法中一个比较重要的数据结构，本文里的hash函数专指秘密学中用到的hash函数，这些函数杂设计上要求更多，也特别复杂；
3.更多的内容和王小云教授的一些逸事，可以看这里。