是否存在一個字元串，它的md5值是其自身？

12-26

是否存在一個字元串str，它的md5值是其自身？
即： md5(str) == str
擴展一下，是否存在字元串str1和str2，滿足str1的md5值是str2，str2的md5值是str1？
即：
md5(str1) == str2
md5(str2) == str1
除了寫程序暴力驗證外，有沒有其他好的驗證方法？
假設暴力驗證，當今最快的計算機大約能多長時間出答案？
利用現在流行的分散式系統能否快速驗證？

個人猜測沒辦法快速驗證。
因為md5的目的是為了hash，我們假設每個字元串md5之後的結果是一個獨立均勻分布的隨機128比特串，那麼每個128比特串hash到自己的概率是 $2^{-128}$ ，不存在 md5(str) == str的概率是 $(1-2^{-128})^{2^{128}}$ 。這個值幾乎就等於 $frac{1}{e}$ ，既不是足夠大，也不是足夠小，所以很難說。
如果暴力驗證，需要驗證數目的數量級在10^38左右。即使保守估計一台計算機一微秒能夠hash一個字元串，全球100億台計算機一起驗證，仍需要大約10萬億個世紀才能枚舉所有的可能。所以如果不是超級幸運一上來就碰巧發現一個解的話，以地球人的科技短時間內不可能完成。

-1 題注
我在另一個問題數學上：能否實現在文件中保存文件自己的MD5值?對此問題進行了回答，結果那個問題現在跳轉到這個問題來了，桑心… 因此類似的答案也可以回答在這個問題裡面了。為了方便，我把自己的答案移植到這個回答裡面，希望帶給大家一定的幫助。

===============================分割線===============================
0 更新日誌
2014.11.20下午17:45，第一版回答。感謝 @徐釀泉， @bhuztez ， @肖劍等人在討論區的討論，這些討論啟發了我對此問題的回答。
2014.11.20晚上20:50，第二版回答。感謝 @之幽在線下與我的討論，讓我對這個問題有了更深刻的認識，並補充了答案。
2014.11.20晚上22:00，第三版回答。感謝 @玄星指出了我回答中的TYPO，我對回答中的TYPO進行了修改。
2014.11.21上午10:00，第四版回答。感謝 @玄星指出了我回答中的另一個錯誤，並且在其回答中進行了補充。話說知乎能不能增加一個共同回答者的功能啊，問題很複雜的話，可能需要很多人的聯合貢獻才能做出完整的答案吧？

===============================分割線===============================
謝邀。
這個題有點意思，開始的時候我也把這個問題想簡單了。深入思考以後，這個問題還是一個比較有趣的問題呢。

問題是：能否實現在文件中保存文件自己的MD5值？我們進一步對問題進行精練，這個問題一種有2種可能的理解：

By @bhuztez ：找到一個值 $x^*$ ，使得 $x^* = MD5(x^*)$
By @徐釀泉：找到三個值 $x^* in {0,1}^{*},y_1={0,1}^*,y_2={0,1}^*$ ，使得 $x^* = y_1 || MD5(x^*) || y_2$

這裡需要解釋一下，因為文件存儲過程中，文件名本身也將作為文件的內容之一，所以 @bhuztez 給出的類似用git裡面將MD5值當做文件名存儲內容，我認為並不是題主想要的答案，雖然這個方法可行，一定存在並且非常容易實現。在此，我認為文件名也需要包含在MD5的計算過程中，所以這種情況我考慮在第2種可能的解裡面。下面分別予以回答。

1. @徐釀泉的理解

這個問題的答案我想 @肖劍的評論已經給出的很清楚了，鏈接為：stackoverflow.com 的頁面。我們可以稍微翻譯和理解一下這個答案。答案的解釋如下：

（1）x*的條件

因為對於任意的輸入x，MD5(x)的值都是128bit（即： $forall x, MD5(x) in {0,1}^{128}$ ），因此如果我們能找到一個滿足題目條件的值，則必有 $x^* in {0,1}^{128}$ 。

（2）滿足要求的x*是否存在。

假定MD5的輸出分布是均勻的（當然這只是一個假設了，實際上MD5的輸出並非嚴格均勻），因此對於任意x的輸入，其輸出滿足條件的概率為 $frac{1}{2^{128}}$ ，那麼對於任意x的輸入，其輸出不滿足條件的概率為 $1-frac{1}{2^{128}}$ 。那麼，對於所有，其輸出都不滿足條件的概率即為 $(1-frac{1}{t})^t$ ，其中t=2^128。我們知道， $[mathop {lim }limits_{t o infty } {left( {1 - t} ight)^t} = 1/e]$ ，並且2^128確實是一個相對來說非常大的數，因此存在的概率為 $1-(1-frac{1}{t})^t approx 1-1/e$ 。

