????MD5 算法的原理及實現(xiàn)

章節(jié)目錄

簡介

算法描述

實現(xiàn)

作者能力有限, 如果您在閱讀過程中發(fā)現(xiàn)任何錯誤, 還請您務(wù)必聯(lián)系本人,指出錯誤, 避免后來讀者再學(xué)習(xí)錯誤的知識.謝謝!

簡介##

Wiki對其的描述:

MD5消息摘要算法（英語：MD5 Message-Digest Algorithm），一種被廣泛使用的密碼散列函數(shù)，可以產(chǎn)生出一個128位（16字節(jié)）的散列值（hash value），用于確保信息傳輸完整一致。MD5由美國密碼學(xué)家羅納德·李維斯特（Ronald Linn Rivest）設(shè)計，于1992年公開，用以取代MD4算法。這套算法的程序在 RFC 1321 中被加以規(guī)范。

將數(shù)據(jù)（如一段文字）運算變?yōu)榱硪还潭ㄩL度值，是散列算法的基礎(chǔ)原理。

1996年后被證實存在弱點，可以被加以破解，對于需要高度安全性的數(shù)據(jù)，專家一般建議改用其他算法，如SHA-2。2004年，證實MD5算法無法防止碰撞（collision），因此不適用于安全性認(rèn)證，如SSL公開密鑰認(rèn)證或是數(shù)字簽名等用途

MD5 算法是 MD4 算法的擴(kuò)展, MD5 比 MD4 算法稍微慢一些, 但是卻后者更難破解.

算法描述##

假設(shè)我們需要計算一個長度為 b bit 的信息的消息摘要, b 可以是零, b 也不需要是 8 的整數(shù)倍. 我么將它表示為:$$m_0{m}_1...m_{b?1}$$.

計算該消息的摘要,我們需要依次執(zhí)行以下五步:

填充###

我們需要將輸入消息的長度填充到差 64 就是 512 的整數(shù)倍長度.

填充方法:第一 bit 是 1, 接下來的所有比特填充 0.
填充操作總是需要進(jìn)行, 即使輸入的消息長度本身就滿足上述條件, 此時填充的長度時 512. 因此可能的填充長度時 1-512.

填充長度###

長度 b 被表示為 64 bit(little-endian, 低字節(jié)在前), 連接到第一步操作的尾部.

通過這部操作之后, 我們的消息長度此時正好是 512 的整數(shù)倍.

注意這里的長度 b 是原始數(shù)據(jù)的長度, 而不是經(jīng)過第一步填充之后的長度.

初始化幻數(shù)###

這里我們將用到四個幻數(shù): A, B, C, D. 他們的值分別如下:

A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L (至于為什么是這幾個數(shù)字,大家自己研究哈)

計算消息摘要###

這里我們需要 4 個函數(shù), 他們均輸入三個 32bit 的字,輸出一個 32bit 的字.

F(X,Y,Z) = XY v not(X) Z G(X,Y,Z) = XZ v Y not(Z) H(X,Y,Z) = X xor Y xor Z I(X,Y,Z) = Y xor (X v not(Z))

其中 v 為安慰或, not() 為按位取反, xor 為按位異或.

計算消息摘要,我們還需要一個表, 這個表有 64 個元素, 第 i 個元素的值是 4294967296 *abs(sin(i))

在計算消息摘要時, 我們將上述步驟所得消息輸入按照每 16 字(64 bit) 一小組進(jìn)行計算.

接下來我們就可以開始進(jìn)行真正的計算了, 計算方法 RFC 中描述如下:
下面?zhèn)未a中:
N 表示輸入消息所包含的字?jǐn)?shù)(不是字節(jié)數(shù)).
M 表示以字為單位,輸入消息所組成的數(shù)組, 它的長度為 N.
A, B, C, D 為步驟四中所定義的幻數(shù).

