摘要：認(rèn)為要從的結(jié)果中取得原文才算破解，本身就是對(duì)摘要算法的誤解。摘要算法與上面兩種完全不同，前面兩種密碼是用于防止信息被竊取，而摘要算法的目標(biāo)是用于證明原文的完整性，也就是說用于防止信息被篡改。當(dāng)進(jìn)行摘要算法后，信息就丟失了。

轉(zhuǎn)載請(qǐng)注明出處 http://www.paraller.com
原文排版地址 http://www.paraller.com/2016/05/22/%5B%E8%BD%AC%5DMD5%282%29-%E7%A0%B4%E8%A7%A3MD5%E4%B9%8B%E6%88%91%E8%A7%81/

轉(zhuǎn)載：http://blog.csdn.net/raptor/article/details/97270 對(duì)原文做了修改

MD5是一種摘要算法，所以理論上是不可能從簽名取得原文（見下面說明）。認(rèn)為要從MD5的結(jié)果中取得原文才算破解，本身就是對(duì)摘要算法的誤解。它通常應(yīng)用于數(shù)字簽名中，用于標(biāo)識(shí)原文的原始性--即在簽名后未作任何的修改。用不同的原文可以產(chǎn)生相同的簽名，這也就意味著簽名可能失效，就已經(jīng)可以證明這種摘要算法的不安全。

王小云的發(fā)現(xiàn)證明了有方法可以產(chǎn)生碰撞，但正如GIGIX那邊一位匿名兄所說，這只是非特定碰撞，而要偽造簽名則必須能產(chǎn)生特定碰撞。所以說MD5并未被完全攻破，但也已經(jīng)是一個(gè)重大的突破了。

首先要說的是為什么需要使用密碼？因?yàn)槲覀兺ǔ５耐ㄐ怒h(huán)境是不安全的。
那什么是不安全的通信環(huán)境呢？不安全至少表現(xiàn)在兩個(gè)方面：

通信的內(nèi)容可能被竊?。?/p>

二是通信的內(nèi)容可能被篡改。

通常的密碼使用就是為這解決這兩方面的問題。
而如果有方法使某種密碼的作用失效，就可以說這種密碼被破解了。

常用的密碼有很多種類，其中最常用的是這三種：

摘要算法

非對(duì)稱密碼

摘要

對(duì)稱密碼

特點(diǎn)是：加密與解密用相同的密鑰，甚至可能用相同的算法。比如從最簡(jiǎn)單的異或，到常用的DES、BLOWFISH、IDEA等。它們通常的用途是這樣的：
發(fā)送方將源文（M）用密鑰（K）加密：E=ENC（M，K）
然后將E通過不安全網(wǎng)絡(luò)傳給接收方，接收方用相同的密鑰（K）解密：M=DEC（E，K）
只要算法足夠好，并且保管好密鑰（K），就可以保證這種通信是安全的，因?yàn)閯e人即使知道了密文（E）和算法ENC/DEC，也無法知道明文（M）。

對(duì)于這種密碼來說，如果有方法可以從密文（E）和算法ENC/DEC中導(dǎo)到密鑰（K）或明文（M），則意味這種密碼被破解。比如簡(jiǎn)單異或算法就可以用統(tǒng)計(jì)分析法簡(jiǎn)單地破解掉。但即使是現(xiàn)在被認(rèn)為不夠安全的DES算法（已經(jīng)有近三十年歷史了），也需要有大量的明文/密文對(duì)（2的數(shù)十次方對(duì)），并需要大量的計(jì)算時(shí)間才能求得其密鑰（K）。

非對(duì)稱密碼

因?yàn)樵趯?duì)稱密碼中，通信雙方需要約定一個(gè)共同的密鑰（K），如果這個(gè)約定過程也不安全，就可能出現(xiàn)密鑰的泄露，而對(duì)于對(duì)稱算法來說，密鑰一旦泄露，之后的通信過程也就不攻自破了。
通常的非對(duì)稱密碼就是所謂的公鑰密碼算法，比如現(xiàn)在最常用的RSA（由R. L. Rivest和A. Shamir等人基于大數(shù)的因數(shù)分解極為困難的原理而創(chuàng)建），或是最近更為時(shí)髦的“橢圓曲線”，因?yàn)槲业臄?shù)學(xué)水平太差，具體算法也說不清楚，只知道大致是這樣的：
顧名思義，它所用的算法特點(diǎn)在于加密與解密用的密鑰是不一樣的。

