SHA1ハッシュを減らすための部分的な衝突

Question

私は、sha1ハッシュの縮小に基づいて部分的な衝突を与える2つの異なる文を見つけるプロジェクトを行っています。私のプログラムは2つの異なるメッセージを生成します。 2つの文のハッシュの最初の32ビットが一致すると、プログラムは停止し、衝突が検出されるまで繰り返されます。

私のプログラムはうまくいきますが、コリジョンの検索にかかる時間が遅くなります。どうすればスピードアップできますか？私は読んで、私は誕生日のパラドックスを使用できることを知った、どのように私はそれを実装するのですか？

私はいくつかの検索を行い、関連する回答を得ましたが、私はまだ誕生日のパラドックスに混乱しています。

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）チャンスです。

誕生日のパラドックスを利用するには、生成したハッシュを保存し、新しいハッシュをすべて確認する必要があります。これは、との衝突を探しているために機能しますが、最終的に衝突したハッシュがどのように生成されたのかは本当に気にしません。誕生日のパラドックスが人間や誕生日を使ってどのように働くかを読んで、それをハッシュに適用する前に理解しておいてください。 By the math hereあなたは32ビットのためにそれらの間で衝突を見つける50％のチャンスを持つために〜77,000ハッシュしか必要としません。