2008年第08期，第41卷 通 信 技 术 Vol.41，No.08,2008 总第200期Communications Technology No.200,Totally
女朋友哭了怎么办MD5算法的过程分析及其C#实现
杜昌钰
（贵州民族学院 数学与计算机科学学院，贵州 贵阳 550025）
【摘要】文章对MD5即“Message-Digest Algorithm 5（报文摘要算法）”算法进行了简要描述和分析，并利用目前流行的C#对MD5算法进行了具体的实现，给出了一个具体的C#加密实例。虽然MD5因王小云教授在2004国际密码学会议（Crypto’2004）上发表的论文受到了前所未有的冲击，但MD5在一些非关键领域应用还是相当广泛。最后还提出了一些针对MD5现状的解决对策和建议。
【关键词】MD5；C#；循环变换
【中图分类号】TP309.7【文献标识码】A【文章编号】1002-0802(2008)08-0071-02
Process Analysis of MD5 Algorithm and Its C# realization
DU Chang-yu
(Maths and Computer Science College, Guizhou University for Nationalities, Guiyang Guizhou 550025, China)
【Abstract】In this article the author gives a simple and esntial discription and analysis on MD5 ——Message-Digest Algorithm 5, and implements MD5 concretely by using C＃, which is popular at prent. Meanwhile the author gives a detailed example on C＃encryption. Although MD5 has been interogated becau of an essay announced on Crypto’2004, MD5 are widely ued in many non-key fields. In the end of the article the author would like to provide some solution and advice to improve the prent condition of MD5.
【Key words】MD5；C＃；circulating transformation
0 引言
MD5的全称是 “Message-Digest Algorithm 5（报文摘要算法）”，它与SHA (Secure Hash Algorithm，安全散列算法)一起被誉为国际加密大厦的两大奠基石。Rivest在1989年开发出MD2算法。为了加强算法的安全性，Rivest 在1990年又开发出MD4算法。Den Boer和Boslaers以及其他人很快的发现了攻击MD4版本中第一步和第三步的漏洞。1991年，Rivest开发出技术上更为趋近成熟的MD5算法。MD5在MD4的基础上增加了"安全-带子"（Safety-Belts）的概念。虽然MD5比MD4稍微慢一些，但却
更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中，信息-摘要的大小和填充的必要条件与MD4完全相同。[1]
Van Oorschot和Wiener曾经考虑过一个在散列中暴力搜寻冲突的函数（Brute-Force Hash Function），而且他们猜测一个被设计专门用来搜索MD5冲突的机器，可以平均每24天就找到一个冲突。但这个瑕疵并没有太多的影响MD5的安全性。MD5是当前应用最广泛的Hash算法之一，它将任意长度的原文映射成为一个128位的摘要信息串。在非特别关键的应用领域，MD5不失为一种非常优秀的加密技术。
1 MD5算法的应用领域
MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。比如，在UNIX下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如：MD5 () = 0ca175b9c0f726a831d895e 269332461，这就是文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。如果在以后传播这个文件的过程中，无论文件的内容发生了任何形式的改变，只要你对这个文件重新计算MD5时就会发现信息摘要不
收稿日期：2008-05-23。
作者简介：杜昌钰（1967-），男，副教授，主要研究方向为信息安全 CCF高级会员。
71
相同，由此可以确定你得到的只是一个不正确的文件。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的“不承认”行为。
现在使用最多的一种破译密码的方法就是一种被称为“跑字典”的方法。有两种方法得到字典，一种是日常搜集的用做密码的字符串表；另一种是用排列组合方法生成的，先用MD5程序计算出这些字典项的MD5 值，然后再用目标的MD5值在这个字典中检索。我们假设密码的最大长度为8位字节（8 Bytes），同时密码只能是字母和数字，共26+26+10=62个字符，排列组合出的字典的项数则是P(62,1) +P(62,2)….+P(62,8)，那也已经是一个很天文的数字了，存储这个字典就需要TB级的磁盘阵列，而且这种方法还有一个前提，就是能获得目标账户的密码MD5值的情况下才可以。这种加密技术被广泛的应用于UNIX系统中，这也是为什么UNIX系统比一般操作系统更为坚固一个重要原因。
2 MD5的算法分析过程
对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值[2]。 MD5算法的具体分析步骤如下：
第一步，信息填充：使其字节长度对512求余的结果等于448。因此，信息的字节长度（Bits Length）将被扩展至N*512+448，即N*64+56个字节（Bytes），N为一个正整数。填充的方法如下，在信息的后面填充一个1和无数个 0，直到满足上面的条件时才停止用0对信息的填充。
第二步，长度调整：用一个64位的整数表示数据的原始长度(以bit为单位)，将这个数字的8个字节按低位的在前，高位在后的顺序附加在补位后的数据后面。经过这两步的处理，现在的信息字节长度=N*512+448+64=(N+1)*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。
第三步，初始化MD5参数：有4个32位被称作链接变量（Chaining Variable）的整数变量(A,B,C,D)用来计算信息摘要，每一个变量被初始化成以下，以十六进制数表示的数值，低位的字节在前面，他们分别为：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。当设置好这四个链接变量后，就开始进入算法的四轮循环运算。循环的次数是信息中512位信息分组的数目。将上面四个链接变量复制到另外四个变量中：A到a，B到b，C到c，D到d。
第四步，定义MD5基本的按位操作函数：X，Y，Z为32位整数。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))（&是与，|是或，~是非，^是异或）。
这四个函数的说明：如果X、Y和Z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。
F是一个逐位运算的函数。即，如果X，那么Y，否则Z。函数H是逐位奇偶操作符。
再定义四个分别用于四轮变换的函数。假设Mj表示消息的第j个子分组（从0到15），<<s表示循环左移s位。FF(a,b,c,d,Mj,s,ti)表示a=b+((a+(F(b,c,d)+Mj+ti)<<s，GG(a,b,c,d,Mj,s,ti)表示a=b+((a+(G(b,c,d)+Mj+ti)<<s，HH(a,b,c,d,Mj,s,ti)表示a=b+((a+(H(b,c,d)+Mj+ti)<<s，II(a,b,c,d,Mj,s,ti)表示a=b+((a+(I(b,c,d)+Mj+ti)<<s。
第五步，主循环四轮变换过程：主循环有四轮（MD4只有三轮），每轮循环都很相似。第一轮进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。N 是总的字节数，以64个字节为一组，每组作一次循环，每次循环进行四轮操作。要变换的64个字节用16个32位的整数数组15]表示。而数组 64]表示一组常数，T[i]为4294967296*abs(sin(i))的32位整数部分，i的单位是弧度,i的取值从1到64。
具体的分析过程算法因篇幅所限而略。
3 MD5算法之C#程序实现
C#是一种现代的面向对象语言。它使程序员快速便捷地创建基于Microsoft 平台的解决方案。这
种框架使C#组件可以方便地转化为XML网络服务，从而使任何平台的应用程序都可以通过Internet调用它。 C#增强了开发者的效率，同时也致力于消除编程中可能导致严重结果的错误。C#使C/C++程序员可以快速进行网络开发，同时也保持了开发者所需要的强大性和灵活性。
因此，文章所叙的MD5算法分析过程采用C#做语言 实现。
（该算法程序已实现，因篇幅限制，程序略，如需要请与作者联系）。
4 结语
山东大学的王小云教授在2004年召开的国际密码学年会（Crypto 2004）上发表了一篇《散列（哈希）函数MD4、MD5、HAVAL-128和RIPEMD中的碰撞》论文[3]，很多人认为MD5的应用到此终结。不过我认为还只是发现了一些“强碰撞”现象，虽然MD5的根基确实受到了极大的动摇，但要真正将其应用到实际中还有较长过程。而且MD5本身也在不断改进，如再和另外一些算法进行交叉加密或多次加密，或增加明文长度等，MD5在非特别关键领域的应用应该还是有很大的市场和较长的生命期的。
文章仅对MD5算法进行了适当分析，结合目前流行C#，给出了一个实现算法和具体实例。作为加密和解密的搏弈，
（下转第75页）
72
糖霜核桃仁化过后，管理Agent就被创建了，从此管理Agent就一直不停的监视各检测Agent的状态，除非系统被停止运行。如果某个检测Agent长时间的处于空闲状态，就将其状态置为不可用，这样可用的检测Agent数量就减少了，进而降低了因检测Agent而产生的系统无谓开销。当发现没有空闲的可用检测Agent或者收到包分发Agent发送来的没有可用检测Agent的消息时，管理Agent就将状态为不可用的检测Agent 激活，即将其状态由不可用状态置为空闲状态。如果没有状态为不可用的检测Agent可以利用，管理Agent就创建新的检测Agent，这样系统中可用的检测Agent数量就增加了。经过这样的调整，系统中可用的检测Agent的数目对于网络流量来说是合适的，当网络流量增大时，检测Agent的数目是增加的，而当网络流量减少时，检测Agent的数目也是减少的。也就是说检测Agent的数目随网络流量的变化而变化，是动态的。
3 系统测试
本系统可以用于某个局域网，安装在局域网的某台主机上面。这台机器当然还要安装Java的运行环境、Java捕包工具Jpcap和IBM公司的Aglet平台。这台主机理论上可以是专用于入侵检测的，也可以是局域网中普通的一台主机。但在实际应用时，推荐用一台专用的、配置比较好的主机进行入侵检测，以起到良好的检测效果。
李强为自己工作
表1～4记录了在用迅雷5工具下载文件时（显示当时的速率是100-200kb/s），在30秒的时间内，系统中检测Agent的数目分别为1、2、3、4时，各个检测Agent所处理的数据包的数目情况，每种情况都采集了4次数据。
表1 一个检测Agent的测试
身份证换照片测试次数 Agent0
1 1611
2 1039
3 1578
4 1564
表2 两个检测Agent的测试
测试次数 Agent0 Agent1
1 1408 410
2 1582 365
捕鱼高手
3 1493 286
4 1511 363
表3 三个检测Agent的测试
测试次数Agent0 Agent1 Agent2
1 1423 343 196
2 1792 195 165
3 1627 1113 117
4 1693 253 108
表4 四个检测Agent的测试
测试次数Agent0Agent1 Agent2 Agent3
全国人口
1 899 265 1317 93
2 956 461 29
3 156
3 779 233 191 987
排球的英语
4 913 1253 213 191
4 结语
测试结果表明：在系统中检测Agent的数目大于1的
情况下，各检测Agent都不同程度的处理了一定数量的数据包，起到了分担网络流量的作用，一定程度的解决了NIDS
的丢包问题。今后的研究方向是如何做到既分担了网络的流
量又不会给系统增加过多的无谓开销，在分担网络流量和消
耗系统资源之间寻求一个最佳的平衡点。
小学生天地
参考文献
1 Stefan A. Intrusion Detection Systems: A Survey and Taxonomy
[EB/OL]. www.cs.chalmers./~sax/pub/,2004-6-9.
2 魏衍君，沈祥鸿.基于移动Agent的分布式入侵检测系统设计与实
现[J].小型微型计算机系统, 2006，22(15):43-45.
3 Jay Beale,James C.Foster.Snort 2.0 Intrusion Detection[R].
Syngress Publishing,2003.
4 于泠，陈波.IDS中模式匹配算法及其并行化设计[J].计算机工程，
2004，30(4):46-48.
（上接第72页）
新算法被破解是很正常的事情，这也是我们技术进步的源泉。我们希望设计出更强大、更安全、更保密的算法，更希望这世界没有加密算法，人们都相互诚信，相互理解，共同享受这来之不易的世界。
参考文献
1 曹珍富, 薛庆水. 密码学的发展方向与最新进展[J].计算机教育,
2005:19-21.
2 徐茂智，游林. 信息安全与密码学[M].北京: 清华大学出版社 2007:121-127.
3 Wang Xiaoyun, Feng Dengguo, Lai Xuejia, et al. Collisions for
hash functions MD4, MD5, HAVAL-128 and RIPEMD[C]. Cryptology ePrint Archive: Report 2004/1999, Aug. 2004.
75