而其中雙方都不需要知道對(duì)方的私鑰，這就避免了約定密鑰導(dǎo)致的不安全。
非對(duì)稱密碼的算法本身又決定了用私鑰加密的內(nèi)容必須用公鑰才能解，反之亦然，并且算法還保證僅知道公鑰和密文無法導(dǎo)出私鑰，由此決定了通信的安全。
當(dāng)然，如果有方法可以從公鑰導(dǎo)出私鑰來，則這種算法即告被破解。但至少目前RSA還是安全的，因?yàn)閺默F(xiàn)在的數(shù)學(xué)理論上可以證明RSA的算法是一類NPC（NP完備）類問題，只要密鑰足夠長(zhǎng)（RSA要求至少是10的100次方以上，實(shí)際使用時(shí)更要大得多），以現(xiàn)在最先進(jìn)的計(jì)算機(jī)來算，其時(shí)間成本也是不可能達(dá)到的。

摘要算法

與上面兩種完全不同，前面兩種密碼是用于防止信息被竊取，而摘要算法的目標(biāo)是用于證明原文的完整性，也就是說用于防止信息被篡改。通常也被稱為：HASH算法、雜湊算法、簽名算法。它的特點(diǎn)是：從不定長(zhǎng)的原文中產(chǎn)生一個(gè)固定長(zhǎng)度（如MD5是128位）的結(jié)果，稱為“簽名”（S），這個(gè)簽名必須對(duì)原文非常敏感，即原文即使是有少量的變化，也會(huì)導(dǎo)致這個(gè)簽名面目全非。比如傳統(tǒng)的CRC或是現(xiàn)在要說的MD5、SHA等都是這類算法。

摘要算法的用途通常是這樣的：

密碼驗(yàn)證：

如Linux或一些論壇用的方法，用戶設(shè)置密碼時(shí)，服務(wù)端只記錄這個(gè)密碼的MD5，而不記錄密碼本身，以后驗(yàn)證用戶身份時(shí)，只需要將用戶輸入的密碼再次做一下MD5后，與記錄的MD5作一個(gè)比較即可驗(yàn)證其密碼的合法性。

完整性簽名驗(yàn)證：

比如發(fā)布一個(gè)程序，為了防止別人在你的程序里插入病毒或木馬，你可以在發(fā)布這個(gè)程序的同時(shí)，公開這個(gè)程序文件的MD5碼，這樣別人只需要在任何地方下載這個(gè)程序后做一次MD5，然后跟公開的這個(gè)MD5作一個(gè)比較就知道這個(gè)程序是否被第三方修改過。

一個(gè)安全的摘要算法在設(shè)計(jì)時(shí)必須滿足兩個(gè)要求：

尋找兩個(gè)輸入得到相同的輸出值在計(jì)算上是不可行的，這就是我們通常所說的抗碰撞的；

找一個(gè)輸出，能得到給定的輸入在計(jì)算上是不可行的，即不可從結(jié)果推導(dǎo)出它的初始狀態(tài)。

反之，如果某種摘要算法不能同時(shí)滿足上面兩個(gè)條件，則它就是不安全的。其實(shí)主要還是前一個(gè)條件，因?yàn)閺睦碚撋虾苋菀鬃C明后面一個(gè)條件基本上都是可以滿足的：

