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

最新評論