MD5 算法实现

MD5 算法是一种已经被证明不安全的消息摘要算法，其规范在 RFC 1321。

在 GNU/Linux 系统中，命令 md5sum 可以完成校验文件或输入字符串的工作，该命令包含在 GNU core utilities 命令集合中，MD5 算法的核心代码在 gnulib 中可以找到。

实现 MD5 算法的代码并不复杂，动手实践一遍可以提高动手能力。本文依照规范，尝试实现简单字符串的消息摘要计算。

概述

MD5 消息摘要算法接收一段任意长度的输入，输出一个 128 位的“指纹”或“消息摘要”。

一般认为，两段不同的消息不太可能会有一样的消息摘要。同时，也不容易在确定一个目标消息摘要后生成一段会得到这个消息摘要的消息。MD5 算法一般用于数字签名程序，这些程序需要在安全地“压缩”一个大文件后再执行公私钥体系的加密。

MD5 算法是 MD4 消息摘要算法的扩展。由于 MD5 算法采用了一个更加可靠的设计，所以运行速度会比 MD4 算法稍慢。

术语

本文中，“字”是 32 位长度，“字节”是 8 位长度。接收到以“位”组成的消息序列时，可以按照大端字节序规则来将每 8 个位组合成一个字节，同样也可以按小端字节序规则将每 8 个位组成一个字节。

MD5 算法描述

假设有一个 b 位长度的消息 m 作为输入，算法计算这段消息的摘要。

b 可以是任意非负整数，可以是很大的数。
b 可以是 0。
b 不一定能被 8 整除。

那么消息可以写作：

m_0 m_1 ... m_{b-1}

第一步：填充消息到特定长度

将消息填充至其位长度能够在被 512 取模时余 448。即使消息长度刚好被 512 整除余 448 也需要做一次填充。

填充规则：

向消息追加一位 1。
继续追加若干位 0，直到消息长度能被 512 取模余 448。

按此规则，消息至少填充 1 位，最多填充 512 位。

第二步：填充消息本身长度

向上一步填充完成后的消息后填充一个 64 位整数——以 64 位表示的消息长度 b（以位记）。如果消息长度大于 64 位，只取消息长度的低 64 位。附加这个整数时，低有效位在前，即以小端字节序规则，按字节附加。

前两步的 C 语言实现如下。注意：代码中假定处理的消息为字符串，所以处理消息长度时按字节长度处理，但注释中以位说明。

int caculate_padding_length(size_t message_length)
{
    // 512 bits = 64 bytes
    int mod = message_length % 64; //长度对 512 取模
    int padding_bytes = 0;         // 要填充的字节数
    // 448 bits = 56 bytes
    // 余数与 448 比较
    if (mod >= 56)
    {
        // 余数大于 448 时，先补长度到刚好能被 512 整除的长度，再补 448 位
        padding_bytes = 64 - mod + 56;
    }
    else
    {
        padding_bytes = 56 - mod;
    }
    //填充 64 位长度的整数
    padding_bytes += 8;
    return padding_bytes;
}
unsigned char *append_bytes(size_t message_length)
{
    int padding_length = caculate_padding_length(message_length);
    unsigned char *text = NULL; //填充在消息后的字符串
    text = (unsigned char *)malloc(sizeof(unsigned char) * padding_length);
    if (text != NULL)
    {
        memset(text, 0, padding_length);
        int i;
        //第一步填充
        for (i = 0; i < padding_length - 8; i++)
        {
            if (i == 0)
            {
                // 填充的第一个字节为 1000 0000，第一位是1，后面附加 0
                text[i] = 0x80;
            }
            else
            {
                text[i] = 0x00;
            }
        }
        //第二步填充
        size_t message_length_bits = message_length * 8;
        memcpy(text + i, (unsigned char *)(&message_length_bits), 8);
    }
    return text;
}

第三步：消息分块

完成两步填充后，消息长度将刚好能被 512 整除。即能以每块 16 个字（ 16个 32 位整数）的方式，分成整数块，记每块消息为 X[1...16]。

