| 導購 | 订阅 | 在线投稿
分享
 
 
 

看看Md5自然産生重複的概率

來源:互聯網網民  2006-01-10 07:45:33  評論

問題:假設有十萬個不同的文件,每個文件對應于一個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碼,其中有兩個重複的概率是上面那麽多個可能的加和。

因此,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沖突。事實上,在一般的系統中,並沒有必要考慮這兩種情況。

 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
問題:假設有十萬個不同的文件,每個文件對應于一個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碼,其中有兩個重複的概率是上面那麽多個可能的加和。 因此,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沖突。事實上,在一般的系統中,並沒有必要考慮這兩種情況。
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 
 熱帖排行
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有