md5算法

Message Digest Algorithm MD5（中文名为消息摘要算法第五版）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。
（1）概述：
MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32 位分组级联后将生成一个128位散列值。
（2）算法流程：



分别对每个流程作出解释：
信息填充
目的：使信息位长度恰好是512的整数倍。
填充的方法：在信息的后面填充一个1和无数个 0，直到使信息的位长（Bits Length）将被扩展至N*512+448，才停止用0对信息的填充。然后，在这个结果后面附加一个以64位二进制表示的填充前信息长度。这样做的原因是为满足后面处理中对信息长度的要求。
主循环操作
首先给定链接变量，具体包括四个32位的整数参数，分别为：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。将上面四个链接变量复制到另外四个变量中：A到a，B到b，C到c，D到d。
将当前将要处理的512位信息分成16组，每组32位，分别表示为：M0，M1，……，M15。
ti表示一个常数，可以如下选择：在第i步中，ti是4294967296*abs(sin(i))的整数部分，i的单位是弧度。
每轮循环操作都很相似，都要进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组Mj和一个常数ti。再将所得结果向右环移一个不定的数s，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。
一轮循环
第一轮循环所用到的非线性函数：F(X,Y,Z) =(X&Y)|((~X)&Z)。
每一次操作可以表示为FF(a, b, c, d, Mj, s, ti)：a = b + ((a + F(b, c, d) + Mj + ti) << s)。
第一轮的16次操作可以分别表示为：
FF(a, b, c, d, M0, 7, 0xd76aa478)
FF(d, a, b, c, M1, 12, 0xe8c7b756)
FF(c, d, a, b, M2, 17, 0x242070db)
FF(b, c, d, a, M3, 22, 0xc1bdceee)
FF(a, b, c, d, M4, 7, 0xf57c0faf)
FF(d, a, b, c, M5, 12, 0x4787c62a)
FF(c, d, a, b, M6, 17, 0xa8304613)
FF(b, c, d, a, M7, 22, 0xfd469501)
FF(a, b, c, d, M8, 7, 0x698098d8)
FF(d, a, b, c, M9, 12, 0x8b44f7af)
FF(c, d, a, b, M10, 17, 0xffff5bb1)
FF(b, c, d, a, M11, 22, 0x895cd7be)
FF(a, b, c, d, M12, 7, 0x6b901122)
FF(d, a, b, c, M13, 12, 0xfd987193)
FF(c, d, a, b, M14, 17, 0xa679438e)
FF(b, c, d, a, M15, 22, 0x49b40821)
二轮循环
第二轮循环所用到的非线性函数：G(X,Y,Z) =(X&Z)|(Y&(~Z))。
每一次操作可以表示为GG(a, b, c, d, Mj, s, ti)：a = b + ((a + G(b, c, d) + Mj + ti) << s)。
第二轮的16次操作可以分别表示为：
GG(a, b, c, d, M1, 5, 0xf61e2562)
GG(d, a, b, c, M6, 9, 0xc040b340)
GG(c, d, a, b, M11, 14, 0x265e5a51)
GG(b, c, d, a, M0, 20, 0xe9b6c7aa)
GG(a, b, c, d, M5, 5, 0xd62f105d)
GG(d, a, b, c, M10, 9, 0x02441453)
GG(c, d, a, b, M15, 14, 0xd8a1e681)
GG(b, c, d, a, M4, 20, 0xe7d3fbc8)
GG(a, b, c, d, M9, 5, 0x21e1cde6)
GG(d, a, b, c, M14, 9, 0xc33707d6)
GG(c, d, a, b, M3, 14, 0xf4d50d87)
GG(b, c, d, a, M8, 20, 0x455a14ed)
GG(a, b, c, d, M13, 5, 0xa9e3e905)
GG(d, a, b, c, M2, 9, 0xfcefa3f8)
GG(c, d, a, b, M7, 14, 0x676f02d9)
GG(b, c, d, a, M12, 20, 0x8d2a4c8a)
三轮循环
第三轮循环所用到的非线性函数：H(X,Y,Z) =X^Y^Z。
每一次操作可以表示为HH(a, b, c, d, Mj, s, ti)：a = b + ((a + H(b, c, d) + Mj + ti) << s)。
第三轮的16次操作可以分别表示为：
HH(a, b, c, d, M5, 4, 0xfffa3942)
HH(d, a, b, c, M8, 11, 0x8771f681)
HH(c, d, a, b, M11, 16, 0x6d9d6122)
HH(b, c, d, a, M14, 23, 0xfde5380c)
HH(a, b, c, d, M1, 4, 0xa4beea44)
HH(d, a, b, c, M4, 11, 0x4bdecfa9)
HH(c, d, a, b, M7, 16, 0xf6bb4b60)
HH(b, c, d, a, M10, 23, 0xbebfbc70)
HH(a, b, c, d, M13, 4, 0x289b7ec6)
HH(d, a, b, c, M0, 11, 0xeaa127fa)
HH(c, d, a, b, M3, 16, 0xd4ef3085)
HH(b, c, d, a, M6, 23, 0x04881d05)
HH(a, b, c, d, M9, 4, 0xd9d4d039)
HH(d, a, b, c, M12, 11, 0xe6db99e5)
HH(c, d, a, b, M15, 16, 0x1fa27cf8)
HH(b, c, d, a, M2, 23, 0xc4ac5665)
四轮循环
第四轮循环所用到的非线性函数：I(X,Y,Z)=Y^(X|(~Z))。
每一次操作可以表示为：II(a, b, c, d, Mj, s, ti)表示 a = b + ((a + I(b, c, d) + Mj + ti) << s)。
第四轮的16次操作可以分别表示为：
II(a, b, c, d, M0, 6, 0xf4292244)
II(d, a, b, c, M7, 10, 0x432aff97)
II(c, d, a, b, M14, 15, 0xab9423a7)
II(b, c, d, a, M5, 21, 0xfc93a039)
II(a, b, c, d, M12, 6, 0x655b59c3)
II(d, a, b, c, M3, 10, 0x8f0ccc92)
II(c, d, a, b, M10, 15, 0xffeff47d)
II(b, c, d, a, M1, 21, 0x85845dd1)
II(a, b, c, d, M8, 6, 0x6fa87e4f)
II(d, a, b, c, M15, 10, 0xfe2ce6e0)
II(c, d, a, b, M6, 15, 0xa3014314)
II(b, c, d, a, M13, 21, 0x4e0811a1)
II(a, b, c, d, M4, 6, 0xf7537e82)
II(d, a, b, c, M11, 10, 0xbd3af235)
II(c, d, a, b, M2, 15, 0x2ad7d2bb)
II(b, c, d, a, M9, 21, 0xeb86d391)
所有这些完成之后，将A、B、C、D分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是A、B、C和D的级联。
（3）算法的应用：
MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。比如，在UNIX下有很多软件在下载的时 候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如：
MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461
这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息， 通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。
大家都知道，地球上任何人都有自己独一无二的指纹，MD5就可以为任何文件（不管其大小、格式、数量）产生一个同样独一无二的“数字指纹”，如果任何人对文件做了任何改动，其MD5值也 就是对应的“数字指纹”都会发生变化。
举个例子，你将一段话写在一个叫 readme.txt文件中，并对这个readme.txt产生一个MD5的值并记录在案，然后你可以传播这个文件给别人，别人如果修改了文件中的任何内容，你对这个文件重新计算MD5时就会发现（两个MD5值不相同）。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的“抵赖”，这就是所谓的数字签名应用。
MD5还广泛用于操作系统的登陆认证上，如Unix、各类BSD系统登录密码、数字签名等诸多方。如在UNIX系统中用户的密码是以MD5（或其它类似的 算法）经Hash运算后存储在文件系统中。当用户登录的时候，系统把用户输入的密码进行MD5 Hash运算，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。
MD5将任意长度的“字节串”映射为一个128bit的大整数，并且是通过该128bit反推原始字符串是困难的，换句话说就是，即使你看到源程序和算法 描述，也无法将一个MD5的值变换回原始的字符串，从数学原理上说，是因为原始的字符串有无穷多个，这有点象不存在反函数的数学函数。
md5算法是一种不可逆加密算法。
不可逆加密算法的特征是加密过程中不需要使用密钥，输入明文后由系统直接经过加密算法处理成密文，这种加密后的数据是无法被解密的，只有重新输入明文，并 再次经过同样不可逆的加密算法处理，得到相同的加密密文并被系统重新识别后，才能真正解密。显然，在这类加密过程中，加密是自己，解密还得是自己，而所谓解密，实际上就是重新加一次密，所应用的“密码”也就是输入的明文。
MD5是基于Hash变换而来的，MD5将任意长度的“字节串”变换成一个128bit的大整数，并且它是一个不可逆的字符串变换算法。换句话说就是，即使你看到源程序和算法描述，也无法将一个MD5的值变换回原始的字符串，从数学原理上说，是因为原始的字符串有无穷多个，这有点像不存在反函数的数学函数。
严格意义上说，md5并不是加密算法，而只是一种得到字节串"指纹"的方法。通过MD5算法可以得到任意长度的信息的“指纹”（或称为报文摘要）。据推测要实现两个不同的报文产生相同的摘要需要2^64次的操作，要恢复给定摘要的报文则需要2^128次操作
MD5一度被广泛应用于安全领域。但是由于MD5的弱点被不断发现以及计算机能力不断的提升，现在已经可以构造两个具有相同MD5的信息，使本算法不再适合当前的安全环境。目前，MD5计算广泛应用于错误检查。例如在一些BitTorrent下载中，软件通过计算MD5和检验下载到的碎片的完整性。


