基于迭代置换的MD5改进算法

曾凌静，黄金凤

（福建船政交通职业学院 信息工程系，福建 福州 350004）

基于迭代置换的MD5改进算法

曾凌静，黄金凤

（福建船政交通职业学院 信息工程系，福建 福州 350004）

针对目前网络安全中，数据加密技术存在加密强度、运算量大等缺陷，提出了一种基于迭代置换的MD5改进算法。首先将MD5以512位的分组来处理输入的信息，然后每一分组又被划分成为16个32位的子分组，经过了填充、加长、分块、迭代、置换5个步骤，输出由8个64位的分组，最后将这8个64位的分组结合后映射生成一个256位散列值。改进后的MD5算法与已有的算法对比，更加有效地保证了用户的密码安全。

MD5算法；单向散列函数；迭代置换；密码；安全

随着网络通信技术和Internet的联系日益增强，出现了一系列与网络安全相关的问题。虽然目前已有很多加密技术应用于各个领域，但是存在加密强度、运算量大等缺陷。传统的MD5算法加密完是128位散列值，通过对MD5算法加密研究和改进，然后每个两次加密加起来成为一个新的算法，长度也比原来增加一倍，变成256散列值。本文提出了一种改进的MD5加密算法，使更加的复杂，使信息更加的安全[1]。MD5的全称是Message-Digest Algorithm 5（信息-摘要算法），早在20世纪90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L.Rivest开发出来。MD5加密算法是一种免费的加密算法，它不但能对信息管理系统加密还广泛的应用于计算机，数据安全传输，数字签名认证等安全领域。针对数据在存储的时候存在大量的安全问题，在现有MD5加密算法基础上，提出了一种改进的MD5数据存储加密策略。同时，针对MD5算法而进行进一步的了解和研究。

1 传统的MD5算法

1.1 传统的MD5算法思想

MD5是对称性加密技术的一种。对MD5算法简要的叙述为：MD5以512位的分组来处理输入的信息，并且每一分组又被划分成为16个32位的子分组，经过了一系列的处理后，算法的输出由4个32位的分组组成，将这4个32位的分组结合后将生成一个128位散列值[2]。

1.2 传统的MD5算法设计思路

首先把一个要加密的文件，存储到内存中，这个文件在内存中是以二进制的形式的存储，将其分成N*512bit加上剩余的末尾段，进行填充变成至512bit，最终长度是512的整数倍，这样就满足后面处理中对信息长度的要求。先取出一个内存中的512bit进行摘要处理，变成16个块的32bit，为公式处理提供数据。定义一个128的散列值为A，B，C，D都是十六进制的数。分别赋值A=a，B=b，C=c，D=d。由公式说明，主循环有四轮，每轮循环都很相似。第一轮进行16次操作。每次操作对a、b、c和d中的其中3个作一次非线性函数运算，然后将所得结果加上第4个变量，文本的一个子分组和一个常数。再将所得结果向左环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。这样A，B，C，D就变成了新的数，重复公式进行16次结束，这时A，B，C，D就成了新数，换下一个公式，每个公式进行16轮，直到64轮结束，输出新的A，B，C，D数，最终的结果取内存中的数据。

1.3 传统的MD5算法存在的不足

目前对于信息系统或者网站系统来说，传统MD5算法的应用主要是在对于用户登录注册时的口令进行加密处理。一般情况下，在用户的密码加密强度不足或者是强度一般时，还是有多种方法对其加密后的密码进行破解的[3]。

一般地，归纳有下面几种方法：MD5加密后为128位，通过伪造软件签名可以攻击MD5算法；使用MD5破解软件设置字典来进行破解[4]；一些在线的MD5值查询网站提供MD5密码值的查询很快获取其密码值；通过社会工程学来获取或者重新设置用户的口令。

以上几点不难看出，随着破解技术的不断更新，对于加密强度不够的MD5加密很难使加密后的密码免于受到破解攻击。

