1. MD5

MD5是一种消息摘要（message-digest）算法，也常被当作哈希函数，用以产生128位定长的哈希值。既然是哈希函数，那么自然一个很重要的特性就是不可逆。

消息摘要算法，顾名思义，其在密码学中通常用来产生一段消息的摘要信息，可以将此摘要信息看作原文的指纹（fingerprint），人们常说世界上没有两个完全一样的指纹，所以人们自然也希望没有两个不同的原文能产生同样的摘要。

那么计算一个消息的摘要有什么用呢？其实这就类似于计算机网络中常用的 CRC 循环冗余校验，可以用来看数据在传输过程中是否出现了差错，因为一旦出现一丁点差错则消息摘要一定会出现变化，接收方只需要再次用同样的算法再次计算消息摘要即可判断数据是否出错。这其实也可以引申出另一个用途，即判断消息是否被恶意篡改，若被篡改则消息摘要一定会变化，接收方再次计算即可查明。

消息摘要的要求可以简单的归结如下：

• 给定一个消息，应能很容易的求出消息摘要
• 给定消息摘要，应该很难求出原先的消息
• 给定两个不同的消息，求出的摘要应该不同、

这里的用词比较委婉，“应该不同”。既然MD5产生的消息摘要只有128位，那么根据抽屉原理我们知道，假设给定了 $2^{128} + 1$ 个不同的消息，那么必有至少两个消息的摘要会重复，这称为冲突。但显然$\frac{1}{2^{128}}$是一个很小很小的概率了。

但现实是，MD5已经被证实有大量的缺陷，所以已经不会被用在加密问题中了。现在MD5常见的用途是用作校验和来验证数据的完整性，如果文件被修改过则其MD5会出现很大的变化，但即使在这种情况下MD5也只能抵抗非故意的冲突。

2. 算法步骤

首先推荐几个网站，第一个是MD5的wiki页面 https://en.wikipedia.org/wiki/MD5 ，第二个是MD5所在的RFC 1321文档 https://tools.ietf.org/html/rfc1321 ，第三个是将MD5的每一步的计算结果展示的网站 https://cse.unl.edu/~ssamal/crypto/genhash.php ，debug的时候非常好用，可以知道错出在哪一步。

这个博客相对注重具体实现中的一些问题。

2.1 预处理

首先需要对输入的原文进行一定的预处理。预处理分为两步，第一步在原文后面填充一些补位，第二步在补位后面添加64位的消息原长。

填充

填充的目的是让填充后的总长度为512位的倍数减64位。例如，原文为1000位，则要填充472位，因为 1000 + 472 + 64 = 1536 = 512 * 3。

填充的的首位为1，其余位为0。

注意，填充总是要进行，假如原文加64刚好就是512的倍数，则需要512位的填充。

添加长度

填充后面的64位用于放置原文的长度，用位数表示。

所以最终预处理完成后这个待散列消息应该变成下面的样子：

在编程实现的时候预处理这一部分是超级的坑。

首先要处理的是字节序的问题，这里可能有人就要问了，这一部分不是位就是字节哪来的字节序的问题。先预告一下，后面的计算需要把这一串数据分割成32位32位的小块，然后对这些32位的小块做很多加法运算，所以用C语言实现的时候当然需要把这些32位的小块看作unsigned int方便直接相加。既然用了unsigned int就需要考虑计算机小端字节序的问题了。但是这里坑就坑在根本就不用考虑小端字节序！直接把输入的原文一字节一字节拷贝到plain text的位置就可以了。可以想象，假如我的原文是abcd，暂且用0xabcd表示它的十六进制，这里就直接把a拷贝到最低字节，直到d拷贝到最高字节，所以后面把这四字节看成一个unsigned int的时候其实是把0xdcba和其他数据相加而不是0xabcd，这也就可以看做是大端字节序了。这里很多讲解都说的模棱两可，看wiki和文档里面的用词都是什么high-order bit、low order byte，实在是有些搞不清楚。

之后的填充仍然不用考虑什么字节序，把0x80(1000 0000)拷贝到原文的下一个字节就好。

最后64位长度也需要格外的注意，需要把长度的低32位放到低地址的32位处，长度的高32位放到高地址的32位处，并且这里需要用小端字节序存储。

多说无益，下面看一个例子，这是原文abcd经过预处理后在内存中的示意图：

如图，存储原文和填充的时候不需要考虑小端字节序，而原文长度却要按照小端字节序存储。

2.2 将输入分成512位的块

上面的预处理已经得到了长度为512位倍数的待散列消息，接下来只需要将这串消息分为512位512位的块即可。

然后后面的步骤是针对每一个512位的块所做的，也就是后面需要循环处理每一个512位的块，处理的步骤完全一样。

2.3 主循环

