MD5加密算法详解_md5加密逻辑

1. 引言

对于软件研发人员来说 MD5 不是一个陌生的词汇，平时的软件研发中，经常使用 MD5 校验消息是否被篡改、验证文件完整性，甚至将MD5当作加密算法使用。
MD5虽不陌生，但不是所有研发人员都了解其算法原理，通过这篇文章详细学习MD5 摘要算法。

• 认识 MD5
• 掌握 MD5 算法原理
• 编码实现 MD5 摘要算法
• 使用Java开发语言 编码实现MD5摘要算法

2. 简介

MD5全称Message Digest Algorithm 5，翻译过来就是：消息摘要算法第5版，是计算机安全领域广泛使用的一种散列函数，由美国密码学家罗纳德·李维斯特（Ronald Linn Rivest）设计，于1992年公开，用以取代MD4算法，用于确保信息传输的完整性。MD5算法是典型的消息摘要算法，是由MD2、MD3、MD4演变而来，是一种单向加密算法一个具有注脚的文本。一种不可逆的加密方式，无论是哪一种MD算法，其原理都是接受一个任意长度的消息并产生一个128位的消息摘要。如果把得到的消息摘要转换成十六进制字符串，则会得到一个32字节长度的字符串，我们平常见到的大部分MD数字指纹就是一个长度为32的十六进制字符串。因为MD5算法最终生成的是一个128位长的数据，从原理上说有2^128种可能，这是一个非常巨大的数据，但是世界上可以进行加密的数据原则上说是无限的，因此是可能存在不同的内容经过MD5加密后得到同样的摘要信息，但这个碰中的概率非常小。可用于数字签名、信息完整性检查等用途。

MD5算法具有以下特点：

1. 压缩性：任意长度的数据，算出的MD5值长度都是固定的
2. 容易计算：MD5使用散列算法，从原数据计算出MD5值很容易，速度较快
3. 抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别
4. 强抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的

MD5的作用是让大容量信息在用数字签名软件签署私人密钥前被"压缩"成一种保密的格式(就是把一个任意长度的字节串变换成一定长的16进制数字串)。

3. MD5的发展历程

1992年8月，罗纳德·李维斯特向互联网工程任务组（IETF）提交了一份重要文件，描述了这种算法的原理。由于这种算法的公开性和安全性，在90年代被广泛使用在各种程序语言中，用以确保资料传递无误等。
MD5由MD4、MD3、MD2改进而来，主要增强算法复杂度和不可逆性。MD5算法因其普遍、稳定、快速的特点，仍广泛应用于普通数据的加密保护领域。
MD2
Rivest在1989年开发出MD2算法。在这个算法中，首先对信息进行数据补位，使信息的字节长度是16的倍数。然后，以一个16位的校验和追加到信息末尾，并且根据这个新产生的信息计算出散列值。后来，Rogier和Chauvaud发现如果忽略了校验和MD2将产生冲突。MD2算法加密后结果是唯一的（即不同信息加密后的结果不同）。
MD4
为了加强算法的安全性，Rivest在1990年又开发出MD4算法 。MD4算法同样需要填补信息以确保信息的比特位长度减去448后能被512整除（信息比特位长度mod 512 = 448）。然后，一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成512位damgard/merkle迭代结构的区块，而且每个区块要通过三个不同步骤的处理。Den boer和Bosselaers以及其他人很快的发现了攻击MD4版本中第一步和第三步的漏洞。Dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到MD4完整版本中的冲突（这个冲突实际上是一种漏洞，它将导致对不同的内容进行加密却可能得到相同的加密后结果）。
MD5
1991年，Rivest开发出技术上更为趋近成熟的MD5算法。它在MD4的基础上增加了"安全带"（safety-belts）的概念。虽然MD5比MD4复杂度大一些，但却更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中，信息-摘要的大小和填充的必要条件与MD4完全相同。Den boer和Bosselaers曾发现MD5算法中的假冲突（pseudo-collisions），但除此之外就没有其他被发现的加密后结果了。

4. 加密原理

