1. MD5

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

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

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

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

这里的用词比较委婉,“应该不同”。既然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位的变量ABCD,并且他们需要分别初始化为0x674523010xEFCDAB890x98BADCFE0x10325476

然后需要创建一个拥有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
};

最后需要四个辅助函数F1F2F3F4

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轮相似的计算组成,其中一轮计算可以用下图来表示:

在这一轮计算中,第一步将BCD的值当作一个辅助函数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原来的值赋值给CC原来的值赋值给DD原来的值赋值给A

这样就完成了一轮计算,下一轮再将新的ABCD当作输入重新计算即可。

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

在64轮计算完成后其实还需要用到ABCD的初始值,所以编程实现的时候需要将ABCD赋值给四个中间变量abcd,上面的计算其实改变的都是abcd的值。

下图展示了64轮计算中M[i]的顺序以及ABCD的取值。

第一次迭代:

轮次 a b c d M
1 a b c d M[0]
2 d a b c M[1]
3 c d a b M[2]
4 b c d a M[3]
5 a b c d M[4]
6 d a b c M[5]
7 c d a b M[6]
8 b c d a M[7]
9 a b c d M[8]
10 d a b c M[9]
11 c d a b M[10]
12 b c d a M[11]
13 a b c d M[12]
14 d a b c M[13]
15 c d a b M[14]
16 b c d a M[15]

第二次迭代:

轮次 a b c d M
1 a b c d M[1]
2 d a b c M[6]
3 c d a b M[11]
4 b c d a M[0]
5 a b c d M[5]
6 d a b c M[10]
7 c d a b M[15]
8 b c d a M[4]
9 a b c d M[9]
10 d a b c M[14]
11 c d a b M[3]
12 b c d a M[8]
13 a b c d M[13]
14 d a b c M[2]
15 c d a b M[7]
16 b c d a M[2]

第三次迭代:

轮次 a b c d M
1 a b c d M[5]
2 d a b c M[8]
3 c d a b M[11]
4 b c d a M[14]
5 a b c d M[1]
6 d a b c M[4]
7 c d a b M[7]
8 b c d a M[10]
9 a b c d M[13]
10 d a b c M[0]
11 c d a b M[3]
12 b c d a M[6]
13 a b c d M[9]
14 d a b c M[12]
15 c d a b M[15]
16 b c d a M[2]

第四次迭代:

轮次 a b c d M
1 a b c d M[0]
2 d a b c M[7]
3 c d a b M[14]
4 b c d a M[5]
5 a b c d M[12]
6 d a b c M[3]
7 c d a b M[10]
8 b c d a M[1]
9 a b c d M[8]
10 d a b c M[15]
11 c d a b M[6]
12 b c d a M[13]
13 a b c d M[4]
14 d a b c M[11]
15 c d a b M[2]
16 b c d a M[9]

最后,进行完64轮计算后,将abcd的值分别加回ABCD。所有计算完成。如果有下一个512位块则用新的ABCD进行计算。

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

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;
}

最后验证一下结果:

Last modification:December 9th, 2019 at 09:24 pm