MD5 加密算法改进及其特征码在杀毒软件中的应用

贾晓强

（渭南师范学院数学与信息科学学院信息工程系， 陕西 渭南 714099）

随着计算机网路技术和网络通信技术[1]的应用广泛应用， 各种数据信息尤其是关系到用户利益的敏感数据与Internet 联系日益增强，云计算以及大数据时代的到来，企业网建设，数据存储和传输安全引起了更为广大的关注。 在人们感受到网路通信带给自己生活以及工作便利的同时，出现了一系列的与网络信安全相关的问题，用户敏感数据的安全关系到用户的切身利益。Message-Digest Algorithm 5（MD5）是一种被广泛使用的散列算法。 此算法用来确保信息在网络传输中的完整性，和一致性。 也被叫做哈希算法，或者摘要算法等。 散列算法的基本原理是：将数据，或者一段字符经过一系列的变化运算，移位运算变为另一种特定的长度。MD2、MD3、MD4 都是MD5 的前身。 为了减小碰撞的概率和其安全性，必须对它进行改进。

1 MD5 加密算法的安全性分析及改进

1.1 MD5 加密算法的原理

在MD5 算法中，开始需要对信息进行补充，使其字节长度对512 取余数的结果为448。 必须保证所有的信息对512取余数的结果为448 这样就需要对与512 取余结果不为448的数进行填充，填充的值为“1”以及若干个0 附加在消息的末尾。然后将消息要以512 bit 分为许多组，分组之后，再将分组后的数据分别使用MD5 进行加密[2]。然后将每组512 bit 的数据分为16 个32 位的分组[3]，接着将每个32 位的分组作为目标数据进行一系列的计算。

在进行运算之前，首先要把消息进行分组，输入的消息要以512 bit 分为许多组，分组之后，再将分组后的数据分别使用MD5 进行加密。 然后将每组分为16 个32 位的分组，接着进行一系列的计算。 最后的记过有4 组，分别都是32 位的分组成员， 然后见不过4 组成员链接成为一个128 bit 的值。即就是一个32 位的字符串。

第一步：消息的填充

在MD5 算法中，开始需要对信息进行补充，使其字节长度对512 取余数的结果为448。 必须保证所有的信息对512 取余数的结果为448 这样就需要对与512 取余结果不为448 的数进行填充，填充的值为“1”以及若干个0 附加在消息的末尾。

第二步:记录消息长度

在上一步填充处理的基础上， 附上64 比特的填充前消息长度的二进制表示.（将填充前的信息的长度用二进制表示后附在其后作为附加信息以示区别）。

第三步：加载初始标准数据

MD5 算法中含有4 个链变量，在进行运算之前必须将链变量加载进去，4 个链变量加载后才能进行四轮循环的运算，4 个链变量分别为：A=14224567，B=19cbcdef，C=edcba98，D=76543210

第四步：四轮运算

四轮运算，每一轮循环的过程都是一样的，每一轮操作16 次，每次分别对链变量的其中3 个利用提供的非线性函数做一次运算，然后用第4 个变量加上循环所得出的结果。 接着进行文本接下来的一个子分组和另一个常熟的运算，将结果向左进行随机移位。 并加上链变量的任意一个，接着用所得结果替换链变量中的任意一个。 循环的次数是分组的个数（N+1）也就是求模运算的商值加上补齐的一组的512 数据块的数目进行循环，每轮循环都很相似。

通过MD5 算法运算后，可以将任意长度的文件，转换成一个不可逆的整数，此整数非常大长度为128 bit；通常情况下所有的字符组合却有无穷多个，MD5[4]所运算出来的数字值域并不能完全的一对一的表示所有的字符组合。 所以就有可能有多个字符串计算出来的128 bit的特征码是一样的，也即是发生了碰撞。

1.2 MD5 加密算法的改进意见

以下是对Hash 算法的改进策略：加盐值（salt）是最容易实现的一种改进策略，具体做法为，在进行散列计算式时，加入足够长的干扰[6]字符串，这些字符串就被叫做“盐值”。 比较高级的一些盐值常常为一些动态信息。 比如根据时间生成随机数，或者其他随机码[5]等。 这样的做法更大程度上提高了MD5 算法的安全性能。

