今天在一本書上,看到說MD5這種檢查碼是唯一的
這看起來實在有點不對…
MD5為一個長度有限的檢查碼
那本書是寫 128bits,可是我看到的結果好像又不是這麼一回事
27f3c2198a992d2f6748363f0c9d8feb 這是隨便找一個檔案算出來的
為一個長度32的16進位碼,換算成2進位是32*16=512bits

不過不管結果為多少,在長度有限的情況下,就不可能是唯一的結果
不過讓人好奇的又來了,如果不是唯一,那遇到MD5 hash相同的機率是多少呢?

有一點概念的可能會很快的算出是2的512次方
先說一下怎麼得到的

想像每一個位元代表一個開關,每一個開關有開跟關兩種變化
所以兩個開關有2的平方四種變化,那512個開關就有2的512次方這麼多種

可是真的是這樣嗎?這個結果只是假設對無窮的檔案來說,MD5 hash算出的各種結果是平均的
就是每一個開關被打開的機率是一樣。
如果每一種開關被打開的機率不一樣呢?

先來做個簡單的,來丟銅版吧
一個正常的銅版丟兩次,兩次一樣的機是1/2
算法有兩種

第一種:不管第一次出現的是什麼,第二次出現的一定要和第一次一樣,而第二次只有兩種可能,所以是1/2
第二種:第一次丟到正面的機率是1/2,第二次丟到正面的機率還是1/2
或是 第一次丟到反面的機率是1/2,第二次丟到反面的機率還是1/2
所以兩次都正面的機率是 1/4,兩次都反面的機率也是1/4,加起來就是1/2

那不公正的呢?假設正面的機率是1/3,反面是2/3呢?會算嗎?
答案是5/9
算法一樣有兩種,而且跟前面一樣

先說第二種:
第二種:第一次丟到正面的機率是1/3,第二次丟到正面的機率還是1/3
或是 第一次丟到反面的機率是2/3,第二次丟到反面的機率還是2/3
所以兩次都正面的機率是 1/9,兩次都反面的機率也是4/9,加起來就是5/9
第一種則稍微有點變化
一樣是不論第一次丟到什麼,第二次還是要跟第一次一樣
可是由於第一次正反出現的機率or可以說權重不一樣,所以答案是5/9

第一種的方法有點類似通訊講的事情機率,事後機率等,不過太複雜了,請自行去看通訊的書吧。
很明顯的,銅版不公正的時候,兩次一樣的機率反而變大了
會証明嗎?
簡單的來証一下吧

假設正面的機率是p,反面就是1-p
用法二得到丟兩次出現相同的機率就是:p^2+(1-p)^2
展開得到:2*p^2-2*p+1
這是一個二元一次多項式,最小值是1/2

所以可以知道在公正的情況下出現相同的機率是最小,1/2
不過這只是很簡單的例子,如果要套用在上面的MD5 hash,要用連續函數下次証比較快。
不過可以知道,2的512次方是MD5 hash出現一樣的最小機率…

但話又說回來,如果MD5是一個平均分佈,對每一個位元出現的機率都相等的時候
遇到兩個檔案算出來的MD5 hash一樣的可能是2的512次方
那還是在假設每一種檔案出現的機率都一樣,所以才會有這樣的答案
又是一個事前機率,事後機率的問題了…
所以還是無法算出真正遇到兩次相同的機率,只能知道這其中的最小值而已

Powered by ScribeFire.

Loading Comments…
more
Allowed HTML tags and attributes: <a href="" title=""> <blockquote> <code> <em> <strong>