MDI5算法簡(jiǎn)介及主要實(shí)現(xiàn)

MD5算法簡(jiǎn)介及其實(shí)現(xiàn)Abstract：Withtheabroadapplicationofcomputertechnology,moreandmorepeoplehavebeendependingontheinformationsystems,theresearchofdataencryptiontechnologyhasbeenpaidmoreandmoreattentionbypeopleaswell.Datasecurityisnotonlyneedinthemilitary,politicalandthediplomatic,butalsoeverywhereinscience,technologyresearchanddevelopment,tradeandsoon.Cryptologytechniqueisthecoreofsafeguardinginformationsecurity,anddigitalsignatureisalwayscompanionedwithHashfunctions,whichisakernelofmodernCryptography.MD5isatypicalHashencryptiontechniquewhichisquitepopular.ThepapermainlygivesdetaildiscussionoftheMD5encryptionalgorithmsprincipleanditsrealization.Keywords：MD5digitalsignature摘要：隨著計(jì)算機(jī)在社會(huì)各個(gè)領(lǐng)域的廣泛應(yīng)用，人們對(duì)信息系統(tǒng)的依賴程度越來(lái)越高，數(shù)據(jù)加密技術(shù)的研究也越來(lái)越受到人們重視，數(shù)據(jù)安全保密問(wèn)題己不僅僅出于軍事、政治和外交上的需要，科學(xué)技術(shù)的研究和發(fā)展及商業(yè)等方面，無(wú)一不與數(shù)據(jù)安全息息相關(guān)。信息產(chǎn)業(yè)的核心技術(shù)之一就是密碼算法，單向散列（Hash）函數(shù)是現(xiàn)代密碼學(xué)的核心，而基于Hash函數(shù)的MD5數(shù)據(jù)加密算法是目前研究的熱點(diǎn)之一。本文主要詳細(xì)的論述了MD5算法的基本原理、應(yīng)用實(shí)現(xiàn),并提供了主要代碼。關(guān)鍵字：MD5數(shù)字簽名1.MD5算法簡(jiǎn)介MD5的全稱是Message-Digestalgorithm5（信息-摘要算法），MD5是一種不可逆的法，即對(duì)生成的密文求逆，對(duì)應(yīng)著無(wú)窮個(gè)可逆。在90年代初由MITLaboratoryforComputerScience（IT計(jì)算機(jī)科學(xué)實(shí)驗(yàn)室）和RSADataSecurityInc（RSA數(shù)據(jù)安全公司）的RonaldL.Rivest開(kāi)發(fā)出來(lái)，經(jīng)MD2、MD3和MD4發(fā)展而來(lái)。它的作用是讓大容量信息在用數(shù)字簽名軟件簽署私人密鑰前被“壓縮”成一種保密的格式（就是把一個(gè)任意長(zhǎng)度的字節(jié)串變換成一定長(zhǎng)的大整數(shù)）。不管是MD2、MD4還是MD5，它們都需要獲得一個(gè)隨機(jī)長(zhǎng)度的信息，并產(chǎn)生一個(gè)128位的信息摘要。雖然這些算法的結(jié)構(gòu)或多或少有些相似，但是MD2的設(shè)計(jì)與MD4和MD5完全不同，是因?yàn)镸D2是為8位機(jī)器做過(guò)設(shè)計(jì)優(yōu)化的，而MD4和MD5卻是面向32位的電腦。這三個(gè)算法的描述和C語(yǔ)言源代碼在internetrfcs1321中有詳細(xì)的描述，這是一份最具權(quán)威的文檔，由RonaldL.Rivest在1992年8月向IEFT提交。Rivest在1989年開(kāi)發(fā)出MD2算法，在這個(gè)算法中，首先對(duì)信息進(jìn)行數(shù)據(jù)補(bǔ)位，使信息的字節(jié)長(zhǎng)度是16的倍數(shù)，然后，以一個(gè)16位的檢驗(yàn)和追加到信息末尾，并且根據(jù)這個(gè)新產(chǎn)生的信息計(jì)算出散列值。后來(lái)，Rogier和Chauvaud發(fā)現(xiàn)如果忽略了檢驗(yàn)和將產(chǎn)生MD2沖突。MD2算法的加密后結(jié)果是唯一的---即沒(méi)有重復(fù)的。為了加強(qiáng)算法的安全性,Rivest在1990年又開(kāi)發(fā)出MD4算法。MD4算法同樣需要填補(bǔ)信息以確保信息的字節(jié)長(zhǎng)度加上448后能被512整除（信息字節(jié)長(zhǎng)度mod512=448）。然后，一個(gè)以64位二進(jìn)制表示的信息的最初長(zhǎng)度被添加進(jìn)來(lái)。信息被處51位迭代結(jié)構(gòu)的區(qū)塊，而且每個(gè)區(qū)塊要通過(guò)三個(gè)不同步驟的處理。DenBoer和Bosselaers以及其他人很快的發(fā)現(xiàn)了攻擊MD4版本中第一步和第三步的漏洞°Dobbertin向大家演示了如何利用一部普通的個(gè)人電腦在幾分鐘內(nèi)找到MD4完整版中的沖突（這個(gè)沖突實(shí)際上是一種漏洞，它將導(dǎo)致對(duì)不同的內(nèi)容進(jìn)行加密卻可能得到相同的加密后果）。毫無(wú)疑問(wèn)，MD4就此被淘汰掉了。盡管MD4算法在安全上有個(gè)這么大的漏洞，但它對(duì)在其后才被開(kāi)發(fā)出來(lái)的好幾種信息安全加密算法的出現(xiàn)卻有著不可忽視的引導(dǎo)作用。除MD5以外，其中比較有名的還有SHA-1、Snefru以及Haval等。一年以后，即1991年，Rivest開(kāi)發(fā)出技術(shù)上更為趨近成熟的MD5算法。它在MD4的基礎(chǔ)上增加了"安全-帶子"（safety-belts）的概念。雖然MD5比MD4稍微慢一些，但卻更為安全。這個(gè)算法很明顯的由四個(gè)和MD4設(shè)計(jì)有少許不同的步驟組成。在MD5算法中，信息-摘要的大小和填充的必要條件與MD4完全相同oDenBoer和Bosselaers曾發(fā)現(xiàn)MD5算法中的假?zèng)_突（pseudo-collisions），但除此之外就沒(méi)有其他被發(fā)現(xiàn)的加密后結(jié)果了。VanOorschot和Wiener曾經(jīng)考慮過(guò)一個(gè)在散列中暴力搜尋沖突函數(shù)（brute-forcehashfunction），而且他們猜測(cè)一個(gè)被設(shè)計(jì)專門用來(lái)搜索MD5沖突的機(jī)器（這臺(tái)機(jī)器在1994年的制造成本大約是一百萬(wàn)美元）可以平均每24天就找到一個(gè)沖突。2.MD5用途MD5用途：1、防止被篡改：1）比如發(fā)送一個(gè)電子文檔，發(fā)送前，我先得到MD5的輸出結(jié)果a。然后在對(duì)方收到電子文檔后，對(duì)方也得到一個(gè)MD5的輸出結(jié)果bo如果a與b一樣就代表中途未被篡改。2）比如我提供文件下載，為了防止不法分子在安裝程序中添加木馬，我可以在網(wǎng)站上公布由安裝文件得到的MD5輸出結(jié)果。3）SVN在檢測(cè)文件是否在Checkout后被修改過(guò)，也是用到了MD5。2、 防止直接看到明文：現(xiàn)在很多網(wǎng)站在數(shù)據(jù)庫(kù)存儲(chǔ)用戶的密碼的時(shí)候都是存儲(chǔ)用戶密碼的MD5值。這樣就算不法分子得到數(shù)據(jù)庫(kù)的用戶密碼的MD5值，也無(wú)法知道用戶的密碼（其實(shí)這樣是不安全的，后面我會(huì)提到）。（比如在UNIX系統(tǒng)中用戶的密碼就是以MD5（或其它類似的算法）經(jīng)加密后存儲(chǔ)在文件系統(tǒng)中。當(dāng)用戶登錄的時(shí)候，系統(tǒng)把用戶輸入的密碼計(jì)算成MD5值，然后再去和保存在文件系統(tǒng)中的MD5值進(jìn)行比較，進(jìn)而確定輸入的密碼是否正確。通過(guò)這樣的步驟，系統(tǒng)在并不知道用戶密碼的明碼的情況下就可以確定用戶登錄系統(tǒng)的合法性。這不但可以避免用戶的密碼被具有系統(tǒng)管理員權(quán)限的用戶知道，而且還在一定程度上增加了密碼被破解的難度。）3、 防止抵賴（數(shù)字簽名）：這需要一個(gè)第三方認(rèn)證機(jī)構(gòu)。例如A寫(xiě)了一個(gè)文件，認(rèn)證機(jī)構(gòu)對(duì)此文件用MD5算法產(chǎn)生摘要信息并做好記錄。若以后A說(shuō)這文件不是他寫(xiě)的，權(quán)威機(jī)構(gòu)只需對(duì)此文件重新產(chǎn)生摘要信息，然后跟記錄在冊(cè)的摘要信息進(jìn)行比對(duì)，相同的話，就證明是A寫(xiě)的了。這就是所謂的“數(shù)字簽名”。3.MD5算法的基本原理

