SHA1の衝突の確率

Question

どのようにSHA1は、文字列の衝突を消化する確率を定量化することができ、同じ長さの100個の異なる文字列の集合を考えるには、ほとんどありませんか...？

Answer 1

  

160ビットのハッシュ値が生成され、   SHA-1を保証するのに十分な大きさによって、   すべてのブロックのフィンガープリントは、ユニークなのですか？   ランダムハッシュ値を仮定すると、   一様分布のコレクション   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)

の最初のアイテムは、確率100％で一意である10の空間内の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

これはバースデー問題のだ - 記事を推定することが非常に簡単に素敵な近似値を提供します確率。実際の確率は非常に非常に非常に低くなります - この質問を参照するたとえばます。