第四步：定义“魔数”与计算函数

消息摘要变量

准备 4 个 32 位无符号整数，计算从这 4 个数字将参与消息摘要的计算并存储摘要计算的中间值。计算完成后，4 个变量组成最后的摘要。

4 个数字记为 A、B、C、D，规定其在内存中其值（16 进制）分别是 A = 01234567，B = 89abcdef，C = fedcba98，D = 76543210，编码时需要转换成小端字节序。
```
 __uint32_t A = 0x67452301, B = 0xefcdab89, C = 0x98badcfe, D = 0x10325476;
```

定义“魔数”表

定义一个长为 64 的表 T[1 ... 64]，T[i] 表示表中第 i 个元素，表中元素将参与消息摘要的计算。T[i] 的值为弧度 i 的正弦值的绝对值与 429496726 乘积的整数部分。其值可以用下面的代码计算得到。

  for (size_t i = 1; i <= 64; i++)
  {
     __uint32_t t = fabs(sin(i) * 0x100000000UL);
     printf("0x%08x,\n", t);
  }

计算后，将表数据作为常量数组。

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

定义移位表

下一步计算消息摘要过程中，会使用循环左移运算，循环左移的位数在这里定义。每一轮消息摘要计算分为 4 组，故左移数组分为 4 组；每组计算 16 次，在第 i 组计算时，选择左移数组中第 i 行中的 4 个值循环使用 4 遍。
```
const __uint32_t S[4][4] = {
    {7, 12, 17, 22}, {5, 9, 14, 20}, {4, 11, 16, 23}, {6, 10, 15, 21}};
```

定义消息计算函数

定义 4 个位运算函数，F、G、H、I，每个函数接收 3 个 32 位整数。实际计算时函数实参为消息摘要中间值中的 3 个。

F(X,Y,Z) = (X & Y) | ((~X) & Z)
G(X,Y,Z) = (X & Z) | (Y & (~Z))
H(X,Y,Z) = X ^ Y ^ Z
I(X,Y,Z) = Y ^ (X | (~Z))

C 语言实现如下。

__uint32_t F(__uint32_t X, __uint32_t Y, __uint32_t Z)
{
    return (X & Y) | ((~X) & Z);
}
__uint32_t G(__uint32_t X, __uint32_t Y, __uint32_t Z)
{
    return (X & Z) | (Y & (~Z));
}
__uint32_t H(__uint32_t X, __uint32_t Y, __uint32_t Z) 
{
    return X ^ Y ^ Z; 
}
__uint32_t I(__uint32_t X, __uint32_t Y, __uint32_t Z)
{
    return Y ^ (X | (~Z));
}

定义 4 个消息计算函数，FF、GG、HH、II，每个函数接收 7 个 32 位无符号整数作为输入，前 4 个为消息摘要中间值，第 5 个是某一组消息块中的一个 32 位无符号整数，第 6 个是循环左移位数，第 7 个参数来自“魔数”表中的一个值。

FF(a, b, c, d, k, i, s)：
	a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s)
GG(a, b, c, d, k, i, s):
	a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s)
HH(a, b, c, d, k, i, s):
	a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s)
II(a, b, c, d, k, i, s):
	a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s)

X <<< s：循环左移，表示 X 向左移动 s 位，移出的 s 位填补到右侧。

C 语言实现如下。

__uint32_t Rotate_Left(__uint32_t x, __uint32_t n) {
  return (x << n) | (x >> (32 - n));
}
__uint32_t FF(__uint32_t a, __uint32_t b, __uint32_t c, __uint32_t d,
              __uint32_t x, __uint32_t s, __uint32_t ac) {
  a += F(b, c, d) + x + ac;
  a = Rotate_Left(a, s);
  a += b;
  return a;
}
__uint32_t GG(__uint32_t a, __uint32_t b, __uint32_t c, __uint32_t d,
              __uint32_t x, __uint32_t s, __uint32_t ac) {
  a += G(b, c, d) + x + ac;
  a = Rotate_Left(a, s);
  a += b;
  return a;
}
__uint32_t HH(__uint32_t a, __uint32_t b, __uint32_t c, __uint32_t d,
              __uint32_t x, __uint32_t s, __uint32_t ac) {
  a += H(b, c, d) + x + ac;
  a = Rotate_Left(a, s);
  a += b;
  return a;
}
__uint32_t II(__uint32_t a, __uint32_t b, __uint32_t c, __uint32_t d,
              __uint32_t x, __uint32_t s, __uint32_t ac) {
  a += I(b, c, d) + x + ac;
  a = Rotate_Left(a, s);
  a += b;
  return a;
}

