有限集内 MD5/SHA1 可逆吗—— MD5、SHA1 算法

今天讲一讲 hash 算法。

hash 算法不可逆，大家都知道，因为这是一个一对多的问题，一个 MD5/SHA1 值理论上是可以对应多个原始数据的，所以 MD5/SHA1 是无法还原出原始信息的。

但是，如果我指定范围，你能通过 MD5/SHA1 倒推出原始数据吗？

举个例子：定义一个 hash 算法，取值在 255 下的模，这样的 hash 值也是不能直接反推数据的，但是如果我说我数据就是在 1 ～ 255 之间的值，那我给定一个 hash 值，无疑你是能得到原始数据的。

但是 MD5/SHA1 呢？

这里容我先卖个关子，今天主要是先介绍 MD5/SHA1 算法，最后我们会讨论这个问题。

散列算法

在了解 MD5、SHA1 之前，我们先了解一下什么是散列算法。

散列算法，或者叫哈希函数，主要是一种通过计算得出数据特征值的算法，算法主要是在字典结构中使用，通过哈希算法算得数据的哈希值可以快速查找数据是否存在或者提取数据。

后来人们发现，这些特征值其实也是数据的一种特有性质或者属性，而且当你的算法比较完备的时候，不同数据的特征值几乎不可能存在重复的，就跟人的指纹一样，指纹可能会有相似的，但是指纹到目前为止还可以作为重要的断案依据。所以，为什么不使用散列算法为这些数据建立特征值呢？于是便诞生了安全领域的散列算法，又叫做安全散列算法。

安全领域的散列算法主要就是通过一些比较快的处理方式，可以快速计算出数据的哈希值，然后使用该值进行数据确认，安全传输确认等工作。

举个简单的例子：一个用户在某个网站下载了一个软件的安装镜像文件，他为了确认这个软件的安装程序是否是真的安装镜像，防止是伪造的病毒或者特洛伊木马，他就可以去访问软件官网确认一下安装包的镜像 MD5 值是多少，然后跟下载回来的镜像 MD5 值做比对（大部分软件巨头的软件都提供他们的镜像 MD5 校验），如果 MD5 值不同就说明被动过手脚。如果还不放心他可以继续比对二者的 SHA1、SHA-256 之类的哈希值。

安全的散列算法现在已经广泛应用于安全登录、安全认证、安全访问等领域，它与加密算法不同，只提供数据特征值，过程单向，大部分情况推出原始数据是不可能的……好像绕回来了。总之先不管这些，散列算法大部分都是不可逆的。

但是它跟加密算法又有千丝万缕的联系，有些甚至是加密算法的一个子集，通过加密算法修改几个步骤、添加一些输出它就摇身一变变成了散列算法。

所以我苦苦追查了好久 MD5/SHA1 的历史由来，到底是怎么发展来的，换一种说法是当时是从什么加密算法变种设计而来的，很遗憾的是算法的真正发展历史已经不可考，只知道 MD5 经历过 MD2→MD3→MD4→MD5 几个阶段，SHA1 则是在 MD5 的基础上修改而来，其他的信息少的可怜，已经不知道发明这算法的人当初是怎么把它们设计出来的了……

当下流行的安全领域散列算法主要是两个派系：MD2/3/4/5 系列和 SHA 系列，接下来主要介绍两者的主要代表：MD5 和 SHA1。

MD5 算法

如上面所说 MD5 算法经历了怎样的设计目前已经不可考，所以下面直接说明 MD5 的算法流程：

MD5 首先定义了如下几个函数：

1
2
3
4
5
6
7
8
9
int32_t F(a, b, c) { return (a & b) | ((~a) & c); }
int32_t G(a, b, c) { return (a & c) | (b & (~c)); }
int32_t H(a, b, c) { return a ^ b ^ c; }
int32_t I(a, b, c) { return b ^ (a | (~c)); }

& 按位与
| 按位或
^ 按位异或
~ 取补码

由这四个函数延伸出如下几个函数：

1
2
3
4
5
6
void FF(a, b, c, d, M, s, t) { a = b + (a + F(b, c, d) + M + t) << s; }
void GG(a, b, c, d, M, s, t) { a = b + (a + G(b, c, d) + M + t) << s; }
void HH(a, b, c, d, M, s, t) { a = b + (a + H(b, c, d) + M + t) << s; }
void II(a, b, c, d, M, s, t) { a = b + (a + I(b, c, d) + M + t) << s; }

