md5算法浅析

背景

MD5算法是一个信息摘要算法，而不算一个加密算法。由MD2，MD3，MD4发展而来。MD5摘要算法就是把任意长度的字符串变换成一定长的大整数。MD5是一种哈希算法。
网络信息时代，每天有大量的信息进行网络传输，最害怕的就是信息被篡改，MD5算法就是用来校验信息是否被篡改过。

举个栗子：
A用户把文件F传给B，在F文件传给B的同时，A会把F文件用MD5算法计算出一串数字，这串数字连同F文件一起传给B，当B接收到文件F时，同样对F进行MD5计算，然后和接收到的数字比较，如果不相同，就被篡改过。

原理

补位，存储

MD5就是把一串字符串转成512固定的比特位。一个字符的长度是8bit，也就是一个字节的长度。我们先将一个长字符串分割成每512位为一个分组，这样任何字符串就可以被分割成N*512+R；我们对R进行补位，让它变成512位（第一位补1，后面全部补0）

这里要注意，如果R=0，依然要补一个512位，第一位为1，后面补0；
如果R>448，也就是剩余补位的bit不足64位，不能用来存放原字符串的长度，则需要补足R，并且再补足一个512位。

现在字符串已经被分为512位了，我们继续把512位分为16*32个分组，32位就是4个字节，可以存放4个字符（ASCII码，如果是中文也是类似的思想），32位正好是一个int类型，因此我们可以考虑用int类型来存储4个字符，通常我们按小端规则存放。

举个栗子：abcd四个字符存放在int变量中，就变成了dcba。
最后512位表示的16个int数组是：小端对齐
M[0] = 64 63 62 61 ===> d c b a
M[1] = 00 00 00 80 ===> 0000 0000 0000 1000
M[2] = 0
.......
M[15] = 0
内存中的样式为：61 62 63 64 80 00 00 ......

设置初始值（链接变量）

MD5的哈希的结果是128位，按32位分为4组，每个组都是从A,B,C,D四个值不断的演变过来，A,B,C,D的值如下(16进制)：

A=0x67452301，
B=0xefcdab89，
C=0x98badcfe，
D=0x10325476。
这四个链接变量怎么来的？是根据内存中0_f0按照小端规则排序来存储的，如下：
01 23 45 67 ...ef dc ... 32 10

循环加工

先设置四个变量a,b,c,d，初始值如下：

a=A, b=B, c=C, d= D
定义四个函数：
F(X,Y,Z)=(X&Y)|((~X)&Z)
G(X,Y,Z)=(X&Z)|(Y&(~Z))
H(X,Y,Z)=X^YZ
I(X,Y,Z)=Y^(X|(~Z))

由于我们的消息是512(N+1)，因此需要循环N+1次，主要的循环步骤如下：
假设M[j]表示消息的第j个子分组（从0到15），<<表示循环左移s，常数ti是4294967296abs(sin(i))的整数部分，i取值从1到64，单位是弧度。(4294967296等于2的32次方)

1. //第一轮计算：j 从0 循环到15，轮数ln=0，i=j%16=j。
   FF(a, b, c, d, M[j], s, ti)表示 a = b + ((a + F(b, c, d) + Mj + ti) <<< s)
2. // 第二轮计算：j 从0 循环到15, 轮数ln=1，i=(1+5*j)%16，使用循环函数G，
   GG(a, b, c, d, M[j], s, ti)表示 a = b + ((a + G(b, c, d) + Mj + ti) <<< s)
3. //第三轮计算：j 从0 循环到15, 轮数ln=2，i=(5+3*j)%16，使用循环函数H
   HH(a, b, c, d, M[j], s, ti)表示 a = b + ((a + H(b, c, d) + Mj + ti) <<< s)
4. //第四轮计算：j 从0 循环到15, 轮数ln=3，i=(7*j)%16，使用循环函数I，其他同第一轮
   II(a, b, c, d, M[j], s, ti)表示 a = b + ((a + I(b, c, d) + Mj + ti) <<< s)

上面每一轮计算中对于每一次循环a,b,c,d都需要更换不同的位置比如第一轮计算：
FF(a, b, c, d, M[j], s, ti)
FF(d, a, b, c, M[j], s, ti)
......

参考文档

[1] https://www.cnblogs.com/arsense/p/6485073.html