ドキュメントを保存し、タイムスタンプを含むいくつかのSHA1ダイジェストに基づいて各ドキュメントにUIDを与えるアプリケーションを作成しています。ダイジェストには多くの文字が含まれているため、ユーザーが完全なダイジェストの最初のx文字を使用してドキュメントを識別できるようにしたいと思います。ドキュメントの数が約10K〜100Kの場合、xの適切な値は何ですか？
9995 次
5 に答える
26
ウィキペディアの誕生日の問題の式を適用すると、衝突の確率を次のように概算できます1 - e^(-n^2/(2^(b+1)))。ここnで、はドキュメント数、bはビット数です。この式をn=100,000でグラフ化すると、少なくともb>45が必要になるようです。私はそれを素敵で丸い数字にするために64を使う傾向があります。とはいえ、衝突が発生した場合に対処する計画はありますか（タイムスタンプを少し変更するか、ナンスを追加しますか？）
さらに言えば、sha1がドキュメントのコンテンツだけに基づいていない場合は、単純にランダムIDにしてみませんか？この場合、いつでも新しい乱数を生成して再試行できるため、衝突はそれほど問題になりません（ただし、1回の試行で衝突する確率は同じです）。
于 2011-01-24T16:33:03.953 に答える
3
小さいハッシュが安全であるという証拠が減ることはないので、切り捨てに注意してください。Kelseyのhttp://csrc.nist.gov/groups/ST/hash/documents/Kelsey_Truncation.pdfを参照してください。Kelseyは、同じことを示すヒューリスティックな議論を行います（「関連するハッシュ出力」と「衝突の近く」）。Biham / Chenは、近接衝突の例を示しています。Knudsenは、切差分解読法を示しています。
最後に、データを切り捨てられたサイズのHMACにフィードして（サイズもHMACによってダイジェストされます）、切り捨てられたHMACを使用することをお勧めします。
于 2012-12-18T05:20:16.290 に答える
2
これには実際には価値がありません。SHAを優れた汎用ハッシュアルゴリズムにする理由の1つは、類似したデータが必ずしも類似したハッシュ値を生成するとは限らないことです。（システムについて他に何も知らなくても）最善の策は、ハッシュがユーザーから提供された値で始まるドキュメントのリストを検索し、選択するドキュメントのリストを提示するか、ドキュメントに直接移動することです。 1つしかない場合。
于 2011-01-24T16:27:23.750 に答える
0
さて、これはおそらく単純すぎる答えです。
完全なsha1を使用すると、衝突の可能性が2 ^ 160分の1になる場合、1つの文字を切り捨てることにより、衝突の可能性が16（切り捨てられた文字のすべての可能な値）増加します...これは2^4です。 x文字を切り捨てると、衝突の可能性が2 ^（160-4 * x）に1になります。
于 2011-01-24T16:27:40.660 に答える