/* Process each 16-word block. */ For i = 0 to N/16-1 do/* Copy block i into X. */For j = 0 to 15 doSet X[j] to M[i*16+j].end /* of loop on j *//* Save A as AA, B as BB, C as CC, and D as DD. */AA = ABB = BCC = CDD = D/* Round 1. *//* Let [abcd k s i] denote the operationa = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). *//* Do the following 16 operations. */[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4][ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8][ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12][ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]/* Round 2. *//* Let [abcd k s i] denote the operationa = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). *//* Do the following 16 operations. */[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20][ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24][ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28][ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]/* Round 3. *//* Let [abcd k s t] denote the operationa = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). *//* Do the following 16 operations. */[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36][ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40][ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44][ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]/* Round 4. *//* Let [abcd k s t] denote the operationa = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). *//* Do the following 16 operations. */[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52][ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56][ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60][ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]/* Then perform the following additions. (That is increment eachof the four registers by the value it had before this block was started.) */A = A + AAB = B + BBC = C + CCD = D + DDend /* of loop on i */

輸出消息摘要###

通過上一步的計算, 我們得到了四個結(jié)果 A, B, C, D. 將上述四個字表示為 128 bit 即為輸入消息的消息摘要. 注意將 A, B, C, D 轉(zhuǎn)化為 bit 時采用小段表示法(低字節(jié)在前).

算法實現(xiàn)##

在這里, 我們采用 go 語言實現(xiàn)該算法.

