数据长度与 CRC 长度

StackOverflow https://stackoverflow.com/questions/2321676

  •  22-09-2019
  •  | 
  •  

题

我见过 8 位、16 位和 32 位 CRC。

我什么时候需要跳转到更广泛的 CRC？

我的直觉反应是它基于数据长度：

  1. 1-100字节：8位CRC校验
  2. 101 - 1000 字节：16 位CRC
  3. 1001 - ???字节：32位CRC

编辑：看看关于 CRC 的维基百科页面和 Lott 的答案，我们得到的是：

<64 字节：8位CRC校验

<16K 字节：16 位CRC

<512M 字节：32位CRC

有帮助吗？

解决方案

这不是一个研究课题。确实很好理解： http://en.wikipedia.org/wiki/Cyclic_redundancy_check

数学很简单。8 位 CRC 将所有消息归结为 256 个值之一。如果您的消息长度超过几个字节，则多条消息具有相同哈希值的可能性会越来越高。

同样，16 位 CRC 为您提供 65,536 个可用哈希值之一。任意两条消息具有这些值之一的几率是多少？

32 位 CRC 为您提供大约 40 亿个可用哈希值。

来自维基百科文章：“最大总块长度等于 2**r − 1”。这是以位为单位的。你不需要做太多研究就能看到这一点 2**9 - 1 是511位。使用 CRC-8，长度超过 64 字节的多个消息将具有相同的 CRC 校验和值。

其他提示

CRC 的有效性取决于多种因素。您不仅需要选择 CRC 的大小，还需要选择要使用的生成多项式。存在复杂且非直观的权衡，具体取决于：

  • 信道的预期误码率。
  • 错误是否倾向于突发发生或倾向于分散（突发很常见）
  • 需要保护的数据长度——最大长度、最小长度和分布。

Philip Koopman 和 Tridib Chakravarty 发表在 2004 年国际可靠系统和网络会议论文集上的论文《嵌入式网络的循环冗余码多项式选择》给出了非常好的概述并提出了一些建议。它还提供了进一步理解的参考书目。

http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

CRC 长度与文件大小的选择主要与以下情况相关：输入更有可能与“正确”输入相差三位或更少位，而不是相差很大。给定两个截然不同的输入，对于大多数形式的 8 位校验值（包括 CRC），错误匹配的可能性约为 1/256，对于大多数形式的 16 位校验值（包括 CRC），错误匹配的可能性约为 1/65536 ， ETC。CRC 的优势在于它对非常相似的输入的处理。

对于其多项式生成两个长度为 128 的周期的 8 位 CRC，数据包中比未检测到的短的单比特、双比特或三比特错误的分数将不会是 1/256，而是为零。同样，对于周期为 32768 的 16 位 CRC，使用 32768 位或更少的数据包。

然而，如果数据包比 CRC 周期长，并且错误位之间的距离是 CRC 周期的倍数，则双位错误将无法检测到。虽然这看起来不太可能发生，但 CRC8 在捕获长数据包中的双位错误方面比捕获“数据包完全被扰乱”错误方面要差一些。如果双位错误是第二常见的故障模式（仅次于单位错误），那就糟糕了。然而，如果任何破坏某些数据的因素都可能破坏大量数据，那么具有双位错误的 CRC 的不良行为可能不是问题。

我认为 CRC 的大小更多地与您需要的 CRC 的唯一性有关，而不是与输入数据的大小有关。这与您计算 CRC 的特定用途和项目数量有关。

应根据消息的长度专门选择 CRC，这不仅仅是 CRC 大小的问题： http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

这是 CRC-N 的一个很好的“现实世界”评估http://www.backplane.com/matt/crc64.html

我使用 CRC-32 和文件大小比较，并且在检查的数十亿个文件中从未遇到匹配的 CRC-32 和文件大小冲突。但我知道有一些存在，但不是故意强迫存在的。（黑客技巧/漏洞）

在进行比较时，您还应该检查“数据大小”。在正确的大小范围内，很少会发生相同数据大小与匹配 CRC 的冲突。

故意操纵数据以伪造匹配，通常是通过添加额外数据直到 CRC 与目标匹配来完成的。但是，这会导致数据大小不再匹配。尝试暴力破解，或者循环使用大小相同的随机或顺序数据，将会留下真正狭窄的碰撞率。

您还可能在数据大小内发生冲突，这只是由于所使用的公式的通用限制以及使用位/字节和十进制系统的约束，这取决于浮点值，这些值会被截断和剪裁。

当你开始看到许多无法“确认”为“原始”的碰撞时，你会想要考虑扩大规模。（当它们都具有相同的数据大小时，并且（向后测试时，它们具有匹配的 CRC。反向/字节或反向/位，或位偏移）

无论如何，它永远不应该用作唯一的比较形式，只是为了快速比较形式，用于索引。

您可以使用 CRC-8 来索引整个互联网，并将所有内容划分为 N 个类别之一。你想要那些碰撞。现在，通过这些预先排序，您只需检查 N 个目录之一，查找“文件大小”或“反向 CRC”，或者您可以快速对较小的数据集进行的任何其他比较。 ..

对同一数据块向前和向后执行 CRC-32 比仅在一个方向上使用 CRC-64 更可靠。（或者 MD5，就此而言。）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top