問題タブ [hash-collision]

これはおそらく現実の世界ではまだ起こらなかったでしょうし、起こらないかもしれませんが、これを考えてみましょう：gitリポジトリがあり、コミットを行い、非常に不運になります：ブロブの1つが同じSHA-1を持つことになりますすでにリポジトリにある別のものとして。問題は、Gitがこれをどのように処理するかということです。単に失敗しますか？2つのブロブをリンクし、コンテキストに応じてどちらが必要かを確認する方法を見つけますか？

実際の問題よりも頭の体操ですが、この問題は興味深いものでした。

平文/鍵のペアで動作する特定の (対称または非対称) 暗号化アルゴリズムによって生成された特定の暗号文が、同じ暗号文を生成する別の平文/鍵のペアを見つけるのはどれくらい難しいですか?

そして、2 つの平文と鍵のペアが同じ暗号文につながることを 2 人で見つけるのはどれくらい難しいのでしょうか?

この質問につながったのは、上記の質問とは何の関係もない別の質問です。

暗号文と鍵があり、何らかの復号化ルーチンを使用して復号化したい場合、通常、ルーチンは鍵が正しかったかどうかを教えてくれます。しかし、それはどのようにそれを知っていますか？復号化が成功したことを示す、結果の平文で何らかのパターンを探しますか? パターンを含み、ルーチンによって「有効」と報告される別のキー結果が別の平文に存在するか?

回答とコメントに触発されたフォローアップの質問:

許可されたプレーンテキスト/キーのペアが次の (または両方の) 方法で制限されている場合:

1) 平文は鍵の KCV (Key check value) から始まります。

2) 平文は、平文とキーの組み合わせのハッシュ値で始まります

これにより、衝突検出が実行不可能になりますか? そのような平文/キーが存在することは明らかですか=

ファイルと文字列の両方でうまく機能することを確認した md5 関数があります。しかし、非常に大きなファイルの可変サイズのチャンクで使用すると、同じ md5 値が生成されますが、チャンクのサイズは異なります。

長さは異なるが内容が同じである可能性のある2つのチャンクが同様のmd5フィンガープリントになる可能性があるのだろうか。

ほとんどのアプリケーション、特にデータベースは、文字列比較よりもはるかに高速に小さな整数または浮動小数でソートおよびフィルタリングできます。

したがって、文字列ではなく整数で比較できるように、短い文字列 (約 5 ～ 40 文字) の 32 ビットまたは 64 ビットの数値を返すために使用できるハッシュ関数があるかどうか疑問に思っています。

私は最初にcrc32について考えましたが、数が少なすぎて、50,000未満のハッシュで衝突が発生する可能性があるようです（100万を超える必要があります）。

主に Python、PHP、V8 Javascript、PostgreSQL、および MySQL に興味があります。

2^25 のランダムな文字列の SHA256 ハッシュを見つける必要があります。そして、衝突を探します (たとえば、最後の 50 ビットのハッシュのみに誕生日のパラドックスを使用します)。

string:hash ペアを dict 変数に格納しています。次に、変数を値 (キーではなく) でソートし、O(n) ループを使用して衝突を探します。

問題は、2^25 文字列とその 2^25 ハッシュがあるため、dict 変数には 2^50 値が含まれることです。これは非常にリソースを消費します。では、たとえば 1GB 程度の限られた RAM でこれを行うにはどうすればよいでしょうか。

