逆向是不可能逆向的
在正式介紹MD5“破解”的方法前，先說(shuō)明一點(diǎn)：我們沒(méi)辦法把MD5碼還原對(duì)應(yīng)的原文。道理很簡(jiǎn)單，任意長(zhǎng)度的數(shù)據(jù)經(jīng)過(guò)MD5處理后，所包含的信息量已經(jīng)大大減少。要是可以還原的話，那MD5豈不是成為壓縮算法？？
所謂的“破解”指的是“碰撞”。即找到一個(gè)原文，算出來(lái)的MD5碼和已知的MD5碼一樣。接下來(lái)介紹一些常見(jiàn)的破解方法。
暴力碰撞：窮舉法&字典法
小標(biāo)題上寫(xiě)了兩種方法：窮舉法和字典法。但是我認(rèn)為它們的本質(zhì)是一樣的，都是利用計(jì)算機(jī)的資源嘗試碰撞已知的MD5碼。這里就放在一起了。
窮舉法非常簡(jiǎn)單，就是不停地嘗試各種字符的排列組合，看哪一個(gè)組合的MD5碼能對(duì)上�？上秉c(diǎn)是太耗費(fèi)時(shí)間了。我們舉個(gè)栗子，假設(shè)我們要破解一個(gè)6位大小寫(xiě)字母和數(shù)字混合的密碼，那么一共有 [公式] 種組合。這個(gè)數(shù)的大小超過(guò)500億。
既然計(jì)算如此費(fèi)時(shí)，能不能考慮把計(jì)算結(jié)果以映射表的形式存放起來(lái)，一個(gè)蘿卜一個(gè)坑，一個(gè)原文對(duì)應(yīng)著一個(gè)MD5碼呢？可以呀！這就是傳說(shuō)中的“字典法”。將已知的MD5碼查表，直接反查出原文。字典法體現(xiàn)了算法設(shè)計(jì)的“以空間換時(shí)間”的思想。缺點(diǎn)是比較耗費(fèi)空間。不過(guò)現(xiàn)在硬盤(pán)的價(jià)格變得白菜價(jià)了，空間開(kāi)銷不算什么。
這是一個(gè)用字典法破解MD5的網(wǎng)站：https://www.cmd5.com/password.aspx
時(shí)間和空間的折中：哈希鏈表&彩虹表法
如果說(shuō)窮舉法太耗費(fèi)時(shí)間，字典法太耗費(fèi)存儲(chǔ)空間的話，我們能不能考慮在時(shí)間消耗和空間消耗之間折中呢？我們可以考慮用鏈表將一系列有意義的原文和MD5碼串起來(lái)。
要構(gòu)造這樣的鏈表，我們需要兩個(gè)函數(shù)：哈希函數(shù)H(x)和衰減函數(shù)（reduction function）R(x)。哈希函數(shù)可以是MD5，也可以是其他的消息摘要算法。H(x)的值域是R(x)的定義域，R(x)的值域是H(x)的定義域。R(x)不是H(x)的反函數(shù)。
將一個(gè)原文不停地使用H(x)和R(x)交替進(jìn)行運(yùn)算k次，再將原文本身和運(yùn)算結(jié)果以鏈表的形式串接起來(lái)，就可以得到結(jié)點(diǎn)個(gè)數(shù)為2k+1的鏈表。實(shí)際存放的時(shí)候只存放首端和末端兩個(gè)原文即可。這種鏈表叫做“哈希鏈表”，體現(xiàn)了算法設(shè)計(jì)的“時(shí)空權(quán)衡”（Space and Time Tradeoffs）。
舉個(gè)栗子，假設(shè)原文s=abcabc，經(jīng)過(guò)2次交替運(yùn)算，得到以下的鏈表：
abcabc->H(x)->3C8B0D7A->R(x)->eopmca->H(x)->7E9F216C->R(x)->rapper
以上數(shù)據(jù)均為舉例編造的，僅為說(shuō)明原理使用。那我們存放這個(gè)鏈表的時(shí)候，只需要記錄abcabc和rapper兩個(gè)原文即可。
假設(shè)我們要破解的摘要值（哈希鏈表的H(x)不一定是MD5算法，這里用更準(zhǔn)確的說(shuō)法代替MD5碼）是7E9F216C，經(jīng)過(guò)R(x)運(yùn)算得到rapper，說(shuō)明我們要尋找的原文就在以rapper為末端的哈希鏈表中。從首端開(kāi)始經(jīng)過(guò)多次運(yùn)算，我們發(fā)現(xiàn)eopmca的摘要值就是7E9F216C。于是就反查出7E9F216C對(duì)應(yīng)的原文是eopmca。
如果在生成哈希鏈表的時(shí)候依次使用多個(gè)不一樣的R(x)，此時(shí)的哈希鏈表就是“彩虹表”。
這里有已經(jīng)計(jì)算好的彩虹表：http://project-rainbowcrack.com/table.htm
差分攻擊
上面介紹的窮舉法、字典法和彩虹表法都是暴力破解，適用于任何的消息摘要算法。真正意義上MD5算法的破解，是2004年山東大學(xué)王小云教授提出的MD5碰撞方法。她所用到的方法正是差分攻擊。
這種方法概括起來(lái)說(shuō)是這樣的：給定一個(gè)1024位的原文M1，加上一個(gè)特定的常數(shù)得到的新的明文M2。M1和M2的MD5碼是一樣的。（出處及具體操作見(jiàn)參考文獻(xiàn)[1]）這個(gè)特定的常數(shù)到底是怎么找出來(lái)的？筆者當(dāng)時(shí)在查閱原始文獻(xiàn)的時(shí)候也不清楚。因此后來(lái)的研究者開(kāi)始對(duì)怎么樣差分進(jìn)行了各種各樣的研究。這里就不再贅述。
后記
其實(shí)還有一種破解MD5的方法——長(zhǎng)度擴(kuò)展攻擊。不過(guò)這種方法是在一定條件下（破解加鹽之后產(chǎn)生的MD5碼）才能用的。這種方法由MD5分塊計(jì)算的特性而來(lái)。
1、算法的公開(kāi)并不意味著不安全；RSA 的算法也是公開(kāi)的，AES 也是公開(kāi)的�，F(xiàn)代密碼學(xué)的安全性從不是靠算法的保密來(lái)保證的。
2、目前沒(méi)有軟件能有效地破解 MD5。大多數(shù)時(shí)候只是把常見(jiàn)字符串的 MD5 存了起來(lái)為彩虹表，然后直接反查。
3、再次強(qiáng)調(diào) MD5 只是哈希，而不是加密。MD5 是沒(méi)有可能解密的，因?yàn)橐粋�(gè) MD5 可能對(duì)應(yīng)無(wú)數(shù)種可能的明文。
4、MD5 目前來(lái)說(shuō)還是可以用的，尤其是考慮到合適的加鹽以后可以解決大多數(shù)彩虹表帶來(lái)的危險(xiǎn)。當(dāng)然現(xiàn)在已經(jīng)很多人提倡用 SHA 系列的哈希算法取代 MD5。
對(duì)密碼學(xué)一竅不通，以上都是我亂編的，實(shí)在編不下去了……
