20 字节数据发生 CRC16 冲突的可能性有多大？

Question

我正在开发一个系统，该系统需要为长度可能少于20 个字节的结构存储散列。但是，为了优化在一系列散列中查找散列的过程，我们希望尽可能减小散列的大小。

所以我的问题是，我们提供给 crc16 哈希的数据量与其与另一个相同长度的条目发生冲突的概率之间是否存在关系？如果是这样，哪个是最佳长度？

18 个字节落在 ascii 表内（az，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，或“1 100_000”），这是方式更差比基于16位的散列（如2 ^ 16的理想散列分布预测估计/ 2^160）。

更新：我看到你已经澄清 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%。