MD5算法的原理与实现

MD5算法的原理与实现
***********************************************声明************************************************
原创作品，出⾃ “晓风残⽉xj” 博客，欢迎转载。

转载时请务必注明出处（）。

因为各种原因。

可能存在诸多不⾜。

欢迎斧正!
*****************************************************************************************************
⼀、MD5概念
MD5，全名Message Digest Algorithm 5 ，中⽂名为消息摘要算法第五版，为计算机安全领域⼴泛使⽤的⼀种散列函数，⽤以提供消息的完整性保护。

上⾯这段话话引⽤⾃百度百科。

我的理解MD5是⼀种信息摘要算法，主要是通过特定的hash散列⽅法将⽂本信息转换成简短的信息摘要，压缩+加密+hash算法的结合体，是绝对不可逆的。

⼆、MD5计算步骤
MD5以512位分组来处理输⼊的信息。

且每⼀分组⼜被划分为16个32位⼦分组。

经过了⼀系列的处理后。

算法的输出由四个32位分组组成，将这四个32位分组级联后将⽣成⼀个128位散列值。

第⼀步、填充
假设输⼊信息的长度(bit)对512求余的结果不等于448，就须要填充使得对512求余的结果等于448。

填充的⽅法是填充⼀个1和n个0。

填充完后，信息的长度就为N*512+448(bit)。

第⼆步、记录信息长度
⽤64位来存储填充前信息长度。

这64位加在第⼀步结果的后⾯，这样信息长度就变为N*512+448+64=(N+1)*512位。

第三步、装⼊标准的幻数（四个整数）
标准的幻数（物理顺序）是（A=(01234567)16，B=(89ABCDEF)16。

C=(FEDCBA98)16，D=(76543210)16）。

假设在程序中定义应该是
（A=0X67452301L，B=0XEFCDAB89L。

C=0X98BADCFEL，D=0X10325476L）。

有点晕哈。

事实上想⼀想就明确了。

第四步、四轮循环运算
循环的次数是分组的个数（N+1）
1）将每⼀512字节细分成16个⼩组，每⼀个⼩组64位（8个字节）
2）先认识四个线性函数(&是与,|是或,~是⾮,^是异或)
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))
3）设Mj表⽰消息的第j个⼦分组（从0到15）。

