数学之美 系列十三 信息指纹及其应用

转自http://www.google.com.hk/ggblog/googlechinablog/2006/08/blog-post_8115.html

任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹（Fingerprint)。只要算法设计的好，任何两段信息的指纹都很难重复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。

我们在图论和网络爬虫一文中提到，为了防止重复下载同一个网页，我们需要在哈希表中纪录已经访问过的网址（URL)。但是在哈希表中以字符串的形式直接存储网址，既费内存空间，又浪费查找时间。现在的网址一般都较长，比如，如果在Google或者百度在查找数学之美，对应的网址长度在一百个字符以上。下面是百度的链接

http://www.baidu.com/s?ie=gb2312&bs=%CA%FD%D1%A7%D6%AE%C3%C0&sr=&z=&cl=3&f=8

&wd=%CE%E2%BE%FC+%CA%FD%D1%A7%D6%AE%C3%C0&ct=0

假定网址的平均长度为一百个字符，那么存贮200亿个网址本身至少需要2TB，即两千GB的容量，考虑到哈希表的存储效率一般只有50%，实际需要的内存在4TB以上。即使把这些网址放到了计算机的内存中，由于网址长度不固定，以字符串的形式查找的效率会很低。因此，我们如果能够找到一个函数，将这200亿个网址随机地映射到128二进位即16个字节的整数空间，比如将上面那个很长的字符串对应成一个如下的随机数:

893249432984398432980545454543

这样每个网址只需要占用16个字节而不是原来的一百个。这就能把存储网址的内存需求量降低到原来的1/6。这个16个字节的随机数，就称做该网址的信息指纹（Fingerprint)。可以证明，只要产生随机数的算法足够好，可以保证几乎不可能有两个字符串的指纹相同，就如同不可能有两个人的指纹相同一样。由于指纹是固定的128位整数，因此查找的计算量比字符串比较小得多。网络爬虫在下载网页时，它将访问过的网页的网址都变成一个个信息指纹，存到哈希表中，每当遇到一个新网址时，计算机就计算出它的指纹，然后比较该指纹是否已经在哈希表中，来决定是否下载这个网页。这种整数的查找比原来字符串查找,可以快几倍到几十倍。

产生信息指纹的关键算法是伪随机数产生器算法（prng)。最早的prng算法是由计算机之父冯诺伊曼提出来的。他的办法非常简单，就是将一个数的平方掐头去尾，取中间的几位数。比如一个四位的二进制数1001（相当于十进制的9），其平方为01010001(十进制的81）掐头去尾剩下中间的四位0100。当然这种方法产生的数字并不很随机，也就是说两个不同信息很有可能有同一指纹。现在常用的MersenneTwister算法要好得多。

信息指纹的用途远不止网址的消重，信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性,也就是说,

无法根据信息指纹推出原有信息，这种性质，正是网络加密传输所需要的。比如说，一个网站可以根据用户的Cookie识别不同用户，这个cookie就是信息指纹。但是网站无法根据信息指纹了解用户的身份，这样就可以保护用户的隐私。在互联网上，加密的可靠性，取决于是否很难人为地找到拥有同一指纹的信息，比如一个黑客是否能随意产生用户的cookie。从加密的角度讲MersenneTwister，算法并不好，因为它产生的随机数有相关性。

互联网上加密要用基于加密伪随机数产生器（csprng)。常用的算法有MD5或者SHA1等标准，它们可以将不定长的信息变成定长的128二进位或者160二进位随机数。值得一提的事，SHA1以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌，因为这和黑客能真正攻破你的注册信息是还两回事。

信息指纹的虽然历史很悠久，但真正的广泛应用是在有了互联网以后，这几年才渐渐热门起来。