# 介绍
MD5 消息摘要算法，英文全称：Message-Digest 5 Algorithm，是一种被广泛使用的密码散列函数，可以产生出一个 128 位（16 字节）的散列值（hash value），用于确保信息传输完整一致。但是，很不幸，自 1996 年后被证实存在弱点，可以被加以 “破解”；可由于这种算法的公开性和安全性，在 90 年代被广泛使用在各种程序语言中，用以确保资料传递无误等，对于非严格的安全信息，还是值得推选的；同时也是哈希算法的一种。
MD5 算法的算法特点如下：
（1）压缩性：任意长度的数据，算出的 MD5 值长度都是固定的。
（2）容易计算：从原数据计算出 MD5 值很容易。
（3）抗修改性：对原数据进行任何改动，哪怕只修改 1 个字节，所得到的 MD5 值都有很大区别。
（4）弱抗碰撞：已知原数据和其 MD5 值，想找到一个具有相同 MD5 值的数据（即伪造数据）是非常困难的。
（5）强抗碰撞：想找到两个不同的数据，使它们具有相同的 MD5 值，是非常困难的。
具体介绍：https://en.wikipedia.org/wiki/MD5
# 算法处理
MD5 是输入不定长度信息，输出固定长度 128-bits 的算法。经过程序流程，生成四个 32 位数据，最后联合起来成为一个 128-bits 散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算，得出结果。
运算方式：
图示：
# 应用场景
1、文件校验
一般来说，我们比较熟悉的校验算法有奇偶校验和 CRC 校验，这 2 种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。
而 MD5 Hash 算法的 “数字指纹” 特性，使它成为目前应用最广泛的一种文件完整性校验和（Checksum）算法，不少 Unix 系统有提供计算 md5 checksum 的命令。
eg：
2、数字签名
Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称 “数字摘要” 进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
eg：
在互联网信息时代，假设你注册一个网站，如果网站后台直接将用户的原始口令存放到数据库中，会产生极大的安全风险：
- 数据库管理员能够看到用户明文口令；
- 数据库数据一旦泄漏，黑客即可获取用户明文口令。
不存储用户的原始口令，那么如何对用户进行认证？
方法是存储用户口令的哈希，例如，MD5。
在用户输入原始口令后，系统计算用户输入的原始口令的 MD5 并与数据库存储的 MD5 对比，如果一致，说明口令正确，否则，口令错误。
就好比：
数据库存储用户名和口令的表内容应该像下面这样：
| username | password |
|---|---|
| Administrator | 25d55ad283aa400af464c76d713c07ad |
这样，你能看出来实际的密码吗？其实际的明文密码是：12345678。
当然，前面也说了，目前 MD5 算法已经被 "破解" 了，但是，注意这个 ” 破解 “ 一词，并不是真正的逆向计算破解，而是用暴力穷举的方法，一个口令一个口令地试，直到某个口令计算的 MD5 恰好等于指定值。
因此，也引出 “彩虹表” 一词。什么是彩虹表呢？对于暴力穷举，是会消耗大量的算力和时间的，即使当前计算机运算速度那么快，但在黑客眼里并不会做这么愚蠢的事，如果有一个预先计算好的常用口令和它们的 MD5 的对照表（如下表），那么通过查表方式，时间上将大大减少，而这个表就叫做彩虹表：
| 常用口令 | MD5 |
|---|---|
| hello123 | f30aa7a662c728b7407c54ae6bfd27d1 |
| 12345678 | 25d55ad283aa400af464c76d713c07ad |
| passw0rd | bed128365216c019988915ed3add75fb |
| 19700101 | 570da6d5277a646f6552b8832012f5dc |
| … | … |
| 20201231 | 6879c0ae9117b50074ce0a0d4c843060 |
这就是为什么不要使用常用密码，以及不要使用生日作为密码的原因。
由于 MD5 具有抗修改性，人们利用这一性质，可以采取相应的措施来抵御彩虹表攻击，方法就是对每个口令额外添加随机数，这个方法称之为加盐（salt）：
digest = md5(salt + inputPassword)
加盐的目的在于使黑客的彩虹表失效，即使用户使用常用口令，也无法从 MD5 反推原始口令。
eg：（摘自心知天气 API 接口文档，注意看第二点）
大致的一个流程：
用户注册时，
- 用户输入【账号】和【密码】（以及其他用户信息）；
- 系统为用户生成【Salt 值】；
- 系统将【Salt 值】和【用户密码】连接到一起；
- 对连接后的值进行散列，得到【Hash1 值】；
- 将【Hash1 值】和【Salt 值】分别放到数据库中。
用户登录时，
- 用户输入【账号】和【密码】；
- 系统通过用户名找到与之对应的【Hash 值】和【Salt 值】；
- 系统将【Salt 值】和【用户输入的密码】连接到一起；
- 对连接后的值进行散列，得到【Hash2 值】（注意是即时运算出来的值）；
- 比较【Hash1 值】和【Hash2 值】是否相等，相等则表示密码正确，否则表示密码错误。
有时候，为了减轻开发压力，程序员会统一使用一个 Salt 值（储存在某个地方），而不是每个用户都生成私有的 Salt 值。
# 公开的 MD5 Message-Digest Algorithm 代码
/* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm | |
*/ | |
/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All | |
rights reserved. | |
License to copy and use this software is granted provided that it | |
is identified as the "RSA Data Security, Inc. MD5 Message-Digest | |
Algorithm" in all material mentioning or referencing this software | |
or this function. | |
License is also granted to make and use derivative works provided | |
that such works are identified as "derived from the RSA Data | |
Security, Inc. MD5 Message-Digest Algorithm" in all material | |
mentioning or referencing the derived work. | |
RSA Data Security, Inc. makes no representations concerning either | |
the merchantability of this software or the suitability of this | |
software for any particular purpose. It is provided "as is" | |
without express or implied warranty of any kind. | |
These notices must be retained in any copies of any part of this | |
documentation and/or software. | |
*/ | |
#include "global.h" | |
#include "md5.h" | |
/* Constants for MD5Transform routine. | |
*/ | |
#define S11 7 | |
#define S12 12 | |
#define S13 17 | |
#define S14 22 | |
#define S21 5 | |
#define S22 9 | |
#define S23 14 | |
#define S24 20 | |
#define S31 4 | |
#define S32 11 | |
#define S33 16 | |
#define S34 23 | |
#define S41 6 | |
#define S42 10 | |
#define S43 15 | |
#define S44 21 | |
static void MD5Transform PROTO_LIST((UINT4[4], unsigned char[64])); | |
static void Encode PROTO_LIST((unsigned char *, UINT4 *, unsigned int)); | |
static void Decode PROTO_LIST((UINT4 *, unsigned char *, unsigned int)); | |
static void MD5_memcpy PROTO_LIST((POINTER, POINTER, unsigned int)); | |
static void MD5_memset PROTO_LIST((POINTER, int, unsigned int)); | |
static unsigned char PADDING[64] = { | |
0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; | |
/* F, G, H and I are basic MD5 functions. | |
*/ | |
#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) | |
#define G(x, y, z) (((x) & (z)) | ((y) & (~z))) | |
#define H(x, y, z) ((x) ^ (y) ^ (z)) | |
#define I(x, y, z) ((y) ^ ((x) | (~z))) | |
/* ROTATE_LEFT rotates x left n bits. | |
*/ | |
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) | |
/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4. | |
Rotation is separate from addition to prevent recomputation. | |
*/ | |
#define FF(a, b, c, d, x, s, ac) \ | |
{ \ | |
(a) += F((b), (c), (d)) + (x) + (UINT4)(ac); \ | |
(a) = ROTATE_LEFT((a), (s)); \ | |
(a) += (b); \ | |
} | |
#define GG(a, b, c, d, x, s, ac) \ | |
{ \ | |
(a) += G((b), (c), (d)) + (x) + (UINT4)(ac); \ | |
(a) = ROTATE_LEFT((a), (s)); \ | |
(a) += (b); \ | |
} | |
#define HH(a, b, c, d, x, s, ac) \ | |
{ \ | |
(a) += H((b), (c), (d)) + (x) + (UINT4)(ac); \ | |
(a) = ROTATE_LEFT((a), (s)); \ | |
(a) += (b); \ | |
} | |
#define II(a, b, c, d, x, s, ac) \ | |
{ \ | |
(a) += I((b), (c), (d)) + (x) + (UINT4)(ac); \ | |
(a) = ROTATE_LEFT((a), (s)); \ | |
(a) += (b); \ | |
} | |
/* MD5 initialization. Begins an MD5 operation, writing a new context. | |
*/ | |
void MD5Init(context) | |
MD5_CTX *context; /* context */ | |
{ | |
context->count[0] = context->count[1] = 0; | |
/* Load magic initialization constants. | |
*/ | |
context->state[0] = 0x67452301; | |
context->state[1] = 0xefcdab89; | |
context->state[2] = 0x98badcfe; | |
context->state[3] = 0x10325476; | |
} | |
/* MD5 block update operation. Continues an MD5 message-digest | |
operation, processing another message block, and updating the | |
context. | |
*/ | |
void MD5Update(context, input, inputLen) | |
MD5_CTX *context; /* context */ | |
unsigned char *input; /* input block */ | |
unsigned int inputLen; /* length of input block */ | |
{ | |
unsigned int i, index, partLen; | |
/* Compute number of bytes mod 64 */ | |
index = (unsigned int)((context->count[0] >> 3) & 0x3F); | |
/* Update number of bits */ | |
if ((context->count[0] += ((UINT4)inputLen << 3)) < ((UINT4)inputLen << 3)) | |
context->count[1]++; | |
context->count[1] += ((UINT4)inputLen >> 29); | |
partLen = 64 - index; | |
/* Transform as many times as possible. | |
*/ | |
if (inputLen >= partLen) | |
{ | |
MD5_memcpy((POINTER)&context->buffer[index], (POINTER)input, partLen); | |
MD5Transform(context->state, context->buffer); | |
for (i = partLen; i + 63 < inputLen; i += 64) | |
MD5Transform(context->state, &input[i]); | |
index = 0; | |
} | |
else | |
i = 0; | |
/* Buffer remaining input */ | |
MD5_memcpy((POINTER)&context->buffer[index], (POINTER)&input[i], | |
inputLen - i); | |
} | |
/* MD5 finalization. Ends an MD5 message-digest operation, writing the | |
the message digest and zeroizing the context. | |
*/ | |
void MD5Final(digest, context) unsigned char digest[16]; /* message digest */ | |
MD5_CTX *context; /* context */ | |
{ | |
unsigned char bits[8]; | |
unsigned int index, padLen; | |
/* Save number of bits */ | |
Encode(bits, context->count, 8); | |
/* Pad out to 56 mod 64. | |
*/ | |
index = (unsigned int)((context->count[0] >> 3) & 0x3f); | |
padLen = (index < 56) ? (56 - index) : (120 - index); | |
MD5Update(context, PADDING, padLen); | |
/* Append length (before padding) */ | |
MD5Update(context, bits, 8); | |
/* Store state in digest */ | |
Encode(digest, context->state, 16); | |
/* Zeroize sensitive information. | |
*/ | |
MD5_memset((POINTER)context, 0, sizeof(*context)); | |
} | |
/* MD5 basic transformation. Transforms state based on block. | |
*/ | |
static void MD5Transform(state, block) | |
UINT4 state[4]; | |
unsigned char block[64]; | |
{ | |
UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16]; | |
Decode(x, block, 64); | |
/* Round 1 */ | |
FF(a, b, c, d, x[0], S11, 0xd76aa478); /* 1 */ | |
FF(d, a, b, c, x[1], S12, 0xe8c7b756); /* 2 */ | |
FF(c, d, a, b, x[2], S13, 0x242070db); /* 3 */ | |
FF(b, c, d, a, x[3], S14, 0xc1bdceee); /* 4 */ | |
FF(a, b, c, d, x[4], S11, 0xf57c0faf); /* 5 */ | |
FF(d, a, b, c, x[5], S12, 0x4787c62a); /* 6 */ | |
FF(c, d, a, b, x[6], S13, 0xa8304613); /* 7 */ | |
FF(b, c, d, a, x[7], S14, 0xfd469501); /* 8 */ | |
FF(a, b, c, d, x[8], S11, 0x698098d8); /* 9 */ | |
FF(d, a, b, c, x[9], S12, 0x8b44f7af); /* 10 */ | |
FF(c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */ | |
FF(b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */ | |
FF(a, b, c, d, x[12], S11, 0x6b901122); /* 13 */ | |
FF(d, a, b, c, x[13], S12, 0xfd987193); /* 14 */ | |
FF(c, d, a, b, x[14], S13, 0xa679438e); /* 15 */ | |
FF(b, c, d, a, x[15], S14, 0x49b40821); /* 16 */ | |
/* Round 2 */ | |
GG(a, b, c, d, x[1], S21, 0xf61e2562); /* 17 */ | |
GG(d, a, b, c, x[6], S22, 0xc040b340); /* 18 */ | |
GG(c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */ | |
GG(b, c, d, a, x[0], S24, 0xe9b6c7aa); /* 20 */ | |
GG(a, b, c, d, x[5], S21, 0xd62f105d); /* 21 */ | |
GG(d, a, b, c, x[10], S22, 0x2441453); /* 22 */ | |
GG(c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */ | |
GG(b, c, d, a, x[4], S24, 0xe7d3fbc8); /* 24 */ | |
GG(a, b, c, d, x[9], S21, 0x21e1cde6); /* 25 */ | |
GG(d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */ | |
GG(c, d, a, b, x[3], S23, 0xf4d50d87); /* 27 */ | |
GG(b, c, d, a, x[8], S24, 0x455a14ed); /* 28 */ | |
GG(a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */ | |
GG(d, a, b, c, x[2], S22, 0xfcefa3f8); /* 30 */ | |
GG(c, d, a, b, x[7], S23, 0x676f02d9); /* 31 */ | |
GG(b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */ | |
/* Round 3 */ | |
HH(a, b, c, d, x[5], S31, 0xfffa3942); /* 33 */ | |
HH(d, a, b, c, x[8], S32, 0x8771f681); /* 34 */ | |
HH(c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */ | |
HH(b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */ | |
HH(a, b, c, d, x[1], S31, 0xa4beea44); /* 37 */ | |
HH(d, a, b, c, x[4], S32, 0x4bdecfa9); /* 38 */ | |
HH(c, d, a, b, x[7], S33, 0xf6bb4b60); /* 39 */ | |
HH(b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */ | |
HH(a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */ | |
HH(d, a, b, c, x[0], S32, 0xeaa127fa); /* 42 */ | |
HH(c, d, a, b, x[3], S33, 0xd4ef3085); /* 43 */ | |
HH(b, c, d, a, x[6], S34, 0x4881d05); /* 44 */ | |
HH(a, b, c, d, x[9], S31, 0xd9d4d039); /* 45 */ | |
HH(d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */ | |
HH(c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */ | |
HH(b, c, d, a, x[2], S34, 0xc4ac5665); /* 48 */ | |
/* Round 4 */ | |
II(a, b, c, d, x[0], S41, 0xf4292244); /* 49 */ | |
II(d, a, b, c, x[7], S42, 0x432aff97); /* 50 */ | |
II(c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */ | |
II(b, c, d, a, x[5], S44, 0xfc93a039); /* 52 */ | |
II(a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */ | |
II(d, a, b, c, x[3], S42, 0x8f0ccc92); /* 54 */ | |
II(c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */ | |
II(b, c, d, a, x[1], S44, 0x85845dd1); /* 56 */ | |
II(a, b, c, d, x[8], S41, 0x6fa87e4f); /* 57 */ | |
II(d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */ | |
II(c, d, a, b, x[6], S43, 0xa3014314); /* 59 */ | |
II(b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */ | |
II(a, b, c, d, x[4], S41, 0xf7537e82); /* 61 */ | |
II(d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */ | |
II(c, d, a, b, x[2], S43, 0x2ad7d2bb); /* 63 */ | |
II(b, c, d, a, x[9], S44, 0xeb86d391); /* 64 */ | |
state[0] += a; | |
state[1] += b; | |
state[2] += c; | |
state[3] += d; | |
/* Zeroize sensitive information. | |
*/ | |
MD5_memset((POINTER)x, 0, sizeof(x)); | |
} | |
/* Encodes input (UINT4) into output (unsigned char). Assumes len is | |
a multiple of 4. | |
*/ | |
static void Encode(output, input, len) unsigned char *output; | |
UINT4 *input; | |
unsigned int len; | |
{ | |
unsigned int i, j; | |
for (i = 0, j = 0; j < len; i++, j += 4) | |
{ | |
output[j] = (unsigned char)(input[i] & 0xff); | |
output[j + 1] = (unsigned char)((input[i] >> 8) & 0xff); | |
output[j + 2] = (unsigned char)((input[i] >> 16) & 0xff); | |
output[j + 3] = (unsigned char)((input[i] >> 24) & 0xff); | |
} | |
} | |
/* Decodes input (unsigned char) into output (UINT4). Assumes len is | |
a multiple of 4. | |
*/ | |
static void Decode(output, input, len) | |
UINT4 *output; | |
unsigned char *input; | |
unsigned int len; | |
{ | |
unsigned int i, j; | |
for (i = 0, j = 0; j < len; i++, j += 4) | |
output[i] = ((UINT4)input[j]) | (((UINT4)input[j + 1]) << 8) | | |
(((UINT4)input[j + 2]) << 16) | (((UINT4)input[j + 3]) << 24); | |
} | |
/* Note: Replace "for loop" with standard memcpy if possible. | |
*/ | |
static void MD5_memcpy(output, input, len) | |
POINTER output; | |
POINTER input; | |
unsigned int len; | |
{ | |
unsigned int i; | |
for (i = 0; i < len; i++) | |
output[i] = input[i]; | |
} | |
/* Note: Replace "for loop" with standard memset if possible. | |
*/ | |
static void MD5_memset(output, value, len) | |
POINTER output; | |
int value; | |
unsigned int len; | |
{ | |
unsigned int i; | |
for (i = 0; i < len; i++) | |
((char *)output)[i] = (char)value; | |
} |
/* MD5.H - header file for MD5C.C | |
*/ | |
/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All | |
rights reserved. | |
License to copy and use this software is granted provided that it | |
is identified as the "RSA Data Security, Inc. MD5 Message-Digest | |
Algorithm" in all material mentioning or referencing this software | |
or this function. | |
License is also granted to make and use derivative works provided | |
that such works are identified as "derived from the RSA Data | |
Security, Inc. MD5 Message-Digest Algorithm" in all material | |
mentioning or referencing the derived work. | |
RSA Data Security, Inc. makes no representations concerning either | |
the merchantability of this software or the suitability of this | |
software for any particular purpose. It is provided "as is" | |
without express or implied warranty of any kind. | |
These notices must be retained in any copies of any part of this | |
documentation and/or software. | |
*/ | |
/* MD5 context. */ | |
typedef struct | |
{ | |
UINT4 state[4]; /* state (ABCD) */ | |
UINT4 count[2]; /* number of bits, modulo 2^64 (lsb first) */ | |
unsigned char buffer[64]; /* input buffer */ | |
} MD5_CTX; | |
void MD5Init PROTO_LIST((MD5_CTX *)); | |
void MD5Update PROTO_LIST((MD5_CTX *, unsigned char *, unsigned int)); | |
void MD5Final PROTO_LIST((unsigned char[16], MD5_CTX *)); |
/* GLOBAL.H - RSAREF types and constants | |
*/ | |
/* PROTOTYPES should be set to one if and only if the compiler supports | |
function argument prototyping. | |
The following makes PROTOTYPES default to 0 if it has not already | |
been defined with C compiler flags. | |
*/ | |
#ifndef PROTOTYPES | |
#define PROTOTYPES 0 | |
#endif | |
/* POINTER defines a generic pointer type */ | |
typedef unsigned char *POINTER; | |
/* UINT2 defines a two byte word */ | |
typedef unsigned short int UINT2; | |
/* UINT4 defines a four byte word */ | |
typedef unsigned long int UINT4; | |
/* PROTO_LIST is defined depending on how PROTOTYPES is defined above. | |
If using PROTOTYPES, then PROTO_LIST returns the list, otherwise it | |
returns an empty list. | |
*/ | |
#if PROTOTYPES | |
#define PROTO_LIST(list) list | |
#else | |
#define PROTO_LIST(list) () | |
#endif |
以上代码摘自：RFC 1321
# 修改后的应用代码
测试：