第五步：循环处理消息块

遍历第三步得到的消息块。

对块内的数组进行如下 4 组计算，共 64 次计算。

备份 A、B、C、D 为 AA、BB、CC、DD。备份完成后，A、B、C、D 加入到计算中。

第一组计算

FF (A, B, C, D, X[ 0], S[0][0], T[ 0]) 
FF (D, A, B, C, X[ 1], S[0][1], T[ 1]) 
FF (C, D, A, B, X[ 2], S[0][2], T[ 2]) 
FF (B, C, D, A, X[ 3], S[0][3], T[ 3]) 
FF (A, B, C, D, X[ 4], S[0][0], T[ 4]) 
FF (D, A, B, C, X[ 5], S[0][1], T[ 5]) 
FF (C, D, A, B, X[ 6], S[0][2], T[ 6]) 
FF (B, C, D, A, X[ 7], S[0][3], T[ 7]) 
FF (A, B, C, D, X[ 8], S[0][0], T[ 8]) 
FF (D, A, B, C, X[ 9], S[0][1], T[ 9]) 
FF (C, D, A, B, X[10], S[0][2], T[10])
FF (B, C, D, A, X[11], S[0][3], T[11])
FF (A, B, C, D, X[12], S[0][0], T[12])
FF (D, A, B, C, X[13], S[0][1], T[13])
FF (C, D, A, B, X[14], S[0][2], T[14])
FF (B, C, D, A, X[15], S[0][3], T[15])

第二组计算

GG (A, B, C, D, X[ 1], S[1][0], T[16])
GG (D, A, B, C, X[ 6], S[1][1], T[17])
GG (C, D, A, B, X[11], S[1][2], T[18])
GG (B, C, D, A, X[ 0], S[1][3], T[19])
GG (A, B, C, D, X[ 5], S[1][0], T[20])
GG (D, A, B, C, X[10], S[1][1], T[21])
GG (C, D, A, B, X[15], S[1][2], T[22])
GG (B, C, D, A, X[ 4], S[1][3], T[23])
GG (A, B, C, D, X[ 9], S[1][0], T[24])
GG (D, A, B, C, X[14], S[1][1], T[25])
GG (C, D, A, B, X[ 3], S[1][2], T[26])
GG (B, C, D, A, X[ 8], S[1][3], T[27])
GG (A, B, C, D, X[13], S[1][0], T[28])
GG (D, A, B, C, X[ 2], S[1][1], T[29])
GG (C, D, A, B, X[ 7], S[1][2], T[30])
GG (B, C, D, A, X[12], S[1][3], T[31])

第三组计算

HH (A, B, C, D, X[ 5], S[2][0], T[32])
HH (D, A, B, C, X[ 8], S[2][1], T[33])
HH (C, D, A, B, X[11], S[2][2], T[34])
HH (B, C, D, A, X[14], S[2][3], T[35])
HH (A, B, C, D, X[ 1], S[2][0], T[36])
HH (D, A, B, C, X[ 4], S[2][1], T[37])
HH (C, D, A, B, X[ 7], S[2][2], T[38])
HH (B, C, D, A, X[10], S[2][3], T[39])
HH (A, B, C, D, X[13], S[2][0], T[40])
HH (D, A, B, C, X[ 0], S[2][1], T[41])
HH (C, D, A, B, X[ 3], S[2][2], T[42])
HH (B, C, D, A, X[ 6], S[2][3], T[43])
HH (A, B, C, D, X[ 9], S[2][0], T[44])
HH (D, A, B, C, X[12], S[2][1], T[45])
HH (C, D, A, B, X[15], S[2][2], T[46])
HH (B, C, D, A, X[ 2], S[2][3], T[47])

