有限集内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首先定义了如下几个函数：
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)); }
& 按位与
| 按位或
^ 按位异或
~ 取补码
由这四个函数延伸出如下几个函数：
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，举例：
原始数据：0x7AD2
二进制：0x01111011 11010010
原数据长度：16 bits
需补齐长度：448 - 16 = 432
补齐之后：0x7AD28000 0x00000000 ...省略12个0x00000000
二进制：0x01111011 11010010 10000000 00000000 ...省略416个0
算法的初始状态MD5定义了四个幻数：
A = 0x01234567
B = 0x89ABCDEF
C = 0xFEDCBA98
D = 0x76543210
幻数以小端字节序存储（内存地址由低到高）
而编程中我们的变量存储方式是大端字节序（内存地址从高到低）
所以编程时我们定义的幻数应该是：
A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476
数据处理按照块进行，每块大小为512 bits（64 bytes）。
这里你会发现如果按照刚刚的补齐，数据原始长度在512的模不是0，缺少的64 bits 怎么办？这里并不是MD5把这64 bits 忘记了，而是定义了他们的特殊作用。MD5最后64 bits的作用是存储原始数据长度，长度也是以小端字节序存储。
最后64 bits处理举例：
原始数据为字符串“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个分组的数据，每轮的操作如下：
// 第一轮
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]的定义是：
t[i] = (int32_t)(pow(2, 32) * abs(sin(i + 1)));
也就是说t[i]就是2的32次方乘以sin(i + 1)的绝对值取整数的部分。
四轮全部完成之后，加上初始的A、B、C、D即得到本块数据的处理结果。
A = A + A0
B = B + B0
C = C + C0
D = D + D0
如果还有其他数据块剩余，使用这块的结果作为初始值继续处理后续的数据块，直到没有数据块剩余。
完全处理完所有数据块之后，A、B、C、D按照小端字节序排列输出就是MD5的结果。顺序按照A→B→C→D。
举例：
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定义了如下几个变换函数：
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中的例子举例：
原始数据为字符串“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在初始处理状态下定义了几个如下几个幻数：
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分组按照如下方式填充：
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
然后执行下面的处理：
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]计算如下：
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顺序输出结果，输出结果直接按照数据原始形态输出，不需要按照小端字节序输出。
举例：
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，这样我们其实得到了一个二元一次方程，我们把他计作：
ℵ(B16, M[15]) = B
同理我们继续向上推算，C的计算中，D、A已知，B16被我们设为了未知数，结果C我们也知道了，但是这里由于M[14]未知，我们依旧要设一个新的未知数C15，这时其实我们得到了一个新的方程：
ℵ(B16, C15, M[14]) = C
类似的继续向上推演，我们最终会得到一个方程组：
ℵ(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]是唯一不知道的一个。
这样下来方程简化为了：
ℵ(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的话我这里给几个临界校验值供参考：
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