多くのファイルのチェックサムを含むデータベースを作成したいのですが、チェックサムの衝突（同じチェックサムを持つ2つの異なるファイル）が心配です。
質問1：2つの異なるファイルが同じMD5合計を持つ確率はどれくらいですか？
回避策として、チェックサムを増やすことを考えました。小さなチェックサムから始めて、衝突の場合には、小さなチェックサムから導出できる大きなチェックサムを計算するので、データベースにすでにあるすべてのファイルのチェックサムを再計算する必要はありません...小さいサイズのチェックサムを検索できます。
質問2：どのチェックサム/ダイジェストアルゴリズムがこのトリックを実行できますか？特定のサイズの値を計算でき、（より小さなサイズの）「下位」互換性のあるチェックサムアルゴリズムが必要です。つまり。file1には0x1234の2バイトのチェックサムと0x12345678の4バイトのチェックサムがあります。2バイトのチェックサムは4バイトのチェックサムから導出できます。
質問1：ファイルの数によって異なります。各ペアについて、2^128の約1です。2 ^ 64個のファイルがある場合（おそらくそうではないと思います）、それらの間で少なくとも1つの衝突が発生する確率は約0.5です。
これは、ファイルを作成する人の側に悪意がないことを前提としています。既知のMD5衝突、および衝突するファイルを生成する既知の方法があります。誰かがあなたを衝突にさらすことによってあなたの費用でお金を稼ぐことができるなら、衝突の確率は1に近いです:-)
質問2：通常は、最初はより適切なハッシュ（おそらく、SHA-256）を使用します。その後、「小さい」ハッシュは、大きいハッシュの最初の数バイトか、大きい数を法として取られた最初のハッシュのいずれかです。プライム。しかし、それはあなたがそれを何のために望むかによります。
安価で陽気なオプションは、「大きな」ハッシュを2つ以上の「小さな」ハッシュを連結したものにすることです。たとえば、ファイルを前後にハッシュします。もちろん、小さなハッシュが壊れると、その壊れが2つ以上のハッシュの組み合わせの壊れにつながるかどうかはわかりません。
グーグルは「誕生日のパラドックス」を意味し、その数が手に負えないほど膨大であることを知って満足している。衝突の確率はかなり急速に増加しますが、SHAやMDのようなものの場合、最初の2つの元の確率に大きな打撃を与えることはありません。
ところで、これが暗号化の目的である場合、MD5は非推奨になります。重複排除などを行う場合は、MD5で問題ありません。