MD5 信息摘要算法

发表于 分类于 阅读次数： 本文字数： 8.9k
翻译自 RFC 1321 文档

meta

1. 摘要

本文描述了 MD5 信息摘要算法。该算法将任意长度的信息作为输入，并产生一个 128 位的“指纹”或“信息摘要”作为输出。产生两个具有相同信息摘要的信息，或者产生任何具有给定预先指定的目标信息摘要的信息，被认为是计算上不可行的。MD5 算法旨在用于数字签名应用程序，其中必须在使用诸如 RSA 的公钥密码系统加密之前以安全的方式“压缩”大文件。

MD5 算法的设计在 32 位的机器上运行非常快。此外，MD5 算法不依赖于任何映射表，算法可以编码得非常紧凑。

MD5 算法是 MD4 信息摘要算法的扩展。MD5 稍微比 MD4 慢一点，但是在设计上更“保守”，MD5 被设计的原因是因为人们认为 MD4 的使用速度可能比现有的严格审查所证明的要快；由于 MD4 被设计得特别快，就成功进行密码分析攻击的风险而言，它处于 “边缘”。MD5 后退了一点，放弃了一点速度，最终以获得更大的安全性。它包含了不同审阅者提出的一些建议，并包含其他优化。 MD5 算法正在被置于公共领域以供审查并可能被采用为标准。

对于基于 OSI 的应用程序，MD5 的对象标识符是 md5 OBJECT IDENTIFIER ::= iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5。在 X.509 类型 AlgorithmIdentifier 中，MD5 的参数应该具有类型 NULL。

2. 符号和专业用语

本文档中，“word”是 32 位的量，“byte”是 8 位的量。位序列可以按照自然方式解释为字节序列，其中每个连续的 8 位组被解释为一个字节，其中每个字节的高位（最高有效位）被列为第一个。类似地，字节序列可以按照自然方式解释为 32 位字序列，其中每个连续的 4 个字节被解释为一个字，其中每个字的低位（最低有效位）被列为第一个。

x_i 表示 x sub i。如果下标是一个表达式，我们用大括号括起来，如 x_{i+1}。类似地，我们使用 ^ 表示上标（指数），因此 x^i 表示 x 的 i 次幂。

我们用 + 来表示字的加法（即，模 2^32 加法）。让 X <<< s 表示通过将 X 循环左移 s 位获得的 32 位值。让 not(X) 表示 X 的位补码，让 X v Y 表示 X 和 Y 的位或。让 X xor Y 表示 X 和 Y 的位异或，让 XY 表示 X 和 Y 的位与。

3. MD5 算法描述

我们首先假设我们有一个 b 位的信息作为输入，并且我们希望找到它的信息摘要。这里 b 是任意的非负整数；b 可以是零，它不需要是 8 的倍数，它可以是任意大的。我们将信息的位写成如下形式：m_0 m_1 ... m_{b-1} 。接下来执行以下五个步骤来计算信息的信息摘要。

3.1 第一步。追加填充位

将信息“填充”（扩展），使其长度（以位为单位）对 512 取模为 448。也就是说，将信息扩展，使其只比 512 的倍数位长多 64 位。填充总是执行的，即使信息的长度对 512 取模为 448。

填充按照一下方式进行，首先在信息后面追加一个单独的“1”，然后追加“0”，使得填充后的信息的长度对 512 取模为 448。总之，至少追加一个位，最多追加 512 位。

3.2 第二步。追加长度

用 64 个比特位（位的长度）的 b 的 64 位表示（在填充之前）追加到上一步的结果中。如果 b 大于 2^64，则只使用 b 的低 64 位。 （这些位按照前面的约定作为两个 32 位字追加，低位字先追加。）

此时，结果信息（在填充位和 b 之后）的长度是 512 的倍数。等价地，该消息的长度是 16（32 位）word 的倍数。让 M[0 … N-1] 表示结果消息的word，其中 N 是 16 的倍数。

3.3 第三步。初始化 MD 缓冲区

一个四字缓冲区（A、B、C、D）用于计算信息摘要。这里的每个 A、B、C、D 都是一个 32 位的寄存器。这些寄存器的初始化值如下（以十六进制表示，低位字先）：

1
2
3
4
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 第四步。以 16 个字为单位处理消息

我们首先定义四个辅助函数，每个函数都以三个 32 位字作为输入，并产生一个 32 位字作为输出。

1
2
3
4
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))

在每个比特位上，F 的作用类似于条件：如果 X 则 Y 否则 Z。函数 F 可以使用 + 来定义，而不是 v，因为 XY 和 not(X)Z 永远不会在同一比特位上有 1。有趣的是，如果 X、Y 和 Z 的比特位是独立且随机的，则 F(X,Y,Z) 的每个比特位都是独立且随机的。