下面就是MD5算法的主循环了，也就是最重要的计算部分。

首先把512位块分为16个32位子块，代码实现中直接用一个16个元素的unsigned int数组M[]存储即可。

然后需要四个32位的变量A、B、C、D，并且他们需要分别初始化为0x67452301、0xEFCDAB89、0x98BADCFE、0x10325476。

然后需要创建一个拥有64个元素的常量数组K[]。

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

然后创建一个拥有64个元素的常量数组S[]。

const unsigned int S[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
};

最后需要四个辅助函数F1、F2、F3、F4。

unsigned int F1(unsigned int x, unsigned int y, unsigned int z) {
    return (x & y) | ((~x) & z);
}

unsigned int F2(unsigned int x, unsigned int y, unsigned int z) {
    return (x & z) | (y & (~z));
}

unsigned int F3(unsigned int x, unsigned int y, unsigned int z) {
    return x ^ y ^ z;
}

unsigned int F4(unsigned int x, unsigned int y, unsigned int z) {
    return y ^ (x | (~z));
}

接下来的计算分为4次相似的迭代，每个迭代由16轮相似的计算组成，其中一轮计算可以用下图来表示：

在这一轮计算中，第一步将B、C、D的值当作一个辅助函数F的输入并计算该函数的输出，其中，第一次迭代使用辅助函数F1，第二次迭代使用F2，第三次迭代使用F3，第四次迭代使用F4。

然后，将F函数的输出与A相加。

然后将上一步的结果与上面的数组M[]中的一个元素M[i]相加，其中i的值在四次迭代的共计64轮计算中均不一样，后面将介绍每一轮计算中i的取值。

然后将上一步的结果与上面的常量数组K[]中的一个元素K[j]相加，其中j的值在四次迭代共计64轮计算中从0以此增加到63，也就是每一轮按顺序使用一个K。

之后将上一步的结果循环左移S[z]位，循环左移就是把左边挤掉的位放到最右边。其中z的值在四次迭代共计64轮计算中从0依次增加到63，也就是每一轮按顺序使用一个S。

然后再把上一步的结果与B相加。

最终，将上一步的结果赋值给B，而B原来的值赋值给C，C原来的值赋值给D，D原来的值赋值给A。

这样就完成了一轮计算，下一轮再将新的A、B、C、D当作输入重新计算即可。

实际实现的时候，可以将每一轮的计算稍作修改，不用每一轮的最后都把A、B、C、D的值进行交换，一个优化方案是将这一轮里那一串计算的最终输出不赋值给B而是赋值给A，其他值都不用变。然后下一轮的四个输入分别是D、A、B、C，可以想到结果还是一样的。

在64轮计算完成后其实还需要用到A、B、C、D的初始值，所以编程实现的时候需要将A、B、C、D赋值给四个中间变量a、b、c、d，上面的计算其实改变的都是a、b、c、d的值。

下图展示了64轮计算中M[i]的顺序以及A、B、C、D的取值。

第一次迭代：

第二次迭代：

第三次迭代：

第四次迭代：

最后，进行完64轮计算后，将a、b、c、d的值分别加回A、B、C、D。所有计算完成。如果有下一个512位块则用新的A、B、C、D进行计算。

所有计算做完后，按照小端字节序将A、B、C、D写成十六进制然后拼接起来，就得到了最终的输出。

3. C语言实现

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 预处理函数，输入原文buffer，返回最终的要散列的消息，
// 即经过补位以及加上长度后的消息，长度为512位的倍数
// 输出型参数length返回消息所在数组的大小
unsigned int* preprocess(char* buff, size_t* length) {
    // 根据输入位数计算最终要散列的消息的位数
    // 规则：输入位数 + 补位 + 64 = 512的倍数
    //       必须要有补位，如果不加补位刚好是512的倍数就加512位的补位
    // 所以要补的位数为：512 - (输入位数 + 64) % 512
    // 所以最终要散列的消息的位数为 输入位数 + 补位 + 64
    size_t input_bits = strlen(buff) * 8;
    size_t fills = 512 - (input_bits + 64) % 512;
    size_t total_bits = input_bits + fills + 64;

    unsigned int* message = (unsigned int*)malloc(total_bits / 8);  // 最终要散列的消息共total_bits位，强转成int方便后续计算
    if (message == NULL) {
        perror("malloc error");
        exit(-1);
    }

    // 将这块空间填充为0
    memset(message, 0, total_bits / 8);    

    // 1. 将原文直接复制到这块空间
    memcpy(message, buff, strlen(buff));

    // 2. 填充补位，由于这片空间已经初始化为0了，所以现在只需要在原文后面第一位加一个1
    //    具体就是，将message所在的地址往后 input_bits/8 字节的那个字节的最高位置为1
    *((unsigned char*)message + input_bits / 8) |= 1 << 7;

    // 3. 最后把消息原长填到message的最后64位中，即填入input_bits
    // 若64位无法表示，即原长超过 2^64 位，截取长度的最后64位
    message[total_bits / 32 - 2] += input_bits;  // 将64位的数据加到32位空间内，自动截断高32位数据
    message[total_bits / 32 - 1] += input_bits >> 32;  // 高32位数据加到32位空间内

    *length = total_bits / 32;
    return message;
}

