MD5算法笔记

MD5(x) = y

x长度不限，y长度为128bit。
目的是对于不同的x，经运算后尽量得到不同的y。
可见MD5是一种杂凑算法。

md5算法中有四个“魔数”：0x01234567, 0x89ABCDEF, 0xFEDCBA98, 0x76543210.
    unsigned int h[4] = {0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476};
( -- 文中unsigned int皆为32bit)

两个数组：

unsigned int r[64] =
    {
        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
    };

unsigned int k[64];

k[64]中每一项分别是：sin(1、2、3、。。。、64)取绝对值，然后在其值的2进制形式、把小数点右移32位，换言之此值乘以2的32次方。

for (i = 0; i < 64; i++)
    k[i] = (unsigned int)( abs(sin((double)i + 1)) * pow((double)2,32) );

MD5算法取源数据的512bit为一个基本运算单元，相当于把源数据划分为512bit的块，然后在末尾添加源数据的长度(单位为bit)，长度数据占64bit，以little-endian方式添加到数据末尾。
可见未添加长度信息的结尾块有以下下三种可能：
1.结尾块长度等于448bit，加上64bit数据长度，刚好是完整的一块。
2.结尾块长度小于448bit，那么数据尾添加1bit'1'，若干bit'0'，最终使加上64bit长度组成512bit完整块。
3.结尾块长度大于448bit，那么数据尾添加1bit'1'，若干bit'0'，使得此结尾块完整，并且再多出一块，添加64bit长度构成512bit完整块。
然后进行运算：

#define CROL(value, bits) ( (value) << bits | (value) >> (32 - bits) )  // 循环左移

unsigned int a = h[0];
unsigned int b = h[1];
unsigned int c = h[2];
unsigned int d = h[3];

unsigned int i, j, t, temp;
unsigned __int64 x;

x = SizeInBit / 512;  // SizeInBit为末尾补齐后数据的长度，x则为数据分块数

for (psh = (unsigned int*)p; x--; psh += 16)  // p指向源数据(已经过末尾补齐)，psh是临时unsigned int指针，psh += 16 则指向下一个512bit块：
    {
        for (i = 0; i < 64; i++)
        {
            if (0 <= i && i <= 15)
            {
                t = (b & c) | ((~b) & d);
                j = i;
            }
            else if (16 <= i && i <= 31)
            {
                t = (d & b) | ((~d) & c);
                j = (5*i + 1) % 16;
            }
            else if (32 <= i && i <= 47)
            {
                t = b ^ c ^ d;
                j = (3*i + 5) % 16;
            }
            else if (48 <= i && i <= 63)
            {
                t = c ^ (b | (~d));
                j = (7*i) % 16;
            }

            temp = d;
            d = c;
            c = b;
            b = CROL(a + t + k[i] + *(psh+j), r[i]) + b;
            a = temp;
        }

        //Add this chunk's hash to result so far:
        h[0] += a;
        h[1] += b;
        h[2] += c;
        h[3] += d;
    }

运算完成后，h[0]h[1]h[2]h[3]组成MD5值.

[课程]Android-CTF解题方法汇总！