MD5（Rivest设计）

发表于2025-04-07

一、概述

MD5（Message Digest Algorithm 5）是一种广泛使用的散列函数，用于提供消息的完整性保护。它可以将长度小于image比特的信息输入，输出固定长度的128比特（16字节）散列值。

输入消息以512比特的分组为单位处理。

二、算法框架

L：消息的长度

N：消息扩充后分组个数

image：代表一个分组

三、主要步骤

填充消息（Padding）

在MD5算法中，首先需要对输入信息进行填充，使其位长对512求余的结果等于448，并且填充必须进行，即使其位长对512求余的结果等于448。因此，信息的位长（Bits Length）将被扩展至N*512+448，N为一个非负整数，N可以是零。填充的方法如下：

  1. 在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。

  2. 在这个结果后面附加一个以64位二进制表示的填充前信息长度，如果二进制表示的填充前信息长度超过64位，则取低64位。经过这两步的处理，信息的位长=N*512+448+64=(N+1）*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。

初始化 MD5 缓冲区

MD5 使用 四个 32-bit 寄存器作为中间结果和最终结果的缓冲区，初始化值为：

A=0x01234567, B=0x89ABCDEF, C=0xFEDCBA98, D=0x76543210。

在运算过程中涉及大端和小端的转换问题。

A, B, C, D = 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476。（小端）

处理 512bit 分组

将填充后的消息分成512位(64字节)的块，对每个块进行以下处理：

将块分成16个32位字

将512位的块分成16个32位的小端序字，记为M[0]到M[15]。

初始化哈希值

将当前哈希值(A,B,C,D)保存到临时变量(a,b,c,d)中。

主循环

MD5有4轮，每轮16次操作，共64次操作。每轮使用不同的非线性函数：

  • 第一轮(F函数): F(X,Y,Z) = (X ∧ Y) ∨ (¬X ∧ Z)
  • 第二轮(G函数): G(X,Y,Z) = (X ∧ Z) ∨ (Y ∧ ¬Z)
  • 第三轮(H函数): H(X,Y,Z) = X ⊕ Y ⊕ Z
  • 第四轮(I函数): I(X,Y,Z) = Y ⊕ (X ∨ ¬Z)

每轮操作形式为：<font style="color:#464646;">a = b + ((a + F(b,c,d) + M[k] + T[i]) <<< s)</font>

  • <<< 表示循环左移
  • T[i]是预先定义的常数表中的一个值。image

  • s是循环左移的位数
  • k是消息字索引

4轮操作之前，先将前一分组的链接变量复制到另外四个备用记录单元AA、BB、CC、DD。


所有这些完成之后，将a、b、c、d分别在原来基础上再加上AA、BB、CC、DD。
即image

image
然后用数据继续运行以上算法。

最终输出 MD5 哈希值

所有分组处理完成后，将最终的 A, B, C, D 连接成 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
102
103
104
105
106
107
108
109
#得到十六进制、128比特的散列值
import struct
import math

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

# 计算 T 常数表（64 个值）
T = [int(2**32 * abs(math.sin(i + 1))) & 0xFFFFFFFF for i in range(64)]

# 4 轮使用的函数
F = lambda x, y, z: (x & y) | (~x & z)
G = lambda x, y, z: (x & z) | (y & ~z)
H = lambda x, y, z: x ^ y ^ z
I = lambda x, y, z: y ^ (x | ~z)

# 每轮的左移位数
S = [
    (7, 12, 17, 22) * 4,  # 1st round
    (5, 9, 14, 20) * 4,   # 2nd round
    (4, 11, 16, 23) * 4,  # 3rd round
    (6, 10, 15, 21) * 4   # 4th round
]

# 处理的 M[i] 顺序
M_index = [
    list(range(16)),                 # 1st round
    [1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12],  # 2nd round
    [5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2],  # 3rd round
    [0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9]   # 4th round
]

# 消息填充
def md5_padding(message):
    # 计算消息长度（比特）
    original_length = len(message) * 8
    # 追加 10000000
    message += b'\x80'
    # 填充 0 直到消息长度模 512 余 448
    while (len(message) * 8) % 512 != 448:
        message += b'\x00'
    # 追加长度（小端存储）
    message += struct.pack('<Q', original_length)
    return message

# 将 32 位整数从当前字节序转换为大端字节序
def to_big_endian_32(x):
    return struct.unpack('>I', struct.pack('<I', x))[0]

# MD5 计算
def md5(message):
    # 初始化 MD5 缓冲区，按照小端字节序的初始值
    A, B, C, D = 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476

    # 进行消息填充
    message = md5_padding(message)
    # 将消息分割成 512-bit 分块
    chunks = [message[i: i + 64] for i in range(0, len(message), 64)]

    # 处理每个 512-bit 分块
    for chunk in chunks:
        # 小端解析 16 个 32-bit 字
        M = list(struct.unpack('<16I', chunk))
        # 复制原始值
        AA, BB, CC, DD = A, B, C, D

        # 64 轮循环
        for round_num in range(4):
            # 选择 F/G/H/I 函数
            func = [F, G, H, I][round_num]
            for i in range(16):
                # 选择 M[k] 的索引
                k = M_index[round_num][i]
                # 选择循环左移位数
                shift = S[round_num][i]

                temp = (AA + func(BB, CC, DD) + M[k] + T[i + round_num * 16]) & 0xFFFFFFFF
                # 循环左移
                temp = left_rotate(temp, shift)
                # 加上 B 值
                temp = (BB + temp) & 0xFFFFFFFF

                # 轮换 A, B, C, D
                AA, BB, CC, DD = DD, temp, BB, CC

                # 打印当前轮次结果
                print(f"Round {round_num * 16 + i + 1:02}: A={AA:08x}, B={BB:08x}, C={CC:08x}, D={DD:08x}")

        # 累加结果
        A = (A + AA) & 0xFFFFFFFF
        B = (B + BB) & 0xFFFFFFFF
        C = (C + CC) & 0xFFFFFFFF
        D = (D + DD) & 0xFFFFFFFF

    # 将每个 32 位整数转换为大端字节序
    A = to_big_endian_32(A)
    B = to_big_endian_32(B)
    C = to_big_endian_32(C)
    D = to_big_endian_32(D)

    # 组合最终哈希值
    return f'{A:08x}{B:08x}{C:08x}{D:08x}'

# 运行示例
message = input("请输入要加密的字符串: ").encode('utf-8')
md5_hash = md5(message)
print(f"\nMD5哈希值: {md5_hash}")

MD5.py

MD5_1.py

五、实例

MD5(“iscbupt”)=”16838a414adaec12d8d86f735fd183b7”