密碼學(xué) MD5算法

簡(jiǎn)介

MD5信息摘要算法（英語(yǔ)：MD5 Message-Digest Algorithm），一種被廣泛使用的密碼散列函數(shù)，可以產(chǎn)生出一個(gè)128位（16字節(jié)）的散列值（hash value），用于確保信息傳輸完整一致。MD5由美國(guó)密碼學(xué)家羅納德·李維斯特（Ronald Linn Rivest）設(shè)計(jì)，于1992年公開，用以取代MD4算法。這套算法的程序在 RFC 1321 標(biāo)準(zhǔn)中被加以規(guī)范。 1996年后該算法被證實(shí)存在弱點(diǎn)，可以被加以破解，對(duì)于需要高度安全性的數(shù)據(jù)，專家一般建議改用其他算法，如SHA-2。2004年，證實(shí)MD5算法無(wú)法防止碰撞（collision），因此不適用于安全性認(rèn)證，如SSL公開密鑰認(rèn)證或是數(shù)字簽名等用途。 試驗(yàn)如下鏈接： MD5在線轉(zhuǎn)化

MD5 哈希算法流程：

按位補(bǔ)充數(shù)據(jù)

在MD5算法中，首先需要對(duì)信息進(jìn)行填充，這個(gè)數(shù)據(jù)按位(bit)補(bǔ)充，要求最終的位數(shù)對(duì)512求模的結(jié)果為448。也就是說(shuō)數(shù)據(jù)補(bǔ)位后，其位數(shù)長(zhǎng)度只差64位(bit)就是512的整數(shù)倍。即便是這個(gè)數(shù)據(jù)的位數(shù)對(duì)512求模的結(jié)果正好是448也必須進(jìn)行補(bǔ)位。補(bǔ)位的實(shí)現(xiàn)過(guò)程：首先在數(shù)據(jù)后補(bǔ)一個(gè)1 bit； 接著在后面補(bǔ)上一堆0 bit, 直到整個(gè)數(shù)據(jù)的位數(shù)對(duì)512求模的結(jié)果正好為448。總之，至少補(bǔ)1位，而最多可能補(bǔ)512位 。

擴(kuò)展長(zhǎng)度

在完成補(bǔ)位工作后，又將一個(gè)表示數(shù)據(jù)原始長(zhǎng)度的64 bit數(shù)(這是對(duì)原始數(shù)據(jù)沒(méi)有補(bǔ)位前長(zhǎng)度的描述，用二進(jìn)制來(lái)表示)補(bǔ)在最后。當(dāng)完成補(bǔ)位及補(bǔ)充數(shù)據(jù)的描述后，得到的結(jié)果數(shù)據(jù)長(zhǎng)度正好是512的整數(shù)倍。也就是說(shuō)長(zhǎng)度正好是16個(gè)(32bit) 字的整數(shù)倍 。

初始化MD緩存器

MD5運(yùn)算要用到一個(gè)128位的MD5緩存器，用來(lái)保存中間變量和最終結(jié)果。該緩存器又可看成是4個(gè)32位的寄存器A、B、C、D，初始化為 [8] : A ： 01 23 45 67 B： 89 ab cd ef C： fe dc ba 98 D： 76 54 32 10

處理數(shù)據(jù)段

首先定義4個(gè)非線性函數(shù)F、G、H、I，對(duì)輸入的報(bào)文運(yùn)算以512位數(shù)據(jù)段為單位進(jìn)行處理。對(duì)每個(gè)數(shù)據(jù)段都要進(jìn)行4輪的邏輯處理，在4輪中分別使用4個(gè)不同的函數(shù)F、G、H、I。每一輪以ABCD和當(dāng)前的512位的塊為輸入，處理后送入ABCD(128位) [8] 。

輸出

信息摘要最終處理成以A, B, C, D 的形式輸出。也就是開始于A的低位在前的順序字節(jié)，結(jié)束于D的高位在前的順序字節(jié) [8] 。

C++代碼實(shí)現(xiàn)

