それぞれ1メガバイトの10億の固有の画像があるとしましょう。各ファイルの内容についてSHA-256ハッシュを計算します。衝突の可能性は以下に依存します：
- ファイルの数
単一ファイルのサイズ
それがゼロであると仮定して、この可能性をどこまで無視することができますか？
94397 次
3 に答える
451
通常の答えはこうなります：不正な小惑星が次の1秒以内に地球に衝突し、私たちが知っている文明を破壊し、数十億の人々を殺す確率はどれくらいですか？それよりも確率が低い不運な出来事は、実際にはそれほど重要ではないと主張することができます。
出力サイズがnの「完全な」ハッシュ関数があり、ハッシュするメッセージがp個ある場合（個々のメッセージの長さは重要ではありません）、衝突の確率は約p 2/2 n + 1です（これは近似値です。 「小さい」pに対して有効、つまり2 n / 2よりも大幅に小さい）。たとえば、SHA-256（n = 256）と10億のメッセージ（p = 10 9）の場合、確率は約4.3 * 10-60です。
大量殺戮者のスペースロックは、平均して約3,000万年に1回発生します。これにより、このようなイベントが次の1秒で発生する確率は約10〜15になります。これは、SHA-256の衝突よりも45桁多い可能性があります。簡単に言えば、SHA-256の衝突が怖い場合は、優先順位が間違っています。
攻撃者がハッシュされるメッセージを選択できるセキュリティ設定では、攻撃者は実質的に10億を超えるメッセージを使用する可能性があります。ただし、攻撃者の成功確率は依然として非常に小さいことがわかります。これが、256ビット出力のハッシュ関数を使用することの要点です。衝突のリスクを無視できるようにするためです。
もちろん、上記のすべては、SHA-256が「完璧な」ハッシュ関数であることを前提としています。それでも、SHA-256は非常に堅牢なようです。
于 2010-10-25T12:14:14.800 に答える
54
衝突の可能性は、ファイルのサイズに依存するのではなく、ファイルの数にのみ依存します。
これは誕生日のパラドックスの例です。ウィキペディアのページには、衝突の可能性の見積もりが記載されています。数値を実行すると、地球上でこれまでに製造されたすべてのハードディスクが、SHA-256で0.01％の衝突の可能性を得るのに十分な1MBのファイルを保持できないことがわかります。
基本的に、あなたは単に可能性を無視することができます。
于 2010-10-25T11:39:08.260 に答える
21
まず第一に、それはゼロではありませんが、ゼロに非常に近いです。
重要な問題は、衝突が実際に発生した場合にどうなるかということです。答えが「原子力発電所が爆発する」であるなら、あなたはおそらく衝突の可能性を無視するべきではありません。ほとんどの場合、結果はそれほど悲惨ではないため、衝突の可能性は無視できます。
また、ソフトウェア（またはそのごく一部）が展開され、同時に何億ものコンピューター（今日ではほとんどどこにでもある小さな組み込みマイクロコンピューター）で使用される可能性があることを忘れないでください。そのような場合、あなたはあなたが得た見積もりに可能な限り多くのコピーを掛ける必要があります。
于 2010-10-25T11:31:11.977 に答える