【MD5】
簡介
MD5的全稱是Message-Digest Algorithm 5（信息-摘要算法），在90年代初由Ronald L. Rivest開發出來，經MD2、MD3和MD4發展而來。
MD5是一種散列(Hash)算法，散列算法的用途不是對明文加密，讓別人看不懂，而是通過對信息摘要的比對，防止對原文的篡改。通常對散列算法而言，所謂的“破解”，就是找碰撞。
MD5是把一個任意長度的字節串加密成一個固定長度的大整數（通常是16位或32位），加密的過程中要篩選過濾掉一些原文的數據信息，因此想通過對加密的結果進行逆運算來得出原文是不可能的。
關于MD5的應用，舉個具體的例子吧。例如你在一個論壇注冊一個賬號，密碼設為“qiuyu21”。此密碼經過MD5運算后，變成“287F1E255D930496EE01037339CD978D”，當你點“提交”按鈕提交時，服務器的數據庫中不記錄你的真正密碼“qiuyu21”，而是記錄那個MD5的運算結果。然后，你在此論壇登錄，登錄時你用的密碼是“qiuyu21”，電腦再次進行MD5運算，把“qiuyu21”轉為“287F1E255D930496EE01037339CD978D”，然后傳送到服務器那邊。這時服務器就把你傳過來的MD5運算結果與數據庫中你注冊時的MD5運算結果比較，如果相同則登錄成功。
也就是說，服務器只是把MD5運算結果作比較。你也許會問，服務器為什么不用直接對你的密碼“qiuyu21”進行校驗呢？因為如果服務器的數據庫里存的是你的真實密碼，那么黑客只要破解了服務器的數據庫，那么他也就得到了所有人的密碼，他可以用里面的任意密碼進行登錄。但是如果數據庫里面的密碼都是MD5格式的，那么即使黑客得到了“287F1E255D930496EE01037339CD978D”這一串數字，他也不能以此作為密碼來登錄。
現在再來談談MD5的破解。假設你是攻擊者，已經得到了“287F1E255D930496EE01037339CD978D”這一串數字，那么你怎么能得出我的密碼是“qiuyu21”呢？因為MD5算法是不可逆的，你只能用暴力法(窮舉法)來破解，就是列舉所有可能的字母和數字的排列組合，然后一一進行MD5運算來驗證運算結果是否為“287F1E255D930496EE01037339CD978D”，“qiuyu21”這個密碼是7位英文字符和數字混合，這樣的排列組合的數量是個天文數字，如果一一列舉，那么在你有生之年是看不到了。所以只有使用黑客字典才是一種有效可行的方法，黑客字典可以根據一些規則自動生成。例如“qiuyu21”這個密碼，就是一種常見的組合，規則是：拼音+拼音+數字，拼音總共大約400個，數字以2位數100個來算，這種規則總共約400*400*100=16,000,000種可能，使用優化的算法，估計用1秒就能破解吧。就算考慮到字母開頭大寫或全部大寫的習慣，也只會花大約10幾秒時間。如果是破解你熟悉的某個人的密碼，那么你可以根據你對他的了解來縮小詞典的范圍，以便更快速的破解。這種破解方法在很大程度上依賴于你的運氣。
最后談談MD5的碰撞。根據密碼學的定義，如果內容不同的明文，通過散列算法得出的結果（密碼學稱為信息摘要）相同，就稱為發生了“碰撞”。因為MD5值可以由任意長度的字符計算出來，所以可以把一篇文章或者一個軟件的所有字節進行MD5運算得出一個數值，如果這篇文章或軟件的數據改動了，那么再計算出的MD5值也會產生變化，這種方法常常用作數字簽名校驗。因為明文的長度可以大于MD5值的長度，所以可能會有多個明文具有相同的MD5值，如果你找到了兩個相同MD5值的明文，那么你就是找到了MD5的“碰撞”。
散列算法的碰撞分為兩種，強無碰撞和弱無碰撞。還是以前面那個密碼為例：假如你已知“287F1E255D930496EE01037339CD978D”這個MD5值，然后找出了一個單詞碰巧也能計算出和“qiuyu21”相同的MD5值，那么你就找到了MD5的“弱無碰撞”，其實這就意味著你已經破解了MD5。如果不給你指定的MD5值，讓你隨便去找任意兩個相同MD5值的明文，即找“強無碰撞”，顯然要相對容易些了，但對于好的散列算法來說，做到這一點也很不容易了。
值得一提的是，強無碰撞已經被中國的王小云老師給搞定了，她提出的算法可以在短時間內找到碰撞，在世界上引起了轟動，現在的電腦大約一兩個小時就可以找到一對碰撞。遺憾的是，找到強無碰撞在實際破解中沒有什么真正的用途，所以現在MD5仍然是很安全的。
MD5算法描述
對MD5算法簡要的敘述可以為：MD5以512位分組來處理輸入的信息，且每一分組又被劃分為16個32位子分組，經過了一系列的處理后，算法的輸出由四個32位分組組成，將這四個32位分組級聯后將生成一個128位散列值。
在MD5算法中，首先需要對信息進行填充，使其字節長度對512求余的結果等于448。因此，信息的字節長度（Bits Length）將被擴展至N*512+448，即N*64+56個字節（Bytes），N為一個正整數。填充的方法如下，在信息的后面填充一個1和無數個0，直到滿足上面的條件時才停止用0對信息的填充。然后，在在這個結果后面附加一個以64位二進制表示的填充前信息長度。經過這兩步的處理，現在的信息字節長度=N*512+448+64=(N+1)*512，即長度恰好是512的整數倍。這樣做的原因是為滿足后面處理中對信息長度的要求。
MD5中有四個32位被稱作鏈接變量（Chaining Variable）的整數參數，他們分別為：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。
當設置好這四個鏈接變量后，就開始進入算法的四輪循環運算。循環的次數是信息中512位信息分組的數目。
將上面四個鏈接變量復制到另外四個變量中：A到a，B到b，C到c，D到d。
主循環有四輪（MD4只有三輪），每輪循環都很相似。第一輪進行16次操作。每次操作對a、b、c和d中的其中三個作一次非線性函數運算，然后將所得結果加上第四個變量，文本的一個子分組和一個常數。再將所得結果向右環移一個不定的數，并加上a、b、c或d中之一。最后用該結果取代a、b、c或d中之一。以一下是每次操作中用到的四個非線性函數（每輪一個）。
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))
（&是與，|是或，~是非，^是異或）
這四個函數的說明：如果X、Y和Z的對應位是獨立和均勻的，那么結果的每一位也應是獨立和均勻的。F是一個逐位運算的函數。即，如果X，那么Y，否則Z。函數H是逐位奇偶操作符。
假設Mj表示消息的第j個子分組（從0到15）:
<< FF(a,b,c,d,Mj,s,ti) 表示 a=b+((a+(F(b,c,d)+Mj+ti)
<< GG(a,b,c,d,Mj,s,ti) 表示 a=b+((a+(G(b,c,d)+Mj+ti)
<< HH(a,b,c,d,Mj,s,ti) 表示 a=b+((a+(H(b,c,d)+Mj+ti)
<< II(a,b,c,d,Mj,s,ti) 表示 a=b+((a+(I(b,c,d)+Mj+ti)
這四輪（64步）是：
第一輪
FF(a,b,c,d,M0,7,0xd76aa478)
FF(d,a,b,c,M1,12,0xe8c7b756)
FF(c,d,a,b,M2,17,0x242070db)
FF(b,c,d,a,M3,22,0xc1bdceee)
FF(a,b,c,d,M4,7,0xf57c0faf)
FF(d,a,b,c,M5,12,0x4787c62a)
FF(c,d,a,b,M6,17,0xa8304613)
FF(b,c,d,a,M7,22,0xfd469501)
FF(a,b,c,d,M8,7,0x698098d8)
FF(d,a,b,c,M9,12,0x8b44f7af)
FF(c,d,a,b,M10,17,0xffff5bb1)
FF(b,c,d,a,M11,22,0x895cd7be)
FF(a,b,c,d,M12,7,0x6b901122)
FF(d,a,b,c,M13,12,0xfd987193)
FF(c,d,a,b,M14,17,0xa679438e)
FF(b,c,d,a,M15,22,0x49b40821)
第二輪
GG(a,b,c,d,M1,5,0xf61e2562)
GG(d,a,b,c,M6,9,0xc040b340)
GG(c,d,a,b,M11,14,0x265e5a51)
GG(b,c,d,a,M0,20,0xe9b6c7aa)
GG(a,b,c,d,M5,5,0xd62f105d)
GG(d,a,b,c,M10,9,0x02441453)
GG(c,d,a,b,M15,14,0xd8a1e681)
GG(b,c,d,a,M4,20,0xe7d3fbc8)
GG(a,b,c,d,M9,5,0x21e1cde6)
GG(d,a,b,c,M14,9,0xc33707d6)
GG(c,d,a,b,M3,14,0xf4d50d87)
GG(b,c,d,a,M8,20,0x455a14ed)
GG(a,b,c,d,M13,5,0xa9e3e905)
GG(d,a,b,c,M2,9,0xfcefa3f8)
GG(c,d,a,b,M7,14,0x676f02d9)
GG(b,c,d,a,M12,20,0x8d2a4c8a)
第三輪
HH(a,b,c,d,M5,4,0xfffa3942)
HH(d,a,b,c,M8,11,0x8771f681)
HH(c,d,a,b,M11,16,0x6d9d6122)
HH(b,c,d,a,M14,23,0xfde5380c)
HH(a,b,c,d,M1,4,0xa4beea44)
HH(d,a,b,c,M4,11,0x4bdecfa9)
HH(c,d,a,b,M7,16,0xf6bb4b60)
HH(b,c,d,a,M10,23,0xbebfbc70)
HH(a,b,c,d,M13,4,0x289b7ec6)
HH(d,a,b,c,M0,11,0xeaa127fa)
HH(c,d,a,b,M3,16,0xd4ef3085)
HH(b,c,d,a,M6,23,0x04881d05)
HH(a,b,c,d,M9,4,0xd9d4d039)
HH(d,a,b,c,M12,11,0xe6db99e5)
HH(c,d,a,b,M15,16,0x1fa27cf8)
HH(b,c,d,a,M2,23,0xc4ac5665)
第四輪
II(a,b,c,d,M0,6,0xf4292244)
II(d,a,b,c,M7,10,0x432aff97)
II(c,d,a,b,M14,15,0xab9423a7)
II(b,c,d,a,M5,21,0xfc93a039)
II(a,b,c,d,M12,6,0x655b59c3)
II(d,a,b,c,M3,10,0x8f0ccc92)
II(c,d,a,b,M10,15,0xffeff47d)
II(b,c,d,a,M1,21,0x85845dd1)
II(a,b,c,d,M8,6,0x6fa87e4f)
II(d,a,b,c,M15,10,0xfe2ce6e0)
II(c,d,a,b,M6,15,0xa3014314)
II(b,c,d,a,M13,21,0x4e0811a1)
II(a,b,c,d,M4,6,0xf7537e82)
II(d,a,b,c,M11,10,0xbd3af235)
II(c,d,a,b,M2,15,0x2ad7d2bb)
II(b,c,d,a,M9,21,0xeb86d391)
常數ti可以如下選擇：
在第i步中，ti是4294967296*abs(sin(i))的整數部分，i的單位是弧度。(4294967296等于2的32次方)所有這些完成之后，將A、B、C、D分別加上a、b、c、d。然后用下一分組數據繼續運行算法，最后的輸出是A、B、C和D的級聯。
當你按照我上面所說的方法實現MD5算法以后，你可以用以下幾個信息對你做出來的程序作一個簡單的測試，看看程序有沒有錯誤。
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a
MD5的安全性
MD5相對MD4所作的改進：
1. 增加了第四輪；
2. 每一步均有唯一的加法常數；
3. 為減弱第二輪中函數G的對稱性從(X&Y)|(X&Z)|(Y&Z)變為(X&Z)|(Y&(~Z))；
4. 第一步加上了上一步的結果，這將引起更快的雪崩效應；
5. 改變了第二輪和第三輪中訪問消息子分組的次序，使其更不相似；
6. 近似優化了每一輪中的循環左移位移量以實現更快的雪崩效應。各輪的位移量互不相同。
————————以上內容均轉自《灰灰的密碼學筆記》特此說明！！ |
