MD5算法

作者: downdemo | 来源:发表于2018-03-29 10:24 被阅读12次

Message Digest Algorithm 5（消息摘要算法第五版），对任意长度输入能产生128bit散列值。理论上来说，结果只有2^128种而原文有无数种，因此会存在碰撞，所以有可能两个原文对应相同的散列值，不过找出这样的原文很困难

计算过程

填充消息使其位长mod512为448，填充方法是加一个1和n个0，至少填充1位，至多填充512位，填充后消息长度为512N+448bit
在第一步后填充64位消息长度，如果填充前消息长度大于2^64则只使用低64位，填充后消息长度为512（N+1）bit
用四个幻数ABCD（十六进制的整数）计算消息摘要，ABCD分别是一个32位寄存器

// 物理顺序
A = 01234567h
B = 89abcdefh
C = fedcba98h
D = 76543210h
// 代码中定义
A = 0x67452301;
B = 0xefcdab89;
C = 0x98badcfe;
D = 0x10325476;

每512bit分为一组，再将512bit分为16个64bit（8字节）小组
将ABCD副本abcd中的三个经过FGHI运算后与第四个相加，再加上32位字和一个32位字的加法常数，将结果循环左移若干位后再加上abcd之一，最后回送到ABCD完成一次循环

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))

Mj表示消息的第j个分组（0到15，共16个分组）

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)

四轮运算

// 1
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)
// 2
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)
// 3
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)
// 4
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)

加法常数由一张表T[i]定义，i为1到64之中的值，T[i]等于4294967296*abs(sin i)结果的整数部分，4294967296为2^32，i用弧度表示
所有512bit的分组都运算完后，ABCD连接起来就是最终结果

实现

头文件

/*
*******************************************************
* brief: md5 encryption
* author: Monkey.Knight
*******************************************************
*/

#ifndef __MD5_ENCODE_H__
#define __MD5_ENCODE_H__

// std
#include <string>

// define
#define UInt32 unsigned int
#define BIT_OF_BYTE  8
#define BIT_OF_GROUP 512
#define SRC_DATA_LEN 64

// 四个非线性函数宏定义
#define DEF_F(X, Y, Z ) ((( (X) & (Y) )|((~X)&(Z))))
#define DEF_G(X, Y, Z)  (((X)&(Z))|((Y)&(~Z)))
#define DEF_H(X, Y, Z)  ((X)^(Y)^(Z))
#define DEF_I(X, Y, Z)  ((Y)^((X)|(~Z)))

// 求链接数函数宏定义
#define FF(a, b, c, d, Mj, s, ti)  (a = b + CycleMoveLeft((a + DEF_F(b,c,d) + Mj + ti),s));
#define GG(a, b, c, d, Mj, s, ti)  (a = b + CycleMoveLeft((a + DEF_G(b,c,d) + Mj + ti),s));
#define HH(a, b, c, d, Mj, s, ti)  (a = b + CycleMoveLeft((a + DEF_H(b,c,d) + Mj + ti),s));
#define II(a, b, c, d, Mj, s, ti)  (a = b + CycleMoveLeft((a + DEF_I(b,c,d) + Mj + ti),s));


class Md5Encode {
public:
    // 4轮循环算法
    struct ParamDynamic{
        UInt32 ua_;
        UInt32 ub_;
        UInt32 uc_;
        UInt32 ud_;
        UInt32 va_last_;
        UInt32 vb_last_;
        UInt32 vc_last_;
        UInt32 vd_last_;
    };
public:
    Md5Encode() {
    }
    std::string Encode(std::string src_info);

protected:
    
    UInt32 CycleMoveLeft(UInt32 src_num, int bit_num_to_move);
    UInt32 FillData(const char *in_data_ptr, int data_byte_len, char** out_data_ptr);
    void RoundF(char *data_512_ptr, ParamDynamic & param);
    void RoundG(char *data_512_ptr, ParamDynamic & param);
    void RoundH(char *data_512_ptr, ParamDynamic & param);
    void RoundI(char *data_512_ptr, ParamDynamic & param);
    void RotationCalculate(char *data_512_ptr, ParamDynamic & param);
    std::string GetHexStr(unsigned int num_str);
    
private:
    // 幻数定义
    static const int kA;
    static const int kB;
    static const int kC;
    static const int kD;
    static const unsigned long long k_ti_num_integer;
};

#endif

源文件

#include "md5_encode.h"
#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;
// 幻数定义
const int Md5Encode::kA = 0x67452301;
const int Md5Encode::kB = 0xefcdab89;
const int Md5Encode::kC = 0x98badcfe;
const int Md5Encode::kD = 0x10325476;

const unsigned long long Md5Encode::k_ti_num_integer = 4294967296;

