学习网考试学习资料

Gzu521.com

走近消息摘要--Md5产生重复的概率

计算机软件水平考试   点击:次   发布时间:2006-11-30   【字体: 】   来源:Gzu521.com
贵 州 学 习 网
   问题:假设有十万个不同的文件,每个文件对应于一个md5。这十万个md5中,存在两个相同的md5的概率是多大?

  答:md5是128位hash码(4个整数,每个整数4个字节)。我们假设它的计算结果是足够随机和足够分散的。因此,一个文件的md5码,有2的128次方(用2e128表示,下面都用这种方式表示)个可能。进而我们知道,随意找出来的两个文件的md5码相等的可能性,是2e128分之一。下面讨论中,我们用r来表示这个概率(即r=2e-128)。

  假设这十万个md5是一条条插入到数据库中的。第二个md5插入时,它跟第一条重复的概率是r。第三条url插入时,它有可能跟第一条重复,也有可能跟第二条重复,因此总发生重复的概率是2×r。同理,第四条插入时发生重复的概率是3×r...第n条插入时发生重复的概率是(n-1)×r。n个md5码,其中有两个重复的概率是上面那么多个可能的加和。 ;'W@4g`/q}|=8'n4 [ 本 资 料 来 源 于 贵 州 学 习 网 IT认证计算机软件水平考试 http://Www.gzU521.com ] ;'W@4g`/q}|=8'n4

因此,n个md5码,自然产生重复的概率是:
  (1+2+3+...+(n-1))×r = (1/2)×n×(n-1)×r
  以n=10e4,r=1/2e128 代入,得到重复的概率为:
  (1/2)×10e4×(10e4-1)×(1/2e128)
  10e4-1约等于10e4,上式可以简化:
  (1/2)×10e8×(1/2e128)
  =10e8/(2×2e128)
我们使用近似2e10 = 1024 = 10e3,那么
  =10e8/(10e9*2e89)
  =1/(10*2e89)
  =1/(10*10e27)
  =1/(10e28)

  这个数字小得可怜,到底有多小,我们来算一下:一般福利彩票的中头奖的机会,约一百万份之一,即1/10e6。而上面的数字,相当1/10e22个一百万份之一。也就是说:相当于某人买了一亿亿亿次福彩,每次都中头奖的概率。
结论:对于十万条数据,发生md5冲突的概率非常小,可以忽略不计。

  那么,大约要多少个文件才能产生自然重复呢?根据上面的计算,对于n个md5码的集合,存在重复的概率是:
 (1/2)*(n/2e64)e2
因此,只有n大到可以与2e64比拟,才需要考虑它的冲突问题。

2e64是怎样的一个数字?
  2e64是4g个4g。目前32位系统的内存寻址范围才是区区4g。
形象地说就是:如果一台电脑上可以存放四十亿(4g)个文件,而系统中有四十亿台这样的电脑。那么,这么多的文件数才会令到系统自然产生重复。
  所以md5码作为系统的索引是非常可靠的。


补充:

  上面对于md5的计算,并未考虑到人为制造的md5冲突(现在已经有方法可以制造有冲突的md5码了),也未考虑到计算md5码时,因数据补零而造成的md5冲突。事实上,在一般的系统中,并没有必要考虑这两种情况。

责任编辑:gzu521

IT认证分类
计算机软件水平考试
全国计算机等级考试
思科认证
微软认证
ORACLE/CIW认证
Linux认证
JAVA认证
其它认证
分类推荐信息
更多...
大类最新文章
更多...