给出一个实现代码:

/*
* md5 -- compute and check MD5 message digest.
* this version only can calculate the char string.
*
* MD5 (Message-Digest algorithm 5) is a widely used, partially
* insecure cryptographic hash function with a 128-bit hash value.
*
* Author: redraiment
* Date: Aug 27, 2008
* Version: 0.1.6
*/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>

#define SINGLE_ONE_BIT 0x80
#define BLOCK_SIZE 512
#define MOD_SIZE 448
#define APP_SIZE 64
#define BITS 8

// MD5 Chaining Variable
//链接变量
#define A 0x67452301UL
#define B 0xEFCDAB89UL
#define C 0x98BADCFEUL
#define D 0x10325476UL

// Creating own types
#ifdef UINT64
# undef UINT64
#endif
#ifdef UINT32
# undef UINT32
#endif

typedef unsigned long long UINT64;
typedef unsigned long UINT32;
typedef unsigned char UINT8;
typedef struct
{
    char * message;
    UINT64 length;
}STRING;
const UINT32 X[4][2] = {{0, 1}, {1, 5}, {5, 3}, {0, 7}};
// Constants for MD5 transform routine.

//四次循环环移的次数
const UINT32 S[4][4] = {
                            { 7, 12, 17, 22 },
                            { 5, 9, 14, 20 },
                            { 4, 11, 16, 23 },
                            { 6, 10, 15, 21 }
                            };

