2

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

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

18 个字节在 ascii 表中（az，0-9），其余的范围在 0 到 10 之间

4

4 回答 4

5

以下简单脚本运行一个无限循环，该循环获取 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)。

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

于 2012-12-22T00:58:17.350 回答
4

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

请记住生日悖论。散列大约 2^8 个项目后，您将开始发生冲突。

于 2012-12-22T00:45:29.727 回答
2

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

于 2012-12-22T00:38:43.830 回答
0

哈希冲突的概率不取决于消息的长度，只要消息的熵（有效位数）大于或等于哈希中的位数，并且它是一个好的将输入的位很好地混合到每个散列中的散列。

在您的情况下，您有大约 100 位的熵，因此只要您有一个长度为 100 位或更少的良好哈希，那么冲突概率将仅取决于哈希中的位数和您拥有的机会数量碰撞。这个答案显示了如何计算碰撞的概率。

于 2017-12-12T01:25:55.007 回答