php - Sha1サブストリングの質問

Question

私はペーストビンタイプのサイトを作成していて、IDをpaste.com/4RT65Lのようなランダムな文字列にしようとしています。

データベースに追加する前にIDのsha1を取得していますが、sha1の最初の8文字のサブストリングを取得しています。同じsha1のダブルコピーである可能性はありますか？誤って、すでに使用されているIDを持つ2番目のペーストにしたくないですか？

Answer 1

8文字で衝突する確率は、2つのSha1キーで衝突する確率よりも大幅に高くなりますが、それが発生する可能性が高いという意味ではありません。

テストを行うことをお勧めします。ランダムな入力を生成し、衝突するまでにかかる時間を確認します。結果が気に入ったら、それを使ってください。それ以外の場合は、より長い文字列が必要になります。

編集：誕生日のパラドックスを見ることで、衝突のオッズを計算することもできます。

基本的に、SHA-1から最初の8桁の16進数を取得する場合は、16 ** 8（4,294,967,296）の異なる組み合わせを使用できます。

オンラインのBirthayParadox計算機を使用すると、約9200回のハッシュの後、衝突の可能性が1％になります。10％の確率になるまでに約30,000回のハッシュが必要であり、50％の確率になるまでに77,000回のハッシュが必要です。

ハッシュ関数が疑似ランダムであるという適切な仕事をしている限り、どちらを使用するかは問題ではないことを指摘することが重要です（SHA1、MD5、または任意の形式のチェックサム）-これらの数値は完全にランダムな入力であるため、これらの値に近づくには、ますます優れたハッシュ関数を使用する必要があります。

したがって、最終的には、予想されるトラフィックの量によって異なります。これが小さなサイトであれば、おそらくそれを回避することができます。トラフィックが多い場合、衝突の可能性は非常に高くなります。

Answer 2

IDを割り当てる前に、それが取得されていないことを常に確認できます...またはさらに良いことに、データベースフィールドに一意のIDを配置します...問題は解決しました。:)

待って、あなたはIDのSHA1と言います。autoinc idを意味するのではありませんか？私の最初の推測は次のようになります：

356a192b
da4b9237
77de68de

ランダムIDを使用している場合、なぜそのIDでsha1を実行するのですか？

Answer 3

私はそれを理解しました、私のコードは次のとおりです：

strtoupper(substr(sha1($token_start . $id . $token_end), 0, 8))

ここで、$ idは、データベース内のIDの合計量+1を取得するために取得されるIDであり、自動インクリメントであるため、次のIDになります。

次に、エントリを挿入すると、暗号化されたものが挿入されます。

$token_startと$token_endはどちらもランダムな文字列であり、新しいIDを一意にするために選択できます。

私はそれらをデータベースに32000回挿入するループを作成しました。IDだけで、新しいIDとともに自動インクリメントし、個別の検索を実行しましたが、重複はありませんでした。それは私にとって十分すぎるほどです。コメントがあれば参考になります。衝突するまでどれくらいかかるかわかりません。誰かが最初のものがいつになるかを知っているなら、それは素晴らしいでしょう。