MD5（Message-Digest Algorithm），想必大家都再熟悉不過了吧。通常我們調用第三方支付接口的時候都會遇到這種算法或者SHA等等類似的算法來做簽名驗證，由于其是不可逆的算法，對應破解難度也很大。

底層原理

MD5算法的過程分為四步：處理原文，設置初始值，循環加工，拼接結果。

處理原文

首先，我們計算出原文長度(bit)對512求余的結果，如果不等于448，就需要填充原文使得原文對512求余的結果等于448。填充的方法是第一位填充1，其余位填充0。填充完后，信息的長度就是512*N+448。

之后，用剩余的位置（512-448=64位）記錄原文的真正長度，把長度的二進制值補在最后。這樣處理后的信息長度就是512*(N+1)。

設置初始值

MD5的哈希結果長度為128位，按每32位分成一組共4組。這4組結果是由4個初始值A、B、C、D經過不斷演變得到。MD5的官方實現中，A、B、C、D的初始值如下（16進制）：

A=0x01234567

B=0x89ABCDEF

C=0xFEDCBA98

D=0x76543210

循環加工

這一步是最復雜的一步，我們看看下面這張圖，此圖代表了單次A,B,C,D值演變的流程。

單次子循環過程

圖中，A，B，C，D就是哈希值的四個分組。每一次循環都會讓舊的ABCD產生新的ABCD。一共進行多少次循環呢？由處理后的原文長度決定。

假設處理后的原文長度是M

主循環次數 = M / 512

每個主循環中包含 512 / 32 * 4 = 64 次 子循環。

1.綠色F

圖中的綠色F，代表非線性函數。官方MD5所用到的函數有四種：

F(X, Y, Z) =(X&Y) | ((~X) & Z)

G(X, Y, Z) =(X&Z) | (Y & (~Z))

H(X, Y, Z) =X^Y^Z

I(X, Y, Z)=Y^(X|(~Z))

在主循環下面64次子循環中，F、G、H、I 交替使用，第一個16次使用F，第二個16次使用G，第三個16次使用H，第四個16次使用I。

2.紅色“田”字

很簡單，紅色的田字代表相加的意思。

3.Mi

Mi是第一步處理后的原文。在第一步中，處理后原文的長度是512的整數倍。把原文的每512位再分成16等份，命名為M0~M15，每一等份長度32。在64次子循環中，每16次循環，都會交替用到M1~M16（命名+1）之一。

4.Ki

一個常量，在64次子循環中，每一次用到的常量都是不同的。

5.黃色的<<<S

循環左移S位，S的值也是常量。

“流水線”的最后，讓計算的結果和B相加，取代原先的B。新ABCD的產生可以歸納為：

新A = 原d

新B = b+((a+F(b,c,d)+Mj+Ki)<<<s)

新C = 原b

新D = 原c

總結一下主循環中的64次子循環，可以歸納為下面的四部分：

拼接結果

一步就很簡單了，把循環加工最終產生的A，B，C，D四個值拼接在一起，轉換成字符串即可

整個過程及其復雜和繁瑣，也促使它在一定程度上保證了hash值的均勻分布和安全性。

關于MD5破解的方法

即使MD5的加密如此復雜，但也并非不可破解的。但總體來說，所有的破解方法都采用“碰撞”方式，類似于不同字符的hash值可能相同的原理，即hash(A)==hash(B),盡管大多數的時候在內存中A!=B，但是MD5加密后的值是相同的。

那么怎么實現MD5的摘要碰撞呢？

MD5的破解方法及其多，像暴力枚舉，字典，彩虹表等方法。

1.暴力枚舉法

簡單暴力的枚舉出原文，并計算他們的hash值，看是否與摘要信息一致來達到破解目的。此方法時間復雜度極高，僅僅8位的密碼，只考慮Base64中的字符，就會有64^8中可能，如果只是單機破解，可能需要幾十年。當然，也可以取巧，例如考慮生日或者電話號碼等等，縮小窮舉范圍。

2.字典法

既然暴力破解這么費時，典型的以時間換空間，那么就有人采用了相反的方式，即字典法，拿空間換時間。

原理就是記錄盡可能多的原文和對應的hash值，破解的時候，拿到摘要去找查找對應的原文，即可快速的碰撞摘要信息從而達到破解的目的。

那么，對應的8位密碼，按照Base64可打印字符排列組合，大概需要多大的空間呢？

