42

CRC32可以用作散列函数吗？这种方法有什么缺点吗？有什么取舍吗？

4

3 回答 3

46

CRC32作为散列算法工作得很好。CRC的全部意义在于对字节流进行哈希处理，并尽可能减少冲突。也就是说，有几点需要考虑：

  • CRC 不安全。对于安全散列，您需要一个计算量更大的算法。

  • 不同的 CRC 风味具有不同的特性。确保使用正确的算法，例如散列多项式 0x11EDC6F41 (CRC32C)，这是最佳的通用选择。

  • 作为散列速度/质量的权衡，x86 CRC32 指令很难被击败。但是，该指令在较旧的 CPU 中不存在，因此请注意可移植性问题。

- - 编辑 - -

Mark Adler 提供了一个链接，指向 Bret Mulvey 的一篇有用的哈希评估文章。使用文章中提供的源代码，我为 CRC32C 和 Jenkins96 运行了“桶测试”。这些表格显示了真正均匀分布比偶然测量结果更差的概率。因此，数字越大越好。作者认为 0.05 或更低为弱，0.01 或更低为非常弱。在这一切上我完全信任作者，我只是在报告结果。

在 CRC32C 比 Jenkins96 表现更好的所有实例中，我都放置了一个 *。通过这个简单的统计，CRC32C 是一个比 Jenkins96 更均匀的哈希 54 次 96 次。 特别是如果您可以使用 x86 CRC32 指令，则速度质量权衡非常好。

CRC32C (0x1EDC6F41)

       统一键 文本键 稀疏键

位 下 上 下 上 下 上
 1 0.671 *0.671 *1.000 0.120 *0.572 *0.572
 2 *0.706 *0.165 *0.729 *0.919 0.277 0.440
 3 *0.878 *0.879 *0.556 0.362 *0.535 *0.542
 4 0.573 0.332 0.433 0.462 *0.855 0.393
 5 0.023 *0.681 0.470 0.907 0.266 0.059
 6 *0.145 *0.523 0.354 *0.172 *0.336 0.588
 7 0.424 0.722 0.172 *0.736 0.184 *0.842
 8 *0.767 0.507 *0.533 0.437 0.337 0.321
 9 0.480 0.725 *0.753 *0.807 *0.618 0.025
10 *0.719 0.161 *0.970 *0.740 *0.789 0.344
11 *0.610 0.225 *0.849 *0.814 *0.854 *0.003
12 *0.979 *0.239 *0.709 0.786 0.171 *0.865
13 *0.515 0.395 0.192 0.600 0.869 *0.238
14 0.089 *0.609 0.055 *0.414 *0.286 *0.398
15 *0.372 *0.719 *0.944 0.100 *0.852 *0.300
16 0.015 *0.946 *0.467 0.459 0.372 *0.793

对于 Jenkins96，文章的作者认为它是一个优秀的哈希：

詹金斯96

      统一键 文本键 稀疏键

位 下 上 下 上 下 上
 1 0.888 0.572 0.090 0.322 0.090 0.203
 2 0.198 0.027 0.505 0.447 0.729 0.825
 3 0.444 0.510 0.360 0.444 0.467 0.540
 4 0.974 0.783 0.724 0.971 0.439 0.902
 5 0.308 0.383 0.686 0.940 0.424 0.119
 6 0.138 0.505 0.907 0.103 0.300 0.891
 7 0.710 0.956 0.202 0.407 0.792 0.506
 8 0.031 0.552 0.229 0.573 0.407 0.688
 9 0.682 0.990 0.276 0.075 0.269 0.543
10 0.382 0.933 0.038 0.559 0.746 0.511
11 0.043 0.918 0.101 0.290 0.584 0.822
12 0.895 0.036 0.207 0.966 0.486 0.533
13 0.290 0.872 0.902 0.934 0.877 0.155
14 0.859 0.568 0.428 0.027 0.136 0.265
15 0.290 0.420 0.915 0.465 0.532 0.059
16 0.155 0.922 0.036 0.577 0.545 0.336

---- 编辑 ---- 修复了过期的链接和少量清理。

于 2012-06-09T15:26:01.907 回答
8

我不知道为什么 Mark Adler 说“crc32 很难将输入位分配给哈希”。crc32 散列中没有一个位与输入位完全相等。散列的任何位都是输入位的线性组合。其次，crc 总是将相同数量的不同输入序列均匀地映射到给定的哈希值。例如，如果您有 1000 位长的消息，在 crc32 之后，您总是可以找到 2^(1000-32) 个产生给定哈希值的序列，不多也不少。

如果您不需要安全功能，crc 可以完美地充当散列。

实际上，我认为其他非安全哈希函数可能比 crc 更简单，如果您需要更长的 crc，例如 crc-256。

于 2015-02-27T01:58:15.137 回答
0

CRC32 将字节映射到 32 位整数，然后用 xor 对它们进行累加。这意味着每个字节仅影响散列中 32 位中的 8 位。当然 CRC32 也会发生变化，但它只是隐藏了问题。即它会不均匀地分配密钥，在某些区域会有大量的集群。看起来这样的哈希工作正常，直到你到达那个区域，突然你的 O(1) 哈希表变成了 O(n) 哈希表。

CRC32 旨在检测损坏的文件，而不是散列。正如 Mark 所说，它不会保护您的文件不被修改，因为黑客仍然可以通过在更改后插入正确制作的 32 位值来随意修改它们。

于 2020-10-05T20:41:10.387 回答