MD5算法实现

发表于 | 更新于: |
字数统计: 2.7k 字

本文阐述MD5算法的基本原理及其C++实现方法，并给出源代码

算法原理概述

MD5即Message-Digest Algorithm 5 (信息-摘要算法 5) ，是一种被广泛使用的密码散列(hash)函数，它使用小端模式，输入任意不定长的消息，产生的是128位(16个字节)的散列值(hash value)，用于确保信息传输的完整性和一致性。

MD5算法不是足够安全的，可以找到两个不同的512位的块，它们通过的MD5的hash值相同

但对于有意义的消息，还没有两个不同的消息，它们的MD5的hash值相同

总体结构

MD5算法的基本流程如下图所示：

可以分成几个流程：

  • 填充
  • 分块
  • 循环压缩
  • 得出结果

使用unsigned char作为byte，unsigned int作为bit32

模块分解

填充

算法的输入我使用字符串，而一个字符占一个字节(8位)，而填充后的消息位数是512位(64字节)的倍数，因此可以按字节来填充，填充需要注意的是最后8个字节要使用原始消息长度的低8个字节来填充，其余需要填充的部分，第一个字节使用0x80，其余的字节都使用0x00。

计算填充字节数的方法如下：

1
2
3
4
//count表示要填充的字节数
int count = length % 64;
if (count < 56) count = 64 - 8 - count;
else count = 128 - 8 - count;

中间填充0x80，0x00就不必赘述，需要注意填充原始消息长度的低8个字节这个操作，要按照小端存储来把长度转为8个连续的字节，可以采用移位运算>>来帮助实现。

填充完成后，消息长度为64k字节，为了方便之后的步骤，还需要把消息分块。

分块

分块操作主要是为了把填充好的消息分割成每64字节一组，也可以表示成一组16个32位的字(bit32)。

我使用vector<bit32>来存储每个分组里面的32位字，再用一个vector来存放所有的分组，因此最终分块后的消息存放在vector<vector<bit32> >中(vector<bit32>长度固定为16)

需要注意，填充后的消息中按byte存储，因此需要把连续的4个byte转成bit32，这里又需要按照小端存储的模式，比如4个byte值分别为0x01,0x02,0x03,0x04，转成bit32的值为0x04030201。可以借助左移位运算符<<来实现。

循环压缩

这一部分包含了MD5算法进行加密的主要操作，主要流程是以512位的分组为单位，每一分组经过4轮循环，每轮循环16次迭代，输出128位的结果，存放在缓冲区中，作为下一轮循环缓冲区的输入。

4轮循环的逻辑如图所示：

从缓冲区输入128位，从消息分组输入512位，输出结果128位，要注意结果是由循环的结果加上缓冲区的值得到的(加法为模232加法)。

每轮循环中迭代的逻辑如图所示：

其中：

  • a，b，c，d是缓冲区的当前值
  • g是4个轮函数之一，输入输出都是bit32，进行不同的逻辑运算
  • <<<s是指把bit32循环左移s位，s可查表得到
  • X[k]是当前处理消息分组的第k个bit32，在每一轮循环中都由不同的公式计算出来
  • T[i]通过查表得到，32bit字
  • 所有的加法都是模232加法

需要注意，在迭代过程中缓冲区的值会发生变化，因此要提前存储下循环开始时缓冲区的值，用于之后与循环结果相加。

4个轮函数逻辑如图所示：

每轮循环中X[k]所取的k的计算方法为：

取j为当前迭代轮次

  1. 第一轮循环：k = j
  2. 第二轮循环：k = (1 + 5 * j) % 16
  3. 第三轮循环：k = (5 + 3 * j) % 16
  4. 第四轮循环：k = (7 * j) % 16

得出结果

经过前面的操作，我们已经得到了4个bit32的结果，但最直白的输出最好是字符串，许多在线工具也是把计算结果转成了32位长度的16进制字符串，便于使用。