<<<s表⽰循环左移s位，则四种操作为：
FF(a,b,c,d,Mj,s,ti)表⽰a=b+((a+F(b,c,d)+Mj+ti)<<<s)
GG(a,b,c,d,Mj,s,ti)表⽰a=b+((a+G(b,c,d)+Mj+ti)<<<s)
HH(a,b,c,d,Mj,s,ti)表⽰a=b+((a+H(b,c,d)+Mj+ti)<<<s)
II(a,b,c,d,Mj,s,ti)表⽰a=b+((a+I(b,c,d)+Mj+ti)<<<s)
4）四轮运算
第⼀轮
a=FF(a,b,c,d,M0,7,0xd76aa478)
b=FF(d,a,b,c,M1,12,0xe8c7b756)
c=FF(c,d,a,b,M2,17,0x242070db)
d=FF(b,c,d,a,M3,22,0xc1bdceee)
a=FF(a,b,c,d,M4,7,0xf57c0faf)
b=FF(d,a,b,c,M5,12,0x4787c62a)
c=FF(c,d,a,b,M6,17,0xa8304613)
d=FF(b,c,d,a,M7,22,0xfd469501)
a=FF(a,b,c,d,M8,7,0x698098d8)
b=FF(d,a,b,c,M9,12,0x8b44f7af)
c=FF(c,d,a,b,M10,17,0xffff5bb1)
d=FF(b,c,d,a,M11,22,0x895cd7be)
a=FF(a,b,c,d,M12,7,0x6b901122)
b=FF(d,a,b,c,M13,12,0xfd987193)
c=FF(c,d,a,b,M14,17,0xa679438e)
d=FF(b,c,d,a,M15,22,0x49b40821)
第⼆轮
a=GG(a,b,c,d,M1,5,0xf61e2562)
b=GG(d,a,b,c,M6,9,0xc040b340)
c=GG(c,d,a,b,M11,14,0x265e5a51)
d=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a=GG(a,b,c,d,M5,5,0xd62f105d)
b=GG(d,a,b,c,M10,9,0x02441453)
c=GG(c,d,a,b,M15,14,0xd8a1e681)
d=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a=GG(a,b,c,d,M9,5,0x21e1cde6)
b=GG(d,a,b,c,M14,9,0xc33707d6)
c=GG(c,d,a,b,M3,14,0xf4d50d87)
d=GG(b,c,d,a,M8,20,0x455a14ed)
a=GG(a,b,c,d,M13,5,0xa9e3e905)
b=GG(d,a,b,c,M2,9,0xfcefa3f8)
c=GG(c,d,a,b,M7,14,0x676f02d9)
d=GG(b,c,d,a,M12,20,0x8d2a4c8a)
第三轮
a=HH(a,b,c,d,M5,4,0xfffa3942)
b=HH(d,a,b,c,M8,11,0x8771f681)
c=HH(c,d,a,b,M11,16,0x6d9d6122)
d=HH(b,c,d,a,M14,23,0xfde5380c)
a=HH(a,b,c,d,M1,4,0xa4beea44)
b=HH(d,a,b,c,M4,11,0x4bdecfa9)
c=HH(c,d,a,b,M7,16,0xf6bb4b60)
d=HH(b,c,d,a,M10,23,0xbebfbc70)
a=HH(a,b,c,d,M13,4,0x289b7ec6)
b=HH(d,a,b,c,M0,11,0xeaa127fa)
c=HH(c,d,a,b,M3,16,0xd4ef3085)
d=HH(b,c,d,a,M6,23,0x04881d05)
a=HH(a,b,c,d,M9,4,0xd9d4d039)
b=HH(d,a,b,c,M12,11,0xe6db99e5)
c=HH(c,d,a,b,M15,16,0x1fa27cf8)
d=HH(b,c,d,a,M2,23,0xc4ac5665)
第四轮
a=II(a,b,c,d,M0,6,0xf4292244)
b=II(d,a,b,c,M7,10,0x432aff97)
c=II(c,d,a,b,M14,15,0xab9423a7)
d=II(b,c,d,a,M5,21,0xfc93a039)
a=II(a,b,c,d,M12,6,0x655b59c3)
b=II(d,a,b,c,M3,10,0x8f0ccc92)
c=II(c,d,a,b,M10,15,0xffeff47d)
d=II(b,c,d,a,M1,21,0x85845dd1)
a=II(a,b,c,d,M8,6,0x6fa87e4f)
b=II(d,a,b,c,M15,10,0xfe2ce6e0)
c=II(c,d,a,b,M6,15,0xa3014314)
d=II(b,c,d,a,M13,21,0x4e0811a1)
a=II(a,b,c,d,M4,6,0xf7537e82)
b=II(d,a,b,c,M11,10,0xbd3af235)
c=II(c,d,a,b,M2,15,0x2ad7d2bb)
d=II(b,c,d,a,M9,21,0xeb86d391)
5）每轮循环后，将A，B，C。

D分别加上a，b，c，d。

然后进⼊下⼀循环。

三、MD5应⽤
1、⼀致性验证
MD5的典型应⽤是对⼀段⽂本信息产⽣信息摘要，以防⽌被篡改。

经常在某些软件下载⽹站的某软件信息中看到其MD5值，它的作⽤就在于我们能够在下载该软件后，对下载回来的⽂件⽤专门的软件（如Windows MD5 Check等）做⼀次MD5校验，以确保我们获得的⽂件与该⽹站提供的⽂件为同⼀⽂件。

2、数字证书
假设有⼀个第三⽅的认证机构。

⽤MD5还能够防⽌⽂件作者的“抵赖”，这就是所谓的数字签名应⽤。

3、安全訪问认证
在Unix系统中⽤户的password是以MD5（或其他类似的算法）经Hash运算后存储在⽂件系统中。

当⽤户登录的时候，系统把⽤户输⼊的password进⾏MD5 Hash运算，然后再去和保存在⽂件系统中的MD5值进⾏⽐較，进⽽确定输⼊的password是否正确。

