完全な32ビットCRCの予想衝突

Question

私は自分のCRCがどのように比較されるかを判断しようとしています」理想「32ビットCRC。

そこで、私はCRCを100万回以上ランダムなデータのサンプルを超えて実行し、衝突の量を収集しました。この数を私が期待できる衝突の数と比較したいと思います。理想「CRC。

誰かが予想される衝突を計算する方法を知っていますか？理想「32ビットCRC？

Answer 1

これは、「誕生日の問題」と衝突確率の予測について美しく説明しています CRC32ハッシュ衝突確率

Answer 2

「理想的な」リファレンスとして、0x1EDC6F41を使用して独自のCRCを比較してください。

そうは言っても、理想的な32ビットCRCはありません。異なる多項式は、データの長さに応じて衝突特性が異なります。しかし、1993年のCastagnoliによる論文では、最も広い範囲のデータ長である0x1EDC6F41よりも最高の32ビットCRC値と考えられているものが見つかりました。この多項式は、ISCSIやX86 CRC32命令などの一部のネットワークプロトコルで使用されます。