⼀⽂详解M D5信息摘要算法
对于软件研发⼈员来说 MD5 不是⼀个陌⽣的词汇，平时的软件研发中，经常使⽤ MD5 校验消息是否被篡改、验证⽂件完整性，甚⾄将MD5当作加密算法使⽤。
MD5虽不陌⽣，但不是所有研发⼈员都了解其算法原理，通过这篇⽂章详细学习MD5 摘要算法。
认识 MD5
掌握 MD5 算法原理
编码实现 MD5 摘要算法
使⽤Jav a开发语⾔ 编码实现MD5摘要算法。
⼀、认识M D5
MD5（Mes s age Di ges t A l go r i th m 5）中⽂名为消息摘要算法第五版，是计算机安全领域⼴泛使⽤的⼀种散列函数，⽤以提供消息的完整性保护。
MD5作为⼀种常⽤的摘要算法（或指纹算法），其具有以下⼏个重要的特点（个⼈观点）：
输⼊任意长度信息，输出长度固定：
MD5 可输⼊任意长度的信息，其输出均为128位(b i t)固定长度的⼆进制数据。
运算速度快：
MD5的运算均为32位与、或、⾮、位移等位运算，因此其运算速率快，⼏乎不消耗CP U时间。
不可逆：
根据MD5的的散列结果，⽆法计算出原始数据（查字典除外）。
碰撞性：
原始数据与其M D5散列结果并⾮⼀⼀对应，存在多个原始数据的M D5结果相同的可能性。
不安全：
2011年， 禁⽌MD5⽤作密钥散列消息认证码。
1.1长度
⽇常软件研发中M D5计算结果⼀般为长度为32的字符串，偶尔也会遇到长度为16的字符串。那么，MD5到底是多长的字符串？
MD5散列结果是128位(b i t)固定长度的⼆进制数据，也就是128个0/1的⼆进数据。
⽤128位⼆进制数据呈现M D5的散列结果，对于软件开发者很不友好。
⼀般将⼆进制转成16进制，每4个⼆进制数据转化为⼀个16进制数据，128位⼆进制数据转化为32个⼗六进制数据（128/4=32），最终以字符串形式呈现⼗六进制数据后则为长度为32的字符串。
8位⼆进制数据，转化为2个⼗六进制数据举例如下：
// 8位⼆进制 ——> 2个⼗六进制数据
// ⼆进制数据
0100 0101
// 对应的⼗六制数据
4 5
为什么⽹上还有16位MD5散列结果呢？
这⾥以 Mes s age Di ges t A l go r i th m 作为原始数据，分别计算其32位与16位的散列结果：
// 32位散列结果
MD5(Me s s a g e D i g e s t A l g o ri th m,32) = e4b0190b2fa d c0a d b e54471ffd79a729
// 16位散列结果
MD5(Me s s a g e D i g e s t A l g o ri th m,16) = 2fa d c0a d b e54471f
仔细观察以上两个散列结果，发现其中间部分完全相同均为2f a d c0a d b e54471f。
因此猜测16位长度的散列结果为：32位散列结果去掉前⼋位、后⼋位得到的。
1.2⽤途
平时的软件研发中经常使⽤MD5校验消息是否被篡改、验证⽂件完整性。
验证是否被篡改：
⽐如，上传下载⽂件。
数据的 发送⽅ 将原始数据⽣成MD5摘要，然后把 原始数据 与其 MD5摘要⼀起发送给 接收⽅；
接收⽅收到数据后，先将原始数据⽤MD5算法⽣成摘要信息，然后再将此摘要信息与发送⽅发过来的摘要信息进⾏⽐较，如果⼀致就认为原始数据没有被修改、或者损坏。
防⽌抵赖：
例如A写了⼀个⽂件，某认证机构对此⽂件⽤MD5算法产⽣摘要信息并做好记录。
若以后A说这⽂件不是他写的，权威机构只需对此⽂件重新产⽣摘要信息，然后跟记录在册的摘要信息进⾏⽐对，若摘要信息相同，则证明为A写的⽂件。
1.3不安全
2011年， 禁⽌MD5⽤作密钥散列消息认证码。
MD5不安全主要指的是，不可再⽤M D5对原始秘钥进⾏加密：
⽐如：将⽤户的登录秘钥进⾏MD5加密后，存储于数据库中。
MD5虽然理论上不可逆，但有些⿊客⽹站通过查字典⽅式获取MD5原⽂信息。
提前将⼀些⽐较常见的密⽂做MD5运算，将结果保存下来，破译密⽂时，通过MD5摘要信息直接查询原⽂。
⽐如：字符串123 的MD5值是 202cb962ac59075b964b07152d234b70 ，⿊客在破解后的数据库中看到某位⽤户的密码是 202cb962ac59075b964b07152d234b70 ，通过字典⼀查就知道密码明⽂是 123 了。
MD5的碰撞性，决定了存在两个不⽤的输⼊信息，其MD5相同的可能。
2009年，中国科学院的谢涛和冯登国仅⽤了 2的20.96次幂 的碰撞算法复杂度，破解了MD5的碰撞抵抗，该攻击在普通计算机上运⾏只需要数秒钟。
⼆、算法原理
MD5 摘要算法⼤概计算过程可以描述如下：
MD5 将 “输⼊信息” 分为N*512b i t的数据分组；
每⼀512b i t分组⼜分为16个⼦分组，每个⼦分组为32b i t的原始数据；
16个⼦分组分别命名为M0~M15；
每个⼦分组都要进⾏4次运算，运算公式分别为F F、G G、H H、I I；
总的运算次数为N*16*4（运算均为位运算）。
“输⼊信息” 分组计算情况如下图所⽰：
以上为MD5 摘要算法的⼤概原理总结，下边按照 中算法的介绍顺序，梳理MD5 摘要算法：
填充数据
填充数据，使输⼊数据%512=448
填充长度信息
补充 “输⼊信息” 位长 (Bi ts L en gth)信息，占⽤空间64位
初始化A、B、C、D 四个数据
初始化 A、B、C、D 四个数据，⽤于后续的分组计算
分组数据运算
512b i t分组数据，需进⾏16*4=64次运算
结果累加
2.1填充数据
⾸先需要对 “输⼊信息” 进⾏填充，使其位长对512求余的结果为448（填充必须进⾏，即使其位长对512求余的结果等于448）。
填充数据的⽅式：
在“输⼊信息”的后⾯填充⼀个1和⽆数个0，直到满⾜上⾯的条件时才停⽌信息填充。
填充后的 “输⼊信息” 其位长 (Bi ts L en gth) 将扩展到：
N*512+448 ( N>=0 )
2.2补充长度信息
⽤64b i t记录 “输⼊信息” 的位长 (Bi ts L en gth)，把64位长度⼆进制数据补在最后。
经过此步骤后，其位长 (Bi ts L en gth) 将扩展到：
N*512+448+64=(N+1)*512 ( N>=0 )
2.3初始化A、B、C、D
这⾥需要初始化四个数据 A、B、C、D，这四个变量将⽤于后续的公式计算。
四个数据均为8个16进制数据组合，每个16进制数据为4b i t，每个数据占32b i t。
// 每个数据占空间 32b i t
// 四个数据分别为 8个 16进制数据的组合构成
// 单个16进制数据占空间 4b i t
A: 01 23 45 67（16进制）
B: 89 a b c d e f （16进制）
C: fe d c b a 98（16进制）
D: 76 54 32 10（16进制）
将A、B、C、D输⼊计算机进⾏计算时，A、B、C、D将变化为：
A: 0x67452301
B: 0x e fc d a b89
C: 0x98b a d c fe
D: 0x10325476
为什么会变化为 0x67452301、0x ef cdab89、0x98badcf e、0x10325476 ？
// A的16进制表⽰
A: 01 23 45 67（16进制）
// A的⼆进制表⽰
A: 00000 0001 0010 0011 0100 0101 0110 0111（⼆进制）
// 计算机中⾸先编写的为低字节位，当从右向左获取字节数据(8位⼀个字节)时，最终A将变化为0x67452301 A: 67 45 23 01（16进制）
2.4分组数据运算
上⽂层提到⼦分组的运算公式：F F、G G、H H、I I ，32b i t⼦分组的运算公式如下：
// F F、GG、H H、II
// <<< 为循环左移
F F(a ,b ,c ,d ,Mj ,s ,ti) 操作为 a = b + ( (a + F(b,c,d) + Mj + ti) <<< s)
GG(a ,b ,c ,d ,Mj ,s ,ti) 操作为 a = b + ( (a + G(b,c,d) + Mj + ti) <<< s)
H H(a ,b ,c ,d ,Mj ,s ,ti) 操作为 a = b + ( (a + H(b,c,d) + Mj + ti) <<< s)
II(a ,b ,c ,d ,Mj ,s ,ti) 操作为 a = b + ( (a + I(b,c,d) + Mj + ti) <<< s)
// F、G、H、I
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) )
公式中初始输⼊数据a、b、c、d 为A、B、C、D
Mj 代表32bi t⼦分组数据，每个⼦分组数据均需要经过 F F、G G、H H、I I 四次运算：
512bi t原始输⼊数据，有16个⼦分组，每个分组进⾏4次运算，总共16 * 4 = 64次运算。
s 常量数据，代表循环左移的位数。
ti 常量；
512bi t分组数据，64 次位运算如下（输⼊数据为32bi t原始数据，输出为32bi t数据）：
// 512b i t分组数据，16 * 4次运算
/
/ 输⼊数据为32b i t原始数据，输出为32b i t数据
// 第⼀次运算F F
a = F F(a, b, c, d, M0, 7, 0x d76a a478L);
d = F F(d, a, b, c, M1, 12, 0x e8c7b756L);
c = F F(c, d, a, b, M2, 17, 0x242070
d b L);
b = F F(b, c, d, a, M3, 22, 0x c1b d
c e e e L);
a = F F(a, b, c, d, M4, 7, 0x f57c0fa fL);
d = F F(d, a, b, c, M5, 12, 0x4787c62a L);
c = F F(c, d, a, b, M6, 17, 0x a8304613L);
b = F F(b, c, d, a, M7, 22, 0x fd469501L);
a = F F(a, b, c, d, M8, 7, 0x698098d8L);
d = F F(d, a, b, c, M9, 12, 0x8b44f7a fL);
c = F F(c, d, a, b, M10, 17, 0x ffff5b b1L);
b = F F(b, c, d, a, M11, 22, 0x895
c d7b e L);
a = F F(a, b, c, d, M12, 7, 0x6b901122L);
d = F F(d, a, b, c, M13, 12, 0x fd987193L);
c = F F(c, d, a, b, M14, 17, 0x a679438e L);
字符串长度算不算 0b = F F(b, c, d, a, M15, 22, 0x49b40821L); // 第⼆轮运算GG
a = GG(a, b, c, d, M1, 5, 0x f61e2562L);
d = GG(d, a, b, c, M6, 9, 0x c040b340L);
c = GG(c, d, a, b, M11, 14, 0x265e5a51L);
b = GG(b, c, d, a, M0, 20, 0x e9b6c7a a L);
a = GG(a, b, c, d, M5, 5, 0x d62f105d L);
d = GG(d, a, b, c, M10, 9, 0x2441453L);
c = GG(c, d, a, b, M15, 14, 0x d8a1e681L);
b = GG(b, c, d, a, M4, 20, 0x e7d3fb c8L);
a = GG(a, b, c, d, M9, 5, 0x21e1c d e6L);
d = GG(d, a, b, c, M14, 9, 0x c33707d6L);
c = GG(c, d, a, b, M3, 14, 0x f4d50d87L);
b = GG(b, c, d, a, M8, 20, 0x455a14e d L);
a = GG(a, b, c, d, M13, 5, 0x a9e3e905L);
d = GG(d, a, b, c, M2, 9, 0x fc
e fa3f8L);
c = GG(c, d, a, b, M7, 14, 0x676f02d9L);
b = GG(b, c, d, a, M12, 20, 0x8d2a4c8a L); // 第三轮运算H H
a = H H(a, b, c, d, M5, 4, 0x fffa3942L);
d = H H(d, a, b, c, M8, 11, 0x8771f681L);
c = H H(c, d, a, b, M11, 16, 0x6d9d6122L);
b = H H(b, c, d, a, M14, 23, 0x fd e5380
c L);
a = H H(a, b, c, d, M1, 4, 0x a4
b e e a44L);
d = H H(d, a, b, c, M4, 11, 0x4b d
e c fa9L);
c = H H(c, d, a, b, M7, 16, 0x f6b b4b60L);
b = H H(b, c, d, a, M10, 23, 0x b e b fb c70L);
a = H H(a, b, c, d, M13, 4, 0x289b7e c6L);
d = H H(d, a, b, c, M0, 11, 0x
e a a127fa L);
c = H H(c, d, a, b, M3, 16, 0x d4e f3085L);
b = H H(b, c, d, a, M6, 23, 0x4881d05L);
a = H H(a, b, c, d, M9, 4, 0x d9d4d039L);
d = H H(d, a, b, c, M12, 11, 0x e6d b99e5L);
c = H H(c, d, a, b, M15, 16, 0x1fa27c f8L);
b = H H(b, c, d, a, M2, 23, 0x c4a c5665L); // 第四轮运算II
a = II(a, b, c, d, M0, 6, 0x f4292244L);
d = II(d, a, b, c, M7, 10, 0x432a ff97L);
c = II(c, d, a, b, M14, 15, 0x a b9423a7L);
b = II(b, c, d, a, M5, 21, 0x fc93a039L);
a = II(a, b, c, d, M12, 6, 0x655b59c3L);
d = II(d, a, b, c, M3, 10, 0x8f0c c c92L);
c = II(c, d, a, b, M10, 15, 0x ffe ff47
d L);
b = II(b, c, d, a, M1, 21, 0x85845d d1L);
a = II(a, b, c, d, M8, 6, 0x6fa87e4fL);
d = II(d, a, b, c, M15, 10, 0x fe2c e6e0L);
c = II(c, d, a, b, M6, 15, 0x a3014314L);
b = II(b, c, d, a, M13, 21, 0x4e0811a1L);
a = II(a, b, c, d, M4, 6, 0x f7537e82L);
d = II(d, a, b, c, M11, 10, 0x b d3a f235L);
c = II(c, d, a, b, M2, 15, 0x2a d7d2b b L);
b = II(b, c, d, a, M9, 21, 0x e b86d391L);
2.5结果累加
若A、B、C、D为变量，并且A、B、C、D的初始化信息为 A: 0x67452301；B: 0x ef cdab89；C:
0x98badcf e；D: 0x10325476 ，每⼀512bi t分组的运算结果为a、b、c、d。则第N个512bi t组的计算结果为：// a、b、c、d为每⼀512b i t分组的运算结果；
// A、B、C、D是下⼀组计算的输⼊参数；
// 若⽆下⼀个512b i t分组 A、B、C、D则为最终计算结果；
A = a + A;
B = b + B;
C = c + C;
D = d + D;
三、编码实现M D5摘要算法
⽹上到⼀个⽤Jav a编码实现MD5摘要算法的案例，我从头到尾加了详细的注释。因此对于代码实现，朋友们可以结合注释读代码，打⽇志进⾏MD5摘要算法分析、学习。
/**
* J a v a实现MD5摘要算法：
* 基本每⼀⾏我都加了注释，因此不再对代码进⾏详细介绍，
* 如有疑问，可联系：x i a x v e l i a n g@163.c o m
*/
p u b l i c c l a s s MD5H a s h {
/**
* R F C1321中定义的标准4*4矩阵的常量：循环位移常量数据 s
*/
s ta ti c fi n a l i n t S11 = 7, S12 = 12, S13 = 17, S14 = 22;
s ta ti c fi n a l i n t S21 = 5, S22 = 9, S23 = 14, S24 = 20;
s ta ti c fi n a l i n t S31 = 4, S32 = 11, S33 = 16, S34 = 23;
s ta ti c fi n a l i n t S41 = 6, S42 = 10, S43 = 15, S44 = 21;
/**
* 填充数据 1000 0000 0000 ...
* 长度：64*8 = 512b i t
* 注：-128为1000 0000
*/
s ta ti c fi n a l b y te[] P A D D IN G =
{
-128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0
};
/**
* a、b、c、d四个变量
*/
p ri v a te l o n g[] a b c d = n e w l o n g[4];
/**
* 512字节分组数据缓冲 64*8=512b i t
*/
p ri v a te b y te[] b u ffe r512B i t = n e w b y te[64];
// 输⼊数据的位长信息（64b i t）
p ri v a te l o n g[] i n p u tB i tC o u n t = n e w l o n g[2];
/**
* MD5计算结果

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。