第四组计算

II (A, B, C, D, X[ 0], S[3][0], T[48])
II (D, A, B, C, X[ 7], S[3][1], T[49])
II (C, D, A, B, X[14], S[3][2], T[50])
II (B, C, D, A, X[ 5], S[3][3], T[51])
II (A, B, C, D, X[12], S[3][0], T[52])
II (D, A, B, C, X[ 3], S[3][1], T[53])
II (C, D, A, B, X[10], S[3][2], T[54])
II (B, C, D, A, X[ 1], S[3][3], T[55])
II (A, B, C, D, X[ 8], S[3][0], T[56])
II (D, A, B, C, X[15], S[3][1], T[57])
II (C, D, A, B, X[ 6], S[3][2], T[58])
II (B, C, D, A, X[13], S[3][3], T[59])
II (A, B, C, D, X[ 4], S[3][0], T[60])
II (D, A, B, C, X[11], S[3][1], T[61])
II (C, D, A, B, X[ 2], S[3][2], T[62])
II (B, C, D, A, X[ 9], S[3][3], T[63])

64 次计算后得到 A，B，C，D 的值分别累加到 AA，BB，CC，DD上。

重复1、2 直到所有消息块都参与过计算。

这一步的 C 语言实现如下。为减少代码篇幅，代码中使用了循环，循环中计算下标。

void loop_compute(__uint32_t *AA, __uint32_t *BB, __uint32_t *CC, __uint32_t *DD, unsigned char *padded_message, size_t block)
{
    //将A B C D变量保存一份
    __uint32_t A = *AA, B = *BB, C = *CC, D = *DD;
    __uint32_t *message = (__uint32_t *)padded_message + 16 * block;
    int round = 0;
    for (size_t i = 0; i < 4; i++)
    {
        A = FF(A, B, C, D, message[4 * i + 0], S[round][0], T[round * 16 + 4 * i + 0]);
        D = FF(D, A, B, C, message[4 * i + 1], S[round][1], T[round * 16 + 4 * i + 1]);
        C = FF(C, D, A, B, message[4 * i + 2], S[round][2], T[round * 16 + 4 * i + 2]);
        B = FF(B, C, D, A, message[4 * i + 3], S[round][3], T[round * 16 + 4 * i + 3]);
    }
    round++;
    for (size_t i = 0; i < 4; i++)
    {
        A = GG(A, B, C, D, message[(1 + (4 * i + 0) * 5) % 16], S[round][0], T[round * 16 + 4 * i + 0]);
        D = GG(D, A, B, C, message[(1 + (4 * i + 1) * 5) % 16], S[round][1], T[round * 16 + 4 * i + 1]);
        C = GG(C, D, A, B, message[(1 + (4 * i + 2) * 5) % 16], S[round][2], T[round * 16 + 4 * i + 2]);
        B = GG(B, C, D, A, message[(1 + (4 * i + 3) * 5) % 16], S[round][3], T[round * 16 + 4 * i + 3]);
    }
    round++;
    for (size_t i = 0; i < 4; i++)
    {
        A = HH(A, B, C, D, message[(5 + (4 * i + 0) * 3) % 16], S[round][0], T[round * 16 + 4 * i + 0]);
        D = HH(D, A, B, C, message[(5 + (4 * i + 1) * 3) % 16], S[round][1], T[round * 16 + 4 * i + 1]);
        C = HH(C, D, A, B, message[(5 + (4 * i + 2) * 3) % 16], S[round][2], T[round * 16 + 4 * i + 2]);
        B = HH(B, C, D, A, message[(5 + (4 * i + 3) * 3) % 16], S[round][3], T[round * 16 + 4 * i + 3]);
    }
    round++;
    for (size_t i = 0; i < 4; i++)
    {
        A = II(A, B, C, D, message[((4 * i + 0) * 7) % 16], S[round][0], T[round * 16 + 4 * i + 0]);
        D = II(D, A, B, C, message[((4 * i + 1) * 7) % 16], S[round][1], T[round * 16 + 4 * i + 1]);
        C = II(C, D, A, B, message[((4 * i + 2) * 7) % 16], S[round][2], T[round * 16 + 4 * i + 2]);
        B = II(B, C, D, A, message[((4 * i + 3) * 7) % 16], S[round][3], T[round * 16 + 4 * i + 3]);
    }
   
    *AA = *AA + A;
    *BB = *BB + B;
    *CC = *CC + C;
    *DD = *DD + D;
}
   