即（128+64）*64^8=6PB的空間，假設一臺計算器的內存為1TB，則需要6144臺計算機存儲所有的數據。而這對應的只是一個8位數的密碼，越長，存儲的成本也就成指數增長。

3.彩虹表法（比較燒腦，不感興趣的可以繞開）

了解彩虹表之前，先了解兩個函數：H(X),R(X)

H（X）：生成信息摘要的哈希函數，比如MD5，比如SHA256。

R（X）：從信息摘要轉換成另一個字符串的衰減函數（Reduce）。其中R（X）的定義域是H（X）的值域，R（X）的值域是H（X）的定義域。但要注意的是，R（X）并非H（X）的反函數。

通過交替運算H和R若干次，可以形成一個原文和哈希值的鏈條。假設原文是aaaaaa，哈希值長度32bit，那么哈希鏈表就是下面的樣子

這個鏈條有多長呢？假設H（X）和R（X）的交替重復K次，那么鏈條長度就是2K+1。同時，我們只需把鏈表的首段和末端存入哈希表中：

下面舉例說明：

給定信息摘要：920ECF10
如何得到原文呢？只需進行R（X）運算：

R（920ECF10） = kiebgt

查詢哈希表可以找到末端kiebgt對應的首端是aaaaaa，因此摘要920ECF10的原文“極有可能”在aaaaaa到kiebgt的這個鏈條當中。

接下來從aaaaaa開始，重新交替運算R（X）與H（X），看一看摘要值920ECF10是否是其中一次H（X）的結果。從鏈條看來，答案是肯定的，因此920ECF10的原文就是920ECF10的前置節點sgfnyd。

需要補充的是，如果給定的摘要值經過一次R（X）運算，結果在哈希表中找不到，可以繼續交替H（X）R（X）直到第K次為止

其實，每個hash鏈表維護了一組映射關系，每組包括k個映射，但只需存儲首位兩個字符串。假設K=10，那么其需要的存儲空間則為全量字典的1/10，效率也就提高了10倍。

即使如此，彩虹表的衰減函數R(X)依然存在致命弱點，即使R(X)設計的hash分布再均衡，依然存在hash碰撞的可能。

示例：

給定信息摘要：FB107E70
經過多次R（X），H（X）運算，得到結果kiebgt

通過哈希表查找末端kiebgt，可以找出首端aaaaaa

但是，FB107E70并不在aaaaaa到kiebgt的哈希鏈條當中，這就是R（X）的碰撞造成的。

這個問題看似沒什么影響，既然找不到就重新生成一組首尾映射即可。但是想象一下，當K值較大的時候，哈希鏈很長，一旦兩條不同的哈希鏈在某個節點出現碰撞，后面所有的明文和哈希值全都變成了一毛一樣的值。

這樣造成的后果就是冗余存儲。原本兩條哈希鏈可以存儲 2K個映射，由于重復，真正存儲的映射數量不足2K。

這個時候，彩虹表出現了，嗯，現在才是真正的彩虹表原理部分：

彩虹表對鏈表進行了改進，把原來的R(X)分割成R(1)....R(K)個衰減函數，這樣也可能發生碰撞，但最多同一級的碰撞，即R1和R1，R2和R2碰撞，大大避免了數據重復存儲的可能。

彩虹表示例

至于比彩虹表更厲害的方法，只能求助于中國的工程師了：

2004年，王小云教授提出了非常高效的MD5碰撞方法。

2009年，馮登國、謝濤利用差分攻擊，將MD5的碰撞算法復雜度進一步降低。

對于單機來說，暴力枚舉法的時間成本很高，字典法的空間成本很高。但是利用分布式計算和分布式存儲，仍然可以有效破解MD5算法。因此這兩種方法同樣被黑客們廣泛使用。

JAVA中MD5好用的工具

在java.security.MessageDigest下提供了獲取MD5示例和加密的方法

結果：4QrcOUm6Wau+VuBX8g+IPg==

為了方便大家閱讀，代碼使用了Base64對加密的結果進行了處理。

MD5/SHA到底是不是加密算法

網上看到大家討論MD5/SHA到底算不算加密算法，百度百科將其列為不可逆加密算法，我覺得既然傳輸的內容并進行了哈希計算，并且內容不可知且難以破解，原則上算是一種加密算法，但本人覺得沒必要在這上面浪費時間進行討論，面試官也絕不會因為這個問題決定是否聘用你，你只要搞清楚其中原理就好了。