MD5算法及其性能优化
- 格式：pdf
- 大小：214.17 KB
- 文档页数：3
计算机科学２００６Ｖ０１．３３ＮＱ．８（增刊）ＭＤ５算法及其性能优化ＭＤ５ＡｌｇｏｒｉｔｈｍａｎｄｉｔｓＰｅｒｆｏｒｍａｎｃｅＯｐｔｉｍｉｚａｔｉｏｎ
陆琳琳胡亮（吉林大学软件学院长春１３００１２）
ＡｂｓｔｒａｃｔＭＤ５ｉｓａｔｙｐｉｃａｌＨａｓｈｅｎｃｒｙｐｔｉｏｎｔｅｃｈｎｉｑｕｅａｎｄｉｔｉｓｑｕｉｔｅｐｏｐｕｌａｒ．Ｉｔｉｓ
ａ
ｋｉｎｄｏｆＭｅｓｓａｇｅ－Ｄｉｇｅｓｔ
ａｌｇｏ－
ｒｉｔｈｒｍＴｈｉｓｐａｐｅｒｉｓｂａｓｅｏｎｔｈｅｒｅｓｅａｒｃｈｏｆＭＤ５，ｏｐｔｉｍｉｚｅｐｒｉｎｃｉｐｌｅａｎｄｔｈｅｂｅｈａｖｉｏｒａｎａｌｙｓｉｓｗｉｔｈｔｈｅＭＤ５，ｗｅ
ｇａｖｅ
ｔｈｅｅｘａｍｐｌｅｏｆｏｐｔｉｍｉｚｉｎｇａｎｄｔｈｅｍｅａｓｕｒｅｒｅｓｕｌｔｏｆＭＤ５，ｏｎｔｈｅｐｌａｔｆｏｒｍ
ｏｆＩｎｔｅｌＰｅｎｔｉｕｍ４ＣＰＵ／ＷｉｎｄｏｗｓＸＰ／ＩＥ
６．０．Ｉｎｔｈｉｓｐａｐｅｒ，ａｎｏｔｉｃｅｉｓｐｒｅｓｅｎｔｅｄ．Ｙｏｕａｒｅｓｕｇｇｅｓｔｅｄｔｏｅｄｉｔｙｏｕｒｐａｐｅｒｓｉｎｔｈｉｓｆｏｒｍａｔ．ＫｅｙｗｏｒｄｓＭＤ５ａｌｇｏｒｉｔｈｍ，Ｐｅｒｆｏｒｍａｎｃｅ
ｏｐｔｉｍｉｚａｔｉｏｎ
１引言
加密算法的两个重要指标是加密强度和速度。加密强度是算法的基本性质，是算法抵抗各种攻击的能力。在大多数应用中，在保证一定加密强度的前提下，加密／解密的速度是最重要的性质，尤其是对于要求较高速度的应用。加密强度在算法的设计阶段已经确定，算法的不同实现一般不会对加密强度产生影响。而同一加密算法的ＪＪＤ／解密速度在不同的实现中则可能有很大不同。加密速度在根本上由算法本身的设计决定，但在实现中可以使用各种优化技术最大限度地发挥算法速度的潜力。本文研究在算法确定情况下提高算法速度的实现方法，不涉及新算法设计问题，并给出了对ＭＤ５算法的实现进行优化的实例和测量结果。２ＭＤ５算法原理ＭＤ５算法的全称是Ｍｅｓｓａｇｅ－Ｄｉｇｅｓｔａｌｇｏｒｉｔｈｍ５（信息一摘要算法），是由ＭＩＴＬａｂｏｒａｔｏｒｙｆｏｒＣｏｍ—ｐｕｔｅｒＳｃｉｅｎｃｅ（ＩＴ计算机科学实验室）和ＲＳＡＤａｔａＳｅｃｕｒｉｔｙＩｎｃ（ＲＳＡ数据安全公司）的ＲｏｎａｌｄＩ．Ｒｉ—ｖｅｓｔ开发出来的，经ＭＤ２，ＭＤ３和ＭＤ４发展而来，它的作用是将一个任意长度的“字节串”通过一个不可逆的字符串变换算法变换成一个１２８ｂｉｔ的大整数，ＭＤ５算法共分为五步。２．１添加填充比特任意长度的消息首先需要增加填充位，使其长度恰好为一个比５１２的倍数小６４位的数。添加的方法是：消息后第一个填充位是“１”，其余都是“０”。２．２添加长度值将未添加填充位的消息长度以６４位表示（低位字在前），附加到已添加过填充位的消息后面，此时，消息长度恰好是５１２位的整数倍。２．３初始化加缓存初始化消息摘要缓冲器，四个３２位的寄存器变量以十六进制表示，低位字节在前，称之为链接变量。Ａ＝Ｏｘ０１２３４５６７Ｂ＝０ｘ８９ａｂｃｄｅｆＣ一０ｘｆｅｄｃｂａ９８Ｄ—Ｏｘ７６５４３２１０２．４处理５１２ｂｉｔ报文分组序列这一步为主循环，循环的次数是消息中５１２位消息分组的数目。首先定义四个非线性函数：如果Ｘ，Ｙ和Ｚ的对应位是独立和均匀的，那么结果的每一位也是独立和均匀的。（＆是与，Ｉ是或，～是非，‘是异或）Ｆ（ｘ，Ｙ，ｚ）一（ｘ＆ｙ）Ｉ（（～ｘ）＆ｚ）Ｇ（ｘ，Ｙ，ｚ）一（ｘ＆ｚ）Ｊ（ｙ＆（～ｚ））Ｈ（ｘ，Ｙ，ｚ）一ｘ＇ｙｚＩ（ｘ，Ｙ，ｚ）一ｙ－（ｘｆ（～ｚ））
图１ＭＤ５主循环将上一步中的四个变量复制到另外的变量中去。主循环有四轮，每轮进行１６次操作，每次操作
陆琳琳硕｛一研究生．主蛰研究方向为旧络安全。胡亮博＿｛：，教授，研究方向为分布式系统和嘲络软ｆ１。・１７２・对ａ，ｂ，ｃ，ｄ中的其中三个作一次非线性运算，然后将所得结果加上第四个变量，消息的一个子分组（Ｍｉ）和一个常数（ｔｉ），再将所得结果向左循环一个不定的数，并加上ａ，ｂ，ｅ，ｄ中之一，最后用该结果取代ａ，ｂ，ｃ或ｄ中之一，如图１和图２所示。图２ＭＤ５的一个执行过程设Ｍｉ表示消息的第ｉ个子分组（从０到１５）。（（（Ｓ表示循环左移Ｓ位，则四种操作为：ＦＦ（ａ，ｂ，ｃ，ｄ，Ｍｉ，ｓ，ｔｉ）表示ａ＝ｂ＋（（ａ＋（Ｆ（ｂ，ｃ，ｄ）＋Ｍｉ＋ｔｉ）（（＜ｓ）ＧＧ（ａ，ｂ，Ｃ，ｄ，Ｍｉ，ｓ，ｔｉ）表示ａ＝ｂ＋（（ａ＋（Ｇ（ｂ，ｅ，ｄ）＋Ｍｉ＋ｔｉ）（＜（ｓ）ＨＨ（ａ，ｂ，Ｃ，ｄ，Ｍｉ，ｓ，ｔｉ）表示ａ—ｂ＋（（ａ＋（Ｈ（ｂ，ｅ，ｄ）＋Ｍｉ＋ｔｉ）（（＜ｓ）ＩＩ（ａ，ｂ，ｃ，ｄ，Ｍｉ，ｓ，ｔｉ）表示ａ＝ｂ＋（（ａ＋（Ｉ（ｂ，ｃ，ｄ）＋Ｍｉ＋ｔｉ）（（（ｓ）２．５输出上述四轮操作完成之后，将Ａ，Ｂ，Ｃ，Ｄ分别加上ａ，ｂ，ｃ，ｄ９输出的１２８ｂｉｔ消息摘要是Ａ，Ｂ，Ｃ，Ｄ的级联，输出顺序是：从Ａ的低字节开始，直到Ｄ的高字节。３ＭＤ５算法性能优化结合我们对ＭＤ５算法的分析和实验，归纳总结出以下提高算法速度的实现原则，其中测试平台为ＩｎｔｅｌＰｅｎｔｉｕｍ４ＣＰＵ／ＷｉｎｄｏｗＸＰ／ＩＥ６．０。测试数据都是１０次测试结果的平均值。３．１展开加密循环和函数加密算法的大部分运行时间是执行加密循环。展开加密循环实际上是将加密循环变为多个循环体中的程序模块，同时将加密循环中调用的函数展开。这样减少了很多条件跳转指令和计算指令，并且将许多变量变为常量，大大提高了速度。表１加密循环和展开加密循环的速度比较加密速度编程方式（千字节／秒）提高（％）加密循环４９２８４．３３展开加密循环５１８４５．５８５．２０３．２内存拷贝优化在ＭＤ５主函数中有一段代码：这段代码对含有填充的数据块进行处理。ｆｏｒ（ｉｎｔｉｘ—Ｏ；ｉｘ＜ｂｕｆｆＬｅｎ－－ｎｌｎｄｅｘ；＋＋ｉｘ）｛
＊（ｐＡｄｄＢｕｆｆ＋ｉｘ）＝＊（ｂｕｆｆ＋ｎｌｎｄｅｘ＋ｉｘ）；｝
ｆｏｒ（ｉｎｔｉｙ＝０；ｉｙ＜ｎＡｄｄＢｕｆｆＳｉｚｅ一８一ｂｕｆｆＬｅｎ＋ｎｌｎｄｅｘｔ＋＋
ｉｙ）｛
＊（ｐＡｄｄＢｕｆｆ＋ｂｕｆｆＬｅｎ－－ｎｌｎｄｅｘ＋ｉｙ）＝＊（ＡＤＤＢＹＴＥ＋ｉｙ）；｝
ｆｏｒ（ｉｎｔｉｚ＝０，ｉｚ＜８；＋＋ｉｚ）｛
＊（ｐＡｄｄＢｕｆｆ＋ｎＡｄｄＢｕｆｆＳｉｚｅ－－８＋ｉｚ）一＊（（ｕｎｓｉｇｎｅｄｃｈａｒ＊）（１ＢｉｔＬｅｎ＋ｉｚ））；）
这处之所以要修改的原因是非常明显的，ｆｏｒ循环语句是非常慢的，一般可以把类似的代码段替换成为Ｃ语言中的库函数或者操作系统的标准函数。这段Ｃ代码可以优化为：ｍｅｍｃｐｙ（ｐＡｄｄＢｕｆｆ，ｂｕｆｆ＋ｎｌｎｄｅｘ，ｂｕｆｆＩ。ｅｎ－－ｎｌｎｄｅｘ）；ｍｅｍｃｐｙ（ｐＡｄｄＢｕｆｆ＋ｂｕｆｆＬｅｎ—ｎｌｎｄｅｘ，ＡＤＩ）ＢＹＴＥ，ｎＡｄｄ－Ｂｕｆｆｓｉｚｅ一８一ｂｕｆｆＬｅｎ＋ｎｌｎｄｅｘ）；
ｍｅｍｃｐｙ（ｐＡｄｄＢｕｆｆ＋ｎＡｄｄＢｕｆｆＳｉｚｅ一８，（ｕｎｓｉｇｎｅｄｃｈａｒ＊）ｌＢｉｔＬｅｎ。８）ｌ
表２内存拷贝优化前后的速度比较加密速度（千字节／秒）提高（％）优化前４９２８４．３３
优化后５１１７４．１８
３．８３
３．３数组转换函数的优化在ＭＤ５算法中有这样一个函数：
。ｏｕｔｐｕｔ［＿ｊ＇］＝（ｕｎｓｉｇｎｅｄ）＆二ｏｘｆｆ）；
：帅ｕ。［ｊ＋２］娟喊黜摭燃黜殴器鬻勰爻
：：毒：：吕丰；ｊ三｛兰ｉ警篡３：警窨｛｛；：嚣：［习；；！；；受：：嚣；
．显而易见，这个函数的功能只是将一个无符号整形数组转换成为了一个无符号字符形数组。这段代码确实可以优化如下：
表３数组转换函数优化前后的速度比较加密速度（千字节／１５＂）提高（％）
优化前４９２８４．３３优化后５３３１８．４０８．１９
这个地方也可叫作算法的优化，不过叫作算法的优化可能有点牵强，但是算法的优化确实是最为重要的，比如说搜索算法，如果选择不当，可能要丧
・１７３・失很多的效率。３．４不同的操作系统我们把Ｗｉｎｄｏｗｓ操作系统下的ＭＤ５源程序移植到Ｌｉｎｕｘ操作系统下，代码是相同的，基本没有变动。通过表４的速度比较，我们可以看出，在Ｗｉｎ—ｄｏｗｓ操作系统下ＭＤ５算法对文件处理的速度比Ｌｉｎｕｘ下更快。表４不同操作系统的速度比较加密速度提高操作系统（千字节／秒）（％）ＷｉｎｄｏｗｓＸＰ（ＩｎｔｅｌＰｅｎｔｉｕｍ４ＣＰＯ２．７９ＧＨｚ４９２８４．３３５０４ＭＢ的内存）ＬｉｎｕｘＲｅｄＨａｔ９．０（１ａｔｅｌ１．０３５Ｐｅｎｔｉｕｍ４ＣＰＵ）４９７３８．０７结束语由于ＭＤ５算法的复杂性比较大，近几年来ＭＤ５算法也已经很完善了，所以对ＭＤ５算法的性能改进很困难，尤其在硬件方面。本文基本是在软件方面实现了对ＭＤ５算法的性能改进，程序中所使用的代码是在ＶＣ＋＋６．０的环境下编写的，但是还有一些方面，如对ＭＤ５的安全性能分析等，这些都需要在今后的日子里继续研究和完善。
参考文献１Ｋａｈａｔｅ八ＣｒｙｐｔｏｇｒａｐｈｙａｎｄＮｅｔｗｏｒｋＳｅｃｕｒｉｔｙ．邱仲潘，等译．北京：清华大学出版社，２００５．１１０～１２１２ＨｅａｈｈｆｉｅｌｄＲ，Ｌａｗｒｅｎｃｅｋｉｒｂｙ，等著．ＵｎｌｅａｓｈｅｄＣ张晓晖，张晓
昕，等译．北京：电子工业出版社，２００１．５ｌ～７６３徐千洋．ＬｉｎｕｘＣ函数库参考手册．北京：中国青年出版社，２００２．４０～８５４ＲｏｎａｌｄＬＲｉｖｅｓｔ．ＭＤ５Ｍｅｓｓａｇｅ－ＤｉｇｅｓｔＡｌｇｏｒｉｔｈｍ．ｈｔｔｐ：／／
Ⅵ１ｊｌｍｉｅｔｆ．ｏｒｇ／ｒｆｅ／ｒｆｅｌ３２１．ｔｘｔ，１９９２
（上接第１６５页）（５）在图像块ｘ“’中嵌入ｑ；位水印信息ｍａ’：从Ｄｑ×。中取ｑ。行和ｎ，列组成矩阵Ｄ“’；根据湿纸码构造线性方程组Ｈ‘１’ｖ＝ｍ‘‘’一Ｄ‘ｉ’Ｘ（”，得出解ｖ；根据ｖ调整Ｘ（ｏ，得到含水印图像Ｙ“’。３．２水印的提取算法（１）根据密钥ｋ生成矩阵Ｄａ×。。（２）将图像ｙ基于图像内容分块，每块图像为ｙ（．）。（３）从Ｄｑ×。中取ｑｉ行和ｎ；列组成矩阵Ｄ“’。（４）提取水印信息ｍ“’一Ｄｏ’Ｙｏ’。４实验图３为原始图像，其大小为２９４×３７８像素。其中有３３９个像素的可翻转优先级为０．６２５，有８１３个像素的可翻转优先级为０．３７５。选取门限值Ｔ为０．３７５，水印信息为图４所示，其大小为１８×６４像素。在图３中嵌入了１１５２位信息得到图５，即含水印图像。可以看出嵌人大量水印信息后的图像与原始图像差别不大，保持了较好的视觉隐蔽性。围３原始一值蹭像圈５岔水印二二值附慷图馋认证图旃认证圈４水印信息图６提取的水印信息局部篡改是二值图像所面临的一个主要恶意攻击，所以脆弱水印算法对局部篡改的抵抗和检测能力，是评价脆弱水印算法有效性的主要依据。依据汉字大小对图像分块，每个图像块大小为１９＊１６。对图５随机选取两处进行修改，如图７所示。图６・１７４・是从图７提取的水印信息。可以看出提取的水印有明显变化，具有脆弱性。图８为可能被篡改的位置。
