hash - SHA1衝突の確率

Question

同じ長さの100の異なる文字列のセットが与えられた場合、文字列のSHA1ダイジェスト衝突が発生する可能性が低い確率をどのように定量化できますか...？

Answer 1

SHA-1 によって生成された 160 ビットのハッシュ値は、すべてのブロックのフィンガープリントが一意であることを保証するのに十分な大きさですか? 一様分布のランダム ハッシュ値、n 個の異なるデータ ブロックのコレクション、および b ビットを生成するハッシュ関数を仮定すると、1 つまたは複数の衝突が発生する確率 p は、ブロックのペアの数に確率を乗じた値によって制限されます。特定のペアが衝突します。

(ソース: http://bitcache.org/faq/hash-collision-probabilities )

Answer 2

さて、衝突の確率は次のようになります。

1 - ((2^160 - 1) / 2^160) * ((2^160 - 2) / 2^160) * ... * ((2^160 - 99) / 2^160)

10 個のスペースで 2 個のアイテムが衝突する確率を考えてみてください。最初のアイテムは確率 100% で一意です。2 番目は、9/10 の確率で一意です。したがって、両方が一意で100% * 90%ある確率は であり、衝突の確率は次のとおりです。

1 - (100% * 90%), or 1 - ((10 - 0) / 10) * ((10 - 1) / 10), or 1 - ((10 - 1) / 10)

それはかなりありそうもありません。可能性が低いためには、さらに多くの文字列が必要です。

ウィキペディアのこのページの表を見てください。128 ビットと 256 ビットの行の間を補間するだけです。

Answer 3

That's Birthday Problem - この記事では、確率を簡単に見積もることができる優れた近似値を提供しています。実際の確率は非常に非常に低くなります。例については、この質問を参照してください。