摘要算法對(duì)任意長(zhǎng)的原文產(chǎn)生定長(zhǎng)的簽名，按照香農(nóng)的信息論，當(dāng)原文的長(zhǎng)度超過一定的程度的時(shí)候，簽名中就無法記錄原文中的所有信息，這意味著存在著信息的丟失，所以我說理論上不可能從簽名中恢復(fù)原文。
為什么說理論上呢？就是說當(dāng)這種摘要算法被完全攻破時(shí)，也就是說可以從簽名恢復(fù)出任意原文，注意：是任意原文，因?yàn)?strong>所有的摘要算法的特點(diǎn)就是存在著一個(gè)無窮大的碰撞原文的集合。而真正的原文只是其中一份。對(duì)應(yīng)這個(gè)無窮大的集合來說，這就是一個(gè)無窮小，便是我曾經(jīng)說過的：

可能性為零，不表示不可能。

解釋得具體一點(diǎn)是這樣：假設(shè)原文含有信息量（I），而簽名的長(zhǎng)度有限（如MD5的128位），則它的信息量只有(i)，因?yàn)橥ǔ?i < I （除非原文非常短），所以可以這么說：I=i+i"。因?yàn)镮沒有限制，而i有限制，則 i" 也是一個(gè)沒有限制的量。當(dāng)進(jìn)行摘要算法后，i" 信息就丟失了。
反過來，如果現(xiàn)在這種摘要算法被攻破了，可以從 i 反推回去，但因?yàn)?i" 信息已經(jīng)丟失，意味著 i + I" （其中 I" 為任意信息）都可能是 I （碰撞）。但 I" 是一個(gè)無窮集合，并且 i" 屬于 I"。這說明：理論上可以從 I" 中找到 i" 從而恢復(fù)出原文 I ，但是可能性為零（1/∞=0）。

但要做到前面一點(diǎn)就不容易了。因?yàn)?strong>絕對(duì)無碰撞的算法不可能是一個(gè)摘要算法，而只能是一個(gè)無損壓縮算法。它必須包含原文的所有信息，也就意味著它一但被攻破，可以唯一地恢復(fù)出原文。并且它的結(jié)果肯定是不定長(zhǎng)的，因?yàn)樗枰牡乃行畔ⅲ?dāng)然會(huì)根據(jù)原文的長(zhǎng)度而變。僅這兩點(diǎn)就決定了，它不可能是一個(gè)好的簽名算法。
最主要的一點(diǎn)是：摘要算法的用途決定了，它只要能找到碰撞就足以讓它失效，并不需要找到原文。

以前面的兩個(gè)例子來說：·
比如Linux的用戶安全機(jī)制，只要得到用戶密碼文件（其中記錄了密碼的MD5），然后隨便生成一個(gè)碰撞的原文（不一定要跟原密碼相同），就可以用這個(gè)密碼登錄了。
但后面的程序發(fā)布的例子就要難得多，因?yàn)樗仨毮苌商囟ǖ呐鲎?，即在程序中插入病毒或木馬后再填充一些數(shù)據(jù)使之生成與原來相同的MD5。
不過我昨天仔細(xì)想了一下，以MD5為例，要產(chǎn)生特定的碰撞應(yīng)該還是不太可能的，因?yàn)镸D5的128位信息量已經(jīng)有點(diǎn)大了，如果要產(chǎn)生特定碰撞，需要填充的數(shù)據(jù)可能非常之大，導(dǎo)致偽造的原文比真實(shí)的原文大得多，可能達(dá)到若干個(gè)數(shù)量級(jí)的差別，這樣的偽造就已經(jīng)失去意義了。

我舉的例子來說明一下。比如昨天我說的，假如有兩個(gè)人的指紋完全相同，而且我可以很快的找出這兩個(gè)人，那么，在法律角度來說，我們就不能把指紋作為一個(gè)有效證據(jù)。雖然這兩個(gè)同指紋的人并沒有互相冒充的意思。

同樣的，現(xiàn)在刻意去偽造文件并產(chǎn)生相同的MD5碼還做不到，但是，如果可以在短時(shí)間內(nèi)找到兩份相同的檔案，他們的MD5碼相同，那么，MD5作為數(shù)字簽名的“法律意義”便失去了。而數(shù)字簽名是用來干嗎的？就是讓一個(gè)電子文檔具有法律意義的。所以，我說，這個(gè)發(fā)現(xiàn)是動(dòng)搖了數(shù)字簽名的根基。