MD5算法以512位分組來(lái)處理輸入文本，每一分組又劃分為16個(gè)32位子分組。算法的輸出由4個(gè)32位分組組成，將它們級(jí)聯(lián)形成一個(gè)128位散列值。第1步：填充MD5的第1步是在原消息中增加填充位，目的是使原消息長(zhǎng)度等于一個(gè)值，即比512的倍數(shù)少64位。例如，如果原消息長(zhǎng)度為1000位，則要填充472位，使消息長(zhǎng)度為1472位，因?yàn)?4+1472=1536，是512的倍數(shù)（1536=512*3）。這樣，填充后，原消息的長(zhǎng)度為448位（比512少64），960位（比1024少64位），1472位（比1536少64位），等等，如下圖2-1所示。原始消息圖2-1填充過(guò)程原始消息圖2-1填充過(guò)程填充對(duì)用一個(gè)1位和多個(gè)0位。注意填充總是增加，即使消息長(zhǎng)度已經(jīng)是比512的倍數(shù)少64。因此，如果消息長(zhǎng)度已經(jīng)是448，則要填充512位，使長(zhǎng)度變成960位。因此，填充長(zhǎng)度為1?512的值。填充對(duì)用一個(gè)1位和多個(gè)0位。注意填充總是增加，即使消息長(zhǎng)度已經(jīng)是比512的倍數(shù)少64。因此，如果消息長(zhǎng)度已經(jīng)是448，則要填充512位，使長(zhǎng)度變成960位。因此，填充長(zhǎng)度為1?512的值。第2步：添加長(zhǎng)度增加填充位后，下一步要計(jì)算消息原長(zhǎng)，將其加進(jìn)填充后的消息末尾。先計(jì)算消息長(zhǎng)度，不包括填充位（即增加填充位前的長(zhǎng)度）。例如，如果原消息1000位，則填充472位，使其變成比512的倍數(shù)（1536）少64位，但長(zhǎng)度為1000，而不是1472。這個(gè)消息原長(zhǎng)表示為64位值，添加到加進(jìn)填充后的消息末尾。如果消息長(zhǎng)度超過(guò)264位（即64位無(wú)法表示，因?yàn)橄⑻L(zhǎng)），則只用長(zhǎng)度的低64位，即等于計(jì)算lengthmod264?？梢钥吹剑@時(shí)消息長(zhǎng)度為512的倍數(shù)，成為要散列的消息。如圖2-2所示。原始消息填充（可選）原始消息填充（可選）原始消息填充（可選）長(zhǎng)度64位要散列的數(shù)據(jù)（摘要）圖2-2添加長(zhǎng)度第3步：將輸入分成512位的塊。下面要將輸入分成512的塊，如圖2-3所示。