函数 G、H 和 I 与函数 F 类似，因为它们以“位并行”的方式从 X、Y 和 Z 的位中产生它们的输出，这样，如果 X、Y 和 Z 的相应位是独立且随机的，则 G(X,Y,Z)、H(X,Y,Z) 和 I(X,Y,Z) 的每个比特位都是独立且随机的。注意，函数 H 是其输入的位异或或“奇偶校验”函数。

这个步骤使用一个从正弦函数构造的 64 元素表 T[1 … 64]。让 T[i] 表示表的第 i 个元素，它等于 4294967296 的整数部分乘以 abs(sin(i))，其中 i 是以弧度表示的。表的元素在附录中给出（译者注：原文并未在附录中给出，本文按照原文的示例代码整理出该序列）。

像下面这样做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/* 处理每个512 比特块 */
For i = 0 to N/16 - 1 do
    /* 复制块 i 到 X */
    For j = 0 to 15 do
        Set X[j] to M[i*16+j].
    end
    /* 保存 A 为 AA，B 为 BB，C 为 CC，D 为 DD */
    AA = A
    BB = B
    CC = C
    DD = D

    /* 第一轮 */
    /* 让 [abcd k s i] 表示操作 a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s)。*/
    /* 执行以下 16 个操作。*/
    [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]

    /* 第二轮 */
    /* 让 [abcd k s i] 表示操作 a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s)。*/
    /* 执行以下 16 个操作。*/
    [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]

    /* 第三轮 */
    /* 让 [abcd k s t] （译者注：经过验证，这儿应该为 [abcd k s i]）表示操作 a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s)。*/
    /* 执行以下 16 个操作。*/
    [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]

    /* 第四轮 */
    /* 让 [abcd k s t] （译者注：经过验证，这儿应该为 [abcd k s i]）表示操作 a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s)。*/
    /* 执行以下 16 个操作。*/
    [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]

    /* 然后执行以下操作。（将每个值与进行本次循环保存的值相加）*/
    A = A + AA
    B = B + BB
    C = C + CC
    D = D + DD

3.5 第五步。输出

产生的消息摘要作为输出是 A、B、C、D。也就是说，我们从 A 的低位字开始，以 D 的高位字结束。

这就完成了 MD5 的描述。C 语言的参考实现在附录中给出（译者注：本文不含 c 语言实现的附录）。

4. 总结

MD5 信息摘要算法的实现是比较简单的，为任意长度的信息提供了一个“指纹”或“信息摘要”。据推测，得出具有相同消息摘要的两条消息的难度约为 2^64 次操作，而得出具有给定消息摘要的任何消息的难度约为 2^128 次操作。MD5 算法已经过仔细检查以找出弱点。 然而，它是一种相对较新的算法，进一步的安全分析当然是合理的，就像任何此类新提案的情况一样。

5. MD4 与 MD5 的不同点

这儿列举了一些 MD4 与 MD5 的不同点：

  1. 添加了第四轮的计算
  2. 每一轮都有一个唯一的加法常数
  3. 第二轮的函数 g 从 (XY v XZ v YZ) 改为 (XZ v Y not(Z))，使得 g 不那么对称
  4. 每一轮都添加了上一轮的结果，这促进了更快的“雪崩效应”
  5. 在第二轮和第三轮中访问输入字的顺序已经改变，使得这些模式不那么相似
  6. 每一轮的移位量已经近似优化，以产生更快的“雪崩效应”。不同轮次的移位是不同的。

参考文献

  • [1] Rivest, R., “The MD4 Message Digest Algorithm”, RFC 1320, MIT and RSA Data Security, Inc., April 1992.
  • [2] Rivest, R., “The MD4 message digest algorithm”, in A.J. Menezes and S.A. Vanstone, editors, Advances in Cryptology - CRYPTO ‘90 Proceedings, pages 303-311, Springer-Verlag, 1991.
  • [3] CCITT Recommendation X.509 (1988), “The Directory - Authentication Framework.”

附录

1. T 的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
T[1 ... 64] = [
    0xd76aa478
    0xe8c7b756
    0x242070db
    0xc1bdceee
    0xf57c0faf
    0x4787c62a
    0xa8304613
    0xfd469501
    0x698098d8
    0x8b44f7af
    0xffff5bb1
    0x895cd7be
    0x6b901122
    0xfd987193
    0xa679438e
    0x49b40821
    0xf61e2562
    0xc040b340
    0x265e5a51
    0xe9b6c7aa
    0xd62f105d
    0x02441453
    0xd8a1e681
    0xe7d3fbc8
    0x21e1cde6
    0xc33707d6
    0xf4d50d87
    0x455a14ed
    0xa9e3e905
    0xfcefa3f8
    0x676f02d9
    0x8d2a4c8a
    0xfffa3942
    0x8771f681
    0x6d9d6122
    0xfde5380c
    0xa4beea44
    0x4bdecfa9
    0xf6bb4b60
    0xbebfbc70
    0x289b7ec6
    0xeaa127fa
    0xd4ef3085
    0x04881d05
    0xd9d4d039
    0xe6db99e5
    0x1fa27cf8
    0xc4ac5665
    0xf4292244
    0x432aff97
    0xab9423a7
    0xfc93a039
    0x655b59c3
    0x8f0ccc92
    0xffeff47d
    0x85845dd1
    0x6fa87e4f
    0xfe2ce6e0
    0xa3014314
    0x4e0811a1
    0xf7537e82
    0xbd3af235
    0x2ad7d2bb
    0xeb86d391
]