（3）如果存在，如何尋找x*。

尋找方式似乎沒有多項式解法。我本來以為，尋找這個值的演算法難度至少大於找到MD5碰撞的難度。但是我原始答案給出的Reduction是錯誤的。 @玄星同學給出了一個構造，即使存在x=MD5(x)的解，MD5本身也可能是抗碰撞的，請參考他的回答：是否存在一個字元串，它的md5值是其自身？ - 知乎用戶的回答。

2. @徐釀泉的理解

（1）x*的條件。

我們可以類似地得到，如果我們能找到滿足題目條件的值，那麼x*的位數至少大於等於128。

（2）滿足要求的x*是否存在。

經過一定的討論，我們可以得出如下推理。我們設想一個簡單的情況，我們只在MD5(x)前面補項，題目變為了：找到兩個值 $x^* in {0,1}^{*},y={0,1}^*$ ，使得 $x^* = y || MD5(x^*)$ 。同樣假設MD5的輸出是均勻分布的，那麼MD5(x*)與x*的後128位嚴格相等的概率是 $frac{1}{2^{128}}$ ，其輸出都不滿足條件的概率即為 $(1-frac{1}{t})^{t+t$ ，其中t=2^128，t"=2^l，且l是y的比特長度。注意到，這個概率式指數上變大了，這是因為所有可能的情況又2^128變成了2^{128+l}。前面我們知道當t=2^128時，概率約為1-1/e。而新的概率式可以寫為 $(1 - t)^{t cdot t$ 。因此，隨著t的增大，這個等式的概率將逐漸趨近於0，也就是說，存在滿足條件的x的概率逐漸趨近於1。舉個例子，當l也為128時，t" = t = 2^128，存在這樣的x的概率結果變為了 $1-(1/{e^2}) approx 86.4\%$ 。

如果考慮在後面補位，也能得到類似的結論。如果前面後面都補位的話，也可以等價地思考，結論就是：隨著允許補位的y_1，y_2的長度變長，存在解的概率也將逐漸趨近於1。由於我們只要找到一個滿足條件的y即可，則最終的概率結果會更高，但是似乎不能嚴格取到1.

（3）如果存在，如何尋找x*。

與上面的相同，尋找方式似乎沒有多項式解法。

===============================分割線===============================

2014.11.20晚上20:50補充答案。

在線下， @之幽和我對此問題進行了深入的討論。他通過構造的形式證明了一定存在這樣的x，使得x = y_1 || MD5(x) || y_2。在此我用一個等價形式描述 @之幽的構造。在我的證明中，對於l變長，存在x的概率趨近於1，但是應該不能取到1.然而， @之幽的構造是正確的，他找到了一個必然解。對此我需要說明為何其構造與我的證明有違背的地方。

@之幽的等價構造如下。考慮一個子串x，其構造形式如下： $[x = underbrace {0 ldots 00}_{128}parallel underbrace {0 ldots 01}_{128}parallel underbrace {0 ldots 10}_{128}parallel cdots parallel underbrace {1 ldots 10}_{128}parallel underbrace {1 ldots 11}_{128}]$

也就是說，x為從全0到全1的全部128倍比特串的拼接。由於 $MD5(x)in {0.1}^{128}$ ，因此x中必然存在一個子串，使得這個子串等於MD5(x)，這樣就構造出了滿足題目條件的x。

這個子串既然一定能夠構造，那麼為何與我給出的證明有矛盾之處呢？這是因為l的取值已經不是一個多項式值了。我們注意到，x的長度為128*2^{128}，這個子串的長度使得t"遠遠大於t，因此我答案中的概率取值式子就不成立了。

但
是，這個構造有個小問題，就是x的長度太長，以至於我們不能認為其能用多項式長度的存儲空間來表示。因此，MD5演算法的輸入不為多項式長度，在這種情況
下，我們也就不能認為MD5本身是一個多項式函數了。當然了，這也反映出了計算機科學與數學之間的Gap，即多項式與指數的區別。

進一步補充，既然一定存在這樣的x，我們能否用多項式時間找到這樣的x 呢？ @之幽給我看了這樣一個鏈接：MD5原理說明_WuD1873_新浪博客。其中一段重要的說明如下：

2007
年，Marc Stevens，Arjen K. Lenstra和Benne de
Weger進一步指出通過偽造軟體簽名，可重複性攻擊MD5演算法。研究者使用前綴碰撞法（chosen-prefix
collision），使程序前端包含惡意程序，利用後面的空間添上垃圾代碼湊出同樣的MD5 Hash值。

也就是說，這個演算法以x作為輸入，構造了x||y，使得MD5(x) = MD5(x || y)。這個構造雖然與題目的描述不太一樣，不過也是一個有價值的引用了。其原文引用為：
Marc
Stevens, Arjen K. Lenstra, Benne de Weger: Chosen-Prefix Collisions for
MD5 and Colliding X.509 Certificates for Different Identities.
EUROCRYPT 2007: 1-22。

MD5 是否有不動點尚無定論
周期軌的話……你從全 0 開始反覆 MD5 總能構造出一個來，因為所有 128 位串數量是有限的

這問題挺有意思的，如果擴展一下，變成對於一個加密演算法，假設明文和密文等長，明文是否有可能和密文相等。這個答案是肯定的，因為任何加密演算法都可以看作是規定長度的二進位位的組合。如果明文只有一位，例如0，如果通過某個演算法，密文也是0的話，就出現了明文和密文一致。

這種極端情況下搜索空間只有1位，也就是所有可能性是2^1次。你心算就好。如果是md5演算法，輸出128位的，那麼搜索空間急劇增大，對於每一組明文，搜索空間變成2^128，那暴力破解基本是做不到了。

那如何解決這個搜索問題呢，目前的基本思路是通過某些演算法的數學特性來降低搜索空間，比如把搜索空間從2^128降低到2^100就是一種進步。對於MD5這種HASH演算法，它的破解可以理解為找到一個碰撞，也就是兩個不同的明文，MD5後的128位的HASH碼相同。目前這個搜索空間已經降低到了2^50左右（數字不太準確，手機打，懶得看網頁查精確數據了）。

關於題主的問題，明文和密文（Hash值）完全一樣，應該是找碰撞的一個子問題，目前通過數學方式解決它的話，搜索複雜度差不多就是2^50左右吧。

首先，支持 @劉巍然的回答。

此回答是對 @劉巍然的回答里，一個地方的補充說明以及其它的思考。

斷言1：

如果h"是一個抗碰撞散列函數，則對於時間複雜度為多項式的隨機演算法A，尋找到一個x*,使得x*=h"(x*)這件事不一定是困難的。

(以下用英語寫證明的原因主要是便於同行閱讀，因為術語的確太多。)

Claim 1. If h『 is a collision resistant hash function, it is NOT always hard for ppt adversary A to find a x*, such that x* = h』(x*).

Proof: (sketch)

Let $mathcal{H}$ be a general collision resistant hash function family ${h|{0,1}^* o {0,1}^k}$ , (general := Exept for digest size and collision resistance, another common property of 2 hash function h_i and h_j exists only with negligible probability, if they are sampled from H uniformly at random).

$mathcal{H}$ can be publicly known.

Define a keyed hash function h" =(Gen, Hash)as:

$Gen(1^n):$

Sample h from $mathcal{H}$ uniformly at random.

return s=h as key for h". (s can be interpreted as binary description, or a index of h in H)

$Hash(s, x)$ :

$h$

Remark: Here, the key of h" is s=h, which would also be sent to the adversary A agianst h" in the game HashColl(1^n).

It is trivial that $x^{*}=0^l$ .

However, it still remains hard for A to determine an x" with $x$ (reducible to the collision resistance and sampling of h. In addtion, collision resistance also implies 2nd pre-image resistance)

or to find

x1,x2 with $x_1 e x_2 wedge h$ (reducible to the collision resistance of and sampling of h).

Thus, the existence of x* with x*=h"(x*) does not necessarily break the collision resistance of h".

(證明完畢)

p.s.：

用帶key的Hash和Hash函數族增加隨機性, 是為了避免了討論更特殊的hash。

所謂特殊hash，是指比如再次從h"(x)定義一個h""(x), 使得有兩個已知固定值被映射到0^L的話，直接同時破壞了collision resistance。

另，如果直接把h換成RO來構造h『，結論就非常直接了。(一如既往地overkilling……)

=================分割線========================================

目前在 @劉巍然的答案中已經證明的是存在x，使得 $x = y_1 || MD5(x) || y_2$ 。

我自己試著從概率的方式來推論一下。

如果x為完全隨機選取的0，1字元串，那麼x需要多長，才能保證MD5(x)以大於1/2的概率在x內部出現？

如果簡化問題，把x視為由128位的一個個block所組成，設L為總共的block數。那麼這個問題（在某種程度上）可轉化為，為使x有可能覆蓋一半以上的來自{0,1}^128的字元串，L的期望值是多少？

設這個字元串的個數為C=2^127。

這就變成了類似

Coupon collector"s problem

L的數量級是O(C log(C))。

比構造的、使MD5(x)一定出現的L長度，即2^128 = 2C 還要長……

如果不簡化，問題比較複雜，方程我還沒想出來……

不過肯定比簡化版的L小，因為一個129位的0,1字元串相當於兩個128位的，一個130位的相當於3個128位。

分割線到這裡為止是亂彈，請輕拍：P

用python寫了個「碰運氣」的解決方案，大體思路是從某個隨機的字元串a開始，對這個字元串求md5得到字元串b，然後比較b是否和a相同，不相同的話就對b再次求md5然後比較。找到就記錄並停止。
代碼如下：

#!/usr/bin/env python # coding=utf-8 import os import md5 import datetime import random a = str(random.randint(0,36**32)) start = a try: os.mkdir("find_md5") except: pass open("find_md5/%s.txt"%start,"a+").write("start from %s at %s"%(a,datetime.datetime.now())) temp_a = a count = 0 while True: b = md5.new(a).hexdigest() count += 1 if count % 100000 == 0: print count if a == b: print "find:",a open("find_md5/%s.txt"%start,"a+").write("find md5(a)=a : %s at %s"%(a,datetime.datetime.now())) break if temp_a == b: print "ab,",temp_a,b open("find_md5/%s.txt"%start,"a+").write("find md5(a)=b : %s %s at "%(temp_a,b,datetime.datetime.now())) temp_a = a a = b

附一張霸氣的運行監控截圖：

有人也在找MD5的fixed point. See this: The Kember Identity : Elliott Kember dot Com
似乎還沒有人找到這樣的數.
Google了一下, 發現並沒有相關文章從MD5的機制上對這個問題進行論證.

我想這個問題沒人敢拍著胸脯說一定沒有，那就不妨實驗一下。
在這個問題中，由於明文也是md5，即128bit，那麼不妨遍歷所有的md5空間，並逐個hash，尋找這對值，空間大小是2^128。
有答主說用人類最牛逼的計算機，需要計算xxx年就會有結果了，咱不吹那不著邊的牛逼。我家旁邊是山東省計算中心，裡面有台超級計算機，全部開啟每小時電費需要30w rmb，馬雲可能都嫌貴。
另外我還有台筆記本，i3-2350M 2.3GHZ，不過這個用得起，benchmark走起

加密了32個A，正好128bit，省去了演算法中填充分組的時間，4千萬次只需要17秒多。平均每秒232w
什麼，用C、彙編寫benchmark會快一些，能快一個量級嗎？
benchmark是單線程，只佔用一個核心，CPU佔用率也維持在25%左右。

算你i3牛逼帶冒煙，四個核心一起跑運算效率*4（i3其實是雙核虛擬四核我會告訴你？），就算不太夠超超頻也總是能夠的，結果：929w/s
一年能跑：29318768158w/year 加起來繞地球三圈
那麼要遍歷2^128的md5空間則需要：
1160629822803571901201142.5422336 年
我不太清楚山東超算中心的計算機與我的I3性能差距是多少，抱歉真沒概念（聽說有國內黑客入侵過超算，膜拜）。但就同一時期同一製造工藝的同是馮諾依曼架構的單個計算核心，不會有幾個數量級的差距（我會告訴你超級計算機的核心技術其實就是「大主板」技術？）。

削弱版一定存在的。。

構造方法很簡單，先隨便來一段隨機字元，然後循環：

如果當前字元不含其自身md5，那麼將其md5加在當前字元之後；
如果包含的話return

end if

循環一定結束，因為md5 space 有限

按我的經驗，650tiboost顯卡加速的多線程md5演算法，1億或10億條/s的水平！！！！是不是嚇人？，just try！

我覺得是不太可能的，見：
RSA演算法原理（一）
RSA演算法原理（二）

md5加密等於本身
有人研究過。我感覺是有的。哈哈

這個你可以自己寫程序去驗證一下，MD5的值是有限個數，窮舉一個個去驗證就好了。

可以試試咯，16的32次方運算就知道了，全世界的計算機不考慮調度損耗的話跑一年應該夠了吧。

可以比較明確的說沒有，從hash運算的角度來說
1. 好的hash運算在同等位數的情況來說是滿映射的，
2.hash運算是雪崩效應，即使微小的改動，hash會發生較大的變化
你可以驗證所有的hash運算結果（32位的，比如crc等），沒有這樣的可能

當然會重複了，想想md5 個數只有 (26+10)^32個，字元串個數顯然不止這麼多

要說它一定有，應該也不可能，比如說最簡單的例子：
2^2通過y=f(x) x=0，1，2，3映射到y=3，2，1，0。
找不到一個x可以讓x=f(x)。

要麼證明hash128不屬於上面的f(x)類型。
要麼證明2^128 到2^128的映射，存在fixed point。

有時間了用彙編在支持HW hash的機器上寫個程序試試看就好了。

update:下面的計算方式太慢了。
----------------------------------------------------------------------------------------
如果是128bit的計算機，應該是挺快才對：

for(UInt128 i = 0; i &< = MAX_UInt128, i++){ if(hash(i) = i){ print("i = [%d] ", i); break; } }