MDI5算法简介及主要实现

MD5算法简介及其实现Abstract：Withtheabroadapplicationofcomputertechnology,moreandmorepeoplehavebeendependingontheinformationsystems,theresearchofdataencryptiontechnologyhasbeenpaidmoreandmoreattentionbypeopleaswell.Datasecurityisnotonlyneedinthemilitary,politicalandthediplomatic,butalsoeverywhereinscience,technologyresearchanddevelopment,tradeandsoon.Cryptologytechniqueisthecoreofsafeguardinginformationsecurity,anddigitalsignatureisalwayscompanionedwithHashfunctions,whichisakernelofmodernCryptography.MD5isatypicalHashencryptiontechniquewhichisquitepopular.ThepapermainlygivesdetaildiscussionoftheMD5encryptionalgorithmsprincipleanditsrealization.Keywords：MD5digitalsignature摘要：随着计算机在社会各个领域的广泛应用，人们对信息系统的依赖程度越来越高，数据加密技术的研究也越来越受到人们重视，数据安全保密问题己不仅仅出于军事、政治和外交上的需要，科学技术的研究和发展及商业等方面，无一不与数据安全息息相关。信息产业的核心技术之一就是密码算法，单向散列（Hash）函数是现代密码学的核心，而基于Hash函数的MD5数据加密算法是目前研究的热点之一。本文主要详细的论述了MD5算法的基本原理、应用实现,并提供了主要代码。关键字：MD5数字签名1.MD5算法简介MD5的全称是Message-Digestalgorithm5（信息-摘要算法），MD5是一种不可逆的法，即对生成的密文求逆，对应着无穷个可逆。在90年代初由MITLaboratoryforComputerScience（IT计算机科学实验室）和RSADataSecurityInc（RSA数据安全公司）的RonaldL.Rivest开发出来，经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密钥前被“压缩”成一种保密的格式（就是把一个任意长度的字节串变换成一定长的大整数）。不管是MD2、MD4还是MD5，它们都需要获得一个随机长度的信息，并产生一个128位的信息摘要。虽然这些算法的结构或多或少有些相似，但是MD2的设计与MD4和MD5完全不同，是因为MD2是为8位机器做过设计优化的，而MD4和MD5却是面向32位的电脑。这三个算法的描述和C语言源代码在internetrfcs1321中有详细的描述，这是一份最具权威的文档，由RonaldL.Rivest在1992年8月向IEFT提交。Rivest在1989年开发出MD2算法，在这个算法中，首先对信息进行数据补位，使信息的字节长度是16的倍数，然后，以一个16位的检验和追加到信息末尾，并且根据这个新产生的信息计算出散列值。后来，Rogier和Chauvaud发现如果忽略了检验和将产生MD2冲突。MD2算法的加密后结果是唯一的---即没有重复的。为了加强算法的安全性,Rivest在1990年又开发出MD4算法。MD4算法同样需要填补信息以确保信息的字节长度加上448后能被512整除（信息字节长度mod512=448）。然后，一个以64位二进制表示的信息的最初长度被添加进来。信息被处51位迭代结构的区块，而且每个区块要通过三个不同步骤的处理。DenBoer和Bosselaers以及其他人很快的发现了攻击MD4版本中第一步和第三步的漏洞°Dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到MD4完整版中的冲突（这个冲突实际上是一种漏洞，它将导致对不同的内容进行加密却可能得到相同的加密后果）。毫无疑问，MD4就此被淘汰掉了。尽管MD4算法在安全上有个这么大的漏洞，但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除MD5以外，其中比较有名的还有SHA-1、Snefru以及Haval等。一年以后，即1991年，Rivest开发出技术上更为趋近成熟的MD5算法。它在MD4的基础上增加了"安全-带子"（safety-belts）的概念。虽然MD5比MD4稍微慢一些，但却更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中，信息-摘要的大小和填充的必要条件与MD4完全相同oDenBoer和Bosselaers曾发现MD5算法中的假冲突（pseudo-collisions），但除此之外就没有其他被发现的加密后结果了。VanOorschot和Wiener曾经考虑过一个在散列中暴力搜寻冲突函数（brute-forcehashfunction），而且他们猜测一个被设计专门用来搜索MD5冲突的机器（这台机器在1994年的制造成本大约是一百万美元）可以平均每24天就找到一个冲突。2.MD5用途MD5用途：1、防止被篡改：1）比如发送一个电子文档，发送前，我先得到MD5的输出结果a。然后在对方收到电子文档后，对方也得到一个MD5的输出结果bo如果a与b一样就代表中途未被篡改。2）比如我提供文件下载，为了防止不法分子在安装程序中添加木马，我可以在网站上公布由安装文件得到的MD5输出结果。3）SVN在检测文件是否在Checkout后被修改过，也是用到了MD5。2、 防止直接看到明文：现在很多网站在数据库存储用户的密码的时候都是存储用户密码的MD5值。这样就算不法分子得到数据库的用户密码的MD5值，也无法知道用户的密码（其实这样是不安全的，后面我会提到）。（比如在UNIX系统中用户的密码就是以MD5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成MD5值，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。）3、 防止抵赖（数字签名）：这需要一个第三方认证机构。例如A写了一个文件，认证机构对此文件用MD5算法产生摘要信息并做好记录。若以后A说这文件不是他写的，权威机构只需对此文件重新产生摘要信息，然后跟记录在册的摘要信息进行比对，相同的话，就证明是A写的了。这就是所谓的“数字签名”。3.MD5算法的基本原理