要散列的數(shù)據(jù)（已摘要）512位512位512位512位 512位512位塊2塊3???塊1圖2-3將數(shù)據(jù)分成512塊第4步：初始化鏈接變量第4步要初始化四個(gè)鏈接變量，分別稱為A,B,C,D,它們都是32位的數(shù)字，這些鏈接變量的初始十六進(jìn)制值如表2-1所示，低位的字節(jié)在前面。表2-1鏈接變量A十卜六進(jìn)制01234567B卜六進(jìn)制89ABCDEFC卜六進(jìn)制FEDCBA98D十卜六進(jìn)制76543210注意低位的字節(jié)在前面指的是LittleEndian平臺(tái)上內(nèi)存中字節(jié)的排列方式，而在程序書(shū)寫(xiě)時(shí),要寫(xiě)成： A=0x01234567B=0x89abcdefC=0xfedcba98

D=0x7654321第5步：處理塊初始化之后,就要開(kāi)始實(shí)際算法了。這是個(gè)循環(huán),對(duì)消息中的多個(gè)512位塊行。5.1步：將四個(gè)鏈接變量復(fù)制到四個(gè)變量a,b,c,d中,使a=A,b=B,c=C,d=D,如圖2-4所示。實(shí)際上，這個(gè)算法將a，b，c，d組合成128位寄存器（abed）,寄存器（abed）在實(shí)際算法運(yùn)算中保存中間結(jié)果和最終結(jié)果，如圖2-5所示實(shí)際上，這個(gè)算法將a，b，c，d組合成128位寄存器（abed），寄存器（abed）ab cd在實(shí)際算法運(yùn)算中保存中間結(jié)果和最終結(jié)果，如圖2-5所示）ab cdabcd圖2-5鏈接變量抽象視圖5.2步：將當(dāng)前512位塊分解為16個(gè)子塊，每個(gè)子塊為32位圖2-6將當(dāng)前512塊分解為16個(gè)字塊5.3步：主循環(huán)有四輪，每輪很相似。每一輪進(jìn)行6次操作，處理一個(gè)塊中的16個(gè)子塊。每一輪的輸入如下：（a）16個(gè)子塊；（b）變量a,b,c,d；（c）常量t,如圖2-7和2-8所示。這四輪中的第1步進(jìn)行不同處理，其他步驟是相同的?！恳惠営?6個(gè)輸入子塊M[0],M[l],???，M[15],或表示為M[i],其中i為1?15。每個(gè)子塊為32位?！猼是個(gè)常量數(shù)組，包含64個(gè)元素，每個(gè)元素為32位。把數(shù)組t的元素表示為t[1],t[2],???，t[64]，或t[i],其中i為1?64。由于有四輪，因此每一輪用64個(gè)t值中的16個(gè)。圖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是或，?是非，人是異或)這些函數(shù)是這樣設(shè)計(jì)的：如果x，y和z的對(duì)應(yīng)位是獨(dú)立和均勻的，那么結(jié)果的每一位也是獨(dú)立和均勻的，函數(shù)F是按逐位方式操作；如果X,那么Y,否則乙函數(shù)H是逐位奇偶操作。設(shè)Mi表示消息的第i個(gè)子分組(從0到15)，<<<S表示循環(huán)左移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,然后用下一分組數(shù)據(jù)繼續(xù)運(yùn)行算法，最后MD5算法產(chǎn)生128位的輸出是A，B，C和D的級(jí)聯(lián)，其中低字節(jié)始于A，高字節(jié)終于D。至此整個(gè)MD5算法處理結(jié)束。4.運(yùn)行環(huán)境及語(yǔ)言運(yùn)行環(huán)境：Eclipse條件：普通PC機(jī)編程語(yǔ)言：java5.MD5算法的實(shí)現(xiàn)：了解MD5算法的基本原理之后，本文將調(diào)用MD5主函數(shù)實(shí)現(xiàn)對(duì)文件處理的測(cè)試程序。此程序的功能是在WindowsXP操作系統(tǒng)下用JAVA語(yǔ)言在Eclipse編程環(huán)境下實(shí)現(xiàn)對(duì)固定的文件生成128位的MD5值，實(shí)驗(yàn)結(jié)果如下：keyBeaiiTestsuite:keyBeaiiC):D41D&CD98FO0B2O4E98OO^8ECF8427EkeyBeaiit"學(xué)號(hào)A泌焉FOB花嗣包C貂爼52応AB孔6CF564k眇B(yǎng)ean〔迄01311眇5廠)<644BBEDD2F^9703A0EE7CE5DE4D9DS26keyBeaii("cheng1and:DABD1DB2327