截斷md5的統一分佈？

我們可以說截斷的md5散列仍然是均勻分佈的嗎？截斷md5的統一分佈？

爲了避免誤解：我知道碰撞的可能性遠大於從md5結果中剔除零件的時刻;我的用例實際上是感興趣在故意碰撞。我也知道有other hash methods這可能更適合於較短散列的使用情況（包括，實際上，我自己的），我絕對正在研究這些。

但我也很想知道md5的均勻分佈是否也適用於它的大塊。（考慮它好奇）

由於mediawiki使用它（特別是最左邊的兩個十六進制字符作爲結果的字符）來生成圖像的文件路徑（例如/4/42/The-image-name-here.png），他們可能也對至少附近 - 均勻分佈，我想答案是'是'，但我其實知道。

來源

2011-11-18 pinkgothic

雖然我們在這裏，任何人都有良好的鏈接到證明非截斷md5總和的一致性嗎？ – naught101

@ naught101：由於這個問題相當老舊（通過互聯網測量）並且有一個可接受的答案，所以不太可能從能夠回答您的問題的人那裏獲得更多的曝光 - 也許會提出自己的問題？ :) – pinkgothic

是的，沒有表現出任何偏見是加密散列的設計要求。從密碼學的角度來看，MD5被打破了，但結果的分佈從來沒有問題。

如果仍然需要說服，那麼對一堆文件進行散列，截斷輸出並使用ent（http://www.fourmilab.ch/random/）來分析結果並不是一項巨大的任務。

來源

2011-11-20 03:26:38

非常感謝 - 這正是我正在尋找的答案。 – pinkgothic

我寫了一個小小的PHP程序來回答這個問題。這不是非常科學，但它顯示散列值的第一個和最後8位使用自然數作爲哈希文本的分佈。經過大約40.000.000次哈希之後，最高和最低計數之間的差異降低到1％，所以我認爲分配是可以的。我希望代碼更精確地解釋什麼是計算:-) 順便說一句，與類似的程序，我發現最後8位似乎分佈略好於第一。

<?php 
// Setup count-array: 
for ($y=0; $y<16; $y++) { 
    for ($x=0; $x<16; $x++) { 
    $count[dechex($x).dechex($y)] = 0; 
    } 
} 

$text = 1; // The text we will hash. 
$hashCount = 0; 
$steps = 10000; 

while (1) { 
    // Calculate & count a bunch of hashes: 
    for ($i=0; $i<$steps; $i++) { 
    $hash = md5($text); 
    $count[substr($hash, 0, 2)]++; 
    $count[substr($hash, -2)]++; 
    $text++; 
    } 
    $hashCount += $steps; 

    // Output result so far: 
    system("clear"); 
    $min = PHP_INT_MAX; $max = 0; 
    for ($y=0; $y<16; $y++) { 
    for ($x=0; $x<16; $x++) { 
     $n = $count[dechex($x).dechex($y)]; 
     if ($n < $min) $min = $n; 
     if ($n > $max) $max = $n; 
     print $n."\t"; 
    } 
    print "\n"; 
    } 
    print "Hashes: $hashCount, Min: $min, Max: $max, Delta: ".((($max-$min)*100)/$max)."%\n"; 
} 
?>

來源

2012-02-19 04:05:04 rob

這太棒了。謝謝！（我想我可以/應該自己做到這一點，真的！） – pinkgothic

截斷md5的統一分佈？

回答

相關問題