問題タブ [hash-collision]

ハッシュテーブルの大きさにサイズ制限を設ける必要がありますか？

ハッシュテーブルを小さくしすぎると問題が発生する理由がわかるので、少し困惑しています。ハッシュテーブルが大きすぎると、プローブがSigエラーをスローしているように見えますか？誰かがハッシュテーブルの経験があるなら、これが私のコードです。私は確かにあなたが提供しなければならないアドバイスに感謝します（代わりに編み物をすることを超えてください）：

これらのアルゴリズムは常に改善されており、新しいエクスプロイトが発見され、新しい問題が常に発生しているため、これについてグーグルで検索すると、答えに少し矛盾します...使用するアルゴリズムに関する多くのアドバイスは単に古いものです、または最良の方法であった古い時代からのアイデアを保持します。

ここではっきりさせておきたいのですが、私はパスワードについて話しているのではありません。暗号化ハッシュではなく、メッセージ ダイジェストについて話しているのです。

先に進んで、md5 をメッセージ ダイジェストの最初のヒントとして使用することもできましたが (その名前は正しいです)、最近のアルゴリズムよりも多くの衝突があることを思い出しました。しかし、これらの新しいアルゴリズムが、ファイルや短い文字列のメッセージ ダイジェストにより適している理由は何でしょうか?

それが私の質問です。使用すべき最新のメッセージ ダイジェスト アルゴリズムは何ですか?

ELFHash で同じハッシュ値を生成する、アルファベット文字のみで構成される 2 つの文字列の例を挙げられる人はいますか?

コードをテストするにはこれらが必要です。しかし、簡単に生産できるものではないようです。そして驚いたことに、インターネット上にはさまざまなハッシュ関数のサンプルコードがたくさんありますが、衝突した文字列の例を提供しているものはありません。

必要な場合に備えて、以下に ELF ハッシュを示します。

オブジェクトのハッシュを生成するための次のコードがありました。

つまり、すべてのプロパティのハッシュコードを追加してから、このハッシュを取得します。

レビューでは、同僚はこれがあまりにも頻繁に衝突することを示唆しました。これが正しいかどうかはわかりません。理由は次のとおりです。

1. ハッシュコードが正の数と負の数の間で同じ頻度で選択され、それらが折り返されることを考えると、数自体ではなく、これらの数の合計の可能性について私たちが得る追加情報はないと思います
2. それらの合計がランダムでない限り、ハッシュコードは、「互いに近い」数値が「離れた」数値になるように設計されているため、関数に不均一に分散された値をフィードすることは問題になりません。

誰が正しいですか？

答えが言語固有の場合に備えて、C＃です。

SHA0ハッシュ関数がどのように壊れているのかを理解したかったのです。誕生日の問題/ピジョンホールドの原則を利用して、ハッシュ衝突が見つかったことを理解しています。 http://www.mail-archive.com/cryptography%40metzdowd.com/msg02554.htmlには、サンプルメッセージが含まれています。

私が見つけたり理解したりするのに苦労していること：これは、常にハッシュ衝突を生成するためのタイムリーで数学的な方法があることを意味しますか？

最終的に、m1！= m2、sha（m1）== sha（m2）のような特定のm1のm2を見つけることができますか、それとも可能なメッセージのサブセットでのみ可能ですか？言い換えると、パスワードに衝突の別のメッセージが表示される可能性は保証されていますか？

上記のリンクのように、同じハッシュ値を持つ2つのランダムな長いメッセージを見つけることの重要性は何ですか？ 「茶色の犬がキツネを飛び越えた」のような実用的なメッセージのために衝突を考え出すのではなく、なぜ彼らは衝突のために長いランダムなメッセージをふるいにかける必要があったのですか？

ハッシュ衝突のいくつかの例は、メッセージの衝突を生成するためのタイムリーな方法ほど重要ではないようですが、すべての投稿で前者について説明しています。

助けてくれてありがとう/あなたの時間！私はたくさんの投稿/記事を読みましたが、私の混乱を回避するために頭を動かすことができません。MD5のような他の壊れたハッシュ関数についても同じ質問があると思います。

編集：

回答で参照されている論文（衝突を見つけるための改善された方法を説明している）

1からXまで数える場合、Xは前の番号とmd5の衝突が発生した最初の番号ですが、Xは何番ですか？

シリアル番号にmd5を使用しているかどうか、衝突する前に列挙できると予想できるユニット数を知りたいです。

HashTable は同じキーを複数の値にマップできることを読みました。それが衝突です。

今、私はこのようにプログラムを実行します:

私の考えでは、 と を取得する必要がaaありabます。

しかし、実際の出力はab

なぜそうなのですか？その場合、衝突はどこにありますか？

明らかに、SHA-1ハッシュは毎回40文字を生成するため、可能なハッシュの数には限りがあります。正確にいくつあるか知っている人はいますか？

興味深いことに、ワールプールのような単一の 512 ビット ハッシュと md5、sha1 などの 4 つの 128 ビット ハッシュの連結との衝突の可能性のテストまたは実験に関する十分な情報が見つかりませんでした。

4 つの 128 ビット ハッシュが同じように見える可能性は、ハッシュが実行されるデータが平均 100 文字のかなり小さいサイズの場合、単一の 512 ビット ハッシュよりも可能性が低いようです。

しかし、私はテストを実行していないため、根拠のない明らかな推測にすぎません。あなたはそれについてどう思いますか？

512 ビット ハッシュと 128 ビット ハッシュのように編集します。128 ビット ハッシュ。128 ビット ハッシュ。128bit ハッシュ (4 つの 128bit ハッシュ連結)

Edit2 RAMを考慮したURLまたはハッシュ のこのインデックスにハッシュを使用したい のですが、URL列ではなくハッシュ列を一意に設定したいため、衝突の可能性を最小限に抑えることが目的です。

Edit3 この質問の目的は、衝突の可能性を最小限に抑える方法を見つけることであることに注意してください。そうは言っても、なぜ衝突の可能性を最小限に抑えることにもっと集中する必要があるのでしょうか? これは、RAM の使用量を減らすための解決策を見つけることにつながる私の Edit2 の説明です。そのため、衝突を最小限に抑えることと、RAM の使用量を減らすことに関心があります。しかし、この質問の主な焦点は、衝突の可能性を下げることです。

MD5 ハッシュ値の束を一緒にハッシュして新しいハッシュを作成するのが「安全」なのか、それとも衝突の可能性が何らかの形で増加するのか疑問に思います。

背景: 依存関係のあるファイルがいくつかあります。各ファイルには、その内容に基づいて計算された関連付けられたハッシュ値があります。これを「単一ファイル」ハッシュ値と呼びましょう。これに加えて、ファイルには、すべての依存ファイルを含むハッシュ値、「マルチファイル」ハッシュ値も必要です。

問題は、依存ファイルの単一ファイルの MD5 ハッシュ値をすべて取得して連結し、連結された値に対して MD5 を計算して、複数ファイルのハッシュ値を取得できるかどうかです。または、これにより、すべての依存ファイルのコンテンツを連結する場合よりも衝突する可能性が高い MD5 ハッシュが生成されます。

あるいは、単一ファイルのハッシュ値を xor して複数ファイルのハッシュ値を生成することはできますか?それとも衝突が増える可能性がありますか?