任何一段信息文字,都可以对应一个不太长的随机数,作为区别它和其它信息的指纹(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 亿个网址本身至少需要 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 以前被认为是没有漏洞的,现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌, 因为这和黑客能真正攻破你的注册信息是还两回事。
信息指纹的虽然历史很悠久,但真正的广泛应用是在有了互联网以后,这几年才渐渐热门起来。
分享到:
相关推荐
第三篇讲解如何亲手打造指纹模式识别系统,带领读者制作一个指纹模式识别系统的软硬件系统;第四篇讲解指纹模式识别应用技术基础,包括指纹模式识别技术各类应用的系统构造和源代码实现;第五篇讲解指纹电子产品技术...
本文重点研究应用于指纹识别、验证和分类的各种特征提取技术,因为它是图像处理中最重要的步骤。 特征提取技术分为局部(低级)和全局(高级)特征。 全局特征,如拱形、环形、三角形和螺纹,而局部特征如脊端和分叉...
OpenCV(Open Source Computer Vision Library)是一款开源的计算机视觉库,专门为图像和视频处理任务设计,广泛应用于学术研究、工业应用以及个人项目中。以下是关于OpenCV的详细介绍: 历史与发展 起源:OpenCV...
4.4 指纹识别的实际应用案例 204 4.4.1 指纹门禁系统 204 4.4.2 指纹考勤系统 205 4.5 指纹处理算法库测试程序 206 4.6 本章小结 218 第5章 数字水印技术 219 5.1 基本概念 219 5.1.1 水印技术的基本...
12、Internet安全体系结构有那三层() A、 应用层 B、 物理层 C、 网络层 D、 传输层 答案: ACD 13、鉴别服务的目的在于保证信息的可靠性。实现身份认证的主要方法包括口令、数字证书、基于生物特征(比如指纹、...
LZW压缩算法VC实现、改进及其应用研究.pdf MATCOM与VC_混合编程中自定义函数作为输入参数的调用方法.pdf MATCOM与VC_混合编程方法在图像处理中的应用.pdf MATLAB与VC_混合编程在系统辨识中的应用.pdf Matlab与VC...
LZW压缩算法VC实现、改进及其应用研究.pdf MATCOM与VC_混合编程中自定义函数作为输入参数的调用方法.pdf MATCOM与VC_混合编程方法在图像处理中的应用.pdf MATLAB与VC_混合编程在系统辨识中的应用.pdf Matlab与VC...
LZW压缩算法VC实现、改进及其应用研究.pdf MATCOM与VC_混合编程中自定义函数作为输入参数的调用方法.pdf MATCOM与VC_混合编程方法在图像处理中的应用.pdf MATLAB与VC_混合编程在系统辨识中的应用.pdf Matlab与VC...
MATLAB在数学建模中的应用(上下 源程序).rar MATLAB夜间车牌识别程序.rar MATLAB实现不同插值方法的GUI界面设计 源程序代码.rar MATLAB实现偏微分方程的差分计算 源程序代码.rar MATLAB实现图像去噪 滤波 锐化 ...
MATLAB在数学建模中的应用(上下 源程序).rar MATLAB夜间车牌识别程序.rar MATLAB实现不同插值方法的GUI界面设计 源程序代码.rar MATLAB实现偏微分方程的差分计算 源程序代码.rar MATLAB实现图像去噪 滤波 锐化 ...