md5算法实现

前言

md5算法是我们经常会用到的一个hash函数, 虽然已经被证明是不安全的了, 但其应用依然十分广泛.

哈希函数具有如下特点:

1. 将任意长度的字符串映射为固定长度
2. 源数据微小的改动会导致结果差异巨大
3. 不可逆
4. 暴力破解困难

你有没有好奇过, 哈希函数是如何做到这些的呢? 本文就拿md5举例, 看一看它具体的计算过程.

注意: 本文仅设计计算过程, 不涉及证明过程. 也就是说只介绍How, 不介绍Why , 满足一下好奇心即可

计算过程

不管是文件还是字符串, 在计算时都是一个byte数组, 因此无需进行区分.

md5的计算过程大致分为如下几步(看起来稍稍费点脑子)

1. 进行数据填充

首先将准备计算的数据准备好, 步骤如下:

1. 在数据后面拼接一个 int64 类型的数据, 这个数据是源数据的位长度
2. 源数据与长度中间填充数据 100… , 使得填充后的长度是 64(字节) 的倍数
   • 填充的数据最短为 1 个字节, 最长为 64 个字节

这里以字符串hello举例, 其16进制表示为: 68656c6c6f

1. 其共有40位, 也就是16进制的28. 因为是 int64 类型, 因此共8字节, 以小端序表示为: 2800000000000000
2. 源数据5字节, 算上长度的8字节共13字节, 因此填充数据的长度为64-13=51

填充后的数据为: 68656c6c6f8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002800000000000000

共64字节.

2. 对数据进行分组计算并迭代

到这一步就是重头戏了, 主要计算逻辑全部都在这里, 认真看咯.

首先, 我们知道, md5的计算结果是一个32位的16进制数字, 也就是16个字节. 我们将这16个字节分成4组, 每组4个字节也就是一个int类型的数字.

假设这4个数字分别为a, b, c, d, 我们所有的计算结果, 都是对这4个数字进行的.

将上一步拼装好的数据, 按照每64字节进行拆分

针对每一组进行迭代计算, 其中每组的计算过程大致如下:

1. 进行4组不同的计算规则, 每组规则计算16次. 共16*4轮迭代计算
2. 每组计算中, 以a, d, c, b的顺序, 依次迭代每个数字(计算规则不同)

以第一组第一次迭代为例:

• n的计算规则为: (b & c) | (!b & d)
  • 每组迭代计算规则不同:
    • 第二组: (b & d) | (c & !d)
    • 第三组: b ^ c ^ d
    • 第四组: c ^ (b | !d)
• m的计算规则为: n + data[i] + a + sin(i+1)*2^32
  • 其中, data[i]为取原数据的第i个数字 (原数据64个字节, 可转为16个 int)
    • 第一组: i
    • 第二组: (5i+1)%16
    • 第三组: (3i+5)%16
    • 第四组: 7i % 16
• o 的计算规则为: (m << calcNum[i%4]) | (m >> (32 - calcNum[i%4]))
  • 其中calcNum 是一组魔数, 每组不同
• num 的计算规则为: o+b
• 最终, 将num赋值给a, 完成本次计算. (本次计算的结果为下一次迭代计算的输入)

而这, 仅仅是64次迭代中的一次, 还要进行64次, 才会完成对这64个字节的计算. (剩余的迭代计算规则不再赘述, 具体可查看下面的代码实现)

最后, 当对这64个字节迭代计算完成后, 依次对数据后面所有组进行相同的迭代, 知道所有源数据计算完成.

3. 输出结果

上一步计算完成后, 我们将得到4个经过很多次迭代的int数字. 而这4个数字, 就是我们计算的结果了, 我们只需要简单的将其转为16进制输出即可. (以上所有的数字与字节的转换, 均按照小端序进行)

code

希望到这里, 你没有看的云里雾里, 当然了, 我也知道自己没怎么写明白…

下面是我用Go实现的一版md5算法, 一共才100行左右. 算法的细节都在里面了, 你可以查看代码分析其具体计算流程, 也可以拿到本地跑一下, 或者依据此Go版本实现, 用其他编程语言试着实现一版.

package main

import (
	"encoding/binary"
	"encoding/hex"
	"fmt"
	"math"
)

func main() {
	fmt.Println(md5("hello"))
}