// function: CycleMoveLeft
// @param src_num:要左移的数
// @param bit_num_to_move:要移动的bit位数
// @return  循环左移后的结果数
UInt32 Md5Encode::CycleMoveLeft(UInt32 src_num, int bit_num_to_move) {
    UInt32 src_num1 = src_num;
    UInt32 src_num2 = src_num;
    if (0 >= bit_num_to_move) {
        return src_num;
    }
    UInt32 num1 = src_num1 << bit_num_to_move;
    UInt32 num2 = src_num2 >> (32 - bit_num_to_move);
    
    return ((src_num1 << bit_num_to_move) \
        | (src_num2 >> (32 - bit_num_to_move)));
}

// function: FillData
// @param in_data_ptr:    要加密的信息数据
// @param data_byte_len: 数据的字节数
// @param out_data_ptr:  填充必要信息后的数据
// return : 填充信息后的数据长度,以字节为单位
UInt32 Md5Encode::FillData(const char *in_data_ptr, int data_byte_len, char** out_data_ptr) {
    int bit_num = data_byte_len*BIT_OF_BYTE;
    int grop_num = bit_num / BIT_OF_GROUP;
    int mod_bit_num = bit_num % BIT_OF_GROUP;
    int bit_need_fill = 0;
    if (mod_bit_num > (BIT_OF_GROUP - SRC_DATA_LEN)) {
        bit_need_fill = (BIT_OF_GROUP - mod_bit_num);
        bit_need_fill += (BIT_OF_GROUP - SRC_DATA_LEN);
    }
    else {
        bit_need_fill = (BIT_OF_GROUP - SRC_DATA_LEN) - mod_bit_num; //  这里多加了一个BIT_OF_GROUP，避免bit_need_fill正好等于0,暂时不加
    }
    int all_bit = bit_num + bit_need_fill;
    if (0 < bit_need_fill) {
        *out_data_ptr = new char[all_bit / BIT_OF_BYTE + SRC_DATA_LEN / BIT_OF_BYTE];
        memset(*out_data_ptr, 0, all_bit / BIT_OF_BYTE + SRC_DATA_LEN / BIT_OF_BYTE);
        // copy data
        memcpy(*out_data_ptr, in_data_ptr, data_byte_len);
        // fill rest data
        unsigned char *tmp = reinterpret_cast<unsigned char *>(*out_data_ptr);
        tmp += data_byte_len;
        // fill 1 and 0
        *tmp = 0x80;
        // fill origin data len
        unsigned long long * origin_num = (unsigned long long *)((*out_data_ptr) + ((all_bit / BIT_OF_BYTE)));
        *origin_num = data_byte_len*BIT_OF_BYTE;
    }
    return (all_bit / BIT_OF_BYTE + SRC_DATA_LEN / BIT_OF_BYTE);
}

void Md5Encode::RoundF(char *data_BIT_OF_GROUP_ptr, ParamDynamic & param) {
    UInt32 *M = reinterpret_cast<UInt32*>(data_BIT_OF_GROUP_ptr);
    int s[] = { 7, 12, 17, 22 };
    for (int i = 0; i < 16; ++i) {
        UInt32 ti = k_ti_num_integer * abs(sin(i + 1));
        if (i % 4 == 0) {
            FF(param.ua_, param.ub_, param.uc_, param.ud_, M[i], s[i % 4], ti);
        }
        else if (i % 4 == 1) {
            FF(param.ud_, param.ua_, param.ub_, param.uc_, M[i], s[i % 4], ti);
        }
        else if (i % 4 == 2) {
            FF(param.uc_, param.ud_, param.ua_, param.ub_, M[i], s[i % 4], ti);
        }
        else if (i % 4 == 3) {
            FF(param.ub_, param.uc_, param.ud_, param.ua_, M[i], s[i % 4], ti);
        }
    }
}

void Md5Encode::RoundG(char *data_BIT_OF_GROUP_ptr, ParamDynamic & param) {
    UInt32 *M = reinterpret_cast<UInt32*>(data_BIT_OF_GROUP_ptr);
    int s[] = { 5, 9, 14, 20 };
    for (int i = 0; i < 16; ++i) {
        UInt32 ti = k_ti_num_integer * abs(sin(i + 1 + 16));
        int index = (i * 5 + 1) % 16;
        if (i % 4 == 0) {
            GG(param.ua_, param.ub_, param.uc_, param.ud_, M[index], s[i % 4], ti);
        }
        else if (i % 4 == 1) {
            GG(param.ud_, param.ua_, param.ub_, param.uc_, M[index], s[i % 4], ti);
        }
        else if (i % 4 == 2) {
            GG(param.uc_, param.ud_, param.ua_, param.ub_, M[index], s[i % 4], ti);
        }
        else if (i % 4 == 3) {
            GG(param.ub_, param.uc_, param.ud_, param.ua_, M[index], s[i % 4], ti);
        }
    }
}

