散列算法-MD5

简介: 信息摘要技术把明文内容按某种规则生成一段哈西值,即使明文消息只改动了一点点,生成的结果也会完全不同。MD5(Message-digest algorithm 5)就是信息摘要的一种实现,它可以从任意长度的明文字符串生成128位的哈希值。

信息摘要技术把明文内容按某种规则生成一段哈西值,即使明文消息只改动了一点点,生成的结果也会完全不同。

MD5(Message-digest algorithm 5)就是信息摘要的一种实现,它可以从任意长度的明文字符串生成128位的哈希值。

摘要哈希生成的正确姿势是什么样呢?分三步:

1.收集相关业务参数。

2.按照规则,把参数名和参数值拼接成一个字符串,同时把给定的密钥也拼接起来。之所以需要密钥,是因为攻击者也可能获知拼接规则。

3.利用MD5算法,从原文生成哈希值。MD5生成的哈希值是128位的二进制数,也就是32位的十六进制数。

第三方支付平台如何验证请求的签名?同样分三步:

1.发送方和请求方约定相同的字符串拼接规则,约定相同的密钥。

2.第三方平台接到支付请求,按规则拼接业务参数和密钥,利用MD5算法生成Sign。

3.用第三方平台自己生成的Sign和请求发送过来的Sign做对比,如果两个Sign值一模一样,则签名无误,如果两个Sign值不同,则信息做了篡改。这个过程叫做验签

MD5算法底层原理:

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值演变的流程。

图中,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之一。

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次子循环,可以归纳为下面的四部分:

第一轮:

      FF(a,b,c,d,M0,7,0xd76aa478)     s[0]=7,   K[0] = 0xd76aa478

  FF(a,b,c,d,M1,12,0xe8c7b756)   s[1]=12,  K[1] = 0xe8c7b756

  FF(a,b,c,d,M2,17,0x242070db)

  FF(a,b,c,d,M3,22,0xc1bdceee)

  FF(a,b,c,d,M4,7,0xf57c0faf)

  FF(a,b,c,d,M5,12,0x4787c62a)

  FF(a,b,c,d,M6,17,0xa8304613)

  FF(a,b,c,d,M7,22,0xfd469501)

  FF(a,b,c,d,M8,7,0x698098d8)

  FF(a,b,c,d,M9,12,0x8b44f7af)

  FF(a,b,c,d,M10,17,0xffff5bb1)

  FF(a,b,c,d,M11,22,0x895cd7be)

  FF(a,b,c,d,M12,7,0x6b901122)

  FF(a,b,c,d,M13,12,0xfd987193)

  FF(a,b,c,d,M14,17, 0xa679438e)

  FF(a,b,c,d,M15,22,0x49b40821)

  第二轮:

  GG(a,b,c,d,M1,5,0xf61e2562)

  GG(a,b,c,d,M6,9,0xc040b340)

  GG(a,b,c,d,M11,14,0x265e5a51)

  GG(a,b,c,d,M0,20,0xe9b6c7aa)

  GG(a,b,c,d,M5,5,0xd62f105d)

  GG(a,b,c,d,M10,9,0x02441453)

  GG(a,b,c,d,M15,14,0xd8a1e681)

  GG(a,b,c,d,M4,20,0xe7d3fbc8)

  GG(a,b,c,d,M9,5,0x21e1cde6)

  GG(a,b,c,d,M14,9,0xc33707d6)

  GG(a,b,c,d,M3,14,0xf4d50d87)

  GG(a,b,c,d,M8,20,0x455a14ed)

  GG(a,b,c,d,M13,5,0xa9e3e905)

  GG(a,b,c,d,M2,9,0xfcefa3f8)

  GG(a,b,c,d,M7,14,0x676f02d9)

  GG(a,b,c,d,M12,20,0x8d2a4c8a)

  第三轮:

  HH(a,b,c,d,M5,4,0xfffa3942)

  HH(a,b,c,d,M8,11,0x8771f681)

  HH(a,b,c,d,M11,16,0x6d9d6122)

  HH(a,b,c,d,M14,23,0xfde5380c)

  HH(a,b,c,d,M1,4,0xa4beea44)

  HH(a,b,c,d,M4,11,0x4bdecfa9)

  HH(a,b,c,d,M7,16,0xf6bb4b60)

  HH(a,b,c,d,M10,23,0xbebfbc70)

  HH(a,b,c,d,M13,4,0x289b7ec6)

  HH(a,b,c,d,M0,11,0xeaa127fa)

  HH(a,b,c,d,M3,16,0xd4ef3085)

  HH(a,b,c,d,M6,23,0x04881d05)

  HH(a,b,c,d,M9,4,0xd9d4d039)

  HH(a,b,c,d,M12,11,0xe6db99e5)

  HH(a,b,c,d,M15,16,0x1fa27cf8)

  HH(a,b,c,d,M2,23,0xc4ac5665)

  第四轮:

  Ⅱ(a,b,c,d,M0,6,0xf4292244)

  Ⅱ(a,b,c,d,M7,10,0x432aff97)

  Ⅱ(a,b,c,d,M14,15,0xab9423a7)

  Ⅱ(a,b,c,d,M5,21,0xfc93a039)

  Ⅱ(a,b,c,d,M12,6,0x655b59c3)

  Ⅱ(a,b,c,d,M3,10,0x8f0ccc92)

  Ⅱ(a,b,c,d,M10,15,0xffeff47d)

  Ⅱ(a,b,c,d,M1,21,0x85845dd1)

  Ⅱ(a,b,c,d,M8,6,0x6fa87e4f)

  Ⅱ(a,b,c,d,M15,10,0xfe2ce6e0)

  Ⅱ(a,b,c,d,M6,15,0xa3014314)

  Ⅱ(a,b,c,d,M13,21,0x4e0811a1)

  Ⅱ(a,b,c,d,M4,6,0xf7537e82)

  Ⅱ(a,b,c,d,M11,10,0xbd3af235)

  Ⅱ(a,b,c,d,M2,15,0x2ad7d2bb)

  Ⅱ(a,b,c,d,M9,21,0xeb86d391) 