<< 循环左移，举例：0x01001100 << 5 = 0x10001001

MD5 在开始处理数据之前会先对数据进行补齐，使数据变成 N * 512 + 448 bits 的形式。如果数据原始长度在 512 上的模刚好是 448 也需要补齐，补齐方法是在原始数据后面跟上一位1和若干个 0，举例： 

1
2
3
4
5
6
7
原始数据：0x7AD2 
二进制：0x01111011 11010010
原数据长度：16 bits
需补齐长度：448 - 16 = 432

补齐之后：0x7AD28000 0x00000000 ...省略12个0x00000000
二进制：0x01111011 11010010 10000000 00000000 ...省略416个0

算法的初始状态 MD5 定义了四个幻数：

1
2
3
4
A = 0x01234567
B = 0x89ABCDEF
C = 0xFEDCBA98
D = 0x76543210

幻数以小端字节序存储（内存地址由低到高）
而编程中我们的变量存储方式是大端字节序（内存地址从高到低）
所以编程时我们定义的幻数应该是：

1
2
3
4
A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476

数据处理按照块进行，每块大小为512 bits（64 bytes）。
这里你会发现如果按照刚刚的补齐，数据原始长度在 512 的模不是 0，缺少的 64 bits 怎么办？这里并不是 MD5 把这 64 bits 忘记了，而是定义了他们的特殊作用。MD5 最后 64 bits 的作用是存储原始数据长度，长度也是以小端字节序存储。
最后 64 bits 处理举例：

1
2
3
4
5
6
7
8
原始数据为字符串“abc”，长度为 24 bits（3 bytes）
最后 64 bits 为：0x18000000 00000000

原始数据为 264 bits（33 bytes）
最后 64 bits 为：0x08010000 00000000

原始数据长度超过 64 bits 可存储的大小，取其低 64 位。
换一种说法就是按照长度的小端字节序存储，存满为止。

数据和初始幻数定义完毕之后，下面就是对数据的处理。
MD5 对每块数据做 4 轮处理，每轮进行 16 次运算，每轮都将数据分为 16 个分组，每组 32 bits（4 bytes），每块数据处理开始时继承上一轮处理完毕之后的 A、B、C、D 作为初始值，最开始的一块数据使用的就是 4 个初始幻数。
假设 M[j] 表示第 i 个分组的数据，每轮的操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 第一轮
for (i = 0; i < 16; i++) {
    switch (i % 4) {
        case 0:
            FF(A, B, C, D, M[i], 7, t[i]);
            break;
        case 1:
            FF(D, A, B, C, M[i], 12, t[i]);
            break;
        case 2:
            FF(C, D, A, B, M[i], 17, t[i]);
            break;
        case 3:
            FF(B, C, D, A, M[i], 22, t[i]);
            break;
    }
}
// 第二轮
for (i = 0; i < 16; i++) {
    switch (i % 4) {
        case 0:
            GG(A, B, C, D, M[i * 5 + 1] % 16, 5, t[i + 16]);
            break;
        case 1:
            GG(D, A, B, C, M[i * 5 + 1] % 16, 9, t[i + 16]);
            break;
        case 2:
            GG(C, D, A, B, M[i * 5 + 1] % 16, 14, t[i + 16]);
            break;
        case 3:
            GG(B, C, D, A, M[i * 5 + 1] % 16, 20, t[i + 16]);
            break;
    }
}
// 第三轮
for (i = 0; i < 16; i++) {
    switch (i % 4) {
        case 0:
            HH(A, B, C, D, M[(i * 3 + 5) % 16], 4, t[i + 32]);
            break;
        case 1:
            HH(D, A, B, C, M[(i * 3 + 5) % 16], 11, t[i + 32]);
            break;
        case 2:
            HH(C, D, A, B, M[(i * 3 + 5) % 16], 16, t[i + 32]);
            break;
        case 3:
            HH(B, C, D, A, M[(i * 3 + 5) % 16], 23, t[i + 32]);
            break;
    }
}
// 第四轮
for (i = 0; i < 16; i++) {
    switch (i % 4) {
        case 0:
            II(A, B, C, D, M[i * 7 % 16], 6, t[i + 48]);
            break;
        case 1:
            II(D, A, B, C, M[i * 7 % 16], 10, t[i + 48]);
            break;
        case 2:
            II(C, D, A, B, M[i * 7 % 16], 15, t[i + 48]);
            break;
        case 3:
            II(B, C, D, A, M[i * 7 % 16], 21, t[i + 48]);
            break;
    }
}