#include<iostream>
#include<string>
using namespace std;
#define shift(x, n) (((x) << (n)) | ((x) >> (32-(n))))//右移的時(shí)候，高位一定要補(bǔ)零，而不是補(bǔ)充符號(hào)位
#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)))
#define A 0x67452301
#define B 0xefcdab89
#define C 0x98badcfe
#define D 0x10325476
//strBaye的長(zhǎng)度
unsigned int strlength;
//A,B,C,D的臨時(shí)變量
unsigned int atemp;
unsigned int btemp;
unsigned int ctemp;
unsigned int dtemp;
//常量ti unsigned int(abs(sin(i+1))*(2pow32))
const unsigned 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};
//向左位移數(shù)
const unsigned 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};
const char str16[]="0123456789abcdef";
void mainLoop(unsigned int M[])
{
    unsigned int f,g;
    unsigned int a=atemp;
    unsigned int b=btemp;
    unsigned int c=ctemp;
    unsigned int d=dtemp;
    for (unsigned int i = 0; i < 64; i++)
    {
        if(i<16){
            f=F(b,c,d);
            g=i;
        }else if (i<32)
        {
            f=G(b,c,d);
            g=(5*i+1)%16;
        }else if(i<48){
            f=H(b,c,d);
            g=(3*i+5)%16;
        }else{
            f=I(b,c,d);
            g=(7*i)%16;
        }
        unsigned 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;
}
/*
*填充函數(shù)
*處理后應(yīng)滿足bits≡448(mod512),字節(jié)就是bytes≡56（mode64)
*填充方式為先加一個(gè)1,其它位補(bǔ)零
*最后加上64位的原來(lái)長(zhǎng)度
*/
unsigned int* add(string str)
{
    unsigned int num=((str.length()+8)/64)+1;//以512位,64個(gè)字節(jié)為一組
    unsigned int *strByte=new unsigned int[num*16];    //64/4=16,所以有16個(gè)整數(shù)
    strlength=num*16;
    for (unsigned int i = 0; i < num*16; i++)
        strByte[i]=0;
    for (unsigned int i=0; i <str.length(); i++)
    {
        strByte[i>>2]|=(str[i])<<((i%4)*8);//一個(gè)整數(shù)存儲(chǔ)四個(gè)字節(jié)，i>>2表示i/4 一個(gè)unsigned int對(duì)應(yīng)4個(gè)字節(jié)，保存4個(gè)字符信息
    }
    strByte[str.length()>>2]|=0x80<<(((str.length()%4))*8);//尾部添加1 一個(gè)unsigned int保存4個(gè)字符信息,所以用128左移
    /*
    *添加原長(zhǎng)度，長(zhǎng)度指位的長(zhǎng)度，所以要乘8，然后是小端序，所以放在倒數(shù)第二個(gè),這里長(zhǎng)度只用了32位
    */
    strByte[num*16-2]=str.length()*8;
    return strByte;
}
string changeHex(int a)
{
    int b;
    string str1;
    string str="";
    for(int i=0;i<4;i++)
    {
        str1="";
        b=((a>>i*8)%(1<<8))&0xff;   //逆序處理每個(gè)字節(jié)
        for (int j = 0; j < 2; j++)
        {
            str1.insert(0,1,str16[b%16]);
            b=b/16;
        }
        str+=str1;
    }
    return str;
}
string getMD5(string source)
{
    atemp=A;    //初始化
    btemp=B;
    ctemp=C;
    dtemp=D;
    unsigned int *strByte=add(source);
    for(unsigned int i=0;i<strlength/16;i++)
    {
        unsigned int num[16];
        for(unsigned int j=0;j<16;j++)
            num[j]=strByte[i*16+j];
        mainLoop(num);
    }
    return changeHex(atemp).append(changeHex(btemp)).append(changeHex(ctemp)).append(changeHex(dtemp));
}
unsigned int main()
{
    string ss;
//    cin>>ss;
    string s=getMD5("abc");
    cout<<s;
    return 0;
}