MD5算法改进及其应用研究

摘 要：哈希算法是现代密码学的核心，本文在给出MD5常见优化算法的基础上，采取两种思路对MD5进行改进，并对改进结果进行对比。同时对算法的应用场合及其应用效果进行了研究。 关键词：MD5；802.1X；EAP-MD5

MD5 Research

CUI Yonghui1 JIA Lianxing2 LI Zhiwei3

Abstract:

The HASH algorithm is the core of modern cryptography. The paper presents the common optimization algorithm

based on MD5, and takes two means of improvement with programming on MD5 algorithm. We can make an intuitive understanding of the algorithm with the comparisons.At last, the application situation and the application effect of the algorithm are studied in this paper.

Keywords: MD5; 802.1X; EAP-MD5

0.MD5算法

MD5算法[1]对任意长度的文件进行不可逆变换，是按照固定的循环和计算对源数据信息进行加密，最终生成128位的加密数据。由于整个过程计算量比较大，而且过程非常繁琐，所以在算法实现时，会耗费大量的时间。

目前对MD5算法的研究及性能优化方法较多[2][3][4]，主要体现在增强其加密强度和提高它的执行效率两个方面。通常考虑通过以下手段加以改进：一是改变MD5初始数值。把4个MD缓冲寄存器初始数值稍微更改，形成新消息摘要算法。二是改变sin函数值。算法中，sin函数从0开始每次累加1，可以更改为从64开始每次累减1，或者变sin函数为cos函数，变动的程序较易修改，也具有较好的移植性。三是多次加密。实行单次消息摘要算法加密之后，针对产生的密码所有或者一些再次实行单次或者多次修改，使其更难在字典中快速查找。四是查询库添加盐(salt)。客户设置密码过程中，产生随机盐（Salt），储存于另外的信息表或者查询库内，和客户口令彼此联系，之后使用hash函数针对盐（Salt）实行消息摘要算法加密，进而使逆向查询更难。 1算法改进

一是精简迭代次数，为了提高其执行效率，降低MD5算法复杂度，可以适当精简

MD5迭代次数64步至16步。MD5算法中的每一轮输入为当前处理的分组和128bit的缓存区ABCD，每轮都需要进行16步操作，四轮中可以以不同顺序使用分组的16位字。精

11114(C?C?C?C444)?16777216种，本文挑选的MD5迭代次数有两简迭代次数的方案共有4个方案，一个为主方案，另一个为备用方案。

方案一对应的挑选步次为： 第1轮：

FF(a,b,c,d,M0,7,0xd76aa478)????1FF(d,a,b,c,M1,12,0xe8c7b756)????2FF(c,d,a,b,M2,17,0x242070db)????3FF(b,c,d,a,M3,22,0xc1bdceee)????4

第2轮：

GG(d,a,b,c,M6,9,0xc040b340)????18GG(a,b,c,d,M5,5,0xd62f105d)????21GG(b,c,d,a,M4,20,0xe7d3fbc8)????24GG(c,d,a,b,M7,14,0x676f02d9)????31

第3轮：

HH(d,a,b,c,M8,11,0x8771f681)????34HH(c,d,a,b,M11,16,0x6d9d6122)????35HH(b,c,d,a,M10,23,0xbebfbc70)????40HH(a,b,c,d,M9,4,0xd9d4d039)????45

第4轮：

II(c,d,a,b,M14,15,0xab9423a7)????51II(a,b,c,d,M12,6,0x655b59c3)????53II(d,a,b,c,M15,10,0xfe2ce6e0)????58II(b,c,d,a,M13,21,0x4e0811a1)????60

方案二对应的挑选步次为

【2,3,4,5， 18,31,28,25， 35,46,41,36， 49,52,55,58】

二是嵌入汇编语言。实际上，嵌入汇编语言，实质是为了减少对内存的访问，提高代码执行效率，使数据在寄存器内部完成快速访问，而不需要反复访问内存。MD5C的代码虽然效率不高，但绝对优秀。一般而言，逻辑运算和四则运算的平均指令周期为4，而内存访问指令平均周期为10，内存访问指令将大大消耗程序访问时间。编程用到的寄存

器共有EAX、EBX、ECX、EDX、ESI、EDI、MM1-MM7共计13个寄存器，剩余的数据读取仍然在内存中加以实现。

通过编程查看改进后MD5算法的性能，并进行对比，包含四个算法实现。第一种算法是标准MD5 C++语言算法；第二种算法为减少迭代次数到16步的C++语言改进算法；第三种算法为嵌入汇编语言的MD5改进算法；第四种算法为嵌入汇编语言并减少迭代次数至16步的MD5改进算法。时间的取得是通过GetCpuTimeTickCount()函数取得。

图一：算法改进一

图二：算法改进二

Figure 1: MD5 algorithm with C++ Figure 2: The first improment

图三：算法改进三

图四：算法改进四

Figure 3: The second improment Figure 4: The third improment

通过以上运算结果，可以看到：

1、第一种优化算法字符串“abc”的散列值发生了改变，单次运算结果比优化前有了改进，10万次运算结果比优化前提高了约1/8的时间效率。

2、第二种优化算法字符串“abc”的散列值并没有发生改变，单次运算结果比优化前有了改进，10万次运算结果比优化前提高了约20倍。