要得到16进制字符串类型的结果，首先需要把这4个bit32转成16个byte，再把每一个byte用两位16进制字符来表示。

把bit32转成byte的过程又一次需要用到小端存储模式：

1
2
3
4
5
6
7
for (int i = 0; i < 4; ++i) {
    //利用了小端编码
    MD5[i * 4 + 0] = CV[i] & 0xff;
    MD5[i * 4 + 1] = (CV[i] >> 8) & 0xff;
    MD5[i * 4 + 2] = (CV[i] >> 16) & 0xff;
    MD5[i * 4 + 3] = (CV[i] >> 24) & 0xff;
}

之后输出每一个byte，分别计算出它除以16的商和余数即可：

1
2
3
4
5
6
7
8
9
10
11
12
char HEX[16] = {
    '0', '1', '2', '3',
    '4', '5', '6', '7',
    '8', '9', 'a', 'b',
    'c', 'd', 'e', 'f'
};
for (int i = 0; i < 16; ++i) {
    byte quotient = MD5[i] / 16;
    byte remainder = MD5[i] % 16;
    str.append(1, HEX[quotient]);
    str.append(1, HEX[remainder]);
}

最终得到的是一个长度为32的16进制字符串。

数据结构

首先最重要的是表示方法，由于C++里char占8位，int占32位，因此分别使用unsigned char和unsigned int来表示byte和bit32是很合适的。

此外，要存放消息，使用vector这个数据结构十分方便，对每一个分块使用vector<bit32>来存放16个bit32，所有的分块存放在一个vector中方便检查填充和分块是否出错。

此外，用到了MD5算法固定使用的一些表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//T表,共64个元素，每个元素为32位字，也称为加法常数
bit32 T[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
};

//s表，各次迭代运算采用的左循环移位的s值
byte s[64] = {
    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
};

源代码

在此贴出MD5算法主要部分的源码，完整源码见github

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include "MD5.hpp"
#include <vector>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using std::vector;
using std::string;

//存放填充完成后的原始消息
//每个分组512位，即16个32位的字
vector<vector<bit32> > groups;

//128位的MD5缓冲区
//表示为4个32位寄存器
bit32 CV[4] = {0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476};
//缓冲区初始向量IV
bit32 IV[4] = {0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476};

//加密结果，长度为16的字符串
byte MD5[16];


//填充函数
//输入为字符串类型的原始消息和消息长度
void padding(byte* input, int length) {
    //由于输入的每一个字符占一个字节(8位)
    //因此按字节填充，而不是按位填充
    //每一组64字节，最后一组的8个字节另外填

    //count表示要填充的字节数
    int count = length % 64;
    if (count < 56) count = 64 - 8 - count;
    else count = 128 - 8 - count;

    //填充操作
    byte* paddingInput = new byte[length + count + 8];
    memcpy(paddingInput, input, length);
    paddingInput[length] = 0x80;
    for (int i = length + 1; i < length + count - 8; ++i) {
        paddingInput[i] = 0x00;
    }
    //再向填充好的消息尾部附加消息长度的低8个字节
    //int转byte要注意小端存储
    for (int i = 0; i < 8; ++i) {
        //用((length * 8) >> (i * 8)) & 0xff出现了奇怪的结果
        //改用除法
        paddingInput[length + count + i] = ((byte)((length * 8) / pow(2, (i * 8)))) & 0xff;
    }

    /* std::cout << count + 8 << std::endl;
    for (int i = 0; i < length + count + 8; ++i)
        std::cout << (int)paddingInput[i] << " "; 
    std::cout << std::endl; */
    
    vector<bit32> group;
    group.reserve(16);
    for (int i = 0, flag = 0; i < length + count + 8; i += 4) {
        bit32 word = 0;
        //4个byte转成一个int，采用小端存储
        //如0x01,0x02,0x03,0x04
        //int为0x04030201
        for (int j = 0; j < 4; ++j) {
            word |= (paddingInput[i + j] << (j * 8));
        }
        group.push_back(word);
        flag++;
        if (flag == 16) {
            groups.push_back(group);
            flag = 0;
            group.clear();
        }
    }
    
}

