两个数据块产生相同CRC64值的可能性有多大？

Question

我有一个缓存应用程序，它使用CRC64值来确保数据完整性。我正在考虑添加一个额外的字段，一个时间戳，用于在不同的缓存服务器之间传递数据，并进行比较，以查看数据是否发生了更改。

但是，这需要更改协议。虽然这不是什么大问题，但我已经有了一个CRC64，它可以用来指示一些事情已经发生了变化。

有谁知道产生相同CRC64的两个数据块的统计数据吗？如果不是，我如何计算它或估计它的可能性？

Answer 1

如果你假设crc64是“完美的”，那么这些数字是相当合理的：

For a 1% probability of collision, you need 6.1 × 10^8 entries. For a 50% probability of collision, you need 5.1 × 10^9 entries.

当然，如果数据可能是由恶意来源提供的，那么像crc64这样简单的散列中的冲突可能很容易生成，并且冲突可能会很猖獗。因此，您是否走这条路线取决于输入数据的来源和冲突的潜在后果。

Answer 2

不同随机数据上的两个CRC64s相同的概率接近1/ 2** 64。但由于CRC对数据模式有些敏感，因此可能会出现一些退化的情况，您可能会失去几个二进制保护顺序。可能不可能给出一个确切的数字，但你很可能会安全地假设最坏的情况下碰撞的可能性将小于1/ 2** 50左右。

如果您使用加密散列而不是CRC64，则可以确保更接近理论上的限制，但是加密散列的计算成本通常要高得多。