什麼是最小輸入值的 MD5 衝突？
我對小輸入消息的 MD5 衝突感興趣。
http://www.mscs.dal.ca/~selinger/md5collision/上給出的碰撞範例顯示了兩個不同的字元串，其中只更改了少量數據以提供相同的 md5，但感覺更像只是更改未計入計算的值。我還沒有遇到過兩個看似隨機的事物達到相同值的例子。我確實嘗試了一個小腳本來找出答案，但顯然它離得還不夠遠。
我的問題的一種形式化是：
什麼是最小b∈ñ $ b\in\mathbb N $ 使得存在一種∈[0,b) $ a\in[0,b) $ 和米D5(一種)=米D5(b) $ \mathbf{MD5}(a)=\mathbf{MD5}(b) $
要回答您的問題，我們必須首先說明對於整數X $ x $ , 我們定義 MD5(X $ x $ ) 為編碼的MD5 散列X $ x $ 作為位序列。實際上，MD5 需要一個位序列作為輸入，而不是整數。我們應該選擇正常編碼；我選擇big-endian。因此，整數44 $ 44 $ 編碼為 6 位序列：101100。有人可能會注意到，這樣做，我錯過了一半可能的 MD5 輸入：實際上，當將整數轉換為其最小長度的大端無符號編碼時，第一位始終是'1’。
儘管編碼對於下面的討論並不重要，但它會影響b $ b $ 你正在尋找的。事實上，每個編碼都會產生另一個b $ b $ .
由於 MD5 有一個128 $ 128 $ -bit 輸出，它可以有（最多）2128 $ 2^{128} $ 不同的輸出。如果我取整數0 $ 0 $ 到2128 $ 2^{128} $ （含），那麼我有2128+1 $ 2^{128}+1 $ ：因此在數學上可以保證其中至少有兩個散列到相同的值。換句話說，證明存在整數值一種 $ a $ 和b $ b $ 這樣0≤一種<b≤2128 $ 0 \leq a < b \leq 2^{128} $ 和MD5（一種 $ a $ ) = MD5)b $ b $ ).
的實際最小值b $ b $ 不知道。但是，預計最小b $ b $ 在附近264 $ 2^{64} $ . 這來自於所謂的生日問題：如果我隨意取n $ n $ 一組大小內的值ñ $ N $ ，然後我會選擇一個我之前已經選擇過的n $ n $ 到達√ñ $ \sqrt{N} $ 或者。
獲得b $ b $ , 確實必須生成 MD5(X $ x $ ) 對於所有的值X $ x $ ， 以。。。開始0 $ 0 $ , 直到我們得到一個我們已經擁有的值。MD5 的預期成本很高：264 $ 2^{64} $ 是在技術範圍內，但不是家用電腦。在四核 x86 上，人們可能期望大約226 $ 2^{26} $ 每秒 MD5 評估；使用好的 GPU，您可以達到233 $ 2^{33} $ 每秒（這傢伙聲稱比236 $ 2^{36} $ ，但那是使用 8 個 GPU）。你仍然需要大約 60年才能達到264 $ 2^{64} $ . 另一個問題，從長遠來看可能會成為一個相當大的問題，是如何檢測您確實獲得了兩倍的相同雜湊輸出：264 $ 2^{64} $ 16 字節的結果不適合 RAM ……事實上，這個搜尋問題可能比僅僅計算所有 MD5 是一個更大的問題。
（有漂亮的碰撞搜尋算法需要很少的 RAM，但我不確定它們是否可以應用於您所說的確切問題，在這個問題中，您不只是尋找碰撞，而是尋找最小的b $ b $ 價值。）