2. MD5 的 Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import math
import struct

# 常量定义
T = [int(4294967296 * abs(math.sin(i + 1))) & 0xFFFFFFFF for i in range(64)]
s = [7, 12, 17, 22] * 4 + [5, 9, 14, 20] * 4 + [4, 11, 16, 23] * 4 + [6, 10, 15, 21] * 4


# 左循环移位
def left_rotate(x, amount):
    x &= 0xFFFFFFFF
    return ((x << amount) | (x >> (32 - amount))) & 0xFFFFFFFF


# MD5初始化
def md5(message):
    message = bytearray(message)  # 将消息转换为字节数组
    orig_len_in_bits = (8 * len(message)) & 0xFFFFFFFFFFFFFFFF
    message.append(0x80)
    while len(message) % 64 != 56:
        message.append(0)
    message += orig_len_in_bits.to_bytes(8, byteorder='little')

    # 初始化变量
    h0, h1, h2, h3 = 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476

    # 分块处理
    for chunk_ofst in range(0, len(message), 64):
        a, b, c, d = h0, h1, h2, h3
        chunk = message[chunk_ofst : chunk_ofst + 64]
        M = [int.from_bytes(chunk[i : i + 4], byteorder='little') for i in range(0, 64, 4)]

        for i in range(64):
            if 0 <= i <= 15:
                f = (b & c) | (~b & d)
                g = i
            elif 16 <= i <= 31:
                f = (d & b) | (~d & c)
                g = (5 * i + 1) % 16
            elif 32 <= i <= 47:
                f = b ^ c ^ d
                g = (3 * i + 5) % 16
            elif 48 <= i <= 63:
                f = c ^ (b | ~d)
                g = (7 * i) % 16
            f = (f + a + T[i] + M[g]) & 0xFFFFFFFF
            a, d, c, b = d, c, b, (b + left_rotate(f, s[i])) & 0xFFFFFFFF

        h0 = (h0 + a) & 0xFFFFFFFF
        h1 = (h1 + b) & 0xFFFFFFFF
        h2 = (h2 + c) & 0xFFFFFFFF
        h3 = (h3 + d) & 0xFFFFFFFF

    return struct.pack('<4I', h0, h1, h2, h3).hex()


# 测试MD5函数
message = b"123456"
print(md5(message))  # 输出: e10adc3949ba59abbe56e057f20f883e

3. MD5 的 Go 实现

参考官方实现方式 crypto/md5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package main

import (
	"encoding/binary"
	"fmt"
)

var s = [64]int{
	7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
	5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
	4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
	6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21,
}

var K = [64]uint32{
	0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
	0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
	0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
	0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
	0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
	0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
	0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
	0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
	0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
	0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
	0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
	0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
	0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
	0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
	0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
	0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391,
}

func leftRotate(x uint32, c int) uint32 {
	return (x << c) | (x >> (32 - c))
}

func md5(message []byte) [16]byte {
	origLen := uint64(len(message) * 8)
	message = append(message, 0x80)
	for len(message)%64 != 56 {
		message = append(message, 0)
	}

	lenBytes := make([]byte, 8)
	binary.LittleEndian.PutUint64(lenBytes, origLen)
	message = append(message, lenBytes...)

	var h0, h1, h2, h3 uint32 = 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476

	for i := 0; i < len(message); i += 64 {
		var M [16]uint32
		for j := 0; j < 16; j++ {
			M[j] = binary.LittleEndian.Uint32(message[i+4*j:])
		}

		a, b, c, d := h0, h1, h2, h3

		for i := 0; i < 64; i++ {
			var f uint32
			var g int
			if i < 16 {
				f = (b & c) | (^b & d)
				g = i
			} else if i < 32 {
				f = (d & b) | (^d & c)
				g = (5*i + 1) % 16
			} else if i < 48 {
				f = b ^ c ^ d
				g = (3*i + 5) % 16
			} else {
				f = c ^ (b | ^d)
				g = (7 * i) % 16
			}

			f = f + a + K[i] + M[g]
			a = d
			d = c
			c = b
			b = b + leftRotate(f, s[i])
		}

		h0 += a
		h1 += b
		h2 += c
		h3 += d
	}

	var result [16]byte
	binary.LittleEndian.PutUint32(result[0:4], h0)
	binary.LittleEndian.PutUint32(result[4:8], h1)
	binary.LittleEndian.PutUint32(result[8:12], h2)
	binary.LittleEndian.PutUint32(result[12:16], h3)
	return result
}

func main() {
	message := "123456"
	hash := md5([]byte(message))
	fmt.Printf("MD5(\"%s\") = %x\n", message, hash)
}