看到網(wǎng)上一些對(duì)于MD5的介紹，還有對(duì)于當(dāng)初王小云所做的破解有很多的誤解，或者說(shuō)不理解，然后覺(jué)得對(duì)于這些事情只要說(shuō)明白，還是比較好理解的說(shuō)。
首先MD5其實(shí)就是一種hash，或者叫散列函數(shù)，有的地方叫雜湊函數(shù)，都是一個(gè)東西，其實(shí)它就是一種映射，而平常最常見(jiàn)的就是說(shuō)MD5是不可逆的，為什么不可逆呢？有人就說(shuō)就是像有些函數(shù)沒(méi)有反函數(shù)那樣了，其實(shí)還是有點(diǎn)抽象，考慮MD5是多對(duì)一的映射，也就是說(shuō)很多不同的經(jīng)過(guò)MD5變換之后可能會(huì)是相同的，那么既然多對(duì)一，自然是不可逆啦，你怎么會(huì)知道他到底是由哪個(gè)變換過(guò)來(lái)的呢。在密碼學(xué)的應(yīng)用里，說(shuō)是單向函數(shù)，或者說(shuō)單向變換，一種是這種多對(duì)一不可逆，還有一種是說(shuō)逆工程會(huì)非常困難，舉個(gè)例子吧，假設(shè)f(x)=x^6-x-1，然后你知道f(1)=-1，在知道x=1和f的情況下計(jì)算f(1)是很簡(jiǎn)單的，而知道f(x)=-1和f去求x卻是很困難的，這里就不展開(kāi)說(shuō)了，大家有個(gè)大體的認(rèn)識(shí)就可以了。
 
（圖來(lái)自維基百科）
 
剛才說(shuō)過(guò)了由于MD5是多對(duì)一的，所以肯定會(huì)出現(xiàn)變換后的值是一樣的情況，這種情況叫做沖突，或者叫碰撞。為了保證安全性，定義了兩種，一種叫無(wú)弱碰撞，一種叫無(wú)強(qiáng)碰撞。
無(wú)弱碰撞是
已知函數(shù)M和一段數(shù)據(jù)H
找到一個(gè)H'
使得M(H)=M(H')
是難的
無(wú)強(qiáng)碰撞是
       已知M
找到一對(duì)H和H'
使得M(H)=M(H')
是難的
很明顯滿足無(wú)強(qiáng)碰撞比滿足無(wú)弱碰撞更難，真的嗎？好吧，就不說(shuō)明顯了，為什么說(shuō)無(wú)強(qiáng)碰撞更難呢，換句話說(shuō)為什么找到強(qiáng)碰撞更簡(jiǎn)單呢，恩，這就涉及到生日悖論了， 或者叫生日攻擊了。
來(lái)想想以前的概率吧，假設(shè)一年365天，那么，至少有多少人使得有兩人是同樣生日的概率會(huì)超過(guò)1/2呢，直覺(jué)上應(yīng)該是365/2個(gè)人吧，其實(shí)答案是23，少的夸張是吧，不然不會(huì)叫做悖論了啊，如何計(jì)算呢，其實(shí)我們是在求一個(gè)最小的n，使得1-(1-1/365)*(1-2/365)*…(1-(n-1)*365)>=1/2，隨便寫(xiě)個(gè)程序驗(yàn)證下就知道是23了，什么你不知道這個(gè)式子怎么得來(lái)的，考慮第二個(gè)人不要和第一個(gè)人生日沖突的概率是(1-1/365)然后第三個(gè)人不和前兩個(gè)人生日相同的概率是(1-2/365)后面就知道了吧。然后這個(gè)人數(shù)其實(shí)是O(sqrt(365))。那么回到前面的問(wèn)題，假設(shè)映射空間，就是說(shuō)最后能夠得到的值的個(gè)數(shù)是m，那么弱碰撞的復(fù)雜度是O(m)，而強(qiáng)碰撞呢是O(sqrt(m))，所以說(shuō)找到強(qiáng)碰撞更簡(jiǎn)單，也就是說(shuō)滿足無(wú)強(qiáng)碰撞更難！
王小云的貢獻(xiàn)呢就是找到了比生日攻擊復(fù)雜度低得多算法來(lái)快速找到一對(duì)強(qiáng)碰撞，弱碰撞嗎依舊是不行的。這里有她的論文，有興趣的可以看一下。那么也就是說(shuō)通過(guò)密文找到明文依舊是不可能的，并且弱碰撞依舊是很難的。
不過(guò)后來(lái)又有外國(guó)的nb人受到了王小云的啟發(fā)，得到了一種很快的算法能夠在已知前綴x1,x2的情況下構(gòu)造一對(duì)后綴y1,y2使得M(x1y1)=M(x2y2)，不過(guò)有兩點(diǎn)需要注意，一個(gè)是他其實(shí)還是一種尋找強(qiáng)碰撞，另一個(gè)就是他的復(fù)雜度比王小云的直接構(gòu)造高的多，然后這里有論文，然后利用這個(gè)搞了個(gè)預(yù)測(cè)2008年美國(guó)大選結(jié)果的東西，為啥叫預(yù)測(cè)呢，因?yàn)榭梢赃@樣
因?yàn)槲艺f(shuō)我知道大選結(jié)果，但是必須事后公布，為了保證我沒(méi)有說(shuō)謊，我先給出一段MD5的值，之后給出我的結(jié)果，只要結(jié)果和MD5相同不就是我預(yù)測(cè)成功了嗎
這個(gè)東西是基于我很難構(gòu)造兩個(gè)東西使得他們的MD5相同的基礎(chǔ)上的，不過(guò)有了上面的算法，這個(gè)事情的復(fù)雜度大大降低，使得變?yōu)榱丝赡堋?br />那么這些破解對(duì)于我們有什么影響呢，首先需要認(rèn)識(shí)到MD5有什么用，現(xiàn)在很多網(wǎng)站都用MD5來(lái)驗(yàn)證文件的完整性，但是你從非官方的地方下載了文件發(fā)現(xiàn)MD5相同，那么你依然不能掉以輕心，因?yàn)榭赡苁峭ㄟ^(guò)上述算法而在程序里加入了某段病毒代碼，但是MD5還是相同的而已，所以下文件還是從官方地址下吧，還一個(gè)就是經(jīng)常在數(shù)字簽名里使用了，至于不知道數(shù)字簽名的這里先不說(shuō)了，然后這個(gè)可以偽造數(shù)字簽名啥的，不過(guò)傳說(shuō)現(xiàn)在貌似沒(méi)誰(shuí)用MD5來(lái)弄數(shù)字簽名了，也不必太過(guò)擔(dān)心了，基本就是這樣子了。