看到網(wǎng)上一些對于MD5的介紹，還有對于當初王小云所做的破解有很多的誤解，或者說不理解，然后覺得對于這些事情只要說明白，還是比較好理解的說。
首先MD5其實就是一種hash，或者叫散列函數(shù)，有的地方叫雜湊函數(shù)，都是一個東西，其實它就是一種映射，而平常最常見的就是說MD5是不可逆的，為什么不可逆呢？有人就說就是像有些函數(shù)沒有反函數(shù)那樣了，其實還是有點抽象，考慮MD5是多對一的映射，也就是說很多不同的經(jīng)過MD5變換之后可能會是相同的，那么既然多對一，自然是不可逆啦，你怎么會知道他到底是由哪個變換過來的呢。在密碼學的應用里，說是單向函數(shù)，或者說單向變換，一種是這種多對一不可逆，還有一種是說逆工程會非常困難，舉個例子吧，假設f(x)=x^6-x-1，然后你知道f(1)=-1，在知道x=1和f的情況下計算f(1)是很簡單的，而知道f(x)=-1和f去求x卻是很困難的，這里就不展開說了，大家有個大體的認識就可以了。

（圖來自維基百科）

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

版權(quán)聲明：本站文章來源標注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務器上建立鏡像，否則將依法追究法律責任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學習參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。