四轮共计64 次操作，除非线性运算每轮一个不同外，运算规则都很类似。 假设M 消息表示的第J 个子分组，ti 表示加入的盐值，从0 到15，表示循环左移位，则改进后MD5 的四轮运算公式如下：

第一轮

（1）FF（a，b，c，d，M0，7，d76aa478）

（2）FF（d，a，b，c，M1，12，e8c7b756）

（3）FF（c，d，a，b，M2，17，24070db）

（4）FF（b，c，d，a，M3，22，c1bdceee）

（5）FF（a，b，c，d，M4，7，f57c0faf）

（6）FF（d，a，b，c，M5，12，4787c62a）

（7）FF（c，d，a，b，M6，17，a8304613）

（8）FF（b，c，d，a，M7，22，fd469501）

（9）FF（a，b，c，d，M8，7，698098d8）

（10）FF（d，a，b，c，M9，12，8b44f7af）

（11）FF（c，d，a，b，M10，17，ffff5bb1）

（12）FF（b，c，d，a，M11，22，895cd7be）

（13）FF（a，b，c，d，M12，7，6b901122）

（14）FF（d，a，b，c，M13，12，fd987193）

（15）FF（c，d，a，b，M14，17，a679438e）

（16）FF（b，c，d，a，M15，22，49b40821）

（15）GG（c，d，a，b，M7，14，676f02d9）

（16）GG（b，c，d，a，M12，20，8d2a4c8a）

第二轮

（1）GG（a，b，c，d，M1，5，f61e2562）

（2）GG（d，a，b，c，M6，9，c040b340）

（3）GG（c，d，a，b，M11，14，265e5a51）

（4）GG（b，c，d，a，M0，20，e9b6c7aa）

（5）GG（a，b，c，d，M5，5，d62f105d）

（6）GG（d，a，b，c，M10，9，02441453）

（7）GG（c，d，a，b，M15，14，d8a1e681）

（8）GG（b，c，d，a，M4，20，e7d3fbc8）

（9）GG（a，b，c，d，M9，5，21e1cde6）

（10）GG（d，a，b，c，M14，9，c33707d6）

（11）GG（c，d，a，b，M3，14，f4d50d87）

（12）GG（b，c，d，a，M5，20，455a14ed）

（13）GG（a，b，c，d，M13，5，a9e3e905）

（14）GG（d，a，b，c，M2，9，fcefa3f8）

（15）GG（c，d，a，b，M7，14，676f02d9）

（16）GG（b，c，d，a，M12，20，8d2a4c8a）

第三轮

（1）HH（a，b，c，d，M5，4，fffa3942）

（2）HH（d，a，b，c，M8，11，8771f681）

（3）HH（c，d，a，b，M11，16，6d9d6122）

（4）HH（b，c，d，a，M14，23，fde5380c）

（5）HH（a，b，c，d，M1，4，a4beea44）

（6）HH（d，a，b，c，M4，11，4bdecfa9）

（7）HH（c，d，a，b，M7，16，a4beea44）

（8）HH（b，c，d，a，M4，23，bebfbc70）

（9）HH（a，b，c，d，M13，4，289b7ec6）

（10）HH（d，a，b，c，M10，11，eaa127fa）

（11）HH（c，d，a，b，M3，16，d4ef3085）

（12）HH（b，c，d，a，M6，23，04881d05）

（13）HH（a，b，c，d，M9，4，d9d4d039）

（14）HH（d，a，b，c，M12，11，e6db99e5）

（15）HH（c，d，a，b，M15，16，1fa27cf8）

（16）HH（b，c，d，a，M2，23，c4ac5665）

第四轮

（1）II（a，b，c，d，M0，6，f4292244）

（2）II（d，a，b，c，M7，10，432aff97）

（3）II（c，d，a，b，M14，15，ab9423a7）

（4）II（b，c，d，a，M5，21，fc93a039）

