MD5算法全解析

前言

这段时间刚好正在做软件安全的实验和课设，学习了各种加密算法，比如对称加密算法的DES,AES；非对称加密算法的RSA；再如今天要讲的主角-单向加密算法的MD5。为什么这么多算法，MD5成为了今天的猪脚呢？，这是因为个人感觉在目前Android开发中MD5算是比较常用的，所以很值得一讲。所以今天让我带你们来全面认识我们的主角MD5。

一、基本概念

1. 单向加密算法

在介绍MD5算法前，很有必要解释一下单向加密算法。单向加密，人如其名，就是只能单向对明文进行加密，而不能逆向通过密文得到明文。该算法在加密过程中，在得到明文后，经过加密算法得到密文，不需要使用密钥。因为没有密钥，所以就无法通过密文得到明文。

2. MD5算法

MD5,全称Message Digest Algorithm 5，翻译过来就是消息摘要算法第5版，是计算机安全领域广泛使用的一种散列函数，用于确保信息传输的完整性。MD5算法是由MD2、MD3、MD4演变而来，是一种单向加密算法，一种不可逆的加密方式。

二、特点

1.长度固定

不过多长的数据，经过MD5加密后其MD5值长度都是固定的。MD5值长度固定为128位，而最后的值一般都用16进制数字表示，一个16进制数字占4位，所以最后的MD5值都是用32个16进制数字表示。

2.计算简单

MD5算法说到底还是散列算法，或者叫做哈希算法，所以计算一个数据的MD5值是比较容易的，同时加密速度也是很快的。

3.抗修改性

对原数据进行任何改动，哪怕只是修改1个字节，所得到的MD5值都有很大的区别。

4.强抗碰撞性

已知原数据和其MD5值，很难找到具有相同MD5值的数据，即很难伪造数据。这里的碰撞在后面的安全性中会提到，在这里我们简单理解为一种破解手段。

三、原理

1.填充数据

首先计算数据长度（bit）对512求余的结果，如果不等于448，就需要填充数据使得数据长度对512求余的结果为448，其填充方式为第一位填充1，其余位填充0.填充后数据长度为512*N+448。

2.记录数据长度

用64位来存储填充前数据的长度，这64位将加在填充后数据的后面，这样最终的数据长度为512*N+448+64=(N+1)*512

3.装入标准幻数

标准幻数其实就是4个整数，我们知道最终的MD5值长度为128位，按32位分成一组的话可以分成4组，而这4组结果就是由这4个标准幻数A,B,C,D经过不断演变得到。在MD5官方的实现中，四个幻数为（16进制）：

A=01234567
B=89ABCDEF
C=FEDCBA98
D=76543210 

其实上面是大端字节序的幻数，而在正常程序中，我们实现的是小端字节序，所以在程序中我们定义的幻数应该是：

A=0X67452301
B=0XEFCDAB89
C=0X98BADCFE
D=0X10325476 

4.四轮循环运算

在上面对数据处理后，数据长度将是（N+1）/512,我们将每512位（64字节）作为一块，总共要循环N+1次，并将块细分为16个小组，每组的长度为32位（4字节），这16个小组即为一轮，总共得循环4轮，即64次循环。总的来说我们需要（N+1）个主循环，每个主循环包含了64次子循环，来不断的改变幻数A,B,C,D才能最终得到数据的MD5值。

4.1 相关系数说明

1）4个非线性函数

• 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))

在4轮循环中，F,G,H,I会交替使用，第一轮使用F,第二轮使用G,第三轮使用H，第四轮使用I。即每隔16次循环会换一个函数。

2）Mi

将每一块512位分成16等分，命名为M0~M15,每一等份长度为32位16次循环中，交替使用

1. Kj

常量数组，在64子循环中用到的常量都是不同的

1. s

左移量，每轮循环用的S各不相同，每轮总共有4个左移量，每4次循环为一周期

4.2 核心公式

总共有四个核心公式，与4个非线性函数一一对应，即每轮使用的核心公式里的公式有差异。

• **FF(a,b,c,d,Mi,s,Kj)**：表示b+((a+F(b,c,d)+Mi+Kj)<<<s)

• **GG(a,b,c,d,Mi,s,Kj)**：表示b+((a+G(b,c,d)+Mi+Kj)<<<s)

• **HH(a,b,c,d,Mi,s,Kj)**：表示b+((a+H(b,c,d)+Mi+Kj)<<<s)

• **II(a,b,c,d,Mi,s,Kj)**：表示b+((a+I(b,c,d)+Mi+Kj)<<<s)

四、算法实现