MD5

Posted by Useless Programmer on February 16, 2019

    MD5 算法的原理及实现

章节目录

  1. 简介
  2. 算法描述
  3. 实现

作者能力有限, 如果您在阅读过程中发现任何错误, 还请您务必联系本人,指出错误, 避免后来读者再学习错误的知识.谢谢!

简介##

Wiki对其的描述:

MD5消息摘要算法(英语: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 的整数倍. 我么将它表示为:.

计算该消息的摘要,我们需要依次执行以下五步:

填充###

我们需要将输入消息的长度填充到差 64 就是 512 的整数倍长度.

填充方法:第一 bit 是 1, 接下来的所有比特填充 0.
填充操作总是需要进行, 即使输入的消息长度本身就满足上述条件, 此时填充的长度时 512. 因此可能的填充长度时 1-512.

填充长度###

长度 b 被表示为 64 bit(little-endian, 低字节在前), 连接到第一步操作的尾部.

通过这部操作之后, 我们的消息长度此时正好是 512 的整数倍.

注意这里的长度 b 是原始数据的长度, 而不是经过第一步填充之后的长度.

初始化幻数###

这里我们将用到四个幻数: A, B, C, D. 他们的值分别如下:

    A=0X67452301L,
    B=0XEFCDAB89L,
    C=0X98BADCFEL,
    D=0X10325476L 
    (至于为什么是这几个数字,大家自己研究哈)

计算消息摘要###

这里我们需要 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 do
        Set 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 = A
    BB = B
    CC = C
    DD = D

    /* Round 1. */
    /* Let [abcd k s i] denote the operation
        a = 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 operation
        a = 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 operation
        a = 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 operation
        a = 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 + AA
    B = B + BB
    C = C + CC
    D = D + DD
    end /* of loop on i */

输出消息摘要###

通过上一步的计算, 我们得到了四个结果 A, B, C, D. 将上述四个字表示为 128 bit 即为输入消息的消息摘要. 注意将 A, B, C, D 转化为 bit 时采用小段表示法(低字节在前).

算法实现##

在这里, 我们采用 go 语言实现该算法.

package md5

import "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 {

    // padding
    var lenData, padLen uint32
    lenData = uint32(len(rawData))
    padLen = 0
    if lenData % 64 < 56 {
        padLen = 56 - (lenData % 64)
    } else {
        padLen = 64 + 56 - (lenData % 64)
    }
    pad := make([]byte, padLen)
    pad[0] = 0x80
    rawData = append(rawData, pad...)

    // append length
    bitLenBytes := make([]byte, 8)
    lenData = lenData << 3
    for 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, D
    chunk := len(m) / 64 // process the data as 16-word block
    for 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]uint32

        j := 0
        for 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])<<24
            j += 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 operation
        a = 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] + 3614090360
        a = a<<7 | a>>(32-7) + b
        d += (((b ^ c) & a) ^ c) + X[1] + 3905402710
        d = d<<12 | d>>(32-12) + a
        c += (((a ^ b) & d) ^ b) + X[2] + 606105819
        c = c<<17 | c>>(32-17) + d
        b += (((d ^ a) & c) ^ a) + X[3] + 3250441966
        b = 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] + 4118548399
        a = a<<7 | a>>(32-7) + b
        d += (((b ^ c) & a) ^ c) + X[5] + 1200080426
        d = d<<12 | d>>(32-12) + a
        c += (((a ^ b) & d) ^ b) + X[6] + 2821735955
        c = c<<17 | c>>(32-17) + d
        b += (((d ^ a) & c) ^ a) + X[7] + 4249261313
        b = 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] + 1770035416
        a = a<<7 | a>>(32-7) + b
        d += (((b ^ c) & a) ^ c) + X[9] + 2336552879
        d = d<<12 | d>>(32-12) + a
        c += (((a ^ b) & d) ^ b) + X[10] + 4294925233
        c = c<<17 | c>>(32-17) + d
        b += (((d ^ a) & c) ^ a) + X[11] + 2304563134
        b = 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] + 1804603682
        a = a<<7 | a>>(32-7) + b
        d += (((b ^ c) & a) ^ c) + X[13] + 4254626195
        d = d<<12 | d>>(32-12) + a
        c += (((a ^ b) & d) ^ b) + X[14] + 2792965006
        c = c<<17 | c>>(32-17) + d
        b += (((d ^ a) & c) ^ a) + X[15] + 1236535329
        b = b<<22 | b>>(32-22) + c

        /* Round 2. */
        /* Let [abcd k s i] denote the operation
        a = 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] + 4129170786
        a = a<<5 | a>>(32-5) + b
        d += (((a ^ b) & c) ^ b) + X[(1+5*1)&15] + 3225465664
        d = d<<9 | d>>(32-9) + a
        c += (((d ^ a) & b) ^ a) + X[(1+5*2)&15] + 643717713
        c = c<<14 | c>>(32-14) + d
        b += (((c ^ d) & a) ^ d) + X[(1+5*3)&15] + 3921069994
        b = 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] + 3593408605
        a = a<<5 | a>>(32-5) + b
        d += (((a ^ b) & c) ^ b) + X[(1+5*5)&15] + 38016083
        d = d<<9 | d>>(32-9) + a
        c += (((d ^ a) & b) ^ a) + X[(1+5*6)&15] + 3634488961
        c = c<<14 | c>>(32-14) + d
        b += (((c ^ d) & a) ^ d) + X[(1+5*7)&15] + 3889429448
        b = 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] + 568446438
        a = a<<5 | a>>(32-5) + b
        d += (((a ^ b) & c) ^ b) + X[(1+5*9)&15] + 3275163606
        d = d<<9 | d>>(32-9) + a
        c += (((d ^ a) & b) ^ a) + X[(1+5*10)&15] + 4107603335
        c = c<<14 | c>>(32-14) + d
        b += (((c ^ d) & a) ^ d) + X[(1+5*11)&15] + 1163531501
        b = 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] + 2850285829
        a = a<<5 | a>>(32-5) + b
        d += (((a ^ b) & c) ^ b) + X[(1+5*13)&15] + 4243563512
        d = d<<9 | d>>(32-9) + a
        c += (((d ^ a) & b) ^ a) + X[(1+5*14)&15] + 1735328473
        c = c<<14 | c>>(32-14) + d
        b += (((c ^ d) & a) ^ d) + X[(1+5*15)&15] + 2368359562
        b = b<<20 | b>>(32-20) + c

        /* Round 3. */
        /* Let [abcd k s t] denote the operation
        a = 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] + 4294588738
        a = a<<4 | a>>(32-4) + b
        d += (a ^ b ^ c) + X[(5+3*1)&15] + 2272392833
        d = d<<11 | d>>(32-11) + a
        c += (d ^ a ^ b) + X[(5+3*2)&15] + 1839030562
        c = c<<16 | c>>(32-16) + d
        b += (c ^ d ^ a) + X[(5+3*3)&15] + 4259657740
        b = 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] + 2763975236
        a = a<<4 | a>>(32-4) + b
        d += (a ^ b ^ c) + X[(5+3*5)&15] + 1272893353
        d = d<<11 | d>>(32-11) + a
        c += (d ^ a ^ b) + X[(5+3*6)&15] + 4139469664
        c = c<<16 | c>>(32-16) + d
        b += (c ^ d ^ a) + X[(5+3*7)&15] + 3200236656
        b = 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] + 681279174
        a = a<<4 | a>>(32-4) + b
        d += (a ^ b ^ c) + X[(5+3*9)&15] + 3936430074
        d = d<<11 | d>>(32-11) + a
        c += (d ^ a ^ b) + X[(5+3*10)&15] + 3572445317
        c = c<<16 | c>>(32-16) + d
        b += (c ^ d ^ a) + X[(5+3*11)&15] + 76029189
        b = 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] + 3654602809
        a = a<<4 | a>>(32-4) + b
        d += (a ^ b ^ c) + X[(5+3*13)&15] + 3873151461
        d = d<<11 | d>>(32-11) + a
        c += (d ^ a ^ b) + X[(5+3*14)&15] + 530742520
        c = c<<16 | c>>(32-16) + d
        b += (c ^ d ^ a) + X[(5+3*15)&15] + 3299628645
        b = b<<23 | b>>(32-23) + c

        /* Round 4. */
        /* Let [abcd k s t] denote the operation
        a = 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] + 4096336452
        a = a<<6 | a>>(32-6) + b
        d += (b ^ (a | ^c)) + X[(7*1)&15] + 1126891415
        d = d<<10 | d>>(32-10) + a
        c += (a ^ (d | ^b)) + X[(7*2)&15] + 2878612391
        c = c<<15 | c>>(32-15) + d
        b += (d ^ (c | ^a)) + X[(7*3)&15] + 4237533241
        b = 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] + 1700485571
        a = a<<6 | a>>(32-6) + b
        d += (b ^ (a | ^c)) + X[(7*5)&15] + 2399980690
        d = d<<10 | d>>(32-10) + a
        c += (a ^ (d | ^b)) + X[(7*6)&15] + 4293915773
        c = c<<15 | c>>(32-15) + d
        b += (d ^ (c | ^a)) + X[(7*7)&15] + 2240044497
        b = 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] + 1873313359
        a = a<<6 | a>>(32-6) + b
        d += (b ^ (a | ^c)) + X[(7*9)&15] + 4264355552
        d = d<<10 | d>>(32-10) + a
        c += (a ^ (d | ^b)) + X[(7*10)&15] + 2734768916
        c = c<<15 | c>>(32-15) + d
        b += (d ^ (c | ^a)) + X[(7*11)&15] + 1309151649
        b = 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] + 4149444226
        a = a<<6 | a>>(32-6) + b
        d += (b ^ (a | ^c)) + X[(7*13)&15] + 3174756917
        d = d<<10 | d>>(32-10) + a
        c += (a ^ (d | ^b)) + X[(7*14)&15] + 718787259
        c = c<<15 | c>>(32-15) + d
        b += (d ^ (c | ^a)) + X[(7*15)&15] + 3951481745
        b = b<<21 | b>>(32-21) + c

        a = AA + a
        b = BB + b
        c = CC + c
        d = DD + d
    }

    md5.r[0] = a
    md5.r[1] = b
    md5.r[2] = c
    md5.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!