package md5import "encoding/hex"const (A = uint32(0x67452301)B = uint32(0xEFCDAB89)C = uint32(0x98BADCFE)D = uint32(0x10325476) )type MD5 struct {r [4]uint32 // result }func (md5 *MD5) prepareData(rawData []byte) []byte {// paddingvar lenData, padLen uint32lenData = uint32(len(rawData))padLen = 0if lenData % 64 < 56 {padLen = 56 - (lenData % 64)} else {padLen = 64 + 56 - (lenData % 64)}pad := make([]byte, padLen)pad[0] = 0x80rawData = append(rawData, pad...)// append lengthbitLenBytes := make([]byte, 8)lenData = lenData << 3for i := uint32(0); i < 8; i++ {bitLenBytes[i] = byte(lenData >> (8 * i))}rawData = append(rawData, bitLenBytes...)return rawData }func (md5 *MD5) Digest(m []byte) {m = md5.prepareData(m)a, b, c, d := A, B, C, Dchunk := len(m) / 64 // process the data as 16-word blockfor k := 0; k < chunk; k++ {/* Copy block i into X. */// For j = 0 to 15 do// Set X[j] to M[i*16+j].// end /* of loop on j */var X [16]uint32j := 0for i := 0; i < 16; i++ {X[i] = uint32(m[(k*64)+j]) | uint32(m[(k*64)+j+1])<<8 | uint32(m[(k*64)+j+2])<<16 | uint32(m[(k*64)+j+3])<<24j += 4}/* Save A as AA, B as BB, C as CC, and D as DD. */AA, BB, CC, DD := a, b, c, d/* Round 1. *//* Let [abcd k s i] denote the operationa = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). *//* Do the following 16 operations. */// [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]a += (((c ^ d) & b) ^ d) + X[0] + 3614090360a = a<<7 | a>>(32-7) + bd += (((b ^ c) & a) ^ c) + X[1] + 3905402710d = d<<12 | d>>(32-12) + ac += (((a ^ b) & d) ^ b) + X[2] + 606105819c = c<<17 | c>>(32-17) + db += (((d ^ a) & c) ^ a) + X[3] + 3250441966b = b<<22 | b>>(32-22) + c// [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]a += (((c ^ d) & b) ^ d) + X[4] + 4118548399a = a<<7 | a>>(32-7) + bd += (((b ^ c) & a) ^ c) + X[5] + 1200080426d = d<<12 | d>>(32-12) + ac += (((a ^ b) & d) ^ b) + X[6] + 2821735955c = c<<17 | c>>(32-17) + db += (((d ^ a) & c) ^ a) + X[7] + 4249261313b = b<<22 | b>>(32-22) + c// [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]a += (((c ^ d) & b) ^ d) + X[8] + 1770035416a = a<<7 | a>>(32-7) + bd += (((b ^ c) & a) ^ c) + X[9] + 2336552879d = d<<12 | d>>(32-12) + ac += (((a ^ b) & d) ^ b) + X[10] + 4294925233c = c<<17 | c>>(32-17) + db += (((d ^ a) & c) ^ a) + X[11] + 2304563134b = b<<22 | b>>(32-22) + c// [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]a += (((c ^ d) & b) ^ d) + X[12] + 1804603682a = a<<7 | a>>(32-7) + bd += (((b ^ c) & a) ^ c) + X[13] + 4254626195d = d<<12 | d>>(32-12) + ac += (((a ^ b) & d) ^ b) + X[14] + 2792965006c = c<<17 | c>>(32-17) + db += (((d ^ a) & c) ^ a) + X[15] + 1236535329b = b<<22 | b>>(32-22) + c/* Round 2. *//* Let [abcd k s i] denote the operationa = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). *//* Do the following 16 operations. */// [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]a += (((b ^ c) & d) ^ c) + X[(1+5*0)&15] + 4129170786a = a<<5 | a>>(32-5) + bd += (((a ^ b) & c) ^ b) + X[(1+5*1)&15] + 3225465664d = d<<9 | d>>(32-9) + ac += (((d ^ a) & b) ^ a) + X[(1+5*2)&15] + 643717713c = c<<14 | c>>(32-14) + db += (((c ^ d) & a) ^ d) + X[(1+5*3)&15] + 3921069994b = b<<20 | b>>(32-20) + c// [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]a += (((b ^ c) & d) ^ c) + X[(1+5*4)&15] + 3593408605a = a<<5 | a>>(32-5) + bd += (((a ^ b) & c) ^ b) + X[(1+5*5)&15] + 38016083d = d<<9 | d>>(32-9) + ac += (((d ^ a) & b) ^ a) + X[(1+5*6)&15] + 3634488961c = c<<14 | c>>(32-14) + db += (((c ^ d) & a) ^ d) + X[(1+5*7)&15] + 3889429448b = b<<20 | b>>(32-20) + c// [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]a += (((b ^ c) & d) ^ c) + X[(1+5*8)&15] + 568446438a = a<<5 | a>>(32-5) + bd += (((a ^ b) & c) ^ b) + X[(1+5*9)&15] + 3275163606d = d<<9 | d>>(32-9) + ac += (((d ^ a) & b) ^ a) + X[(1+5*10)&15] + 4107603335c = c<<14 | c>>(32-14) + db += (((c ^ d) & a) ^ d) + X[(1+5*11)&15] + 1163531501b = b<<20 | b>>(32-20) + c//[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]a += (((b ^ c) & d) ^ c) + X[(1+5*12)&15] + 2850285829a = a<<5 | a>>(32-5) + bd += (((a ^ b) & c) ^ b) + X[(1+5*13)&15] + 4243563512d = d<<9 | d>>(32-9) + ac += (((d ^ a) & b) ^ a) + X[(1+5*14)&15] + 1735328473c = c<<14 | c>>(32-14) + db += (((c ^ d) & a) ^ d) + X[(1+5*15)&15] + 2368359562b = b<<20 | b>>(32-20) + c/* Round 3. *//* Let [abcd k s t] denote the operationa = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). *//* Do the following 16 operations. */// [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]a += (b ^ c ^ d) + X[(5+3*0)&15] + 4294588738a = a<<4 | a>>(32-4) + bd += (a ^ b ^ c) + X[(5+3*1)&15] + 2272392833d = d<<11 | d>>(32-11) + ac += (d ^ a ^ b) + X[(5+3*2)&15] + 1839030562c = c<<16 | c>>(32-16) + db += (c ^ d ^ a) + X[(5+3*3)&15] + 4259657740b = b<<23 | b>>(32-23) + c// [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]a += (b ^ c ^ d) + X[(5+3*4)&15] + 2763975236a = a<<4 | a>>(32-4) + bd += (a ^ b ^ c) + X[(5+3*5)&15] + 1272893353d = d<<11 | d>>(32-11) + ac += (d ^ a ^ b) + X[(5+3*6)&15] + 4139469664c = c<<16 | c>>(32-16) + db += (c ^ d ^ a) + X[(5+3*7)&15] + 3200236656b = b<<23 | b>>(32-23) + c// [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]a += (b ^ c ^ d) + X[(5+3*8)&15] + 681279174a = a<<4 | a>>(32-4) + bd += (a ^ b ^ c) + X[(5+3*9)&15] + 3936430074d = d<<11 | d>>(32-11) + ac += (d ^ a ^ b) + X[(5+3*10)&15] + 3572445317c = c<<16 | c>>(32-16) + db += (c ^ d ^ a) + X[(5+3*11)&15] + 76029189b = b<<23 | b>>(32-23) + c// [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]a += (b ^ c ^ d) + X[(5+3*12)&15] + 3654602809a = a<<4 | a>>(32-4) + bd += (a ^ b ^ c) + X[(5+3*13)&15] + 3873151461d = d<<11 | d>>(32-11) + ac += (d ^ a ^ b) + X[(5+3*14)&15] + 530742520c = c<<16 | c>>(32-16) + db += (c ^ d ^ a) + X[(5+3*15)&15] + 3299628645b = b<<23 | b>>(32-23) + c/* Round 4. *//* Let [abcd k s t] denote the operationa = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). *//* Do the following 16 operations. */// [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]a += (c ^ (b | ^d)) + X[(7*0)&15] + 4096336452a = a<<6 | a>>(32-6) + bd += (b ^ (a | ^c)) + X[(7*1)&15] + 1126891415d = d<<10 | d>>(32-10) + ac += (a ^ (d | ^b)) + X[(7*2)&15] + 2878612391c = c<<15 | c>>(32-15) + db += (d ^ (c | ^a)) + X[(7*3)&15] + 4237533241b = b<<21 | b>>(32-21) + c// [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]a += (c ^ (b | ^d)) + X[(7*4)&15] + 1700485571a = a<<6 | a>>(32-6) + bd += (b ^ (a | ^c)) + X[(7*5)&15] + 2399980690d = d<<10 | d>>(32-10) + ac += (a ^ (d | ^b)) + X[(7*6)&15] + 4293915773c = c<<15 | c>>(32-15) + db += (d ^ (c | ^a)) + X[(7*7)&15] + 2240044497b = b<<21 | b>>(32-21) + c// [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]a += (c ^ (b | ^d)) + X[(7*8)&15] + 1873313359a = a<<6 | a>>(32-6) + bd += (b ^ (a | ^c)) + X[(7*9)&15] + 4264355552d = d<<10 | d>>(32-10) + ac += (a ^ (d | ^b)) + X[(7*10)&15] + 2734768916c = c<<15 | c>>(32-15) + db += (d ^ (c | ^a)) + X[(7*11)&15] + 1309151649b = b<<21 | b>>(32-21) + c// [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]a += (c ^ (b | ^d)) + X[(7*12)&15] + 4149444226a = a<<6 | a>>(32-6) + bd += (b ^ (a | ^c)) + X[(7*13)&15] + 3174756917d = d<<10 | d>>(32-10) + ac += (a ^ (d | ^b)) + X[(7*14)&15] + 718787259c = c<<15 | c>>(32-15) + db += (d ^ (c | ^a)) + X[(7*15)&15] + 3951481745b = b<<21 | b>>(32-21) + ca = AA + ab = BB + bc = CC + cd = DD + d}md5.r[0] = amd5.r[1] = bmd5.r[2] = cmd5.r[3] = d }func (md5 *MD5) MD5Hex() string {bytes := make([]byte, 16)bytes[0] = byte(md5.r[0] & 0xFF)bytes[1] = byte((md5.r[0] & 0xFF00) >> 8)bytes[2] = byte((md5.r[0] & 0xFF0000) >> 16)bytes[3] = byte((md5.r[0] & 0xFF000000) >> 24)bytes[4] = byte(md5.r[1] & 0xFF)bytes[5] = byte((md5.r[1] & 0xFF00) >> 8)bytes[6] = byte((md5.r[1] & 0xFF0000) >> 16)bytes[7] = byte((md5.r[1] & 0xFF000000) >> 24)bytes[8] = byte(md5.r[2] & 0xFF)bytes[9] = byte((md5.r[2] & 0xFF00) >> 8)bytes[10] = byte((md5.r[2] & 0xFF0000) >> 16)bytes[11] = byte((md5.r[2] & 0xFF000000) >> 24)bytes[12] = byte(md5.r[3] & 0xFF)bytes[13] = byte((md5.r[3] & 0xFF00) >> 8)bytes[14] = byte((md5.r[3] & 0xFF0000) >> 16)bytes[15] = byte((md5.r[3] & 0xFF000000) >> 24)return hex.EncodeToString(bytes) }

END!

總結(jié)

以上是生活随笔為你收集整理的MD5 算法描述及实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。