//压缩函数
//对每一个512位(16个32位字)的分组进行压缩
//上一轮压缩的128位结果作为下一轮的CV输入
//最终的结果存放在缓冲区中
void HMD5() {
    for (int i = 0; i < groups.size(); ++i) {
        bit32 A = CV[0];
        bit32 B = CV[1];
        bit32 C = CV[2];
        bit32 D = CV[3];
        //作4轮循环，每一轮作16次迭代
        for (int j = 0; j < 4; ++j) {
            for (int q = 0; q < 16; ++q) {
                bit32 a = A, b = B, c = C, d = D;
                bit32 g;
                int k;
                switch (j) {
                    case 0:
                        g = F(b, c, d);
                        k = q;
                        break;
                    case 1:
                        g = G(b, c, d);
                        k = (1 + 5 * q) % 16;
                        break;
                    case 2:
                        g = H(b, c, d);
                        k = (5 + 3 * q) % 16;
                        break;
                    case 3:
                        g = I(b, c, d);
                        k = (7 * q) % 16;
                        break;
                }

                bit32 tmp = a + g + groups[i][k] + T[j * 16 + q];
                a = b + shiftLeft(tmp, s[j * 16 + q]);
                
                //缓冲区作循环轮换
                //(B, C, D, A) <- (A, B, C, D)
                A = d;
                B = a;
                C = b;
                D = c;
            }
        }
        CV[0] += A;
        CV[1] += B;
        CV[2] += C;
        CV[3] += D;
    }
}

//把128位(4个32位字)的结果转成16个字节的输出
void getBytes() {
    for (int i = 0; i < 4; ++i) {
        //利用了小端编码
        MD5[i * 4 + 0] = CV[i] & 0xff;
        MD5[i * 4 + 1] = (CV[i] >> 8) & 0xff;
        MD5[i * 4 + 2] = (CV[i] >> 16) & 0xff;
        MD5[i * 4 + 3] = (CV[i] >> 24) & 0xff;
    }
}

int main() {
    string test;
    getline(std::cin, test);
    padding((byte*)test.c_str(), test.length());
    HMD5();
    getBytes();
    // 输出十六进制字符串
    string str = "";
    char HEX[16] = {
        '0', '1', '2', '3',
        '4', '5', '6', '7',
        '8', '9', 'a', 'b',
        'c', 'd', 'e', 'f'
    };
    for (int i = 0; i < 16; ++i) {
        byte quotient = MD5[i] / 16;
        byte remainder = MD5[i] % 16;
        str.append(1, HEX[quotient]);
        str.append(1, HEX[remainder]);
    }
    std::cout << str << std::endl;
}

编译运行结果

首先来测试一个简单的字符串的MD5散列值：

1
2
3
4
$ g++ MD5.cpp -o MD5
$ ./MD5
hello,world!
c0e84e870874dd37ed0d164c7986f03a

使用在线MD5加密工具查看结果：

再测试一个很长的字符串：

1
2
3
4
$ g++ MD5.cpp -o MD5
$ ./MD5
In cryptography, a keyed-hash message authentication code(HMAC) is a specific type of MAC involving a cryptographic hashfunction and a secret cryptographic key.It may be used to simultaneously verify both the data integrity andthe authentication of a message, as with any MAC.Any cryptographic hash function, such as MD5 or SHA-1, may beused in the calculation of an HMAC; the resulting MAC algorithm istermed HMAC-MD5 or HMAC-SHA1 accordingly.The cryptographic strength of the HMAC depends upon thecryptographic strength of the underlying hash function, the size ofits hash output, and on the size and quality of the key
a939099e207813b92284271a3fd49dd5

使用在线工具查看结果：

可以看到，结果是正确的，因此实现的MD5算法是正确的。

-------------本文结束感谢您的阅读-------------