本文目的

在我的上一篇文章《MD5算法，看這篇就夠了》中，我描述了md5算法的基本步驟，今天跟大家分享一下破解md5的原理。參考文獻(xiàn)在文末，有興趣的讀者可以讀讀。

符號(hào)

文本中出現(xiàn)諸如M0，M1，以粗體字母+非粗體數(shù)字組合的符號(hào)等同于公式中該字母和以該數(shù)字作為下標(biāo)的符號(hào)。

MD5算法回顧

首先我們來(lái)大概回顧一下MD5算法。

填充。將消息E的長(zhǎng)度進(jìn)行填充，使其滿足對(duì)512取余為448。
補(bǔ)充數(shù)據(jù)長(zhǎng)度。將原消息以64位表示，并添加到填充的數(shù)據(jù)之后，我們得到M。
初始化緩存器。A：01 23 45 67；B：89 ab dc ed；C：fe dc ba 98；D：76 54 32 10。A，B，C，D都是32位的緩存器，在下一步運(yùn)算中使用。
進(jìn)行迭代處理。M的長(zhǎng)度是512的整數(shù)倍（448+64），我們將數(shù)據(jù)M以512長(zhǎng)度為單位進(jìn)行劃分，此時(shí)M=（M0,M1,M2....M(N-1)），在運(yùn)算中我們將這512位用16個(gè)32位的數(shù)來(lái)表示。接下來(lái)，我們對(duì)M進(jìn)行遍歷，對(duì)其中的每一項(xiàng)進(jìn)行四輪運(yùn)算，每一輪都要進(jìn)行16則計(jì)算，計(jì)算的結(jié)果緩存到A，B，C，D緩存器中，并對(duì)下一次迭代產(chǎn)生影響。
輸出。我們從A的低位字節(jié)開會(huì)，到D的高位字節(jié)結(jié)束，每一個(gè)都是32位，最終拼接的結(jié)果就是4*32 = 128位，這就是MD5計(jì)算的結(jié)果。

上述迭代的過(guò)程我們稱之為雜湊運(yùn)算?？梢悦枋龀蛇@樣：

公式中的Mi表示為M中下標(biāo)為i的元素，H0是緩存器中的初始值（A，B，C，D），Hi表示第i-1輪中緩存器中的結(jié)果，四輪運(yùn)算我們抽象成函數(shù)f。

差分攻擊簡(jiǎn)介

哈希函數(shù)最重要的分析方法是差分攻擊，同時(shí)也是分析分組密碼最重要的方法之一。差分攻擊大部分是使用異或運(yùn)算的異或差分攻擊，由Eli Biham和Adi Shamir在分析類似DES加密體系的安全性中提出的，他們描述差分密碼分析是一種分析純文本對(duì)（原文）中的特殊差異對(duì)產(chǎn)生的密碼文本對(duì)的差異的影響的方法。

在本文中，我們使用整數(shù)模減（(A-B) mod C）來(lái)進(jìn)行差分分析。

差分攻擊原理

兩個(gè)數(shù)之間的差我們表示為：

對(duì)于M=（M0,M1,M2,....,M(N-1)）和M'=（M0',M1',M2',....,M(N-1)'）。哈希函數(shù)的整個(gè)過(guò)程的差我們可以表示為：

在上式中，△H0表示初始值（A，B，C，D）之間的差，顯然是0?！鱄表示最終兩個(gè)消息之間的差，△Hi表示在第i次迭代之后結(jié)果的差，當(dāng)然也是下次迭代的初始差值。我們的目標(biāo)很簡(jiǎn)單，假如我們使得最終的結(jié)果△H=0的話，也就是M和M'的哈希結(jié)果是一樣的，M和M'就產(chǎn)生了碰撞。