数据长度vs CRC长度

这不是一个研究课题。大家都很清楚: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

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

一个32位CRC给你大约40亿个可用的散列值。

2**r − 1 ". 那是零零碎碎的。你不需要做太多的研究就能看到这一点 2**9 - 1 是511位。使用CRC-8,多个超过64字节的消息将具有相同的CRC校验和值。

• 信道的预期误码率。
• 要保护的数据的长度—最大长度、最小长度和分布。

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

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

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

但是,如果数据包长于CRC周期,那么如果错误位之间的距离是CRC周期的倍数,则将无法检测到双位错误。虽然这看起来不太可能发生,但CRC8在捕捉长数据包中的双位错误时,比捕捉“数据包完全被加扰”错误时要差一些。如果双位错误是第二个最常见的故障模式(仅次于单位错误),那就不好了。然而,如果任何损坏某些数据的东西都可能损坏大量数据,那么具有双位错误的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的冲突。

您还可以在数据大小内发生冲突,这仅仅取决于所用公式的一般限制,以及使用位/字节和以10为基数的系统的限制,这取决于浮点值,而浮点值会被截断和剪裁。

当你开始看到许多不能被“确认”为“原始”的碰撞时,你会想把它放大(当它们都有相同的数据大小,并且(当向后测试时,它们有一个匹配的CRC。反向/字节或反向/位或位偏移)

在任何情况下,它都不应该被用作唯一的比较形式,只是为了一种快速的比较形式,为了索引。

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

在同一个数据块上前后执行CRC-32比只在一个方向上使用CRC-64更可靠(或者是一个MD5