别忙，我知道你肯定会问这个 t[i] 是个什么鬼东西。
MD5 中对 t[i] 的定义是：

1
t[i] = (int32_t)(pow(2, 32) * abs(sin(i + 1)));

也就是说 t[i] 就是 2 的 32 次方乘以 sin(i + 1) 的绝对值取整数的部分。

四轮全部完成之后，加上初始的 A、B、C、D 即得到本块数据的处理结果。

1
2
3
4
A = A + A0
B = B + B0
C = C + C0
D = D + D0

如果还有其他数据块剩余，使用这块的结果作为初始值继续处理后续的数据块，直到没有数据块剩余。

完全处理完所有数据块之后，A、B、C、D 按照小端字节序排列输出就是 MD5 的结果。顺序按照 A→B→C→D。
举例：

1
2
3
4
5
6
A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476

Result = 0x01234567 89ABCDEF FEDCBA98 76543210

我估计你会被这个大小端字节序搞得很头晕，我也一样=。=，我当时实现 MD5 的时候关于大小端排列的问题也是经过好几次错误的尝试，最后才完全掌握了这个。

简单总结 MD5 中的大小端问题：

  • 定义幻数时由于编译中数字按照大端字节序存储，而给的幻数则按照小端字节序定义，所以要将幻数的存储转化为大端存储。
  • 长度存储也是按照小端字节序存储的，也是跟编程时候相反，存长度应该从长度数据的最后一个字节开始一个一个填进去，填满 64 bits 为止。
  • 在处理的数据的时候我们一般是一个一个字节存储的，由于 MD5 将数据按小端存储看待，所以处理的时候为了保持一致，我们应该把脚标大的放在前面（因为存数据的时候也被当作小端存储扔进去的），脚标小的放在后面。
  • t[i] 不需要变化。
  • 结果的输出中要按照 A→B→C→D 的顺序按照小端字节序输出，因为开始处理的时候我们就把他们反了过来，结果还要反回去。

以上就是 MD5 算法。

SHA1 算法

SHA 家族是由 MDx 家族发展而来，可以理解为 MDx 的一个改进版本。

SHA 定义了如下几个变换函数：

1
2
3
4
int32_t f1(b, c, d) { return (b & c) | ((~b) & d); }
int32_t f2(b, c, d) { return b ^ c ^ d; }
int32_t f3(b, c, d) { return (b & c) | (b & d) | (c & d); }
int32_t f4(b, c, d) { return b ^ c ^ d; }

处理数据的时候第一步与 MD5 一样，先把数据补齐，补齐方法与 MD5 一致不再赘述。

在最后 64 bits 上 SHA1 与 MD5 处理方式不同，但是也是填入数据的长度，不同的地方是不按照小端字节序填，而是按照原始形态填入。
依旧用 MD5 中的例子举例：

1
2
3
4
5
6
7
原始数据为字符串“abc”，长度为 24 bits（3 bytes）
最后64 bits 为：0x00000000 00000018

原始数据为 264 bits（33 bytes）
最后64 bits 为：0x00000000 00000108

原始数据长度超过 64 bits 可存储的大小，该数据无法处理。

从这里你会发现，SHA1 对数据长度是有限制的，当数据长度位数超过 2 的 64 次方减 1 时无法使用 SHA1 进行散列值运算。

SHA1 在初始处理状态下定义了几个如下几个幻数：

1
2
3
4
5
A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476
E = 0xC3D2E1F0

处理过程中，数据也是按照 512 bits（64 bytes）分块，每块数据分成 16 个分组，每组 4 bytes。
处理开始前先申请 80 个长度为 4 bytes 的缓冲区，记每块缓冲区为 W[i]，第 0～15 分组使用当前块数据填充，后面 16～79 分组按照如下方式填充：

1
2
3
W[i] = (W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16]) << 1

<< 表示循环左移

