一. MD5概述

1. MD5介绍

MD5消息摘要算法，属Hash算法一类。

MD5算法对输入任意长度的消息进行运行，产生一个128位的消息摘要(32位的数字字母混合码)。

2. MD5特点

  • 不可逆

知道密文和加密方式，无法反向计算出原密码，但是有md5破解网站，专门查询MD5码

撞库：原理是：通过建立大型的数据库，把日常的各种句子通过md5加密成为密文，不断积累更新大量句子，放在庞大的数据库里；然后，有人拿了别人的密文，想查询真实的密码，就需要把密文拿到这个数据库的网站（免费MD5加密解密：https://md5.cn/）去查询。

  • 长度固定

任意长度的数据，算出来的md5值长度都是固定的

  • 强抗碰撞

想找到两个不同的数据，使它们具有相同的MD5值，是非常困难的。

  • 容易计算

原理通俗易懂

  • 细微性（高度离散性）

对原数据进行任何改动，都会有很大的变化

二. 算法部分

1. 进行数据填充整理

(1) 基本知识

  • 填充长度: 需要把数据填充到64字节 (512bit) 的倍数最少填充9个字节,最多填充(64+8)个字节

填充方式:

    1. 在原始数据的后面填充 0x80
    1. 填充N个0
    1. 使用小端序在最后面用8个字节填充原来的数据的bit长度

这里有一个小端序的概念，下面讲一下简单讲一下小端序和大端序

我们有两个字节：0x01020304和0x05060708 我们要把这俩进行排序

可以看到小端序就是从数值的低位开始排，0x01020304低位往高位依次是04 03 02 01，所以排的时候就是04030201。0x05060708同理，就是 08070605，放一起就是 0403020108070605

大端序就是从高位开始排，就是我们所谓的正常排列顺序。这个简单。

我们回到填充的部分，我们举一个例子。

如图是一个41字节的数据，我们要对他进行填充。

41个字节对应的是（41 * 8）个bit，即328bit，我们要的是512bit，这个少184bit，即（184/8）个字节，即少23个字节。

(2) 填充过程

填充的过程如下：

（1）先在原始数据的后面填充 0x80

这样填了个80，原来少23个字节现在就少了22个字节。

（2）填0

那么填多少个0呢？填22-8即14个字节的0，因为我们要在最后留8个字节放别的东西

这样就填好了，现在还省最后的8个字节

（3）使用小端序在最后面用8个字节填充原来的数据的bit长度

然后我们使用小端序在最后面用8个字节填充原来的数据的bit长度，原来的是328bit，328=0x148，然后把这个0x148变成8个字节，就是在前面加0，变成0x0000000000000148。然后用小端序，即4810000000000000

这就是填充的最后结果，最后是64个字节，填充过程结束。

(3) 不填0的情况

那如果说，原文55个字节的话，我们应该填充9个字节，后面加80就剩了8个字节，之后咋办？这时候就不用填0了，直接加小端序8字节的原来数据就行了。

可以看到，没有填0的过程。

(4) 512bit不够的情况

那么，我们要是原文长度为56个字节呢？56个字节，我们如果填充为64个字节的话，那么还需要填充8个字节，80是必须加的，那么就剩了7个字节，不够用了。

我们刚才是填充为512个bit，我们512不够了，那就用512的倍数，这里用2倍即1024bit

原文56个字节，即448bit，还需要填576bit，即还需要填72字节，填80剩71个字节，然后填71-8个字节的0，然后剩的8个字节填小端排序的8字节原文数据。

2. MD5的执行流程

把填充后的数据按照64字节进行分组

假设有256个字节可分为4组，即一组64个字节

3. 计算过程

我们这里讲一下上图中的计算过程

(1) 四个初始化值

我们要准备四个固定的初始化值

  • A: 0x67452301
  • B: 0XEFCDAB89
  • C: 0x98BADCFE
  • D: 0x10325476

这四个值是固定的。

(2) 赋值

我们将 ABCD赋值给abcd

因为我们在计算的时候需反复的利用那四个值

(3) 计算与循环

计算过程的公式：

1
a = ( (a + F + K[i] + M[g]) << s[i] ) + b

这里的值啥意思下面会讲

然后就是交换数据：

1
2
3
4
a = d
b = a
c = b
d = c

这样abcd就被重新复制了，然后这个过程循环64次。

(4) 最后

当最后循环结束后，ABCD已经重新被赋值了好几次。

结果就是 A的小端序4字节 + B的小端序4字节 + C的小端序4字节 + D的小端序4字节

这就是最后16字节的结果

(5) 计算中的值

从 i = 0 循环到 i = 63 这个过程

I. 当 0 <= i <= 15
1
2
F = (b & c) | ( (-b) & d)
M[g] = 从输入数据的第i个4字节整型 (使用小端序取出)

我们看一下M，比如这样

没四个字节一组

第0次循环，M[g] = 小端序的第1个4字节，即小端序的48656C6C=6C6C6548

第1次循环，M[g] = 小端序的第2个2字节，即小端序的6F20576F=6F57206F

