密码学之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.更多的内容和王小云教授的一些逸事，可以看这里。

以后的事

前些时候因为家里的一些事情担忧了几天，被妈妈说了一顿。唉 ，好像事情越来越多了。有一天晚上梦到毕业的事情，居然忽然醒了。

原来的老板希望我毕业以后能够去原来的实验室。我回答说，这样很不厚道啊，因为现在的老板曾经也希望我留下来，我没有答应，我一直很想出去看看的。说实话我想做点儿事情，一些真正的事情，不想在学校里面了。而且现在的这个老板对我也很不错，从实验室里面退出来，是我自己的意思，当时的想法，是我需要去图书馆看些书了。我喜欢的是高性能计算，在实验室里面也没有人可以帮我提高，我就想自己去图书馆好好学学数学，而且还要写论文。不过以前老板的作风其实不错，因为人很实干，不浮夸，而且如果再回原来实验室，要做的也是高性能计算，是我兴趣所在。

我在原来实验室的朋友丁和周都来作说客了。这样反倒让我觉得很茫然。我自己有一些事情没有做，第一是毕业，还有一件为我赚钱的事情，我不想再这么潦倒了。

冯老师上次说帮我推荐一个数学老师，听说是个数学呆子，水平很高，现在退休了，前些时候去了加拿大讲学。这个事情我还是很期待。

本来决定在这里公布一件我压抑了十几年的事情，因为我忽然发现，虽然我觉得这件事情对我的影响越来越小，可是其实我真的没有正真的面对它。我想也许说出来，就好了（是不是也是一种逃避）。不过我一个朋友劝我不要说了，这个事情是我自己的事情。

江湖的事

遇到打杨式太极的高老师，听说他过些时间要去香港了。便问他上次说给他一些郑曼青的太极拳录像的，怎么给他。商量好到时候从网上传给他儿子。可到了晚上，他又拿来两张刻录碟片要我刻给他。我于是刻了一大段郑曼青的录像，然后是孙剑云、吴图南和董英杰的太极拳录像（高手的拳是看不懂的，可能是在动在里面，节节贯穿吧）。碟片是交给冯老师的，不过不知道为什么心里总有些不安。

旧江湖的人，门户之见是很重的。和别门别派的人接触总是要比较慎重才好。不过，其实我心了倒很想到处去套点儿东西。只是在人后不能说长道短。

师父这次很细致的在教八卦掌，总说我腰没有顶好，可是我自己摸的时候，觉得真的已经填得很满了。倒是上臂一伸开，就发现是很硬很僵，怎么也松不了。这拳越来越难练了。怎么松呢？

有趣的事

一天下雨，唐来宿舍， 把雨伞放在了宿舍们的背后。走的时候，却把我的雨伞拿走了。

又一天，还是这个人，去和几个新认识的朋友谈事情。走的时候，没有忘记拿走放在桌上的小灵通。到了晚上一点多，小灵通忽然响了，对方问他，为什么把她的小灵通拿走。唐才忽然明白，说：妳的小灵通不论长相和新旧程度都和他的太像了。实在不好意思。然后晚上又跑出去，还人家手机。