MD5消息摘要算法

一、MD5算法简介

1.1 MD5特点  

    MD5（Message Digest Algorithm 5）中文名为消息摘要算法第五版，是计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。MD5作为一种常用的摘要算法（或指纹算法），其具有以下几个重要的特点：

• a. 输入任意长度信息，输出长度固定：MD5 可输入任意长度的信息，其输出均为128位(bit)固定长度的二进制数据。
• b. 运算速度快：MD5的运算均为32位 与、或、非、位移等位运算，因此其运算速率快，几乎不消耗CPU时间。
• c. 不可逆：根据MD5的的散列结果，无法计算出原始数据（查字典除外）。
• d. 碰撞性：原始数据与其MD5散列结果并非一一对应，存在多个原始数据的MD5结果相同的可能性。
• e. 不安全：2011年，RFC 6151 禁止MD5用作密钥散列消息认证码。

1.2 MD5长度与不安全 

  长度：MD5散列结果是128位(bit)固定长度的二进制数据，也就是128个0/1的二进数据。用128位二进制数据呈现MD5的散列结果，对于软件开发者很不友好。一般将二进制转成16进制，每4个二进制数据转化为一个16进制数据，128位二进制数据转化为32个十六进制数据（128/4 = 32），最终以字符串形式呈现十六进制数据后则为长度为32的字符串。

  不安全：2011年，RFC 6151 禁止MD5用作密钥散列消息认证码。

• a.MD5不安全主要指的是，不可再用MD5对原始秘钥进行加密：比如：将用户的登录秘钥进行MD5加密后，存储于数据库中。MD5虽然理论上不可逆，但有些黑客网站通过查字典方式获取MD5原文信息。提前将一些比较常见的密文做MD5运算，将结果保存下来，破译密文时，通过MD5摘要信息直接查询原文。
  比如：字符串 123 的MD5值是 202cb962ac59075b964b07152d234b70 ，黑客在破解后的数据库中看到某位用户的密码是 202cb962ac59075b964b07152d234b70 ，通过字典一查就知道密码明文是 123 了。

• b. MD5的碰撞性，决定了存在两个不用的输入信息，其MD5相同的可能。
  2009年，中国科学院的谢涛和冯登国仅用了 2的20.96次幂 的碰撞算法复杂度，破解了MD5的碰撞抵抗，该攻击在普通计算机上运行只需要数秒钟。

1.3 MD5用途

　　（1）一致性验证

