在20字节的数据上，CRC16碰撞的可能性是多少?

Question

我正在开发一个系统，需要存储一个结构20字节的哈希值可能更少的长度。然而，为了优化在一系列哈希中查找哈希的过程，我们希望尽可能地减小哈希的大小。

所以我的问题是，我们输入crc16哈希的数据量与它与另一个相同长度的条目碰撞的概率之间是否存在关系?如果是，那么最优的长度是多少?

18个字节属于ASCII表(a-z, 0-9)，其余的范围在0到10之间

Answer 1

下面的简单脚本运行一个无限循环，获取2个随机的20字节序列，计算CRC16并检查是否存在碰撞。对这个循环的持续评估事实上估计了碰撞百分比:

#!/usr/bin/env perl
use Digest::CRC qw(crc16);
open(my $f, '<', '/dev/urandom');
my $n = 0;
my $coll = 0;
while (1) {
    read $f, $randstr1, 20;
    read $f, $randstr2, 20;
    my $crc1 = crc16($randstr1);
    my $crc2 = crc16($randstr2);
    $n++;
    $coll++ if $crc1 == $crc2;
    printf "percent of collisions = %.6f%%n", $coll * 100.0 / $n if ($n % 100000 == 0);
}

从我在我的计算机上得到的，碰撞百分比似乎在0.0016%(或1e-5，或"100_000中的1")左右，这比基于16位哈希的理想哈希分布(如2^16/2^160)的预测估计更糟糕。

UPDATE:我看到你已经澄清了20个字节不仅仅是完全随机的字节，而是属于[a-z0-9]的范围。以下是估计字母表中碰撞的更新版本:

#!/usr/bin/env perl
use Digest::CRC qw(crc16);
my $n = 0;
my $coll = 0;
my @chars = ('a'..'z', '0'..'9');
sub randstr() {
    my $res;
    foreach (1..20) { $res .= $chars[rand @chars]; }
    return $res;
}
while (1) {
    my $crc1 = crc16(randstr());
    my $crc2 = crc16(randstr());
    $n++;
    $coll++ if $crc1 == $crc2;
    printf "percent of collisions = %.4f%%n", $coll * 100.0 / $n if ($n % 100000 == 0);
}

得到的结果大致相同，关于0.0016%

Answer 2

在给定两个不同输入的情况下，一个好的16位哈希应该有2^-16的碰撞概率。CRC16不是一个很好的散列，但除非你有对手挑选输入，否则它应该足够好。

记住生日悖论。当你对2^8项进行哈希后，你将开始出现碰撞

Answer 3

是否会发生哈希冲突取决于数据的内容，而不是数据的数量。如果不是故意选择碰撞，那么在这种数据大小是哈希大小的10倍的情况下，您应该是非常安全的。也就是说，它仍然是一个16位哈希，按照现代标准，碰撞的可能性相当高。

Answer 4

哈希冲突的概率不依赖于消息的长度，只要消息的熵(有效比特数)大于或等于哈希中的位数，并且它是一个很好的哈希，可以很好地将输入的比特混合到每个哈希中。

在你的例子中，你有大约100比特的熵，所以只要你有一个长度为100比特或更少的哈希，那么碰撞概率将仅取决于哈希中的比特数和碰撞的机会数量。这个答案展示了如何计算碰撞的概率。