MD5算法以512位分组来处理输入文本，每一分组又划分为16个32位子分组。算法的输出由4个32位分组组成，将它们级联形成一个128位散列值。第1步：填充MD5的第1步是在原消息中增加填充位，目的是使原消息长度等于一个值，即比512的倍数少64位。例如，如果原消息长度为1000位，则要填充472位，使消息长度为1472位，因为64+1472=1536，是512的倍数（1536=512*3）。这样，填充后，原消息的长度为448位（比512少64），960位（比1024少64位），1472位（比1536少64位），等等，如下图2-1所示。原始消息图2-1填充过程原始消息图2-1填充过程填充对用一个1位和多个0位。注意填充总是增加，即使消息长度已经是比512的倍数少64。因此，如果消息长度已经是448，则要填充512位，使长度变成960位。因此，填充长度为1〜512的值。填充对用一个1位和多个0位。注意填充总是增加，即使消息长度已经是比512的倍数少64。因此，如果消息长度已经是448，则要填充512位，使长度变成960位。因此，填充长度为1〜512的值。第2步：添加长度增加填充位后，下一步要计算消息原长，将其加进填充后的消息末尾。先计算消息长度，不包括填充位（即增加填充位前的长度）。例如，如果原消息1000位，则填充472位，使其变成比512的倍数（1536）少64位，但长度为1000，而不是1472。这个消息原长表示为64位值，添加到加进填充后的消息末尾。如果消息长度超过264位（即64位无法表示，因为消息太长），则只用长度的低64位，即等于计算lengthmod264。可以看到，这时消息长度为512的倍数，成为要散列的消息。如图2-2所示。原始消息填充（可选）原始消息填充（可选）原始消息填充（可选）长度64位要散列的数据（摘要）图2-2添加长度第3步：将输入分成512位的块。下面要将输入分成512的块，如图2-3所示。

要散列的数据（已摘要）512位512位512位512位 512位512位块2块3•・・块1图2-3将数据分成512块第4步：初始化链接变量第4步要初始化四个链接变量，分别称为A,B,C,D,它们都是32位的数字，这些链接变量的初始十六进制值如表2-1所示，低位的字节在前面。表2-1链接变量A十卜六进制01234567B卜六进制89ABCDEFC卜六进制FEDCBA98D十卜六进制76543210注意低位的字节在前面指的是LittleEndian平台上内存中字节的排列方式，而在程序书写时,要写成： A=0x01234567B=0x89abcdefC=0xfedcba98