//主循环基本操作
// F, G, H and I are basic MD5 functions.
UINT32 F( UINT32 X, UINT32 Y, UINT32 Z )
{
    return ( X & Y ) | ( ~X & Z );
}
UINT32 G( UINT32 X, UINT32 Y, UINT32 Z )
{
    return ( X & Z ) | ( Y & ~Z );
}
UINT32 H( UINT32 X, UINT32 Y, UINT32 Z )
{
    return X ^ Y ^ Z;
}
UINT32 I( UINT32 X, UINT32 Y, UINT32 Z )
{
    return Y ^ ( X | ~Z );
}
// rotates x left s bits.
//这里是环移
UINT32 rotate_left( UINT32 x, UINT32 s )
{
    return ( x << s ) | ( x >> ( 32 - s ) );
}

// Pre-processin

//返回需要填充的字节数(不算64位)
UINT32 count_padding_bits ( UINT32 length )
{
    UINT32 div = length * BITS / BLOCK_SIZE;
    UINT32 mod = length * BITS % BLOCK_SIZE;
    UINT32 c_bits;
    if ( mod == 0 )
        c_bits = MOD_SIZE;
    else
        c_bits = ( MOD_SIZE + BLOCK_SIZE - mod ) % BLOCK_SIZE;
    return c_bits / BITS;
}
//完成填充
STRING append_padding_bits ( char * argv )
{
    UINT32 msg_length = strlen ( argv );
    UINT32 bit_length = count_padding_bits ( msg_length );
    UINT64 app_length = msg_length * BITS;
    STRING string;
    //开辟512的倍数空间
    string.message = (char *)malloc(msg_length + bit_length + APP_SIZE / BITS);
    // Save message
    strncpy ( string.message, argv, msg_length );
    // Pad out to mod 64.
    memset ( string.message + msg_length, 0, bit_length );
    string.message [ msg_length ] = SINGLE_ONE_BIT; //第一位填充1

    //注意:最后64位,64-bit little-endian integer
    //即:低地址存放整数的低位(字节为单位)
    memmove ( string.message + msg_length + bit_length, (char *)&app_length, sizeof( UINT64 ) );
    string.length = msg_length + bit_length + sizeof( UINT64 );
    return string;
}