　　MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。比如，在Unix下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如：
MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461
这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。为了让读者朋友对MD5的应用有个直观的认识，笔者以一个比方和一个实例来简要描述一下其工作过程：
　　大家都知道，地球上任何人都有自己独一无二的指纹，这常常成为司法机关鉴别罪犯身份最值得信赖的方法；与之类似，MD5就可以为任何文件（不管其大小、格式、数量）产生一个同样独一无二的“数字指纹”，如果任何人对文件做了任何改动，其MD5值也就是对应的“数字指纹”都会发生变化。
　　我们常常在某些软件下载站点的某软件信息中看到其MD5值，它的作用就在于我们可以在下载该软件后，对下载回来的文件用专门的软件（如Windows MD5 Check等）做一次MD5校验，以确保我们获得的文件与该站点提供的文件为同一文件。利用MD5算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。
　　（2）数字证书
　　MD5的典型应用是对一段Message(字节串)产生fingerprint(指纹）， 以防止被“篡改”。举个例子，你将一段话写在一个叫 readme.txt文件中，并对这个readme.txt产生一个MD5的值并记录在案，然后你可以传播这个文件给别人，别人如果修改了文件中的任何内 容，你对这个文件重新计算MD5时就会发现（两个MD5值不相同）。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的“抵赖”，这就是所谓的 数字签名应用。
　　（3）安全访问认证
　　MD5还广泛用于操作系统的登陆认证上，如Unix、各类BSD系统登录密码、数字签名等 诸多方面。如在Unix系统中用户的密码是以MD5（或其它类似的算法）经Hash运算后存储在文件系统中。当用户登录的时候，系统把用户输入的密码进行 MD5 Hash运算，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可 以确定用户登录系统的合法性。这可以避免用户的密码被具有系统管理员权限的用户知道。MD5将任意长度的“字节串”映射为一个128bit的大整数，并且 是通过该128bit反推原始字符串是困难的，换句话说就是，即使你看到源程序和算法描述，也无法将一个MD5的值变换回原始的字符串，从数学原理上说，是因为原始的字符串有无穷多个，这有点象不存在反函数的数学函数。所以，要遇到了md5密码的问题，比较好的办法是：你可以用这个系统中的md5（）函数 重新设一个密码，如admin，把生成的一串密码的Hash值覆盖原来的Hash值就行了。
　　正是因为这个原因，现在被黑客使用最多的一种破译密码的方法就是一种被称为"跑字典"的方法。有两种方法得到字典，一种是日常搜集的用做密码的字符串表，另一种是用排列组合方法生成的，先用MD5程序计算出这些字典项的MD5值，然后再用目标的MD5值在这个字典中检索。我们假设密码的最大长度为8位字节（8 Bytes），同时密码只能是字母和数字，共26+26+10=62个字符，排列组合出的字典的项数则是 P（62,1）+P（62,2）….+P（62,8），那也已经是一个很天文的数字了，存储这个字典就需要TB级的磁盘阵列，而且这种方法还有一个前提，就是能获得目标账户的密码MD5值的情况下才可以。这种加密技术被广泛的应用于Unix系统中，这也是为什么Unix系统比一般操作系统更为坚固一个重要原因。

二、MD5算法原理

2.1 算法流程

  MD5 摘要算法大概计算过程可以描述如下：

  a. MD5 将 “输入信息” 分为N*512bit的数据分组；
  b. 每一512bit分组又分为16个子分组，每个子分组为32bit的原始数据；      16个子分组分别命名为 M0~M15；
  c. 每个子分组都要进行4次运算，运算公式分别为FF、GG、HH、II；总的运算次数为N*16*4（运算均为位运算）。

    以上为MD5 摘要算法的大概原理总结，下边按照 rfc1321 中算法的介绍顺序，梳理MD5 摘要算法：

2.2 初始化A、B、C、D

    这里需要初始化四个数据 A、B、C、D，这四个变量将用于后续的公式计算。
四个数据均为8个16进制数据组合，每个16进制数据为4bit，每个数据占32bit。

// 每个数据占空间 32bit 
// 四个数据分别为 8个 16进制数据的组合构成
// 单个16进制数据占空间 4bit
A: 01 23 45 67 （16进制）
B: 89 ab cd ef （16进制）
C: fe dc ba 98 （16进制）
D: 76 54 32 10 （16进制）

    将A、B、C、D输入计算机进行计算时，A、B、C、D将变化为：

A: 0x67452301
B: 0xefcdab89
C: 0x98badcfe
D: 0x10325476

为什么会变化为 0x67452301、0xefcdab89、0x98badcfe、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.3 分组数据运算

    上文层提到子分组的运算公式：FF、GG、HH、II ，32bit子分组的运算公式如下：

// FF、GG、HH、II
// <<< 为循环左移
FF(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)
HH(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. 公式中初始输入数据a、b、c、d 为A、B、C、D

• b. Mj 代表32bit子分组数据，每个子分组数据均需要经过 FF、GG、HH、II 四次运算：
  c. 512bit原始输入数据，有16个子分组，每个分组进行4次运算，总共16 * 4 = 64次运算。

• d. s 常量数据，代表循环左移的位数。

• e. ti 常量；

  f. 四个非线性函数(逻辑运算)：
  

    512bit分组数据，64 次位运算如下（输入数据为32bit原始数据，输出为32bit数据）：

// 512bit分组数据，16 * 4 次运算
// 输入数据为32bit原始数据，输出为32bit数据
// 第一次运算FF
a = FF(a, b, c, d, M0, 7, 0xd76aa478L);
d = FF(d, a, b, c, M1, 12, 0xe8c7b756L);
c = FF(c, d, a, b, M2, 17, 0x242070dbL);
b = FF(b, c, d, a, M3, 22, 0xc1bdceeeL);
a = FF(a, b, c, d, M4, 7, 0xf57c0fafL);
d = FF(d, a, b, c, M5, 12, 0x4787c62aL);
c = FF(c, d, a, b, M6, 17, 0xa8304613L);
b = FF(b, c, d, a, M7, 22, 0xfd469501L);
a = FF(a, b, c, d, M8, 7, 0x698098d8L); 
d = FF(d, a, b, c, M9, 12, 0x8b44f7afL);
c = FF(c, d, a, b, M10, 17, 0xffff5bb1L);
b = FF(b, c, d, a, M11, 22, 0x895cd7beL);
a = FF(a, b, c, d, M12, 7, 0x6b901122L);
d = FF(d, a, b, c, M13, 12, 0xfd987193L);
c = FF(c, d, a, b, M14, 17, 0xa679438eL);
b = FF(b, c, d, a, M15, 22, 0x49b40821L);

// 第二轮运算GG
a = GG(a, b, c, d, M1, 5, 0xf61e2562L);
d = GG(d, a, b, c, M6, 9, 0xc040b340L);
c = GG(c, d, a, b, M11, 14, 0x265e5a51L);
b = GG(b, c, d, a, M0, 20, 0xe9b6c7aaL);
a = GG(a, b, c, d, M5, 5, 0xd62f105dL);
d = GG(d, a, b, c, M10, 9, 0x2441453L);
c = GG(c, d, a, b, M15, 14, 0xd8a1e681L);
b = GG(b, c, d, a, M4, 20, 0xe7d3fbc8L);
a = GG(a, b, c, d, M9, 5, 0x21e1cde6L);
d = GG(d, a, b, c, M14, 9, 0xc33707d6L);
c = GG(c, d, a, b, M3, 14, 0xf4d50d87L);
b = GG(b, c, d, a, M8, 20, 0x455a14edL);
a = GG(a, b, c, d, M13, 5, 0xa9e3e905L);
d = GG(d, a, b, c, M2, 9, 0xfcefa3f8L);
c = GG(c, d, a, b, M7, 14, 0x676f02d9L);
b = GG(b, c, d, a, M12, 20, 0x8d2a4c8aL);

// 第三轮运算HH
a = HH(a, b, c, d, M5, 4, 0xfffa3942L);
d = HH(d, a, b, c, M8, 11, 0x8771f681L);
c = HH(c, d, a, b, M11, 16, 0x6d9d6122L);
b = HH(b, c, d, a, M14, 23, 0xfde5380cL);
a = HH(a, b, c, d, M1, 4, 0xa4beea44L);
d = HH(d, a, b, c, M4, 11, 0x4bdecfa9L);
c = HH(c, d, a, b, M7, 16, 0xf6bb4b60L);
b = HH(b, c, d, a, M10, 23, 0xbebfbc70L);
a = HH(a, b, c, d, M13, 4, 0x289b7ec6L);
d = HH(d, a, b, c, M0, 11, 0xeaa127faL);
c = HH(c, d, a, b, M3, 16, 0xd4ef3085L);
b = HH(b, c, d, a, M6, 23, 0x4881d05L);
a = HH(a, b, c, d, M9, 4, 0xd9d4d039L);
d = HH(d, a, b, c, M12, 11, 0xe6db99e5L);
c = HH(c, d, a, b, M15, 16, 0x1fa27cf8L);
b = HH(b, c, d, a, M2, 23, 0xc4ac5665L);

// 第四轮运算II
a = II(a, b, c, d, M0, 6, 0xf4292244L);
d = II(d, a, b, c, M7, 10, 0x432aff97L);
c = II(c, d, a, b, M14, 15, 0xab9423a7L);
b = II(b, c, d, a, M5, 21, 0xfc93a039L);
a = II(a, b, c, d, M12, 6, 0x655b59c3L);
d = II(d, a, b, c, M3, 10, 0x8f0ccc92L);
c = II(c, d, a, b, M10, 15, 0xffeff47dL);
b = II(b, c, d, a, M1, 21, 0x85845dd1L);
a = II(a, b, c, d, M8, 6, 0x6fa87e4fL);
d = II(d, a, b, c, M15, 10, 0xfe2ce6e0L);
c = II(c, d, a, b, M6, 15, 0xa3014314L);
b = II(b, c, d, a, M13, 21, 0x4e0811a1L);
a = II(a, b, c, d, M4, 6, 0xf7537e82L);
d = II(d, a, b, c, M11, 10, 0xbd3af235L);
c = II(c, d, a, b, M2, 15, 0x2ad7d2bbL);
b = II(b, c, d, a, M9, 21, 0xeb86d391L);

2.4 结果累加

    若A、B、C、D为变量，并且A、B、C、D的初始化信息为 A: 0x67452301；B: 0xefcdab89；C: 0x98badcfe；D: 0x10325476 ，每一512bit分组的运算结果为a、b、c、d。则第N个512bit组的计算结果为：

// a、b、c、d 为每一512bit分组的运算结果；
// A、B、C、D 是下一组计算的输入参数；
// 若无下一个512bit分组 A、B、C、D 则为最终计算结果；
A = a + A;  
B = b + B; 
C = c + C; 
D = d + D;

参考文献

https://zhuanlan.zhihu.com/p/557034655?utm_id=0

原文始发于微信公众号（豆豆咨询）：MD5消息摘要算法