（5）II（a，b，c，d，M12，6，65b59c3）

（6）II（d，a，b，c，M3，10，8f0ccc92）

（7）II（c，d，a，b，M10，15，ffeff47d）

（8）II（b，c，d，a，M1，21，85845dd1）

（9）II（a，b，c，d，M8，6，6fa87e4f）

（10）II（d，a，b，c，M15，10，fe2ce6e0）

（11）II（c，d，a，b，M6，15，a3014314）

（12）II（b，c，d，a，M13，21，4e0811a1）

（13）II（a，b，c，d，M4，6，f7537e82）

（14）II（d，a，b，c，M11，10，bd3af235）

（15）II（c，d，a，b，M2，15，2ad7d2bb）

（16）II（b，c，d，a，M9，21，eb86d391）

其中常数tj可以如下选择：

在第i 步中，tj是4296767296*abs（sun（i））的整数部分，i的单位是弧度。（4294967296 等于2 的32 次方）。所有这些完成之后，将A、B、C、D 分别加上a、b、c、d，然后用下一分组数据继续运行算法，最后的输出是A、B、C 和D 的级联。

在这里假设： 要加密的信息为msg， 其比特串为11110101 01101010 01110011

比特串的长度为24 位，于是在其末尾添加1 个“1”，后边全部添加0 直到与512 的余数为448， 再加上64 比特串（24）16=00000000 0000001816（24 位的长度）

即x=10110101 01101011 01100011 1 0…0 10001100 00110018， 共512 比特， 只有16 分组为：M0，M1，M2，M3，M4，M5，M6，M7，M8，M9，M10，M11，M12，M13，M14，M15， 所 以 有M4=M5=M6=M7=M8=M9=M10=M11=M12=M13=M14=00000000

M15=00000018

首先计算出

A=0123456719=0010 0011 1110 0011 0101 0101 0110 0111=a

B=89ABCDEF16=1011 1001 1011 1011 1100 1001 1110 1111=b

C=FEDCBA9816=1001 1110 1101 1100 1011 1010 1001 1000=d

D=7651321016=0001 0110 0101 0100 0011 0010 0001 0110=d

其次计算F（b，c，d）=（b∧c）|（b∧d）

=（1011 1011 1010 1011 1100 1101 1110 1100 1100 1110 1101 1100 1011 1010 1001 1011）|（0110 0110 0101 0100 0011 0010 0001 00000111 0110 0101 0100 0011 0010 1001 0000 =（1000 1110 1000 1010 1000 1110 1110 1000）|（0111 0110 0101 0111 0011 0010 0001 1100）=1111 1110 1101 1100 1011 1010 1001 1000

d76aa47816转换为二进制为1001 0100 0110 1010 1010 0100 0111 1011

FF（a，b，c，d，M0，d76aa478）结果为

a=b+（（a+（F（b，c，d）+M0+t0）＜＜7））

=（1011 1011 1010 1011 1100 1101 1110 1111）+（（0110 0101 0010 0011 0100 0101 0110 0011+1001 1110 1101 1100 1011 1010 1001 1000+0000 0111 1101 0000 0110 0110 0001 0011）+1101 0111 0110 1010 1010 0110 0111 1110）＜＜7）

=（1110 1001 1010 1011 1100 1101 1110 1100）+（（0110 0110 0011 1100 1000 0000 0110 1110+1101 0111 0110 1010 1010 0100 0111 1111）＜＜7）

=（1001 1111 1010 1010 1100 1101 1110 1001）+（1101 0111 1111 0010 1010 0110 1010 1111＜＜7）

=（1011 1011 1011 1011 1100 1101 1110 1001）+（0011 1111 1010 1111 0100 0101 0110 1011）=1001 1001 0101 1011 0001 0011 0011 1011=3551133116.

其他函数计算相似。

1.3 MD5 算法改进后的安全性分析