D=0x7654321第5步：处理块初始化之后,就要开始实际算法了。这是个循环,对消息中的多个512位块行。5.1步：将四个链接变量复制到四个变量a,b,c,d中,使a=A,b=B,c=C,d=D,如图2-4所示。实际上，这个算法将a，b，c，d组合成128位寄存器（abed）,寄存器（abed）在实际算法运算中保存中间结果和最终结果，如图2-5所示实际上，这个算法将a，b，c，d组合成128位寄存器（abed），寄存器（abed）ab cd在实际算法运算中保存中间结果和最终结果，如图2-5所示）ab cdabcd图2-5链接变量抽象视图5.2步：将当前512位块分解为16个子块，每个子块为32位图2-6将当前512块分解为16个字块5.3步：主循环有四轮，每轮很相似。每一轮进行6次操作，处理一个块中的16个子块。每一轮的输入如下：（a）16个子块；（b）变量a,b,c,d；（c）常量t,如图2-7和2-8所示。这四轮中的第1步进行不同处理，其他步骤是相同的。—每一轮有16个输入子块M[0],M[l],・・・，M[15],或表示为M[i],其中i为1〜15。每个子块为32位。—t是个常量数组，包含64个元素，每个元素为32位。把数组t的元素表示为t[1],t[2],・・・，t[64]，或t[i],其中i为1〜64。由于有四轮，因此每一轮用64个t值中的16个。图2-7每一轮处理F(x,y,z)=(x&y)l((〜x)&z)

