广州高端网站建设定制,番禺建设网站公司哪家好,二手车网站设计,做外文H网站MD5 算法的原理及实现 章节目录
简介算法描述 实现 作者能力有限, 如果您在阅读过程中发现任何错误, 还请您务必联系本人,指出错误, 避免后来读者再学习错误的知识.谢谢! 简介##
Wiki对其的描述:
MD5消息摘要算法#xff08;英语#xff1a;MD5 Message-Digest Algorithm英语MD5 Message-Digest Algorithm一种被广泛使用的密码散列函数可以产生出一个128位16字节的散列值hash value用于确保信息传输完整一致。MD5由美国密码学家罗纳德·李维斯特Ronald Linn Rivest设计于1992年公开用以取代MD4算法。这套算法的程序在 RFC 1321 中被加以规范。
将数据如一段文字运算变为另一固定长度值是散列算法的基础原理。
1996年后被证实存在弱点可以被加以破解对于需要高度安全性的数据专家一般建议改用其他算法如SHA-2。2004年证实MD5算法无法防止碰撞collision因此不适用于安全性认证如SSL公开密钥认证或是数字签名等用途
MD5 算法是 MD4 算法的扩展, MD5 比 MD4 算法稍微慢一些, 但是却后者更难破解.
算法描述##
假设我们需要计算一个长度为 b bit 的信息的消息摘要, b 可以是零, b 也不需要是 8 的整数倍. 我么将它表示为:m0m1...mb−1m_0 m_1 ... m_{b-1}m0m1...mb−1.
计算该消息的摘要,我们需要依次执行以下五步:
填充###
我们需要将输入消息的长度填充到差 64 就是 512 的整数倍长度.
填充方法:第一 bit 是 1, 接下来的所有比特填充 0. 填充操作总是需要进行, 即使输入的消息长度本身就满足上述条件, 此时填充的长度时 512. 因此可能的填充长度时 1-512.
填充长度###
长度 b 被表示为 64 bit(little-endian, 低字节在前), 连接到第一步操作的尾部.
通过这部操作之后, 我们的消息长度此时正好是 512 的整数倍.
注意这里的长度 b 是原始数据的长度, 而不是经过第一步填充之后的长度.
初始化幻数###
这里我们将用到四个幻数: A, B, C, D. 他们的值分别如下: A0X67452301LB0XEFCDAB89LC0X98BADCFELD0X10325476L (至于为什么是这几个数字,大家自己研究哈)计算消息摘要###
这里我们需要 4 个函数, 他们均输入三个 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) 一小组进行计算.
接下来我们就可以开始进行真正的计算了, 计算方法 RFC 中描述如下: 下面伪代码中: N 表示输入消息所包含的字数(不是字节数). M 表示以字为单位,输入消息所组成的数组, 它的长度为 N. A, B, C, D 为步骤四中所定义的幻数.
/* 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*16j].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 */输出消息摘要###
通过上一步的计算, 我们得到了四个结果 A, B, C, D. 将上述四个字表示为 128 bit 即为输入消息的消息摘要. 注意将 A, B, C, D 转化为 bit 时采用小段表示法(低字节在前).
算法实现##
在这里, 我们采用 go 语言实现该算法.
package md5import encoding/hexconst (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*16j].// 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)j1])8 | uint32(m[(k*64)j2])16 | uint32(m[(k*64)j3])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 a7 | a(32-7) bd (((b ^ c) a) ^ c) X[1] 3905402710d d12 | d(32-12) ac (((a ^ b) d) ^ b) X[2] 606105819c c17 | c(32-17) db (((d ^ a) c) ^ a) X[3] 3250441966b b22 | 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 a7 | a(32-7) bd (((b ^ c) a) ^ c) X[5] 1200080426d d12 | d(32-12) ac (((a ^ b) d) ^ b) X[6] 2821735955c c17 | c(32-17) db (((d ^ a) c) ^ a) X[7] 4249261313b b22 | 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 a7 | a(32-7) bd (((b ^ c) a) ^ c) X[9] 2336552879d d12 | d(32-12) ac (((a ^ b) d) ^ b) X[10] 4294925233c c17 | c(32-17) db (((d ^ a) c) ^ a) X[11] 2304563134b b22 | 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 a7 | a(32-7) bd (((b ^ c) a) ^ c) X[13] 4254626195d d12 | d(32-12) ac (((a ^ b) d) ^ b) X[14] 2792965006c c17 | c(32-17) db (((d ^ a) c) ^ a) X[15] 1236535329b b22 | 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[(15*0)15] 4129170786a a5 | a(32-5) bd (((a ^ b) c) ^ b) X[(15*1)15] 3225465664d d9 | d(32-9) ac (((d ^ a) b) ^ a) X[(15*2)15] 643717713c c14 | c(32-14) db (((c ^ d) a) ^ d) X[(15*3)15] 3921069994b b20 | 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[(15*4)15] 3593408605a a5 | a(32-5) bd (((a ^ b) c) ^ b) X[(15*5)15] 38016083d d9 | d(32-9) ac (((d ^ a) b) ^ a) X[(15*6)15] 3634488961c c14 | c(32-14) db (((c ^ d) a) ^ d) X[(15*7)15] 3889429448b b20 | 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[(15*8)15] 568446438a a5 | a(32-5) bd (((a ^ b) c) ^ b) X[(15*9)15] 3275163606d d9 | d(32-9) ac (((d ^ a) b) ^ a) X[(15*10)15] 4107603335c c14 | c(32-14) db (((c ^ d) a) ^ d) X[(15*11)15] 1163531501b b20 | 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[(15*12)15] 2850285829a a5 | a(32-5) bd (((a ^ b) c) ^ b) X[(15*13)15] 4243563512d d9 | d(32-9) ac (((d ^ a) b) ^ a) X[(15*14)15] 1735328473c c14 | c(32-14) db (((c ^ d) a) ^ d) X[(15*15)15] 2368359562b b20 | 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[(53*0)15] 4294588738a a4 | a(32-4) bd (a ^ b ^ c) X[(53*1)15] 2272392833d d11 | d(32-11) ac (d ^ a ^ b) X[(53*2)15] 1839030562c c16 | c(32-16) db (c ^ d ^ a) X[(53*3)15] 4259657740b b23 | 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[(53*4)15] 2763975236a a4 | a(32-4) bd (a ^ b ^ c) X[(53*5)15] 1272893353d d11 | d(32-11) ac (d ^ a ^ b) X[(53*6)15] 4139469664c c16 | c(32-16) db (c ^ d ^ a) X[(53*7)15] 3200236656b b23 | 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[(53*8)15] 681279174a a4 | a(32-4) bd (a ^ b ^ c) X[(53*9)15] 3936430074d d11 | d(32-11) ac (d ^ a ^ b) X[(53*10)15] 3572445317c c16 | c(32-16) db (c ^ d ^ a) X[(53*11)15] 76029189b b23 | 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[(53*12)15] 3654602809a a4 | a(32-4) bd (a ^ b ^ c) X[(53*13)15] 3873151461d d11 | d(32-11) ac (d ^ a ^ b) X[(53*14)15] 530742520c c16 | c(32-16) db (c ^ d ^ a) X[(53*15)15] 3299628645b b23 | 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 a6 | a(32-6) bd (b ^ (a | ^c)) X[(7*1)15] 1126891415d d10 | d(32-10) ac (a ^ (d | ^b)) X[(7*2)15] 2878612391c c15 | c(32-15) db (d ^ (c | ^a)) X[(7*3)15] 4237533241b b21 | 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 a6 | a(32-6) bd (b ^ (a | ^c)) X[(7*5)15] 2399980690d d10 | d(32-10) ac (a ^ (d | ^b)) X[(7*6)15] 4293915773c c15 | c(32-15) db (d ^ (c | ^a)) X[(7*7)15] 2240044497b b21 | 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 a6 | a(32-6) bd (b ^ (a | ^c)) X[(7*9)15] 4264355552d d10 | d(32-10) ac (a ^ (d | ^b)) X[(7*10)15] 2734768916c c15 | c(32-15) db (d ^ (c | ^a)) X[(7*11)15] 1309151649b b21 | 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 a6 | a(32-6) bd (b ^ (a | ^c)) X[(7*13)15] 3174756917d d10 | d(32-10) ac (a ^ (d | ^b)) X[(7*14)15] 718787259c c15 | c(32-15) db (d ^ (c | ^a)) X[(7*15)15] 3951481745b b21 | 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!