// 四轮用到的四个不同的辅助函数
unsigned int P1(unsigned int x, unsigned int y, unsigned int z) {
    return (x & y) | ((~x) & z);
}

unsigned int P2(unsigned int x, unsigned int y, unsigned int z) {
    return (x & z) | (y & (~z));
}

unsigned int P3(unsigned int x, unsigned int y, unsigned int z) {
    return x ^ y ^ z;
}

unsigned int P4(unsigned int x, unsigned int y, unsigned int z) {
    return y ^ (x | (~z));
}

// 定义辅助函数的函数指针类型，方便回调
typedef unsigned int(*func)(unsigned int, unsigned int, unsigned int);

// 将unsigned int循环左移s位
unsigned int circularly_left_shift(unsigned int x, int s) {
    s %= 32;

    x = x << s | x >> (32 - s);

    return x;
}

// 迭代函数
void iteration(unsigned int* a, unsigned int b, unsigned int c, unsigned int d,
    unsigned int M, unsigned int s, unsigned int t, func P) {
    *a = circularly_left_shift((P(b, c, d) + *a + M + t), s) + b;
}

int main() {
    char buff[1024] = { 0 };
    printf("Please input the message: ");
    gets(buff);

    // 首先将原文进行预处理
    size_t message_len = 0;
    unsigned int* message = preprocess(buff, &message_len);

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

    const unsigned int S[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 A = 0x67452301;
    unsigned int B = 0xEFCDAB89;
    unsigned int C = 0x98BADCFE;
    unsigned int D = 0x10325476;

    // 将message按512位分块，最终会分得 message_len * 32 / 512 个块
    // 后面的工作循环处理每一个512位块，处理的操作相同
    for (int i = 0; i < message_len * 32 / 512; i++) {
        // 处理512位的块
        // 将A,B,C,D复制到4个变量a,b,c,d中
        unsigned int a = A;
        unsigned int b = B;
        unsigned int c = C;
        unsigned int d = D;

        // 将当前的512位块分解为16个子块，可知每个子块位32位，刚好是一个unsigned int
        // 这16个子块分别为：message[i * 16 + 0]、message[i * 16 + 1]、...、message[i * 16 + 15]

        // 此时再进行四轮计算
        iteration(&a, b, c, d, message[i * 16 + 0], S[0], T[0], P1);
        iteration(&d, a, b, c, message[i * 16 + 1], S[1], T[1], P1);
        iteration(&c, d, a, b, message[i * 16 + 2], S[2], T[2], P1);
        iteration(&b, c, d, a, message[i * 16 + 3], S[3], T[3], P1);
        iteration(&a, b, c, d, message[i * 16 + 4], S[4], T[4], P1);
        iteration(&d, a, b, c, message[i * 16 + 5], S[5], T[5], P1);
        iteration(&c, d, a, b, message[i * 16 + 6], S[6], T[6], P1);
        iteration(&b, c, d, a, message[i * 16 + 7], S[7], T[7], P1);
        iteration(&a, b, c, d, message[i * 16 + 8], S[8], T[8], P1);
        iteration(&d, a, b, c, message[i * 16 + 9], S[9], T[9], P1);
        iteration(&c, d, a, b, message[i * 16 + 10], S[10], T[10], P1);
        iteration(&b, c, d, a, message[i * 16 + 11], S[11], T[11], P1);
        iteration(&a, b, c, d, message[i * 16 + 12], S[12], T[12], P1);
        iteration(&d, a, b, c, message[i * 16 + 13], S[13], T[13], P1);
        iteration(&c, d, a, b, message[i * 16 + 14], S[14], T[14], P1);
        iteration(&b, c, d, a, message[i * 16 + 15], S[15], T[15], P1);

        iteration(&a, b, c, d, message[i * 16 + 1], S[16], T[16], P2);
        iteration(&d, a, b, c, message[i * 16 + 6], S[17], T[17], P2);
        iteration(&c, d, a, b, message[i * 16 + 11], S[18], T[18], P2);
        iteration(&b, c, d, a, message[i * 16 + 0], S[19], T[19], P2);
        iteration(&a, b, c, d, message[i * 16 + 5], S[20], T[20], P2);
        iteration(&d, a, b, c, message[i * 16 + 10], S[21], T[21], P2);
        iteration(&c, d, a, b, message[i * 16 + 15], S[22], T[22], P2);
        iteration(&b, c, d, a, message[i * 16 + 4], S[23], T[23], P2);
        iteration(&a, b, c, d, message[i * 16 + 9], S[24], T[24], P2);
        iteration(&d, a, b, c, message[i * 16 + 14], S[25], T[25], P2);
        iteration(&c, d, a, b, message[i * 16 + 3], S[26], T[26], P2);
        iteration(&b, c, d, a, message[i * 16 + 8], S[27], T[27], P2);
        iteration(&a, b, c, d, message[i * 16 + 13], S[28], T[28], P2);
        iteration(&d, a, b, c, message[i * 16 + 2], S[29], T[29], P2);
        iteration(&c, d, a, b, message[i * 16 + 7], S[30], T[30], P2);
        iteration(&b, c, d, a, message[i * 16 + 12], S[31], T[31], P2);

        iteration(&a, b, c, d, message[i * 16 + 5], S[32], T[32], P3);
        iteration(&d, a, b, c, message[i * 16 + 8], S[33], T[33], P3);
        iteration(&c, d, a, b, message[i * 16 + 11], S[34], T[34], P3);
        iteration(&b, c, d, a, message[i * 16 + 14], S[35], T[35], P3);
        iteration(&a, b, c, d, message[i * 16 + 1], S[36], T[36], P3);
        iteration(&d, a, b, c, message[i * 16 + 4], S[37], T[37], P3);
        iteration(&c, d, a, b, message[i * 16 + 7], S[38], T[38], P3);
        iteration(&b, c, d, a, message[i * 16 + 10], S[39], T[39], P3);
        iteration(&a, b, c, d, message[i * 16 + 13], S[40], T[40], P3);
        iteration(&d, a, b, c, message[i * 16 + 0], S[41], T[41], P3);
        iteration(&c, d, a, b, message[i * 16 + 3], S[42], T[42], P3);
        iteration(&b, c, d, a, message[i * 16 + 6], S[43], T[43], P3);
        iteration(&a, b, c, d, message[i * 16 + 9], S[44], T[44], P3);
        iteration(&d, a, b, c, message[i * 16 + 12], S[45], T[45], P3);
        iteration(&c, d, a, b, message[i * 16 + 15], S[46], T[46], P3);
        iteration(&b, c, d, a, message[i * 16 + 2], S[47], T[47], P3);

        iteration(&a, b, c, d, message[i * 16 + 0], S[48], T[48], P4);
        iteration(&d, a, b, c, message[i * 16 + 7], S[49], T[49], P4);
        iteration(&c, d, a, b, message[i * 16 + 14], S[50], T[50], P4);
        iteration(&b, c, d, a, message[i * 16 + 5], S[51], T[51], P4);
        iteration(&a, b, c, d, message[i * 16 + 12], S[52], T[52], P4);
        iteration(&d, a, b, c, message[i * 16 + 3], S[53], T[53], P4);
        iteration(&c, d, a, b, message[i * 16 + 10], S[54], T[54], P4);
        iteration(&b, c, d, a, message[i * 16 + 1], S[55], T[55], P4);
        iteration(&a, b, c, d, message[i * 16 + 8], S[56], T[56], P4);
        iteration(&d, a, b, c, message[i * 16 + 15], S[57], T[57], P4);
        iteration(&c, d, a, b, message[i * 16 + 6], S[58], T[58], P4);
        iteration(&b, c, d, a, message[i * 16 + 13], S[59], T[59], P4);
        iteration(&a, b, c, d, message[i * 16 + 4], S[60], T[60], P4);
        iteration(&d, a, b, c, message[i * 16 + 11], S[61], T[61], P4);
        iteration(&c, d, a, b, message[i * 16 + 2], S[62], T[62], P4);
        iteration(&b, c, d, a, message[i * 16 + 9], S[63], T[63], P4);

        // 将此时的a,b,c,d加回A,B,C,D
        A += a;
        B += b;
        C += c;
        D += d;
    }

    printf("md5: ");
    unsigned char* tmp = (unsigned char*)& A;
    printf("%2.2x%2.2x%2.2x%2.2x", tmp[0], tmp[1], tmp[2], tmp[3]);

    tmp = (unsigned char*)& B;
    printf("%2.2x%2.2x%2.2x%2.2x", tmp[0], tmp[1], tmp[2], tmp[3]);

    tmp = (unsigned char*)& C;
    printf("%2.2x%2.2x%2.2x%2.2x", tmp[0], tmp[1], tmp[2], tmp[3]);

    tmp = (unsigned char*)& D;
    printf("%2.2x%2.2x%2.2x%2.2x\n", tmp[0], tmp[1], tmp[2], tmp[3]);

    free(message);

    return 0;
}

最后验证一下结果：