【MD5】
簡介
MD5的全稱是Message-Digest Algorithm 5（信息-摘要算法），在90年代初由Ronald L. Rivest開發(fā)出來，經(jīng)MD2、MD3和MD4發(fā)展而來。
MD5是一種散列(Hash)算法，散列算法的用途不是對明文加密，讓別人看不懂，而是通過對信息摘要的比對，防止對原文的篡改。通常對散列算法而言，所謂的“破解”，就是找碰撞。
MD5是把一個任意長度的字節(jié)串加密成一個固定長度的大整數(shù)（通常是16位或32位），加密的過程中要篩選過濾掉一些原文的數(shù)據(jù)信息，因此想通過對加密的結(jié)果進行逆運算來得出原文是不可能的。
關(guān)于MD5的應(yīng)用，舉個具體的例子吧。例如你在一個論壇注冊一個賬號，密碼設(shè)為“qiuyu21”。此密碼經(jīng)過MD5運算后，變成“287F1E255D930496EE01037339CD978D”，當你點“提交”按鈕提交時，服務(wù)器的數(shù)據(jù)庫中不記錄你的真正密碼“qiuyu21”，而是記錄那個MD5的運算結(jié)果。然后，你在此論壇登錄，登錄時你用的密碼是“qiuyu21”，電腦再次進行MD5運算，把“qiuyu21”轉(zhuǎn)為“287F1E255D930496EE01037339CD978D”，然后傳送到服務(wù)器那邊。這時服務(wù)器就把你傳過來的MD5運算結(jié)果與數(shù)據(jù)庫中你注冊時的MD5運算結(jié)果比較，如果相同則登錄成功。
也就是說，服務(wù)器只是把MD5運算結(jié)果作比較。你也許會問，服務(wù)器為什么不用直接對你的密碼“qiuyu21”進行校驗?zāi)兀恳驗槿绻?wù)器的數(shù)據(jù)庫里存的是你的真實密碼，那么黑客只要破解了服務(wù)器的數(shù)據(jù)庫，那么他也就得到了所有人的密碼，他可以用里面的任意密碼進行登錄。但是如果數(shù)據(jù)庫里面的密碼都是MD5格式的，那么即使黑客得到了“287F1E255D930496EE01037339CD978D”這一串數(shù)字，他也不能以此作為密碼來登錄。
現(xiàn)在再來談?wù)凪D5的破解。假設(shè)你是攻擊者，已經(jīng)得到了“287F1E255D930496EE01037339CD978D”這一串數(shù)字，那么你怎么能得出我的密碼是“qiuyu21”呢？因為MD5算法是不可逆的，你只能用暴力法(窮舉法)來破解，就是列舉所有可能的字母和數(shù)字的排列組合，然后一一進行MD5運算來驗證運算結(jié)果是否為“287F1E255D930496EE01037339CD978D”，“qiuyu21”這個密碼是7位英文字符和數(shù)字混合，這樣的排列組合的數(shù)量是個天文數(shù)字，如果一一列舉，那么在你有生之年是看不到了。所以只有使用黑客字典才是一種有效可行的方法，黑客字典可以根據(jù)一些規(guī)則自動生成。例如“qiuyu21”這個密碼，就是一種常見的組合，規(guī)則是：拼音+拼音+數(shù)字，拼音總共大約400個，數(shù)字以2位數(shù)100個來算，這種規(guī)則總共約400*400*100=16,000,000種可能，使用優(yōu)化的算法，估計用1秒就能破解吧。就算考慮到字母開頭大寫或全部大寫的習慣，也只會花大約10幾秒時間。如果是破解你熟悉的某個人的密碼，那么你可以根據(jù)你對他的了解來縮小詞典的范圍，以便更快速的破解。這種破解方法在很大程度上依賴于你的運氣。
最后談?wù)凪D5的碰撞。根據(jù)密碼學的定義，如果內(nèi)容不同的明文，通過散列算法得出的結(jié)果（密碼學稱為信息摘要）相同，就稱為發(fā)生了“碰撞”。因為MD5值可以由任意長度的字符計算出來，所以可以把一篇文章或者一個軟件的所有字節(jié)進行MD5運算得出一個數(shù)值，如果這篇文章或軟件的數(shù)據(jù)改動了，那么再計算出的MD5值也會產(chǎn)生變化，這種方法常常用作數(shù)字簽名校驗。因為明文的長度可以大于MD5值的長度，所以可能會有多個明文具有相同的MD5值，如果你找到了兩個相同MD5值的明文，那么你就是找到了MD5的“碰撞”。
散列算法的碰撞分為兩種，強無碰撞和弱無碰撞。還是以前面那個密碼為例：假如你已知“287F1E255D930496EE01037339CD978D”這個MD5值，然后找出了一個單詞碰巧也能計算出和“qiuyu21”相同的MD5值，那么你就找到了MD5的“弱無碰撞”，其實這就意味著你已經(jīng)破解了MD5。如果不給你指定的MD5值，讓你隨便去找任意兩個相同MD5值的明文，即找“強無碰撞”，顯然要相對容易些了，但對于好的散列算法來說，做到這一點也很不容易了。
值得一提的是，強無碰撞已經(jīng)被中國的王小云老師給搞定了，她提出的算法可以在短時間內(nèi)找到碰撞，在世界上引起了轟動，現(xiàn)在的電腦大約一兩個小時就可以找到一對碰撞。遺憾的是，找到強無碰撞在實際破解中沒有什么真正的用途，所以現(xiàn)在MD5仍然是很安全的。
MD5算法描述
對MD5算法簡要的敘述可以為：MD5以512位分組來處理輸入的信息，且每一分組又被劃分為16個32位子分組，經(jīng)過了一系列的處理后，算法的輸出由四個32位分組組成，將這四個32位分組級聯(lián)后將生成一個128位散列值。
在MD5算法中，首先需要對信息進行填充，使其字節(jié)長度對512求余的結(jié)果等于448。因此，信息的字節(jié)長度（Bits Length）將被擴展至N*512+448，即N*64+56個字節(jié)（Bytes），N為一個正整數(shù)。填充的方法如下，在信息的后面填充一個1和無數(shù)個0，直到滿足上面的條件時才停止用0對信息的填充。然后，在在這個結(jié)果后面附加一個以64位二進制表示的填充前信息長度。經(jīng)過這兩步的處理，現(xiàn)在的信息字節(jié)長度=N*512+448+64=(N+1)*512，即長度恰好是512的整數(shù)倍。這樣做的原因是為滿足后面處理中對信息長度的要求。
MD5中有四個32位被稱作鏈接變量（Chaining Variable）的整數(shù)參數(shù)，他們分別為：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。
當設(shè)置好這四個鏈接變量后，就開始進入算法的四輪循環(huán)運算。循環(huán)的次數(shù)是信息中512位信息分組的數(shù)目。
將上面四個鏈接變量復制到另外四個變量中：A到a，B到b，C到c，D到d。
主循環(huán)有四輪（MD4只有三輪），每輪循環(huán)都很相似。第一輪進行16次操作。每次操作對a、b、c和d中的其中三個作一次非線性函數(shù)運算，然后將所得結(jié)果加上第四個變量，文本的一個子分組和一個常數(shù)。再將所得結(jié)果向右環(huán)移一個不定的數(shù)，并加上a、b、c或d中之一。最后用該結(jié)果取代a、b、c或d中之一。以一下是每次操作中用到的四個非線性函數(shù)（每輪一個）。
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))
（&是與，|是或，~是非，^是異或）
這四個函數(shù)的說明：如果X、Y和Z的對應(yīng)位是獨立和均勻的，那么結(jié)果的每一位也應(yīng)是獨立和均勻的。F是一個逐位運算的函數(shù)。即，如果X，那么Y，否則Z。函數(shù)H是逐位奇偶操作符。
假設(shè)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)
常數(shù)ti可以如下選擇：
在第i步中，ti是4294967296*abs(sin(i))的整數(shù)部分，i的單位是弧度。(4294967296等于2的32次方)所有這些完成之后，將A、B、C、D分別加上a、b、c、d。然后用下一分組數(shù)據(jù)繼續(xù)運行算法，最后的輸出是A、B、C和D的級聯(lián)。
當你按照我上面所說的方法實現(xiàn)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. 每一步均有唯一的加法常數(shù)；
3. 為減弱第二輪中函數(shù)G的對稱性從(X&Y)|(X&Z)|(Y&Z)變?yōu)?X&Z)|(Y&(~Z))；
4. 第一步加上了上一步的結(jié)果，這將引起更快的雪崩效應(yīng)；
5. 改變了第二輪和第三輪中訪問消息子分組的次序，使其更不相似；
6. 近似優(yōu)化了每一輪中的循環(huán)左移位移量以實現(xiàn)更快的雪崩效應(yīng)。各輪的位移量互不相同。
————————以上內(nèi)容均轉(zhuǎn)自《灰灰的密碼學筆記》特此說明！！ |