MD5 算法将输入的信息进行分组，每组512 位（64个 字节），顺序处理完所有分组后输出128 位结果。
在每一组消息的处理中，都要进行4 轮、每轮16 步、总计64 步的处理。其中每步计算中含一次左循环移位，每一步结束时将计算结果进行一次右循环移位。详细流程如下：

4.1. 数据填充整理

首先需要对原始消息进行填充，使其位长对512求余的结果为448（填充必须进行，即使其位长对512求余的结果等于448）。
填充数据的方式：
将一个字符串Str1分割成每512位为一个分组，形如N*512+R，最后多出来的不足512位的R部分先填充一个1，再接无数个0，直到补足512位。这里要注意，R为0时也要补512位，最高位1，形如1000…00；如果R超出448，除了要补满这个分组外，还要再补上一个512位的分组（因为超过448位则不能留64位出来存放字符串的原长）。这一步只是补充了0-448bit的填充，还未补充最后的数据总长度，所以填充完成后数据长度为：N*512+448

4.2. 记录数据长度

经过上一步数据填充整理之后，用64bit记录 “输入信息” 的位长 (Bits Length)，把64位长度二进制数据补在最后，填充后的数据长度为：N*512+448+64 = (N+1)*512 ( N>=0 )。

4.3. 初始化MD缓存器

MD5运算要用到一个128位的MD5缓存器，用来保存中间变量和最终结果。我们知道最终的MD5值长度为128位，按32位分成一组的话可以分成4组，而这4组结果就是由这4个标准幻数A,B,C,D经过不断演变得到。这一步就需要初始化四个数据 A、B、C、D，这四个变量将用于后续的公式计算。
四个数据均为8个16进制数据组合，每个16进制数据为4bit，每个数据占32bit。

// 每个数据占空间 32bit 
// 四个数据分别为 8个 16进制数据的组合构成
// 单个16进制数据占空间 4bit
A: 01 23 45 67 （16进制）
B: 89 ab cd ef （16进制）
C: fe dc ba 98 （16进制）
D: 76 54 32 10 （16进制）
1
2
3
4
5
6
7

将A、B、C、D输入计算机进行计算时，A、B、C、D将变化为：

A: 0x67452301
B: 0xefcdab89
C: 0x98badcfe
D: 0x10325476
1
2
3
4

为什么会变化为 0x67452301、0xefcdab89、0x98badcfe、0x10325476 ？用A举例子：

// A的16进制表示
A: 01 23 45 67 （16进制）
// A的二进制表示
A: 00000 0001 0010 0011 0100 0101 0110 0111 （二进制）
// 计算机中首先编写的为低字节位，当从右向左获取字节数据(8位一个字节)时，最终A将变化为0x67452301
A: 67 45 23 01 （16进制）
1
2
3
4
5
6

4.4. 四轮循环运算

经过4.1、4.2、4.3之后，现在初始消息被分割成做了填充的N个512bit的数据，并且包含了总数据长度，还初始化了4个标准幻数，接下来就是需要对N个分割的数据循环进行处理。

每个512bit数据都会被再次拆分为16个32bit的子块，这里分别命名为M0~M15 (M[j])，每个子分组都要进行4次运算，分别为四个非线性函数：FF、GG、HH、II；

//（&是与，|是或，~是非，^是异或）
F(X,Y,Z) =(X&Y)|((~X)&Z)
G(X,Y,Z) =(X&Z)|(Y&(~Z))
H(X,Y,Z) =X^Y^Z
I(X,Y,Z)=Y^(X|(~Z))
1
2
3
4
5

这四个函数的说明：如果X、Y和Z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。

FF(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + F(b, c, d) + Mj + ti) <<< s)
GG(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + G(b, c, d) + Mj + ti) <<< s)
HH(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + H(b, c, d) + Mj + ti) <<< s)
II(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + I(b, c, d) + Mj + ti) <<< s)
1
2
3
4

接下来开始循环处理：
然后进行一个MD5算法的主要循环，这个循环的循环次数为512位分组的个数。每次循环执行以下的步骤：
假设M[j]表示消息的第j个子分组（从0到15）