改进后的MD5 算法，可以将任意长度的文件，转换成一个不可逆的整数，此整数非常大长度为128 bit；但是源字符串有可能有无穷多个，128 bit 的大整数只可以表示2 的128 次方的字符串。 所以就有可能有多个字符串计算出来的128 bit的特征码是一样的，也就是发生了碰撞。 也有一些黑客，为了获取密码，使用一种叫做“跑字典”[3]的方法，他们通过搜集常用密码字符串表或者使用排列组合的放大获取字典。 改进后的MD5 算法可以较好的预防通过“跑字典”来获取密码。

1.4 MD5 算法改进后性能分析

加盐值提高加密的可靠性有以下特点：

1）算法结构不用改变，继承了原有算法的稳定性。

2）算法的时间复杂度并没有因为算法的改进而增加（四轮共进行了64 次运算算法复杂度T（n）=O（n）。

3）密码被破译的难度大大增加，穷举耗时更长，很大程度上提升了加密算法的安全性。

4）增加了参数之后，哈希函数的碰撞概率更近一步减小了，由于T 是根据文件时间动态生成的，在原消息摘要加上T再进行哈希运算，其计算空间加大，对原消息的保护强度大大增强。

2 MD5 应用现状以及MD5 特征码原理的杀毒软件的实现

2.1 MD5 的一个实际应用：MD5 特征码原理的杀毒软件

主要功能模块如下：

1）MD5 算法函数的实现与封装

2）配置文件的生成和排序

3）文件的全盘扫描及MD5 值的匹配

4）病毒文件的删除以及病毒进程的结束

5）文件完整性检测模块

2.2 算法流程图

加入盐值后，算法的流程图如图1 所示。

2.3 杀毒软件测试

图1 MD5 算法流程图Fig. 1 Flow chart of MD5 algorithm

根据MD5 码的特征，构造了MD5 特征库配置文件，配置文件如图2 所示。 通过遍历匹配MD5 值，能成功的删除可疑文件。 测试效果如图3、图4 所示。

图2 MD5 特征库配置文件Fig. 2 MD5 feature library configuration file

图3 软件功能截图Fig. 3 The software function screenshot

图4 遍历匹配MD5 值Fig. 4 Traversal matching MD5 value

3 结 论

从MD5 算法的诞生、发展、破解危机入手，研究了MD5算法的原理及其实际应用意义，并对其做了改进，在不改变时空复杂度的情况下，增强了算法的安全性，并通过MD5 特征码将其应用在杀毒软件中。

[1] 廖海生，赵跃龙. 基于MD5算法的重复数据删除技术的研究与改进[J]. 计算机测量与控制，2010，18（3）:635-638.

LIAO Hais-heng，ZHAO Yue-long. The research and improvement of MD5 algorithm of Based on the deduplication[J].Computer Measurement and Control，2010，18（3）:635-638.

[2] 张裔智，赵毅，汤小兵. MD5 算法研究[J]. 计算机科学，2008，38（7）:295-297.

ZHANG Yi-zhi，ZHAO Yi，TANG Xiao-bing. The research of MD5 algorithm[J]. Journal of Computer Science，2008，38（7）:295-297.

[3] 陈少晖，翟晓宁，阎娜. MD5 算法破译过程解析[J]. 计算机工程与应用，2010，46（19）:100-101.

CHEN Shao-hui，ZHAI Xiao-ning，YAN Na. The MD5 algorithm decoding process analysis[J]. Computer Engineering and Application，2010，46（19）:100-101.

[4] 王衍波，薛通.应用密码学[M].北京：机械工业出版社，2013.

[5] 毛熠，陈娜. MD5算法的研究与改进[J].计算机工程，2012，38（24）:112-114.

MAO Yi，CHEN Na. Research and improvement of the MD5 algorithm[J]. Computer Engineering，2012，38（24）:112-114.

[6] 周林，王政，韩文报. MD5 差分和差分路径的自动化构造算法[J]. 四川大学学报:工程科学版，2010，42（6）:133-137.

ZHOU Lin，WNAG Zheng，HAN Wen-bao. automation construction algorithm of MD5 difference and the difference path [J]. Journal of sichuan university:engineering science，2010，42（6）:133-137.