G(x,y,z)=(x&z)l(y&(~z))H(x,y,z)=xAyAzI(x,y,z)=yA(xl(~z))(&是与，I是或，〜是非，人是异或)这些函数是这样设计的：如果x，y和z的对应位是独立和均匀的，那么结果的每一位也是独立和均匀的，函数F是按逐位方式操作；如果X,那么Y,否则乙函数H是逐位奇偶操作。设Mi表示消息的第i个子分组(从0到15)，<<<S表示循环左移S位，则四种操作为：FF(a,b,c,d,Mi,s,ti)表示a=b+((a+(F(b,c,d)+Mi+ti)<<<s)GG(a,b,c,d,Mi,s,ti)表示a=b+((a+(G(b,c,d)+Mi+ti)vvvs)HH(a,b,c,d,Mi,s,ti)表示a=b+((a+(H(b,c,d)+Mi+ti)vvvs)II(a,b,c,d,Mi,s,ti)表示a=b+((a+(I(b,c,d)+Mi+ti)vvvs)这四轮(64步)是：第一轮FF(a,b,c,d,M0,7,0xd76aa478)FF(d,a,b,c,M1,12,0xe8c7b756)FF(c,d,a,b,M2,17,0x242070db)FF(b,c,d,a,M3,22,0xc1bdceee)FF(a,b,c,d,M4,7,0xf57c0faf)FF(d,a,b,c,M5,12,0x4787c62a)FF(c,d,a,b,M6,17,0xa8304613)FF(b,c,d,a,M7,22,0xfd469501)FF(a,b,c,d,M8,7,0x698098d8)FF(d,a,b,c,M9,12,0x8b44f7af)FF(c,d,a,b,M10,17,0xffff5bb1)FF(b,c,d,a,M11,22,0x895cd7be)FF(a,b,c,d,M12,7,0x6b901122)FF(d,a,b,c,M13,12,0xfd987193)FF(c,d,a,b,M14,17,0xa679438e)FF(b,c,d,a,M15,22,0x49b40821)第二轮GG(a,b,c,d,M1,5,0xf61e2562)GG(d,a,b,c,M6,9,0xc040b340)GG(c,d,a,b,M11,14,0x265e5a51)GG(b,c,d,a,M0,20,0xe9b6c7aa)GG(a,b,c,d,M5,5,0xd62f105d)GG(d,a,b,c,M10,9,0x02441453)GG(c,d,a,b,M15,14,0xd8a1e681)GG(b,c,d,a,M4,20,0xe7d3fbc8)GG(a,b,c,d,M9,5,0x21e1cde6)GG(d,a,b,c,M14,9,0xc33707d6)GG(c,d,a,b,M3,14,0xf4d50d87)GG(b,c,d,a,M8,20,0x455a14ed)GG(a,b,c,d,M13,5,0xa9e3e905)GG(d,a,b,c,M2,9,0xfcefa3f8)GG(c,d,a,b,M7,14,0x676f02d9)GG(b,c,d,a,M12,20,0x8d2a4c8a)第三轮HH(a,b,c,d,M5,4,0xfffa3942)HH(d,a,b,c,M8,11,0x8771f681)HH(c,d,a,b,M11,16,0x6d9d6122)HH(b,c,d,a,M14,23,0xfde5380c)HH(a,b,c,d,M1,4,0xa4beea44)HH(d,a,b,c,M4,11,0x4bdecfa9)HH(c,d,a,b,M7,16,0xf6bb4b60)HH(b,c,d,a,M10,23,0xbebfbc70)HH(a,b,c,d,M13,4,0x289b7ec6)HH(d,a,b,c,M0,11,0xeaa127fa)HH(c,d,a,b,M3,16,0xd4ef3085)HH(b,c,d,a,M6,23,0x04881d05)HH(a,b,c,d,M9,4,0xd9d4d039)HH(d,a,b,c,M12,11,0xe6db99e5)HH(c,d,a,b,M15,16,0x1fa27cf8)HH(b,c,d,a,M2,23,0xc4ac5665)第四轮II(a,b,c,d,M0,6,0xf4292244)II(d,a,b,c,M7,10,0x432aff97)II(c,d,a,b,M14,15,0xab9423a7)II(b,c,d,a,M5,21,0xfc93a039)II(a,b,c,d,M12,6,0x655b59c3)II(d,a,b,c,M3,10,0x8f0ccc92)II(c,d,a,b,M10,15,0xffeff47d)II(b,c,d,a,M1,21,0x85845dd1)II(a,b,c,d,M8,6,0x6fa87e4f)II(d,a,b,c,M15,10,0xfe2ce6e0)II(c,d,a,b,M6,15,0xa3014314)II(b,c,d,a,M13,21,0x4e0811a1)II(a,b,c,d,M4,6,0xf7537e82)II(d,a,b,c,M11,10,0xbd3af235)II(c,d,a,b,M2,15,0x2ad7d2bb)II(b,c,d,a,M9,21,0xeb86d391)所有这些完成之后，将A,B,C,D分别加上a,b,c,d,然后用下一分组数据继续运行算法，最后MD5算法产生128位的输出是A，B，C和D的级联，其中低字节始于A，高字节终于D。至此整个MD5算法处理结束。4.运行环境及语言运行环境：Eclipse条件：普通PC机编程语言：java5.MD5算法的实现：了解MD5算法的基本原理之后，本文将调用MD5主函数实现对文件处理的测试程序。此程序的功能是在WindowsXP操作系统下用JAVA语言在Eclipse编程环境下实现对固定的文件生成128位的MD5值，实验结果如下：keyBeaiiTestsuite:keyBeaiiC):D41D&CD98FO0B2O4E98OO^8ECF8427EkeyBeaiit"学号A泌焉FOB花嗣包C貂爼52応AB孔6CF564k眇Bean〔迄01311眇5厂)<644BBEDD2F^9703A0EE7CE5DE4D9DS26keyBeaii("cheng1and:DABD1DB2327