减少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位的冲突。