｛
 	a = A; b = B; c = C; d = D;

 	//第一轮循环
    FF(a,b,c,d,M[0],7,0xd76aa478);
    FF(d,a,b,c,M[1],12,0xe8c7b756);
    FF(c,d,a,b,M[2],17,0x242070db);
    FF(b,c,d,a,M[3],22,0xc1bdceee);
    FF(a,b,c,d,M[4],7,0xf57c0faf);
    FF(d,a,b,c,M[5],12,0x4787c62a);
    FF(c,d,a,b,M[6],17,0xa8304613);
    FF(b,c,d,a,M[7],22,0xfd469501) ;
    FF(a,b,c,d,M[8],7,0x698098d8) ;
    FF(d,a,b,c,M[9],12,0x8b44f7af) ;
    FF(c,d,a,b,M[10],17,0xffff5bb1) ;
    FF(b,c,d,a,M[11],22,0x895cd7be) ;
    FF(a,b,c,d,M[12],7,0x6b901122) ;
    FF(d,a,b,c,M[13],12,0xfd987193) ;
    FF(c,d,a,b,M[14],17,0xa679438e) ;
    FF(b,c,d,a,M[15],22,0x49b40821);
    
    //第二轮循环
    GG(a,b,c,d,M[1],5,0xf61e2562);
    GG(d,a,b,c,M[6],9,0xc040b340);
    GG(c,d,a,b,M[11],14,0x265e5a51);
    GG(b,c,d,a,M[0],20,0xe9b6c7aa) ;
    GG(a,b,c,d,M[5],5,0xd62f105d) ;
    GG(d,a,b,c,M[10],9,0x02441453) ;
    GG(c,d,a,b,M[15],14,0xd8a1e681);
    GG(b,c,d,a,M[4],20,0xe7d3fbc8) ;
    GG(a,b,c,d,M[9],5,0x21e1cde6) ;
    GG(d,a,b,c,M[14],9,0xc33707d6) ;
    GG(c,d,a,b,M[3],14,0xf4d50d87) ;
    GG(b,c,d,a,M[8],20,0x455a14ed);
    GG(a,b,c,d,M[13],5,0xa9e3e905);
    GG(d,a,b,c,M[2],9,0xfcefa3f8) ;
    GG(c,d,a,b,M[7],14,0x676f02d9) ;
    GG(b,c,d,a,M[12],20,0x8d2a4c8a);

    //第三轮循环
    HH(a,b,c,d,M[5],4,0xfffa3942);
    HH(d,a,b,c,M[8],11,0x8771f681);
    HH(c,d,a,b,M[11],16,0x6d9d6122);
    HH(b,c,d,a,M[14],23,0xfde5380c) ;
    HH(a,b,c,d,M[1],4,0xa4beea44) ;
    HH(d,a,b,c,M[4],11,0x4bdecfa9) ;
    HH(c,d,a,b,M[7],16,0xf6bb4b60) ;
    HH(b,c,d,a,M[10],23,0xbebfbc70);
    HH(a,b,c,d,M[13],4,0x289b7ec6);
    HH(d,a,b,c,M[0],11,0xeaa127fa);
    HH(c,d,a,b,M[3],16,0xd4ef3085);
    HH(b,c,d,a,M[6],23,0x04881d05);
    HH(a,b,c,d,M[9],4,0xd9d4d039);
    HH(d,a,b,c,M[12],11,0xe6db99e5);
    HH(c,d,a,b,M[15],16,0x1fa27cf8) ;
    HH(b,c,d,a,M[2],23,0xc4ac5665);
    
    //第四轮循环
    II(a,b,c,d,M[0],6,0xf4292244) ;
    II(d,a,b,c,M[7],10,0x432aff97) ;
    II(c,d,a,b,M[14],15,0xab9423a7);
    II(b,c,d,a,M[5],21,0xfc93a039) ;
    II(a,b,c,d,M[12],6,0x655b59c3) ;
    II(d,a,b,c,M[3],10,0x8f0ccc92) ;
    II(c,d,a,b,M[10],15,0xffeff47d);
    II(b,c,d,a,M[1],21,0x85845dd1) ;
    II(a,b,c,d,M[8],6,0x6fa87e4f) ;
    II(d,a,b,c,M[15],10,0xfe2ce6e0);
    II(c,d,a,b,M[6],15,0xa3014314) ;
    II(b,c,d,a,M[13],21,0x4e0811a1);
    II(a,b,c,d,M[4],6,0xf7537e82) ;
    II(d,a,b,c,M[11],10,0xbd3af235);
    II(c,d,a,b,M[2],15,0x2ad7d2bb);
    II(b,c,d,a,M[9],21,0xeb86d391);

    A += a;
    B += b;
    C += c;
    D += d;
