MD5算法

写在前面：

本文章旨在总结备份、方便以后查询，由于是个人总结，如有不对，欢迎指正；另外，内容大部分来自网络、书籍、和各类手册，如若侵权请告知，马上删帖致歉。

一、介绍

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

/* 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-digestoperation, processing another message block, and updating thecontext.*/
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;}elsei = 0;/* Buffer remaining input */MD5_memcpy((POINTER)&context->buffer[index], (POINTER)&input[i],inputLen - i);
}
/* MD5 finalization. Ends an MD5 message-digest operation, writing thethe 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 isa 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 isa 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

/* 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

/* GLOBAL.H - RSAREF types and constants*/
/* PROTOTYPES should be set to one if and only if the compiler supportsfunction 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 itreturns an empty list.*/
#if PROTOTYPES
#define PROTO_LIST(list) list
#else
#define PROTO_LIST(list) ()
#endif