私がすでに試したこと：
1.これを6GBのスワップスペースで実行します。プログラムは一晩実行され、まだ完了していませんでした。これは基本的に、O(n_square) 検索よりもさらに遅くなります! ハッシュは、約 3.2 GB の RAM 使用量で計算されます。しかし、その後 sort コマンドになると、使用される RAM が再び急増し始めます。Python の並べ替えは In-Place-Quicksort を使用します
:(

データベースなどを使用することは想定されていません。せいぜいテキストファイルですが、それは役に立ちません。また、私はPythonにはかなり慣れていませんが、それがあなたの答えのレベルを制限することはありません.

PS: これは課題です。300MB RAM で 1 分以内に衝突を発見したと主張する人もいます。それが本当かどうかはわかりません。私は問題を解決しましたが、答えは到達できません! 仕事中なので、今はコードにアクセスできません。すぐに追加します。

コード：

100万の可能性の合計順列からハッシュが生成されるシステムがある場合。衝突の可能性が10％ある場合、生成アルゴリズムが5回実行されることを心配する必要がありますか？

• 私はjsfiddleに似たシステムを持っており、ユーザーは自分のサーバーにファイルを「保存」できます。現在'23456789abcdefghijkmnopqrstuvwxyz'、33文字を使用しており、ファイルの長さは4文字で、合計で33^4 = 1,185,921可能性があります。
• 「ファイル名」はランダムに生成され、衝突が発生した場合は再実行して別のファイル名を取得します。誕生日のパラドックス計算機を使用すると、500のエントリを取得した後、衝突の可能性が10％であることがわかります。
• 5回以上連続して衝突する可能性はどのくらいありますか？4はどうですか？
• これを理解する方法はありますか？心配する必要がありますか？5000エントリ後に何が起こりますか？
• 任意の入力でこれを理解できるプログラムはありますか？

可変長（10〜20文字）の英数字+特殊文字（ASCII）文字列を一方向にハッシュする必要があります。出力は可変長である必要がありますが、最大25文字の長さで、英数字であり、大文字と小文字は区別されません。

また、衝突を発生させたくないので、衝突を発生させるには、衝突のないもの、または少なくとも（まだ？）証明されていないものが必要です。

git の使用中にハッシュ衝突が発生した場合、実際にはどうなりますか?

たとえば、同じ sha1 チェックサムで 2 つのファイルをコミットできた場合、git はそれを認識したり、ファイルの 1 つを破損したりしますか?

それに対応するためにgitを改善できますか、それとも新しいハッシュアルゴリズムに変更する必要がありますか?

（それがどれほどありそうもないかについて議論して、この質問をそらさないでください-ありがとう）

データ構造の最終試験を検討していたところ、昨年の最終試験で質問に出くわしました。過去3時間取り組んできましたが、試行錯誤を除いて、解決方法がわかりませんでした。ここに質問があります：

「ハッシュテーブルのサイズが31で、定数gも31であり、次のハッシュコードを使用するとします。

また、衝突を解決するために個別のチェーンを使用すること。テーブル内の同じ場所にハッシュされる5つの異なる名前をリストしてください。」

ハッシュテーブルのサイズが定数gと同じ31であることを考えると、この問題を解決するには、おそらくモジュロ演算子を含む何らかのトリックが必要だと思います。私がそのように聞こえたら申し訳ありませんが、私はコードや何かを求めているのではなく、質問についてのいくつかの考え/ヒントを求めています。コメントをいただければ幸いです。ありがとう

私はSHA-256アルゴリズムを使用して、データベース内の同一の画像を検出しています。さまざまな画像形式を使用しているため、ファイルで直接ハッシュを計算したくありません。代わりに、ピクセルデータを抽出し、その上でハッシュを計算したいと思います。

残念ながら、ランダムな衝突がたくさん発生しています。6000枚の画像から同じピクセル抽出（下記）を使用して同じバイトを持たない68枚の画像は、同じ値にハッシュされます。これは非常に多くの衝突のように感じます。さらに、計算したバイトをピクセルデータからファイルにダンプしてから、次のことを試しました。

echo -n [byteDumpFile] | sha256sum

その結果、ダンプされた画像のハッシュ値が異なり、MessageDigestを使用するときに何か間違ったことをしていると思います。

ピクセルデータを取得する方法は次のとおりです。

次に、MessageDigestクラスを使用してハッシュを計算します。

ここで、encodeHexは次のとおりです。