security - 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 分之一”)，即 < em>比基于 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%。