func md5(str string) string {
	// 填充数据
	data := md5GetPaddingData(str)
	// 过程计算结果 (不要问我为什么是这4个数字, 我也不知道, 就是魔数. 应该是推导出这些魔术的碰撞率比较低)
	result := [4]uint32{0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476}
	// 遍历所有分组
	for i := 0; i < len(data); i += 64 {
		// 计算当前分组的结果
		tmpGroup := md5CalcGroup(result, data[i:i+64])
		for j := 0; j < 4; j++ { // 将结果加到 result 上
			result[j] += tmpGroup[j]
		}
	}
	// 输出结果并将结果转为 16 进制
	md5Byte := make([]byte, 0)
	for _, num := range result {
		md5Byte = binary.LittleEndian.AppendUint32(md5Byte, num)
	}
	return hex.EncodeToString(md5Byte)
}

// 对 md5 计算的数据进行填充
func md5GetPaddingData(str string) []byte {
	data := []byte(str)
	// 计算数据长度 (byte 单位, 所以要乘以 8)
	var lenBuf = make([]byte, 8)
	binary.LittleEndian.PutUint64(lenBuf, uint64(len(data)*8))
	// 计算填充长度
	paddingLen := 64 - (len(data)+len(lenBuf))%64
	// 填充 1 和 0
	data = append(data, 0x80)
	for i := 0; i < paddingLen-1; i++ {
		data = append(data, 0x00)
	}
	// 在最后拼接长度
	data = append(data, lenBuf...)
	return data
}

// 对每组数据进行计算
func md5CalcGroup(lastResult [4]uint32, data []byte) [4]uint32 {
	if len(data) != 64 {
		panic("data length must be 64")
	}
	// 将 result 数组临时复制一份, 防止函数内部修改
	result := [4]uint32{}
	for i, num := range lastResult {
		result[i] = num
	}
	// 计算常量表
	constTable := [64]uint32{}
	for i := 0; i < 64; i++ {
		// sin(i+1) * 2^32
		constTable[i] = uint32(math.Abs(math.Sin(float64(i+1))) * (1 << 32))
	}
	// 将当前分组按照 4 字节一组, 分为 4 组. 并将其转为整形方便后续运算
	calcData := [16]uint32{}
	for i := 0; i < 16; i++ {
		calcData[i] = binary.LittleEndian.Uint32(data[i*4 : i*4+4])
	}

	// 供下面每轮计算使用
	// 获取本轮计算用到的4个结果数 (顺序返回, 0,3,2,1,0,3,2,1,0...)
	// 以及更新的结果数下标
	gotResIndex := func(i int) (uint32, uint32, uint32, uint32, int) {
		resIndex := 4 - i%4
		if resIndex >= 4 {
			resIndex = 0
		}
		return result[resIndex], result[(resIndex+1)%4], result[(resIndex+2)%4], result[(resIndex+3)%4], resIndex
	}
	// 进行第一轮计算
	calcNum := [4]uint32{7, 12, 17, 22} // 同理这4个魔数我也不知道为什么
	for i := 0; i < 16; i++ {
		// 本轮计算的结果数
		a, b, c, d, resIndex := gotResIndex(i)
		n := (b & c) | (^b & d)
		m := n + calcData[i] + constTable[i] + a
		o := (m << calcNum[i%4]) | (m >> (32 - calcNum[i%4]))
		result[resIndex] = o + b
	}
	// 第二轮计算
	calcNum = [4]uint32{5, 9, 14, 20} // 同理这4个魔数我也不知道为什么
	for i := 0; i < 16; i++ {
		a, b, c, d, resIndex := gotResIndex(i)
		n := (b & d) | (c & ^d)
		m := n + calcData[(5*i+1)%16] + constTable[i+16] + a
		o := (m << calcNum[i%4]) | (m >> (32 - calcNum[i%4]))
		result[resIndex] = o + b
	}
	// 第三轮计算
	calcNum = [4]uint32{4, 11, 16, 23} // 同理这4个魔数我也不知道为什么
	for i := 0; i < 16; i++ {
		a, b, c, d, resIndex := gotResIndex(i)
		n := b ^ c ^ d
		m := n + calcData[(3*i+5)%16] + constTable[i+32] + a
		o := (m << calcNum[i%4]) | (m >> (32 - calcNum[i%4]))
		result[resIndex] = o + b
	}
	// 第四轮计算
	calcNum = [4]uint32{6, 10, 15, 21} // 同理这4个魔数我也不知道为什么
	for i := 0; i < 16; i++ {
		a, b, c, d, resIndex := gotResIndex(i)
		n := c ^ (b | ^d)
		m := n + calcData[(7*i)%16] + constTable[i+48] + a
		o := (m << calcNum[i%4]) | (m >> (32 - calcNum[i%4]))
		result[resIndex] = o + b
	}
	return result
}
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

---

以上, 就是md5值计算的全部过程了, 不需要证明, 仅仅好奇. 具体做的时候没有人会闲到自己实现md5算法, 所有语言都带着常用的hash函数实现.

原文地址: https://hujingnb.com/archives/912