第四步:拼接结果

这一步就很简单了,把循环加工最终产生的A,B,C,D四个值拼接在一起,转换成字符串即可。

破解 MD5 算法

破解并不是把摘要恢复成明文,摘要固定只有128bit而原文数量是无穷的。

MD5破解实际上属于碰撞,只要能找到能生成此摘要的其中一个原文即可。

设MD5的哈希函数是H(X),那么:

H(A) = M

H(B) = M

任意一个B即为破解结果。

B有可能等于A,也可能不等于A。

暴力枚举法:

枚举出所有原文,并计算哈希值,看看哪个哈希值和给定的信息摘要一致。

时间复杂度极高,可以取巧,优先尝试生日或者其他有意义的单词。

字典法:

字典法用空间换时间。存储尽可能多的原文和对应的哈希值。每次用给定的信息摘要查找字典,即可快速找到碰撞的结果。

彩虹表法:

时间和空间的取舍,存储空间是全量字典的K分之一,代价是破解一个摘要的运算次数提高了K倍。

H(X):生成信息摘要的哈希函数,比如MD5,比如SHA256。

R(X):从信息摘要转换成另一个字符串的衰减函数(Reduce)。其中R(X)的定义域是H(X)的值域,R(X)的值域是H(X)的定义域。但要注意的是,R(X)并非H(X)的反函数。

通过交替运算H和R若干次,可以形成一个原文和哈希值的链条。假设原文是aaaaaa,哈希值长度32bit,那么哈希链表就是下面的样子:

这个链条有多长呢?假设H(X)和R(X)的交替重复K次,那么链条长度就是2K+1。同时,我们只需把链表的首段和末端存入哈希表中:

 

