江苏龙网

  1. 主页 > 生活百科 > >

信息摘要算法之MD5

MD5

MD5（Message-Digest Algorithm） ， 想必大家都再熟悉不过了吧 。通常我们调用第三方支付接口的时候都会遇到这种算法或者SHA等等类似的算法来做签名验证 ， 由于其是不可逆的算法 ， 对应破解难度也很大 。
底层原理MD5算法的过程分为四步：处理原文 ， 设置初始值 ， 循环加工 ， 拼接结果 。
处理原文
首先 ， 我们计算出原文长度(bit)对512求余的结果 ， 如果不等于448 ， 就需要填充原文使得原文对512求余的结果等于448 。填充的方法是第一位填充1 ， 其余位填充0 。填充完后 ， 信息的长度就是512*N+448 。
之后 ， 用剩余的位置（512-448=64位）记录原文的真正长度 ， 把长度的二进制值补在最后 。这样处理后的信息长度就是512*(N+1) 。
设置初始值
MD5的哈希结果长度为128位 ， 按每32位分成一组共4组 。这4组结果是由4个初始值A、B、C、D经过不断演变得到 。MD5的官方实现中 ， A、B、C、D的初始值如下（16进制）：
A=0x01234567
B=0x89ABCDEF
C=0xFEDCBA98
D=0x76543210
循环加工
这一步是最复杂的一步 ， 我们看看下面这张图 ， 此图代表了单次A,B,C,D值演变的流程 。

信息摘要算法之MD5

文章插图
单次子循环过程
图中 ， A ， B ， C ， D就是哈希值的四个分组 。每一次循环都会让旧的ABCD产生新的ABCD 。一共进行多少次循环呢？由处理后的原文长度决定 。
假设处理后的原文长度是M
主循环次数 = M / 512
每个主循环中包含 512 / 32 * 4 = 64 次 子循环 。
1.绿色F
图中的绿色F ， 代表非线性函数 。官方MD5所用到的函数有四种：
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))
在主循环下面64次子循环中 ， F、G、H、I 交替使用 ， 第一个16次使用F ， 第二个16次使用G ， 第三个16次使用H ， 第四个16次使用I 。
2.红色“田”字
很简单 ， 红色的田字代表相加的意思 。
3.Mi
Mi是第一步处理后的原文 。在第一步中 ， 处理后原文的长度是512的整数倍 。把原文的每512位再分成16等份 ， 命名为M0~M15 ， 每一等份长度32 。在64次子循环中 ， 每16次循环 ， 都会交替用到M1~M16（命名+1）之一 。
4.Ki
一个常量 ， 在64次子循环中 ， 每一次用到的常量都是不同的 。
5.黄色的<<<S
循环左移S位 ， S的值也是常量 。
“流水线”的最后 ， 让计算的结果和B相加 ， 取代原先的B 。新ABCD的产生可以归纳为：
新A = 原d
新B = b+((a+F(b,c,d)+Mj+Ki)<<<s)
新C = 原b
新D = 原c
总结一下主循环中的64次子循环 ， 可以归纳为下面的四部分：
拼接结果
一步就很简单了 ， 把循环加工最终产生的A ， B ， C ， D四个值拼接在一起 ， 转换成字符串即可
整个过程及其复杂和繁琐 ， 也促使它在一定程度上保证了hash值的均匀分布和安全性 。
关于MD5破解的方法即使MD5的加密如此复杂 ， 但也并非不可破解的 。但总体来说 ， 所有的破解方法都采用“碰撞”方式 ， 类似于不同字符的hash值可能相同的原理 ， 即hash(A)==hash(B),尽管大多数的时候在内存中A!=B ， 但是MD5加密后的值是相同的 。
那么怎么实现MD5的摘要碰撞呢？
MD5的破解方法及其多 ， 像暴力枚举 ， 字典 ， 彩虹表等方法 。
1.暴力枚举法
简单暴力的枚举出原文 ， 并计算他们的hash值 ， 看是否与摘要信息一致来达到破解目的 。此方法时间复杂度极高 ， 仅仅8位的密码 ， 只考虑Base64中的字符 ， 就会有64^8中可能 ， 如果只是单机破解 ， 可能需要几十年 。当然 ， 也可以取巧 ， 例如考虑生日或者电话号码等等 ， 缩小穷举范围 。
2.字典法
既然暴力破解这么费时 ， 典型的以时间换空间 ， 那么就有人采用了相反的方式 ， 即字典法 ， 拿空间换时间 。


推荐阅读


上一篇：美团外卖前端容器化演进实践

下一篇：天台茶的由来及历史渊源