｝
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

4.5. 获取结果

处理完所有的512bit的分组后，得到一组新的A,B,C,D的值，将这些值按ABCD的顺序级联，然后输出。这里还要注意，输出的MD5是按内存中数值的排列顺序，所以我们要分别对A,B,C,D的值做一个小端规则的转换最终得到结果。

5. MD5算法的java代码实现

import org.springframework.util.DigestUtils;

public class MD5 {
    /**
     * 四个链接变量
     */
    private static final int A = 0x67452301;
    private static final int B = 0xefcdab89;
    private static final int C = 0x98badcfe;
    private static final int D = 0x10325476;

    /**
     * ABCD的临时变量
     */
    private int Atemp, Btemp, Ctemp, Dtemp;

    /**
     * 常量ti
     * 公式:floor(abs(sin(i+1))×(2pow32)
     */
    private final int[] K = {
            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};
    /**
     * 向左位移数
     */
    private final int[] s = {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};


    /**
     * 初始化函数
     */
    private void init() {
        Atemp = A;
        Btemp = B;
        Ctemp = C;
        Dtemp = D;
    }

    /**
     * 移动一定位数
     */
    private int shift(int a, int s) {
        //右移的时候，高位一定要补零，而不是补充符号位
        return (a << s) | (a >>> (32 - s));
    }

    /**
     * 主循环
     */
    private void mainLoop(int[] m) {
        int F, g;
        int a = Atemp;
        int b = Btemp;
        int c = Ctemp;
        int d = Dtemp;
        for (int i = 0; i < 64; i++) {
            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;
            }
            int tmp = d;
            d = c;
            c = b;
            b = b + shift(a + F + K[i] + m[g], s[i]);
            a = tmp;
        }
        Atemp = a + Atemp;
        Btemp = b + Btemp;
        Ctemp = c + Ctemp;
        Dtemp = d + Dtemp;

    }

    /**
     * 填充函数
     * 处理后应满足bits≡448(mod512),字节就是bytes≡56（mode64)
     * 填充方式为先加一个0,其它位补零
     * 最后加上64位的原来长度
     */
    private int[] add(String str) {
        //以512位，64个字节为一组
        int num = ((str.length() + 8) / 64) + 1;
        //64/4=16，所以有16个整数
        int[] strByte = new int[num * 16];
        for (int i = 0; i < num * 16; i++) {
            //全部初始化0
            strByte[i] = 0;
        }
        int i;
        for (i = 0; i < str.length(); i++) {
            //一个整数存储四个字节，小端序
            strByte[i >> 2] |= str.charAt(i) << ((i % 4) * 8);
        }
        strByte[i >> 2] |= 0x80 << ((i % 4) * 8);//尾部添加1
        //添加原长度，长度指位的长度，所以要乘8，然后是小端序，所以放在倒数第二个,这里长度只用了32位
        strByte[num * 16 - 2] = str.length() * 8;
        return strByte;
    }

    /**
     * 调用函数
     */
    public String getMD5(String source) {
        init();
        int[] strByte = add(source);
        for (int i = 0; i < strByte.length / 16; i++) {
            int[] num = new int[16];
            for (int j = 0; j < 16; j++) {
                num[j] = strByte[i * 16 + j];
            }
            mainLoop(num);
        }
        return changeHex(Atemp) + changeHex(Btemp) + changeHex(Ctemp) + changeHex(Dtemp);

    }

    /**
     * 整数变成16进制字符串
     */
    private String changeHex(int a) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < 4; i++) {
            str.append(String.format("%2s", Integer.toHexString(((a >> i * 8) % (1 << 8)) & 0xff)).replace(' ', '0'));

        }
        return str.toString();
    }

    /**
     * 单例
     */
    private static MD5 instance;

    public static MD5 getInstance() {
        if (instance == null) {
            instance = new MD5();
        }
        return instance;
    }

    private MD5() {
    }

    public static void main(String[] args) {
        String str = MD5.getInstance().getMD5("1234567");
        System.out.println(str);

        String str1 = DigestUtils.md5DigestAsHex("1234567".getBytes());
        System.out.println(str1);
    }

}
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176