void md5(char* info)
{
    STRING string;
    UINT32 w[16];
    UINT32 chain[4];
    UINT32 state[4];
    UINT8 r[16];

    //数组的元素是指针,指针指向一个函数
    UINT32 ( *auxi[ 4 ])( UINT32, UINT32, UINT32 ) = { F, G, H, I };
    int roundIdx;
    int sIdx;
    int wIdx;
    int i;
    int j;

    string = append_padding_bits (info); //信息填充

    UINT8 r2[64];
    memmove ( r2, (char *)string.message, 64 );
    for(i=0;i<64;i++)
        printf("%02x",r2[i]);
    printf("\n");

    // MD5 initialization.
    chain[0] = A;
    chain[1] = B;
    chain[2] = C;
    chain[3] = D;
    for ( j = 0; j < string.length; j += BLOCK_SIZE / BITS) //一次处理512为
    {
        //处理信息放到w
        memmove ( (char *)w, string.message + j, BLOCK_SIZE / BITS );
        //链接元素放到state
        memmove ( state, chain, sizeof(chain) );
        //四轮循环
        for ( roundIdx = 0; roundIdx < 4; roundIdx++ )
        {
            wIdx = X[ roundIdx ][ 0 ]; //信息位的下标
            sIdx = 0;
            for ( i = 0; i < 16; i++ )
            {
                //一次运算 FF(a, b, c, d, Mj, s, ti)：a = b + ((a + F(b, c, d) + Mj + ti) << s)
                state[sIdx] = state [ (sIdx + 1) % 4 ] +rotate_left (
                    state[sIdx] +( *auxi[ roundIdx ] )( state[(sIdx+1) % 4], state[(sIdx+2) % 4], state[(sIdx+3) % 4]) //操作
                    +w[ wIdx ] //32为信息
                    +(UINT32)floor( (1ULL << 32) * fabs(sin( roundIdx * 16 + i + 1 )) ), //常量
                    S[ roundIdx ][ i % 4 ] //环移的次数
                );
                sIdx = ( sIdx + 3 ) % 4;
                wIdx = ( wIdx + X[ roundIdx ][ 1 ] ) & 0xF;
            }
        }
        //每一个512分组,更新一次链接变量
        //这里32位无符号整数进行相加,如果发生溢出,作截断处理.
        chain[ 0 ] += state[ 0 ];
        chain[ 1 ] += state[ 1 ];
        chain[ 2 ] += state[ 2 ];
        chain[ 3 ] += state[ 3 ];
    }
    memmove ( r + 0, (char *)&chain[0], sizeof(UINT32) );
    memmove ( r + 4, (char *)&chain[1], sizeof(UINT32) );
    memmove ( r + 8, (char *)&chain[2], sizeof(UINT32) );
    memmove ( r + 12, (char *)&chain[3], sizeof(UINT32) );
    for ( i = 0; i < 16; i++ )
        printf ( "%02x", r[i] );
    putchar ( '\n' );
}
int main()
{
    //freopen("main.txt","w",stdout);
    char info[]="a";
    md5(info);

    /*
    UINT32 ma=0xfffffffb;
    UINT32 ans=0x1;
    int num=10;
    while(num--)
    {
        ma+=ans;
        printf ( "%x\n", ma);
        printf ( "%u\n", ma);
    }
    */
    return 0;
}