void Md5Encode::RoundH(char *data_BIT_OF_GROUP_ptr, ParamDynamic & param) {
    UInt32 *M = reinterpret_cast<UInt32*>(data_BIT_OF_GROUP_ptr);
    int s[] = { 4, 11, 16, 23 };
    for (int i = 0; i < 16; ++i) {
        UInt32 ti = k_ti_num_integer * abs(sin(i + 1 + 32));
        int index = (i * 3 + 5) % 16;
        if (i % 4 == 0) {
            HH(param.ua_, param.ub_, param.uc_, param.ud_, M[index], s[i % 4], ti);
        }
        else if (i % 4 == 1) {
            HH(param.ud_, param.ua_, param.ub_, param.uc_, M[index], s[i % 4], ti);
        }
        else if (i % 4 == 2) {
            HH(param.uc_, param.ud_, param.ua_, param.ub_, M[index], s[i % 4], ti);
        }
        else if (i % 4 == 3) {
            HH(param.ub_, param.uc_, param.ud_, param.ua_, M[index], s[i % 4], ti);
        }
    }
}

void Md5Encode::RoundI(char *data_BIT_OF_GROUP_ptr, ParamDynamic & param) {
    UInt32 *M = reinterpret_cast<UInt32*>(data_BIT_OF_GROUP_ptr);
    int s[] = { 6, 10, 15, 21 };
    for (int i = 0; i < 16; ++i) {
        UInt32 ti = k_ti_num_integer * abs(sin(i + 1 + 48));
        int index = (i * 7 + 0) % 16;
        if (i % 4 == 0) {
            II(param.ua_, param.ub_, param.uc_, param.ud_, M[index], s[i % 4], ti);
        }
        else if (i % 4 == 1) {
            II(param.ud_, param.ua_, param.ub_, param.uc_, M[index], s[i % 4], ti);
        }
        else if (i % 4 == 2) {
            II(param.uc_, param.ud_, param.ua_, param.ub_, M[index], s[i % 4], ti);
        }
        else if (i % 4 == 3) {
            II(param.ub_, param.uc_, param.ud_, param.ua_, M[index], s[i % 4], ti);
        }
    }
}

void Md5Encode::RotationCalculate(char *data_512_ptr, ParamDynamic & param) {
    if (NULL == data_512_ptr) {
        return;
    }
    RoundF(data_512_ptr, param);
    RoundG(data_512_ptr, param);
    RoundH(data_512_ptr, param);
    RoundI(data_512_ptr, param);
    param.ua_ = param.va_last_ + param.ua_;
    param.ub_ = param.vb_last_ + param.ub_;
    param.uc_ = param.vc_last_ + param.uc_;
    param.ud_ = param.vd_last_ + param.ud_;
    
    param.va_last_ = param.ua_;
    param.vb_last_ = param.ub_;
    param.vc_last_ = param.uc_;
    param.vd_last_ = param.ud_;
}

// 转换成十六进制字符串输出
std::string Md5Encode::GetHexStr(unsigned int num_str) {
    std::string hexstr = "";
    char szch[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
    unsigned char *tmptr = (unsigned char *)&num_str;
    int len = sizeof(num_str);
    // 小端字节序，逆序打印
    for (int i = 0; i < len; i++){
        unsigned char ch = tmptr[i] & 0xF0;
        ch = ch >> 4;
        hexstr.append(1, szch[ch]);
        ch = tmptr[i] & 0x0F;
        hexstr.append(1, szch[ch]);
    }
    return hexstr;
}

// function: Encode
// @param src_info:要加密的信息
// return :加密后的MD5值
std::string Md5Encode::Encode(std::string src_info) {
    ParamDynamic param;
    param.ua_ = kA;
    param.ub_ = kB;
    param.uc_ = kC;
    param.ud_ = kD;
    param.va_last_ = kA;
    param.vb_last_ = kB;
    param.vc_last_ = kC;
    param.vd_last_ = kD;

    std::string result;
    const char *src_data = src_info.c_str();
    char *out_data_ptr = NULL;
    int total_byte = FillData(src_data, strlen(src_data), &out_data_ptr);
    //char * data_BIT_OF_GROUP = out_data_ptr;
    for (int i = 0; i < total_byte / (BIT_OF_GROUP / BIT_OF_BYTE); ++i) {
        char * data_BIT_OF_GROUP = out_data_ptr;
        data_BIT_OF_GROUP += i*(BIT_OF_GROUP / BIT_OF_BYTE);
        RotationCalculate(data_BIT_OF_GROUP, param);
    }
    if (NULL != out_data_ptr) {
        delete[] out_data_ptr, out_data_ptr = NULL;
    }
    result.append(GetHexStr(param.ua_));
    result.append(GetHexStr(param.ub_));
    result.append(GetHexStr(param.uc_));
    result.append(GetHexStr(param.ud_));
    return result;
}

测试

#include <iostream>
#include <cmath>
#include "md5_encode.h"

int main()
{
    std::string src = "123456";
    Md5Encode encode_obj;
    std::string ret = encode_obj.Encode(src);
    std::cout << "info: " << src.c_str() << std::endl;
    std::cout << "md5: " << ret.c_str() << std::endl;
    return 0;
}

MD5算法

计算过程

实现

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读