缓冲区建立完毕开始处理数据，申请五个初始值 H0~H5，H0～H5 继承上一块数据处理的结果，如果是最初的数据块使用初始的五个幻数。
令 A=H0，B=H1，C=H2，D=H3，E=H4
然后执行下面的处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for (i = 0; i < 80; i++) {
    if (i >= 0 && i <= 19) {
        TEMP = (A << 5) + f1(B, C, D) + E + W[i] + K[i / 20];
    } else if (i >= 20 && i <= 39) {
        TEMP = (A << 5) + f2(B, C, D) + E + W[i] + K[i / 20];
    } else if (i >= 40 && i <= 59) {
        TEMP = (A << 5) + f3(B, C, D) + E + W[i] + K[i / 20];
    } else if (i >= 60 && i <= 79) {
        TEMP = (A << 5) + f4(B, C, D) + E + W[i] + K[i / 20];
    }

    E = D; D = C; C = B << 30; B = A; A = TEMP;
}

H0 = H0 + A;
H1 = H1 + B;
H2 = H2 + C;
H3 = H3 + D;
H4 = H4 + E;

<< 表示循环左移

这里的 K[i] 计算如下：

1
2
3
4
5
6
7
K[0] = sqrt(2) * pow(2, 30);
K[1] = sqrt(3) * pow(2, 30);
K[2] = sqrt(5) * pow(2, 30);
K[3] = sqrt(10) * pow(2, 30);

sqrt 开根号
pow 乘方

处理完成之后本块处理结束，如果后续依旧有数据重复这个过程，直到所有数据块处理结束。

全部数据块处理完成之后依照 H0→H1→H2→H3→H4 顺序输出结果，输出结果直接按照数据原始形态输出，不需要按照小端字节序输出。
举例：

1
2
3
4
5
6
7
H0 = 0x67452301
H1 = 0xEFCDAB89
H2 = 0x98BADCFE
H3 = 0x10325476
H4 = 0xC3D2E1F0

Result = 0x67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0

SHA1 依旧要注意字节存储的问题，与 MD5 不同，SHA1 只按照数据原始形态来，所以说存储的时候使用的脚标顺序就是数据的组织顺序，不需要颠倒。

以上就是 SHA1，比 MD5 要简单很多。

有限集可逆？

好了重点来了，有限集中 MD5/SHA1 是否可逆呢？

假设我们知道了数据只有 1 字节（0～255），这样数据只会处理一轮，结果对应的数据，由于是跟初始幻数计算而来，所以由结果和初始幻数可以得到最后一轮的结果。

我们观察一下 MD5 和 SHA1，后面的步骤大部分都是重复的，所以这里简化起见，我们以 MD5 的一个循环为例，分析一下如果要得到这个循环开始的结果能否通过最终的数据推出来。

假设现在已经知道了 MD5 第一轮 FF 处理的结果 A、B、C、D，初始幻数也是知道的，现在要求的是 M[0 ~ 15]。

最后一次计算的是 B 的值，这里用于计算的 B 我们是不知道的，C、D、A 已知，M[15] 也是待求变量，所以我们这里先把用于计算的 B 设为 B16，这样我们其实得到了一个二元一次方程，我们把他计作：

1
ℵ(B16, M[15]) = B

同理我们继续向上推算，C 的计算中，D、A 已知，B16被我们设为了未知数，结果 C 我们也知道了，但是这里由于 M[14] 未知，我们依旧要设一个新的未知数 C15，这时其实我们得到了一个新的方程：

1
ℵ(B16, C15, M[14]) = C

类似的继续向上推演，我们最终会得到一个方程组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ℵ(B16, M[15]) = B
ℵ(B16, C15, M[14]) = C
ℵ(B16, C15, D14, M[13]) = D
ℵ(B16, C15, D14, A13, M[12]) = A
ℵ(B12, C15, D14, A13, M[11]) = B16
ℵ(B12, C11, D14, A13, M[10]) = C15
ℵ(B12, C11, D10, A13, M[9])  = D14
ℵ(B12, C11, D10, A9,  M[8])  = A13
ℵ(B8,  C11, D10, A9,  M[7])  = B12
ℵ(B8,  C7,  D10, A9,  M[6])  = C11
ℵ(B8,  C7,  D6,  A9,  M[5])  = D10
ℵ(B8,  C7,  D6,  A5,  M[4])  = A9
ℵ(C7,  D6,  A5,  M[3]) = B8
ℵ(D6,  A5,  M[2]) = C7
ℵ(A5,  M[1]) = D6
ℵ(M[0]) = A5