给定信息摘要:920ECF10

如何得到原文呢?只需进行R(X)运算:

R(920ECF10) = kiebgt

查询哈希表可以找到末端kiebgt对应的首端是aaaaaa,因此摘要920ECF10的原文“极有可能”在aaaaaa到kiebgt的这个链条当中。

接下来从aaaaaa开始,重新交替运算R(X)与H(X),看一看摘要值920ECF10是否是其中一次H(X)的结果。从链条看来,答案是肯定的,因此920ECF10的原文就是920ECF10的前置节点sgfnyd。

需要补充的是,如果给定的摘要值经过一次R(X)运算,结果在哈希表中找不到,可以继续交替H(X)R(X)直到第K次为止。

要尽量把R(X)设计成结果均匀发布的函数,但是再完美的函数也难免会有碰撞的情况。

给定信息摘要:FB107E70

经过多次R(X),H(X)运算,得到结果kiebgt

通过哈希表查找末端kiebgt,可以找出首端aaaaaa

但是,FB107E70并不在aaaaaa到kiebgt的哈希链条当中,这就是R(X)的碰撞造成的。

这个问题看似没什么影响,既然找不到就重新生成一组首尾映射即可。但是想象一下,当K值较大的时候,哈希链很长,一旦两条不同的哈希链在某个节点出现碰撞,后面所有的明文和哈希值全都变成了一摸一样的值。这样造成的后果就是冗余存储。原本两条哈希链可以存储 2K个映射,由于重复,真正存储的映射数量不足2K。

彩虹表对哈希链进行了改进,把原先的R(X)函数改进成从R1(X)到Rk(X)一共k个衰减函数。

 

目录
相关文章
|
6月前
|
算法 Java 数据处理
Java中MD5加密算法的实现
Java中MD5加密算法的实现
|
3月前
|
算法 数据安全/隐私保护 C++
超级好用的C++实用库之MD5信息摘要算法
超级好用的C++实用库之MD5信息摘要算法
92 0
|
4月前
|
JavaScript 算法 前端开发
国标哈希算法基础:SHA1、SHA256、SHA512、MD5 和 HMAC,Python和JS实现、加盐、算法魔改
国标哈希算法基础:SHA1、SHA256、SHA512、MD5 和 HMAC,Python和JS实现、加盐、算法魔改
631 1
|
4月前
|
算法 JavaScript 前端开发
消息摘要算法:MD5加密
消息摘要算法:MD5加密
67 1
|
5月前
|
算法 安全 Java
Java中MD5加密算法的原理与实现详解
Java中MD5加密算法的原理与实现详解
|
6月前
|
存储 安全 算法
三种常见的加密算法:MD5、对称加密与非对称加密的比较与应用
网络安全聚焦加密算法:MD5用于数据完整性校验,易受碰撞攻击;对称加密如AES快速高效,密钥管理关键;非对称加密如RSA提供身份验证,速度慢但安全。三种算法各有所长,适用场景各异,安全与效率需权衡。【6月更文挑战第17天】
1083 2
|
6月前
|
存储 算法 NoSQL
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
233 1
|
5月前
|
算法 安全 数据安全/隐私保护
支付系统---微信支付09------数字签名,现在Bob想要给Pink写一封信,信件的内容不需要加密,怎样能够保证信息的完整性,使用信息完整性的主要手段是摘要算法,散列函数,哈希函数,H称为数据指纹
支付系统---微信支付09------数字签名,现在Bob想要给Pink写一封信,信件的内容不需要加密,怎样能够保证信息的完整性,使用信息完整性的主要手段是摘要算法,散列函数,哈希函数,H称为数据指纹
|
5月前
|
算法 Java 数据处理
Java中MD5加密算法的实现
Java中MD5加密算法的实现
|
6月前
|
存储 算法 安全
MD5哈希算法:原理、应用与安全性深入解析
MD5哈希算法:原理、应用与安全性深入解析