通过这种步骤，系统在并不知道⽤户password的明码的情况下就能够确定⽤户登录系统的合法性。

四、源码
//MessageDigestAlgorithm5.h
#pragma once
#include<string>
#include<fstream>
#include<iostream>
using namespace std;
typedef unsigned char Byte;
class CMessageDigestAlgorithm5
{
public:
CMessageDigestAlgorithm5(void);
~CMessageDigestAlgorithm5(void);
//MD5算法主函数,对str加密
string Encode(string &str);
string Encode(ifstream& infile);
private:
unsigned int F(unsigned int x, unsigned int y,unsigned int z);
unsigned int G(unsigned int x, unsigned int y,unsigned int z);
unsigned int H(unsigned int x, unsigned int y,unsigned int z);
unsigned int I(unsigned int x, unsigned int y,unsigned int z);
void Initialize();
unsigned int LeftRotate(unsigned int opNumber,unsigned int opBit);
void FF(unsigned int &a, unsigned int b,unsigned int c,unsigned int d, unsigned int Mj,unsigned int s,unsigned int Ti); void GG(unsigned int &a, unsigned int b,unsigned int c,unsigned int d, unsigned int Mj,unsigned int s,unsigned int Ti); void HH(unsigned int &a, unsigned int b,unsigned int c,unsigned int d, unsigned int Mj,unsigned int s,unsigned int Ti); void II(unsigned int &a, unsigned int b,unsigned int c,unsigned int d, unsigned int Mj,unsigned int s,unsigned int Ti); void ByteToUnsignedInt(const Byte* input, unsigned int* output, size_t length);
string ByteToHexString(const Byte* input, size_t length);
void UnsignedIntToByte(const unsigned int * input, Byte* output, size_t length);
void ProcessOfMDA5(const Byte block[64]);
void EncodeByte(const Byte* input, size_t length);
void Final();
private:
unsigned int m_ChainingVariable[4];
unsigned int m_Count[2];
Byte m_Result[16];
Byte m_Buffer[64];
enum
{
S11 = 7,
S12 = 12,
S13 = 17,
S14 = 22,
S21 = 5,
S22 = 9,
S23 = 14,
S24 = 20,
S31 = 4,
S32 = 11,
S33 = 16,
S34 = 23,
S41 = 6,
S42 = 10,
S43 = 15,
S44 = 21,
};
static const Byte g_Padding[64];
};
//MessageDigestAlgorithm5.cpp
#include "stdafx.h"
#include "MessageDigestAlgorithm5.h"
const Byte CMessageDigestAlgorithm5::g_Padding[64] = { 0x80 };//第⼀位补1，其它补0 CMessageDigestAlgorithm5::CMessageDigestAlgorithm5(void)
{
}
CMessageDigestAlgorithm5::~CMessageDigestAlgorithm5(void)
{
}
unsigned int CMessageDigestAlgorithm5::F(unsigned int x, unsigned int y,unsigned int z)
{
return (x & y) | ((~ x) & z);
}
unsigned int CMessageDigestAlgorithm5::G(unsigned int x, unsigned int y,unsigned int z)
{
return (x & z) | (y & (~ z));
}
unsigned int CMessageDigestAlgorithm5::H(unsigned int x, unsigned int y,unsigned int z)
{
return x ^ y ^ z;
}
unsigned int CMessageDigestAlgorithm5::I(unsigned int x, unsigned int y,unsigned int z)
{
return y ^ (x | (~ z));
}
/***************************************************
*參数：空
*功能：初始化链接变量
*返回值：空
****************************************************/
void CMessageDigestAlgorithm5::Initialize()
{
m_Count[0] = m_Count[1] = 0;
m_ChainingVariable[0] = 0x67452301;
m_ChainingVariable[1] = 0xefcdab89;
m_ChainingVariable[2] = 0x98badcfe;
m_ChainingVariable[3] = 0x10325476;
}
/***************************************************
*參数：opNumber表⽰待左移的数
opBit表⽰左移的位数
*功能：完毕循环左移操作
*返回值：循环左移后值
****************************************************/
unsigned int CMessageDigestAlgorithm5::LeftRotate(unsigned int opNumber,unsigned int opBit)
{
unsigned int left = opNumber;
unsigned int right = opNumber;
return (left << opBit) | (right >> (32 - opBit));
}
void CMessageDigestAlgorithm5::FF(unsigned int &a, unsigned int b,unsigned int c,unsigned int d, unsigned int Mj,unsigned int s,unsigned int Ti) {
unsigned int temp = a + F(b,c,d) + Mj + Ti;
a =
b + LeftRotate(temp,s);
}
void CMessageDigestAlgorithm5::GG(unsigned int &a, unsigned int b,unsigned int c,unsigned int d,unsigned int Mj,unsigned int s,unsigned int Ti) {
unsigned int temp = a + G(b,c,d) + Mj + Ti;
a =
b + LeftRotate(temp,s);
}
void CMessageDigestAlgorithm5::HH(unsigned int &a, unsigned int b,unsigned int c,unsigned int d, unsigned int Mj,unsigned int s,unsigned int Ti) {
unsigned int temp = a + H(b,c,d) + Mj + Ti;
a =
b + LeftRotate(temp,s);
}
void CMessageDigestAlgorithm5::II(unsigned int &a, unsigned int b,unsigned int c,unsigned int d, unsigned int Mj,unsigned int s,unsigned int Ti) {
unsigned int temp = a + I(b,c,d) + Mj + Ti;
a =
b + LeftRotate(temp,s);
}
/***************************************************
*參数：input表⽰输⼊字节数组
output表⽰输出unsigned int数组
length表⽰输⼊字节长度
*功能：byte转unsigned int（左低右⾼）
*返回值：空
****************************************************/
void CMessageDigestAlgorithm5::ByteToUnsignedInt(const Byte* input, unsigned int* output, size_t length)
{
for(size_t i = 0,j = 0;j < length;++ i, j += 4)
{
output[i] = ((static_cast<unsigned int>(input[j]))
|((static_cast<unsigned int>(input[j + 1])) << 8)
|((static_cast<unsigned int>(input[j + 2])) << 16)
|((static_cast<unsigned int>(input[j + 3])) << 24));
}
}
/***************************************************
*參数：input表⽰输⼊unsigned int数组
output表⽰输出字节数组
length表⽰输⼊字节长度
*功能：unsigned int转byte
*返回值：空
****************************************************/
void CMessageDigestAlgorithm5::UnsignedIntToByte(const unsigned int * input, Byte* output, size_t length)
{
for (size_t i = 0, j = 0; j < length; ++i, j += 4)
{
output[j] = static_cast<Byte>(input[i] & 0xff);
output[j + 1] = static_cast<Byte>((input[i] >> 8) & 0xff);
output[j + 2] = static_cast<Byte>((input[i] >> 16) & 0xff);
output[j + 3] = static_cast<Byte>((input[i] >> 24) & 0xff);
}
}
/***************************************************
*參数：groups[]表⽰⼀个512位（64字节）分组
*功能：四轮主要操作
*返回值：空
****************************************************/
void CMessageDigestAlgorithm5::ProcessOfMDA5(const Byte groups[64])
{
unsigned int a = m_ChainingVariable[0], b = m_ChainingVariable[1], c = m_ChainingVariable[2], d = m_ChainingVariable[3]; unsigned int M[16];
ByteToUnsignedInt( groups, M, 64);
FF(a, b, c, d, M[ 0], S11, 0xd76aa478);
FF(d, a, b, c, M[ 1], S12, 0xe8c7b756);
FF(c, d, a, b, M[ 2], S13, 0x242070db);
FF(b, c, d, a, M[ 3], S14, 0xc1bdceee);
FF(a, b, c, d, M[ 4], S11, 0xf57c0faf);
FF(d, a, b, c, M[ 5], S12, 0x4787c62a);
FF(c, d, a, b, M[ 6], S13, 0xa8304613);
FF(b, c, d, a, M[ 7], S14, 0xfd469501);
FF(a, b, c, d, M[ 8], S11, 0x698098d8);
FF(d, a, b, c, M[ 9], S12, 0x8b44f7af);
FF(c, d, a, b, M[10], S13, 0xffff5bb1);
FF(b, c, d, a, M[11], S14, 0x895cd7be);
FF(a, b, c, d, M[12], S11, 0x6b901122);
FF(d, a, b, c, M[13], S12, 0xfd987193);
FF(c, d, a, b, M[14], S13, 0xa679438e);
FF(b, c, d, a, M[15], S14, 0x49b40821);
GG(a, b, c, d, M[ 1], S21, 0xf61e2562);
GG(d, a, b, c, M[ 6], S22, 0xc040b340);
GG(c, d, a, b, M[11], S23, 0x265e5a51);
GG(b, c, d, a, M[ 0], S24, 0xe9b6c7aa);
GG(a, b, c, d, M[ 5], S21, 0xd62f105d);
GG(d, a, b, c, M[10], S22, 0x2441453);
GG(c, d, a, b, M[15], S23, 0xd8a1e681);
GG(b, c, d, a, M[ 4], S24, 0xe7d3fbc8);
GG(a, b, c, d, M[ 9], S21, 0x21e1cde6);
GG(d, a, b, c, M[14], S22, 0xc33707d6);
GG(c, d, a, b, M[ 3], S23, 0xf4d50d87);
GG(b, c, d, a, M[ 8], S24, 0x455a14ed);
GG(a, b, c, d, M[13], S21, 0xa9e3e905);
GG(d, a, b, c, M[ 2], S22, 0xfcefa3f8);
GG(c, d, a, b, M[ 7], S23, 0x676f02d9);
GG(b, c, d, a, M[12], S24, 0x8d2a4c8a);
HH(a, b, c, d, M[ 5], S31, 0xfffa3942);
HH(d, a, b, c, M[ 8], S32, 0x8771f681);
HH(c, d, a, b, M[11], S33, 0x6d9d6122);
HH(b, c, d, a, M[14], S34, 0xfde5380c);
HH(a, b, c, d, M[ 1], S31, 0xa4beea44);
HH(d, a, b, c, M[ 4], S32, 0x4bdecfa9);
HH(c, d, a, b, M[ 7], S33, 0xf6bb4b60);
HH(b, c, d, a, M[10], S34, 0xbebfbc70);
HH(a, b, c, d, M[13], S31, 0x289b7ec6);
HH(d, a, b, c, M[ 0], S32, 0xeaa127fa);
HH(c, d, a, b, M[ 3], S33, 0xd4ef3085);
HH(b, c, d, a, M[ 6], S34, 0x4881d05);
HH(a, b, c, d, M[ 9], S31, 0xd9d4d039);
HH(d, a, b, c, M[12], S32, 0xe6db99e5);
HH(c, d, a, b, M[15], S33, 0x1fa27cf8);
HH(b, c, d, a, M[ 2], S34, 0xc4ac5665);
II(a, b, c, d, M[ 0], S41, 0xf4292244);
II(d, a, b, c, M[ 7], S42, 0x432aff97);
II(c, d, a, b, M[14], S43, 0xab9423a7);
II(b, c, d, a, M[ 5], S44, 0xfc93a039);
II(a, b, c, d, M[12], S41, 0x655b59c3);
II(d, a, b, c, M[ 3], S42, 0x8f0ccc92);
II(c, d, a, b, M[10], S43, 0xffeff47d);
II(b, c, d, a, M[ 1], S44, 0x85845dd1);
II(a, b, c, d, M[ 8], S41, 0x6fa87e4f);
II(d, a, b, c, M[15], S42, 0xfe2ce6e0);
II(c, d, a, b, M[ 6], S43, 0xa3014314);
II(b, c, d, a, M[13], S44, 0x4e0811a1);
II(a, b, c, d, M[ 4], S41, 0xf7537e82);
II(d, a, b, c, M[11], S42, 0xbd3af235);
II(c, d, a, b, M[ 2], S43, 0x2ad7d2bb);
II(b, c, d, a, M[ 9], S44, 0xeb86d391);
m_ChainingVariable[0] += a;
m_ChainingVariable[1] += b;
m_ChainingVariable[2] += c;
m_ChainingVariable[3] += d;
}
/***************************************************
*參数：input表⽰输⼊字节数组
length表⽰输⼊字节长度=16（8*16=128位输出）
*功能：byte转16进制
*返回值：16进制字符串
****************************************************/
string CMessageDigestAlgorithm5::ByteToHexString(const Byte* input, size_t length) {
const char MapByteToHex[16] =
{
'0', '1', '2', '3',
'4', '5', '6', '7',
'8', '9', 'A', 'B',
'C', 'D', 'E', 'F'
};
string str;
for (size_t i = 0; i < length; ++ i)
{
unsigned int temp = static_cast<unsigned int>(input[i]);
unsigned int a = temp / 16;
unsigned int b = temp % 16;
str.append(1, MapByteToHex[a]);
str.append(1, MapByteToHex[b]);
}
return str;
}
/***************************************************
*參数：str表⽰待加密⽂本
*功能：MD5算法主函数
*返回值：MD5加密后算列值
****************************************************/
string CMessageDigestAlgorithm5::Encode(string &str)
{
Initialize();
EncodeByte((const Byte * )(str.c_str()), str.length());
Final();
string strMD5 = ByteToHexString(m_Result,16);
return strMD5;
}
/***************************************************
*參数：infile表⽰待加密⽂件
*功能：MD5算法主函数
*返回值：MD5加密后算列值
****************************************************/
string CMessageDigestAlgorithm5::Encode(ifstream & infile)
{
if (!infile)
{
return "";
}
Initialize();
streamsize length;
string str;
char buffer[1024];
while (! infile.eof())
{
infile.read(buffer, 1024);
length = infile.gcount();
if (length > 0)
{
EncodeByte((const Byte* )buffer,length);
Final();
}
}
infile.close();
string strMD5 = ByteToHexString(m_Result,16);
return strMD5;
}
void CMessageDigestAlgorithm5::EncodeByte(const Byte* input, size_t length)
{
unsigned int index, partLen;
size_t i;
index = static_cast<unsigned int>((m_Count[0] >> 3) & 0x3f);//转换成字节mod64
m_Count[0] += (static_cast<unsigned int>(length) << 3);//bit数
if (m_Count[0] < (static_cast<unsigned int>(length) << 3))
{
++m_Count[1];
}
m_Count[1] += (static_cast<unsigned int>(length) >> 29);//
partLen = 64 - index;
if (length >= partLen)
{
memcpy(&m_Buffer[index], input, partLen);
ProcessOfMDA5(m_Buffer);
for (i = partLen; i + 63 < length; i += 64)
{
ProcessOfMDA5(&input[i]);
}
index = 0;
}
else
{
i = 0;
}
memcpy(&m_Buffer[index], &input[i], length - i);
}
void CMessageDigestAlgorithm5::Final()
{
Byte bits[8];
unsigned int tempChainingVariable[4],tempCount[2];
unsigned int index, padLen;
memcpy(tempChainingVariable, m_ChainingVariable, 16);
memcpy(tempCount, m_Count, 8);
UnsignedIntToByte(m_Count, bits, 8);
index = static_cast<unsigned int>((m_Count[0] >> 3) & 0x3f);
padLen = (index < 56) ?
(56 - index) : (120 - index);
EncodeByte(g_Padding, padLen);
EncodeByte(bits, 8);
UnsignedIntToByte(m_ChainingVariable,m_Result, 16);
memcpy(m_ChainingVariable, tempChainingVariable, 16);
memcpy(m_Count,tempCount, 8);
}
五、说明
对于MD5算法，不同的读取格式产⽣的字节流是不⼀样的，并且涉及计算可能须要数据格式转换，如把bit转换成⼀定的整型数据⽅便计算。

因此，不同MD5算法实现版本号算出的结果可能有⾮常⼤不⼀样。

因此，我认为最好多次计算的MD5算法版本号⼀致。

关于MD5算法。

有⼀个⽐較好的在线计算⼯具，点击。

MD5算法是不可逆的。

可是，基于键值对的字典关系原理，有⼀些收集海量MD5信息与摘要的数据库，採⽤枚举法可以从MD5值找到原⽂本信息。

提供⼀个类似的⼯具，点击。

此外。

在此提供MD5的讨论社区。

点击。

版权声明：本⽂博客原创⽂章。

博客，未经同意，不得转载。