基于上述的问题，为了确保系统的安全性，需要改进MD5加密算法，从而提升系统的安全性[5]。

2 改进后的MD5算法的设计

2.1 改进后的MD5算法思想

对改进后的MD5算法简要的叙述为：MD5以512位的分组来处理输入的信息，并且每一分组又被划分成为16个32位的子分组，经过了一系列的处理后，算法的输出由8个64位的分组组成，将这8个64位的分组结合后将生成一个256位散列值[6]。

2.2 改进后的MD5算法的设计原理

（1）填充

首先需要将信息进行填充，使其位长对512求余后的结果等于448，即使其位长对512求余后的结果等于448，也必须要进行填充。因此，信息的位长将被扩展至N*512+448，N是一个非负整数，N也可以是零。

（2）添加长度

第一步骤：在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。

第二步骤：在这个结果后面附加一个以64位二进制表示的填充前信息长度（单位为Bit），如果二进制表示的填充前信息长度超过64位，则取低64位。

经过这两步的处理，信息的位长=N*512+448+64=(N+1）*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。

（3）将输入文字分成N*512位的块

把输入文字分成N*512位的块。并将第一块的512位放入寄存器中，准备。

（4）初始化链接变量

初始化8个链接变量，分别称之为A，B，C，D，E，F，G，H，它们都是 32位的数字，这些链接变量的初始十六进制数值如表1所示，低字节在前。

表1 初始化变量表

（5）处理块

初始化之后，就开始实际算法了。这是个循环，对消息中多个512位块运行。

① 将八个链接变量复制到八个变量a，b，c，d，e，f，g，h中， 使a=A，b=B，c=C，d=D，e=E，f=F，g=G，h=H。

② 将当前512位块分解成16个子块，每个子块为32位，如图1所示。

③ 主循环一共有4轮，每轮都很相似。每一轮的操作，都要去处理一个块中的16个子块。每一轮的输入如下：(a)16 个子块；(b)变量a，b，c，d，e，f，g，h；(c)常量t，如图 2 所示。

图1 摘要信息分解成N*512位

图2 一轮的数据处理

这4轮中的第1步进行着不同处理，其他步骤是相同的。

总结这4轮的迭代。每一轮输出的中间和最终结果都复制到寄存器abcd中，注：每一轮有16个寄存器。

① 先是对a，b，c，d，e，f，g，h进行一次非线性的函数运算，此运算在 4轮中都不同。

②把变量a加入第1步的输出中。

③ 把消息子块M[i]加入第2步的输出中。④ 把常量t[i]加入第3步输出中。

⑤将第4步的输出循环向左移s位。⑥ 把变量b加入第5步输出中。

⑦ 下一步的新a，b，c，d，e，f，g，h则是第6步的输出。

以上步骤是MD5执行过程之一，如图3所示。所有步骤加起来就是4个公式的一个，如a=b+((a+(F(b,c,d,e,f,g,h)+Mi+ti)＜＜＜s)， 进过 16 次循环最后输出新的一个新的a，b，c，d，e，f，g，h。 经过 4 轮运算，进行 64次循环，最输出的a，b，c，d，e，f，g，h，即为MD5加密的值。

图3 MD5其中的一个执行过程

有4个线性函数是在以下操作要用到的，简而言之，就是布尔运算。

设计这些函数需要以下做法：如果x，y，z的对应位都是均匀和独立的，那么得出结果之后的每一位也都是均匀和独立的，函数F是通过逐位方式进行操作；如果X，那么Y，否则Z，函数H是按逐位奇偶进行操作。

设消息的第i个子分组(从0到15)是由Mi来表示的。＜＜＜S则表示循环向左移S位，四种操作分别为：

这4轮(即64步，以下列举第一轮的操作，其他3轮同理。

所有这些操作完成之后，将A，B，C，D，E，F，G，H分别加上a，b，c，d，e，f，g，h，然后用下一分组的数据继续运行算法，最后MD5算法产生 256位的输出是A，B，C，D，E，F，G，H的级联，其中低字节始于A，高字节终于H。到此整个MD5算法处理结束[7]。

2.3 改进后的MD5算法设计思路

首先把一个要加密的文件，存储到内存中，这个文件在内存中是以二进制的形式的存储，把它分成N*512bit加上剩余的末尾段，进行填充变成至512bit，最终它的长度是512的整数倍，这样就满足后面处理中对信息长度的要求[8]。先取出一个内存中的512bit进行摘要处理，把它变成16个块的32bit，为公式处理提供数据。定义一个256的散列值为A，B，C，D，E，F，G，H都是十六进制的数。分别赋值A=a，B=b，C=c，D=d,E=e，F=f，G=g，H=h。由公式说明，主循环有 4轮（MD4只有3轮），每轮循环都很相似。第一轮进行16次操作。每次操作对a，b，c，d，e，f，g和h中的其中7个做一次非线性函数运算，然后将所得结果加上第8个变量，再加上文本的一个子分组和一个常数。再将所得结果向左环移一个不定的数，并加上 a，b，c，d，e，f，g和 h中之一。最后用该结果取代 a，b，c，d，e，f，g和h中之一。 这样ABCDEFGH就变成了新的数，重复公式进行 16次结束，这时ABCDEFGH就成了新数，换下一个公式，每个公式进行16轮，直到64轮结束，输出新的A，B，C，D，E，F，G，H数，最终的结果值取内存中的数据[9]。

现以字符串“jklmn”为例，进行MD5的算法。

该字符串在内存中表示为：6A 6B 6C 6D 6E（从左到右为低地址到高地址，后同），信息长度为40 bits， 即 0x28。

对其填充，填充至448位，即56字节。结果为：

6A 6B 6C 6D 6E 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

剩下64位，即8字节填充填充前信息位长，按小端字节序填充剩下的8字节，结果为。

6A 6B 6C 6D 6E 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 28 00 00 00 00 00 00 00

（64 字节，512 bits）

初始化 A、B、C、D、E、F、G、H 八个变量。

将这64字节填充后数据分成16个小组（程序中对应为16个数组），即：

M0：6A 6B 6C 6D （这是内存中的顺序，按照小端字节序原则，对应数组M(0)的值为0x6D6C6B6A，下同）

M1：6E 80 00 00

M2：00 00 00 00

.....

M14：28 00 00 00

M15：00 00 00 00

经过分组数据处理后，a、b、c、d、e、f、g、h 值 分 别 为 0xD8523F60、0x837E0144、0x517726CA、0x1BB6E5FE、0xEEF10144、0x5FF72231、0x8251E5FE、0x1CC6E538

在内存中为a：60 3F 52 D8

b：44 01 7E 83

c：CA 26 77 51

d：FE E5 B6 1B

e：44 01 F1 EE

f：31 22 F7 5F

g：FE E5 51 82

h：38 E5 C6 C1

a、b、c、d、e、f、g、h 按内存顺序输出即为最终结果：603F52D844017E83CA267751FEE5B61B4401F1EE312F75FFEE5518238E5C6C1。这就是字符“jklmn”的MD5值。

3 传统的MD5算法和和改进后MD5算法的性能比较

测试范围 ：改进后的MD5算法和传统的MD5算法[10]。

样本数据 ：2G大小Vmware虚拟机操作系统的磁盘文件，其中包含其中各种类型的文件，如二进制文件和文本文件等。

软件平台 ：Windows7、Microsoft.NET Framework 2.0

硬件平台 ：

机器 A（SCSI Disk）：软件配置 Windows 2000+Microsoft.NET Framework 2.0；硬件配置 CPU：4（Xeon），2.8G，RAM：2G ，HD：70 GB SCSI

机器 B（IDE Disk）：软件配置 Windows 2003+Microsoft.NET Framework 2.0；硬件配置 CPU：1（P4），2.8G，RAM：1G，HD：40 GB IDE

考虑到整个测试过程只是涉及到文件读取与哈希值的计算，并无过多的与操作系统、软件平台、开发语言相关的操作，因此可以认为上述测试方法的结果具有普遍性，即也适用于其它操作系统平台（如 Linux/Unix）或应用语言/平台（java/android）。

3.1 不同配置机器间的对比

在不同机器配置上的平均运算结果如表2所示。

表2 不同机器的运算时间表 单位：ns

3.2 不同算法的CPU占用率比较

在不同的算法运行时，在机器B上监控其对于CPU的平均使用时间，结果如表3所示。

表3 CPU占用率表

可以看出改进后的MD5算法比传统的MD5算法所使用的资源略有减少，且运算时间的改善十分明显，基本实现了用较少的资源得到较高速率的目标，证明了结构的正确性和合理性，所以都可以应用于大文件数据的加密处理。

4 结束语

本文提出的基于迭代置换的MD5算法不仅可以减少存储空间和节约成本，就目前普通的应用范围来讲，还没有出现过其他或者新的算法来代替。所以MD5在未来加密算法领域里还有相当大的应用价值，实践证明，在网站的建设和应用系统的开发过程中通过引进MD5算法，会非常有效的提高用户重要信息的安全性，因此MD5加密算法是一种十分优秀的信息加密算法。在实际应用中，还可以将MD5算法做适当的修改和补充，以更加适合应用需要。同时，随着企业信息和数据的巨大膨胀，以及确保数据安全的重要性与日俱增，数据的加密有着不可替代的重要性，改进的MD5算法为高效率、易管理的数据安全方案提供了一种新的研究思路。

[1]刘俊辉．MD5 消息摘要算法实现及改进[J]．福建电脑，2007(4):96-97．

[2]RIVEST R．The MD5 message－digest algorithm[S/OL]．（2011－12－01）．http：//www．ietf．org/rfe/rge1321．html.

[3]杨义先，林晓东．信息安全综论[M]．北京：电信科学出版社，1998．

[4]王新忠．电信系统中用户接入网管理信息的安全技术[D]．武汉：华中科技大学，2006．

[5]郭珊琼．MD5数据加密算法的研究与实现[D]．武汉：武汉理工大学学报，2007．

[6]尚华益，姚国祥．基于 Blowfish 和 MD5 的混合加密方案[J]．计算机应用研究，2010，27（1）：231－233．

[7]张绍兰，邢国波，杨义先．对 MD5 的改进及其安全性分析[J]．计算机应用，2009，29（4）：947－949．

[8]喻谦．基于MD5算法的用户身份认证系统研究[D]．北京：华北电力大学，2013．

[9]陆琳琳．MD5算法的技术研究及性能优化[D]．长春：吉林大学，2005．

Research of Improved MD5 Algorithm Based on Iterative Permutation

ZENG Ling-jing,HUANG Jin-fen

（Department of Information Engineering,Fujian Chuanzheng Communications College,Fuzhou 350004,China）

In view of the shortcomings of network security,such as high encryption strength and large computational complexity,an improved MD5 algorithm based on iterative permutation is proposed.Firstly,MD5 algorithm is used to process the input information by 512-bit packets.Then each packet is divided into sixteen 32-bit subpackets.After five steps such as filling,extension,block,initialize variables and processing,the output is composed of eight 64-bit packets.Finally,a 256 hash value is generated by combining the eight 64-bit packets.Compared with the existing algorithms,the improved MD5 algorithm protects users'password security more effectively.

MD5 algorithm;one-way hash function;iterative permutation;password;safety

TP309.7

A

1673-4343（2017）06-0018-07

10．14098/j．cn35－1288/z．2017．06．003

2017-08-08

曾凌静，女，福建福州人，讲师。主要研究方向：Android应用开发。

朱联九）