私はドキュメントを格納し、タイムスタンプを含むいくつかのSHA1ダイジェストに基づいてそれぞれにUIDを与えるアプリケーションを作っています。ダイジェストには多くの文字が含まれており、ユーザーは完全なダイジェストの最初のx文字を使用してドキュメントを識別できるようにしたいと考えています。文書の数が10K〜100K程度の場合、xにはどのような価値がありますか？SHA1ハッシュを切り捨てて、一意のIDを持つことがどれくらい可能ですか？
wikipedia for the Birthday problem上の式を上の適応、あなたはnは、文書数とbはビット数であるe^(-n^2/(2^(b+1)))、との衝突の確率を近似することができます。 Graphing this formula with n=100,000、あなたは少なくともb> 45を望むように見えます。私はそれを素敵で丸い数字にするために64と一緒に行く傾向があります。つまり、タイムスタンプをわずかに変更したり、ノンスを追加したりすると、衝突に対処する計画はありますか？
そのため、sha1が単なるドキュメントの内容以上のものに基づいている場合、単純にランダムなIDにしないのはなぜですか？この場合、常に新しい乱数を生成して再試行することができるため、衝突は問題にはなりません（ただし、1回の試行で衝突する確率は同じです）。
本当にこの値はありません。 SHAを汎用のハッシュアルゴリズムとすることの一部は、類似のデータが必ずしも同様のハッシュ値を生成するとは限りません。あなたの最善の賭けは（あなたのシステムについて他に何も知らない）、ハッシュがユーザによって提供された値で始まる文書のリストを検索し、選択する文書のリストを提示するか、文書に直接行くかもし1つだけあれば。
それはgitがrevsと何をするのですか？ – dan
@danそれは一般的にはかなり良いアプローチです。 –
さて、ここで...答えの可能性が単純すぎるのです
フルSHA1を使用すると、衝突の約1 160^2でチャンスを得る場合は、1つの文字を切り捨てることにより、あなたは16で衝突の可能性を高めます（可能なすべての切り捨て文字の値）...は2^4です。したがって、x文字を切り捨てると、2 ^（160 - 4 * x）の衝突が発生します。
generalizationはthe birthday problemです。あなたの場合nはドキュメントの数であり、定数365の代わりに、カットオフが与える可能性の数があります（kビットの場合は2 kです）。
もちろん、正確な計算は問題になりませんが、approximationを使用することもできます。
Biham/ChenはNear Collisionsの例を提供しています。 KnudsenはTruncated Differentialsを実証しています。どちらも切り詰められたハッシュの問題です。どちらも誕生日のパラドックスの例ではありません。 – jww
小さいハッシュが安全であるという証明の減少がないので、切り捨てに注意してください。ケルシーのhttp://csrc.nist.gov/groups/ST/hash/documents/Kelsey_Truncation.pdfを参照してください。 Kelseyはヒューリスティックな議論に同じことを述べている（「関連するハッシュアウトプット」と「近くの衝突」）。 Biham/ChenはNear Collisionsの例を提供しています。 KnudsenはTruncated Differentialsを実証しています。
最終的には、データをHMAC に入力して、の切り捨てサイズ（このサイズはHMACでも消化されます）を使用して切り捨てられたHMACを使用します。
こんにちはJWW、NIST-PDFについて、どのように解釈していますか？ @ bdonlanの公式、 'e ^（ - n^2 /（2 ^（b + 1）））'は、切り捨てを見積もるかどうかの良い近似ですか？そうでない場合は、SHA1切り捨ての最小ビット数*（_bmin_）を確認する式またはアルゴリズムは何ですか？ –
小規模なニート - 形式は正式ではありません（ - n^2 /（2 ^（b + 1）））？答えはb> 40に少し変わります。 – Fakrudeen
@Fakrudeen、確かに - 私は答えにそれを転記するときにエラーを起こしました。グラフは正しかったです...私は今、stackoverflowがリンクを作成していないことを認識しましたが、 – bdonlan
コメントに合意した正しい式を持つように答えを更新しました。 –