我们知道数据只有一字节，所以说，M[0 ~ 15] 中，还有一些是可以预测的，最简单的 M[15] 是 0x00000000，M[14] 是 0x08000000，M[1] ~ M[13] 则一定是 0x00000000，M[0] 是唯一不知道的一个。
这样下来方程简化为了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ℵ(B16) = B
ℵ(B16, C15) = C
ℵ(B16, C15, D14) = D
ℵ(B16, C15, D14, A13) = A
ℵ(B12, C15, D14, A13) = B16
ℵ(B12, C11, D14, A13) = C15
ℵ(B12, C11, D10, A13) = D14
ℵ(B12, C11, D10, A9)  = A13
ℵ(B8,  C11, D10, A9)  = B12
ℵ(B8,  C7,  D10, A9)  = C11
ℵ(B8,  C7,  D6,  A9)  = D10
ℵ(B8,  C7,  D6,  A5)  = A9
ℵ(C7,  D6,  A5) = B8
ℵ(D6,  A5) = C7
ℵ(A5) = D6
ℵ(M[0]) = A5

共有 16 个方程，但是未知数有 13 个，显然是能解出来的。

其实如果把 MD5 的整个过程全部使用多元方程组表示出来，我们最终会得到 64 个方程，61 个未知量，这个方程组是可解的……
是不是很神奇？（位运算原则上与普通运算没有严格不同，依旧可以使用数学方法推算）
如果扩大有限集的范围到 1 ~ 2 字节时，此时会将未知数增加到 62 个（数据长度我们无法确定了），方程还是可解的。
直到扩大有限集的范围到 1 ~ 12 字节时，未知数数量才增加到 65 个，方程组开始不可解。
也就是说在限定集字节大小变化小于 12 字节浮动的时候我们是可以通过结果反推的。
※ 当然这里也只是数学理论证明，解题过程中应该跟这个结论有出入，但是可以肯定的是在某些情况下方程组是有固定解的。

那么 SHA1 呢？
这里我直接下结论了，不再过多赘述，有兴趣的可以思考一下这个问题。
很遗憾的是，就算限定数据为 1 个字节的数据，SHA1 依旧在原始数据中就会引入一堆未知量，W[0 ~ 79] 中，除了 W[1 ~ 15] 可知，其他的几乎全部未知，未知量不难推算，应该有 58 个。
整理出来的方程组中，主要是跟 E 的值有关，为了求数据，我们会引入 E80 ~ E6，也就是说我们一共有 75+58=133 个未知数，而我们的方程组只有 80 个，这显然是不可解的（理论不可解）。

所以说，MD5 不是当年被 Diss……确实现在来看是不安全的，SHA1 相对来说还算安全，但是目前来看 SHA1 貌似也有一种快速攻击方法，这里就不展开细说了，毕竟也没怎么了解过。

写到最后

MD5 在实现中要确认大小端字节序，这个跟普通编程思路有点不太一样，需要时刻注意，SHA1 则没有这个要求。

不同的哈希算法对数据长度要求是不一样的，MD5 不要求数据长度，SHA 家族中：SHA-0、SHA-1、SHA-224 和 SHA-256 限制长度 2^64-1，SHA-384、SHA-512 限制长度为 2^128-1，SHA-3 无限制。

PS：其实我感觉 MD5 当年应该是一个失败的加密算法设计才对 www，设计出来发现哎呀有时候咋解不出来，索性变成了哈希算法 233。

今天就到这里了。

附录

如果你要尝试实现 MD5 和 SHA1 的话我这里给几个临界校验值供参考：

1
2
3
4
5
6
7
8
9
10
11
MD5("")  = 0xD41D8CD9 8F00B204 E9800998 ECF8427E
MD5("a") = 0x0CC175B9 C0F1B6A8 31C399E2 69772661
MD5("01234567890123456789012345678901234567890123456789012345")
    = 0x8AF270B2 847610E7 42B0791B 53648C09
MD5("012345678901234567890123456789012345678901234567890123456")
    = 0xC620BACE 4CDE41BC 45A14CFA 62EE3487

SHA1("")  = 0xDA39A3EE 5E6B4B0D 3255BFEF 95601890 AFD80709
SHA1("a") = 0x86F7E437 FAA5A7FC E15D1DDC B9EAEAEA 377667B8
SHA1("01234567890123456789012345678901234567890123456789012345")
    = 0x0A40B8FB DAAFB7C2 9651618A C15D27E7 72287130