void process(size_t totoal_length, unsigned char *padded_message, __uint32_t *A, __uint32_t *B, __uint32_t *C, __uint32_t *D)
{
    size_t groups = totoal_length / 64;
    for (size_t i = 0; i < groups; i++)
    {
        loop_compute(A, B, C, D, padded_message, i);
    }
}

第六步处理结果

将上一步更新后的 A、B、C、D 四个无符号整数按照无符号字符类型组合后输出。

void output(__uint32_t *A, __uint32_t *B, __uint32_t *C, __uint32_t *D)
{
    unsigned char *digest = malloc(sizeof(char) * 16);
    if (digest != NULL)
    {
        memcpy(digest + 0, A, 4);
        memcpy(digest + 4, B, 4);
        memcpy(digest + 8, C, 4);
        memcpy(digest + 12, D, 4);
        printf("md5 digest:\n");
        for (size_t i = 0; i < 16; i++)
        {
            printf("%02X", digest[i]);
        }
        printf("\n");
        free(digest);
    }
}

主函数如下。

int main(int argc, const char *argv[])
{
    const char *message;
    unsigned char *padding_bytes;
    unsigned char *padded_message;
    if (argc >= 2)
    {
        message = argv[1];
    }
    else
    {
        message = "abc";
    }
    size_t message_len = strlen(message);
    u_int32_t A = 0x67452301, B = 0xefcdab89, C = 0x98badcfe, D = 0x10325476;
    int padding_len = caculate_padding_length(message_len);
    padding_bytes = append_bytes(message_len);
    if (padding_bytes != NULL)
    {
        padded_message = concat_string(message, message_len, padding_bytes, padding_len);
        if (padded_message != NULL)
        {
            process(message_len + padding_len, padded_message, &A, &B, &C, &D);
            output(&A, &B, &C, &D);
            free(padded_message);
        }
        free(padding_bytes);
    }
    return 0;
}

测试用例

程序编译后接收 1 个字符串参数作为输入，计算该输入字符串的 MD5 值。下面给出几个用例，结果相同时算法实现正确。

a：0CC175B9C0F1B6A831C399E269772661
abc：900150983CD24FB0D6963F7D28E17F72
abcdefghijklmnopqrstuvwxyz：C3FCD3D76192E4007DFB496CCA67E13B
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789：D174AB98D277D9F5A5611C2C9F419D9F
12345678901234567890123456789012345678901234567890123456789012345678901234567890：57EDF4A22BE3C955AC49DA2E2107B67A

总结

上面的实现可以计算简单字符串的 MD5 摘要值。以此为基础，你可以编写可以计算文件 MD5 摘要的程序，看看和系统中的 md5sum 命令效率孰高孰低。

在计算摘要的过程中，消息的每一位都参与了计算，消息原文的任何一位发生更改消息摘要都会完全不一样。消息计算函数在每一步计算时不仅需要“魔数”和消息值作为参数，还需要上一步计算的结果，这使得计算不可逆，这个特点可用于校验消息的一致性。

现在已经能够轻易构造一个与原消息不同的碰撞消息使得原消息与碰撞消息的 MD5 消息摘要一致，在对安全性要求较高的场景下应当使用 SHA512 或更强的消息摘要算法。

概述

术语