同理一直到15次循环

II. 当 16 <= i <= 31
1
2
F=(d & b) | ( (~d) & c)
M[g] = 从输入数据的第 (5 * i + 1) % 16 个4字节整型 (使用小端序取出)

第16次循环，M[g] = 小端序的第 (5 * 16 + 1) % 16 个，即第1个4字节

第17次循环，M[g] = 小端序的第 (5 * 17 + 1) % 16 个，即第6个4字节

同理到31个

III. 当 32 <= i <= 47
1
2
F=b^c^d
M[g] = 从输入数据的第 (3 * i + 5) % 16 个4字节整型 (使用小端序取出)
IV. 当 48 <= i <= 63
1
2
F=c^(b l (~d) 
M[g] = 从输入数据的第 (7 * i ) % 16 个4字节整型 (使用小端序取出)
V. K变量

K[i] =常量表的第i个

常量表如下：

这里一共64个常量

第一次循环，K[1] = 0xd76aa478

第二次循环，K[2] = 0xe8c7b756

……

VI. s变量

s[i]=位移表第i个

这个也是64个数据。

第一次循环，s[1] = 7

第二次循环，s[2] = 12

三. 代码实现

这里用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
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
# 常量表  
Constant_table = [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, ]  
  
# 位移表  
Displacement_table = [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, ]  
  
# 初始化常量  
A = 0X67452301  
B = 0XEFCDAB89  
C = 0X98BADCFE  
D = 0X10325476  
  
maxInt = 0x100000000  
  
  
def fill(sequence):  # 将字节序列按小端序填充成512位【16整数*4字节】的倍数  
    count = len(sequence)  
    multi_16s = ((count + 8) // 64 + 1) * 16  # 共需要整数的个数，每个整数存储4个字节的数据  
    sequence += [0] * (multi_16s * 4 - count)  # 用 0 填充  
    sequence[count] |= 128  # 用一个 1 补在后面  
    multi_4bytes = []  
    for i in range(len(sequence) // 4):  
        sequence[i * 4 + 3], sequence[i * 4 + 2], sequence[i * 4 + 1], sequence[i * 4] = tuple(  
            sequence[i * 4:(i + 1) * 4])  # 大端序存储  
        multi_4bytes.append(  
            int("".join(["{:08b}".format(ii) for ii in sequence[i * 4:(i + 1) * 4]]), 2))  # 每四个Ascii合并成一个4字节整数  
    multi_4bytes[-2], multi_4bytes[-1] = int("{:064b}".format(count * 8)[32:], 2), int("{:064b}".format(count * 8)[:32],  
                                                                                       2)  
    return multi_4bytes  
  
  
def shift(x, n):  # 循环左移  
    return (x << n) | (x >> (32 - n))  
  
  
def F(x, y, z): return (x & y) | ((~x) & z)  
  
  
def G(x, y, z): return (x & z) | (y & (~z))  
  
  
def H(x, y, z): return x ^ y ^ z  
  
  
def I(x, y, z): return y ^ (x | (~z))  
  
  
def Go(a, b, c, d, fun, m, s, K):  
    thesum = (a + fun(b, c, d) + int(m) + K)  
    return (b + shift(thesum, s)) % maxInt  
  
  
def int32ToHex(a):  
    """32位整型集合转16进制"""  
    md5 = ''  
    for i in a:  
        x = "{:08x}".format(i)  # 整型【32位2】->8位16  
        md5 += x[6:] + x[4:6] + x[2:4] + x[:2]  # 每两位切割, 切割4刀->逆序【大端变小端】  
    return md5  
  
  
if __name__ == "__main__":  
    text = input("请输入要摘要的字符串:")  
    sequence = list(bytes(text, 'utf-8'))  # 将unicode转换为字节序列  
    text_int4 = fill(sequence)  # 将字节序列按小端序填充成4字节整数  
    for i in range(len(text_int4) // 16):  # 主循环  
        a, b, c, d = A, B, C, D  
        M = [text_int4[i * 16 + ii] for ii in range(16)]  # 取出16个整数  
        for ii in range(64):  
            if ii < 16:  
                A, B, C, D = D, Go(A, B, C, D, F, M[ii], Displacement_table[ii], Constant_table[ii]), B, C  
            elif ii < 32:  
                A, B, C, D = D, Go(A, B, C, D, G, M[(ii * 5 + 1) % 16], Displacement_table[ii],  
                                   Constant_table[ii]), B, C  
            elif ii < 48:  
                A, B, C, D = D, Go(A, B, C, D, H, M[((ii * 3) + 5) % 16], Displacement_table[ii],  
                                   Constant_table[ii]), B, C  
            else:  
                A, B, C, D = (A + a) % maxInt, (B + b) % maxInt, (C + c) % maxInt, (D + d) % maxInt  # 此处还是大端字节  
        A, B, C, D = (A + a), (B + b), (C + c), (D + d)  # 此处还是大端字节  
    md5 = int32ToHex([A, B, C, D])  
    print("32位小写:", md5)