数学应用-信息指纹及其应用

发表者:吴军,Google 研究员

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

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

假 定网址的平均长度为一百个字符,那么存贮 200 亿个网址本身至少需要 2 TB,即两千 GB 的容量,考虑到哈希表的存储效率一般只有 50%,实际需要的内 存在 4 TB以上。即使把这些网址放到了计算机的内存中,由于网址长度不固定, 以字符串的形式查找的效率会很低。因此,我们如果能够找到一个函数,将这 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 以前被认为是没有漏洞的,现在已经被中国 的王小云教授证明存在漏洞。但是大家不必恐慌, 因为这和黑客能真正攻破你 的注册信息是还两回事。

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

声明: 除非转自他站(如有侵权,请联系处理)外,本文采用 BY-NC-SA 协议进行授权 | 智乐兔
转载请注明:转自《数学应用-信息指纹及其应用
本文地址:https://www.zhiletu.com/archives-2806.html
关注公众号:智乐兔

赞赏

wechat pay微信赞赏alipay pay支付宝赞赏

上一篇
下一篇

相关文章

在线留言

你必须 登录后 才能留言!

在线客服
在线客服 X

售前: 点击这里给我发消息
售后: 点击这里给我发消息

智乐兔官微