6. MD5在信息时代的应用

6.1. 密码加密

在我们日常使用的网站中，经常会遇到密码登陆的场景，当我们在网页上输入“用户名”和“密码”后，点击登陆按钮就会进行登录操作，我们的“用户名”和“密码”会被Http请求在body中发送给网站的服务器，如果我们的密码不进行加密传输，那么黑客等非法用意者，可能会从网络中抓取我们的登录请求，从而获得我们的密码等重要隐私信息。
那么如果要预防这种非法窃取信息的手段，我们就可以使用md5来加密我们的密码信息，比如在登录操作中，开发者可以把用户输入的密码加密成MD5后的字符串，然后通过Http请求的body体传输到网站服务端，服务端在接收到客户端加密后的MD5密码后进行加密后的密文比对(服务端也可以把用户密码保存为MD5后的密文)，来校验密码的正确性。在这个过程中通常还有密码密文加盐值的步骤，用来保证服务端密码的存储安全性和密码对比的安全性。
这种做法既保证了Http请求中用户密码的安全性，又能比对用户密码正确性。用到的就是MD5的强抗碰撞和抗修改性特性。

6.2. 电子签名

请求拦截篡改这个事，对于我们的后端服务系统来说是非常不安全的，非法用户拦截我们的请求之后就可以随意修改请求能容，从而给后端服务造成很大的风险。
为了避免这种风险的发生，通常可以对Http请求的参数进行MD5加密，加密的同时加上本次请求的随机数和时间戳等信息，防止多次请求内容一致被重复攻击，请求加密成功后，把加密结果放入Http请求的Header中传给后端服务。
后端服务在接收到请求之后，可以获取到客户端传来的请求Body和加密的MD5结果，然后再和客户端同样的逻辑把参数(参数、时间戳、随机数)进行MD5加密，加密完成后把结果和客户端的结果进行对比，一致则表示请求是安全的，不一致则表示请求可能被篡改过。
这种做法使用的就是MD5的抗修改性。

6.3. 文件查重

在互联网云时代，用户可以把自己的文件上传到服务器进行云存储，当用户数量达到一定数量的时候，上传的文件数量也会增大很多，这种情况下势必会出现很多用户上传同样的文件，如果每个用户上传的相同文件都进行存储，那么将会非常占用存储资源。如果要节约存储空间，那么对于相同的文件就可以只存储一份，然后记录每个用户对这个文件的所有权即可。
那么如何判断文件是否已经在云存储中存在呢？MD5的特性正好可以满足这一点。
当用户上传文件时，可以把文件在客户端进行MD5加密，加密后的结果先去服务器查询是否有和云服务器上相同的MD5结果的文件，如果有，那么就说明这个文件已经存在于云服务器了，这个时候只需要给上传文件的用户绑定已有文件的所有权即可，不需要再次真实上传用户文件，即实现了文件秒传，又节省了云服务存储空间。
但是上面这种操作仅适用与一些小文件上传，对于交大的文件，直接进行MD5加密会很容易失败；这时候可以把这个大文件按照规则拆分成多个小文件，把每个小文件进行MD5加密，当所有小文件加密完成后，再把所有加密结果传到服务端进行文件重复校验，就可以知道是否有重复文件了。然后再决定是否需要接收用户上传的文件进行存储。
这种做法使用的是MD5的容易计算、抗修改性、强抗碰撞、压缩性。