減少SHA1散列的部分衝突

Question

我正在做一個項目，以找到兩個不同的句子，基於減少的sha1散列給出部分衝突。我的程序將生成兩個不同的消息。如果兩個句子的散列的前32位匹配，則程序將停止，否則它將重複，直到檢測到衝突。

我的程序運行良好，但搜索collission的時間卻很慢。我怎麼能加快Iot。我讀了，發現我可以用生日悖論，我該如何執行？

我做了一些搜索，並得到相關答案，但我仍然對生日悖論感到困惑。

Probability of SHA1 collisions

SHA1 collision demo/example

http://www.metzdowd.com/pipermail/cryptography/2004-August/007409.html

http://www.freelists.org/post/hashcash/Hashcash-and-the-cracking-of-SHA1,2

這是怎麼我的工作方案：

Generate random number() // let say i generate 100 number 
Generate random char1() // we will generate 100 char 
Hash() // the first 100 char 
Generate random char2() // we will generate another 100 char 
Hash2() // this 100 char again 
Get the 32 bit of the random char1() 
Get the 32 bit of the random char2() 
compare the 32 bit for partial collision 
If they dont match we will keep on doing until partial collision is found. 

• 搜索所花費的時間與以毫秒爲單位的某些其他程序相比太長。

Answer 1

如果你試圖通過每個你將不得不接受非常長的運行時間時隨機對輸入尋找散列函數局部衝突。對於32位和一個完美的哈希函數，碰撞機率爲1 /（2^32）。

要利用生日悖論，你需要存儲你生成的哈希值，並檢查新的哈希值對它們全部。這是有效的，因爲你正在尋找a碰撞，你並不關心什麼產生了最終碰撞的哈希。閱讀生日悖論如何使用人類和生日，並確保在將其應用於哈希之前瞭解它。 By the math here你只需要約77,000個散列，就有50％的機會在它們之間找到32位的衝突。