如何计算 CRC32校验和?

也许我只是没有看到它,但 CRC32似乎要么不必要的复杂,或不充分的解释任何地方,我可以在网上找到。

我知道它是消息值的一个非进位算术除法的余数,除以(生成器)多项式,但我不知道它的实际实现。

我读过 CRC 错误检测算法无痛指南,我必须说它不是无痛的。理论上讲得很好,但作者从来没有说过一句简单的“就是这样”他确实说了标准的 CRC32算法的参数是什么,但是他没有清楚地说明如何得到它。

最让我抓狂的是,他说“就是这个了”,然后又补充道,“哦,顺便说一下,它可以被逆转,也可以用不同的初始条件开始”,而且没有给出一个明确的答案,在他刚刚添加的所有修改中,计算 CRC32校验和的最终方法是什么。

  • 对于 CRC32是如何计算的,是否有更简单的解释?

我尝试用 C 语言编写表格的形式:

for (i = 0; i < 256; i++)
{
temp = i;


for (j = 0; j < 8; j++)
{
if (temp & 1)
{
temp >>= 1;
temp ^= 0xEDB88320;
}
else {temp >>= 1;}
}
testcrc[i] = temp;
}

但这似乎产生的价值观与我在互联网上其他地方发现的价值观不一致。我 可以使用我在网上找到的值,但我想了解它们是如何创建的。

如果能帮助我们理清这些令人难以置信的数字,我们将不胜感激。

292215 次浏览

CRC 非常简单; 您将一个多项式表示为位和数据,然后将该多项式划分为数据(或者您将数据表示为多项式并执行相同的操作)。余数介于0和多项式之间是 CRC。您的代码有点难以理解,部分原因是它不完整: temp 和 testcrc 没有声明,因此不清楚正在索引什么,以及有多少数据在算法中运行。

理解 CRC 的方法是尝试用一小段数据(16位左右)和一个短的多项式——也许是4位——来计算一些 CRC。如果您这样练习,您将真正理解如何编写代码。

如果您经常这样做,那么 CRC 在软件中的计算速度是相当慢的。硬件计算要高效得多,只需要几个门。

CRC32的多项式是:

X32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x260 + x261 + x262 + x + 1

或者用十六进制和二进制:

0x 0104 C11D B7
100000100110000010001110110110111

最高术语(x32)通常不是显式写入的,所以它可以用十六进制表示

0x 04 C11D B7

你可以自由地计算1和0,但是你会发现它们与多项式相匹配,其中 1是位0(或第一位) ,x是位1(或第二位)。

为什么是这个多项式?因为需要给定一个标准的多项式,而且标准是由 IEEE 802.3设定的。另外,要找到一个能够有效检测不同位错误的多项式也是非常困难的。

你可以把 CRC-32看作是一系列“无进位的二进制算法”,或者基本上是“异或和移位操作”。这在技术上被称为多项式算术。

为了更好地理解它,想想这个乘法:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

如果我们假设 x 是基数2,那么我们得到:

x^7 + x^3 + x^2 + x^1 + x^0

为什么? 因为3x ^ 3等于11x ^ 11(但我们只需要1或0个前置数字) ,所以我们继续:

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

但是数学家们改变了规则,使之成为模式2。所以基本上任何二进制多项式 mod 2都是没有进位或 XOR 的加法。我们最初的方程是这样的:

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

我知道这是一个信念的飞跃,但这超出了我作为线程编程人员的能力。如果你是一个计算机科学的核心学生或工程师,我挑战打破这一点。每个人都会从这个分析中受益。

举个完整的例子:

   Original message                : 1101011011
Polynomial of (W)idth 4         :      10011
Message after appending W zeros : 11010110110000

现在我们使用 CRC 算法将增强消息除以 Poly,这与之前的除法相同:

            1100001010 = Quotient (nobody cares about the quotient)
_______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
-----,,.,,....
10011,.,,....
10011,.,,....
-----,.,,....
00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Remainder = THE CHECKSUM!!!!

除法得到一个商,我们抛弃它,余数是计算出来的校验和。这样计算就结束了。通常,校验和随后被追加到消息和传输的结果。在这种情况下,传输将是: 11010110111110。

只使用32位数作为除数,并使用整个流作为股息。把商数丢掉,剩下的留下。在邮件的末尾添加其余部分,就得到了一个 CRC32。

普通男人的评论:

         QUOTIENT
----------
DIVISOR ) DIVIDEND
= REMAINDER
  1. 取前32位。
  2. 移位
  3. 如果32位小于 DIVISOR,则转到步骤2。
  4. XOR 32位被 DIVISOR。转到步骤2。

(请注意,流必须可以被32位除以,否则它应该被填充。例如,一个8位 ANSI 流必须填充。同样在溪流的尽头,分水也停止了。)

除了维基百科的 循环冗余校验< em > 计算结直肠癌文章,我发现一篇题为 逆转结直肠癌-理论与实践< b > * 的论文是一个很好的参考。

计算 CRC 基本上有三种方法: 代数方法、面向位方法和表驱动方法。在 逆转结直肠癌-理论与实践< b > * 中,这三种算法/方法都在理论上得到了解释,并在 APPENDIX 中用 C 语言实现了 CRC32。

* PDF 连结
逆向 CRC-理论与实践。
胡柏林公共报道
SAR-PR-2006-05
二零零六年五月
作者:
Martin Stigge Henryk Plötz Wolf Müller Jens-Peter Redlich

对于 IEEE802.3,CRC-32。把整个消息想象成一个串行位流,在消息的末尾追加32个零。接下来,您必须反转消息的每个字节的位,并对前32位进行1的补充。现在除以 CRC-32多项式,0x104C11DB7。最后,必须用1来补充这个除法位的32位余数——将余数的4个字节中的每一个都反过来。这将成为追加到消息末尾的32位 CRC。

这个奇怪过程的原因是,第一个以太网实现将一次序列化消息一个字节,并首先传输每个字节中最低有效位。串行位流然后经过一个串行 CRC-32移位寄存器计算,这个移位寄存器只是简单的补充,并在消息完成后通过网络发送出去。补充消息前32位的原因是,即使消息全部为零,也不会得到全零的 CRC。

我在这里发表了一篇关于 CRC-32散列的教程: CRC-32散列教程-AutoHotkey 社区

在这个例子中,我演示了如何计算‘ ANSI’(每个字符1字节)字符串‘ abc’的 CRC-32哈希值:

calculate the CRC-32 hash for the 'ANSI' string 'abc':


inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7


start with the 3 bytes 'abc':
61 62 63 (as hex)
01100001 01100010 01100011 (as bin)


reverse the bits in each byte:
10000110 01000110 11000110


append 32 0 bits:
10000110010001101100011000000000000000000000000000000000


XOR (exclusive or) the first 4 bytes with 0xFFFFFFFF:
(i.e. flip the first 32 bits:)
01111001101110010011100111111111000000000000000000000000


next we will perform 'CRC division':


a simple description of 'CRC division':
we put a 33-bit box around the start of a binary number,
start of process:
if the first bit is 1, we XOR the number with the polynomial,
if the first bit is 0, we do nothing,
we then move the 33-bit box right by 1 bit,
if we have reached the end of the number,
then the 33-bit box contains the 'remainder',
otherwise we go back to 'start of process'


note: every time we perform a XOR, the number begins with a 1 bit,
and the polynomial always begins with a 1 bit,
1 XORed with 1 gives 0, so the resulting number will always begin with a 0 bit


'CRC division':
'divide' by the polynomial 0x104C11DB7:
01111001101110010011100111111111000000000000000000000000
100000100110000010001110110110111
---------------------------------
111000100010010111111010010010110
100000100110000010001110110110111
---------------------------------
110000001000101011101001001000010
100000100110000010001110110110111
---------------------------------
100001011101010011001111111101010
100000100110000010001110110110111
---------------------------------
111101101000100000100101110100000
100000100110000010001110110110111
---------------------------------
111010011101000101010110000101110
100000100110000010001110110110111
---------------------------------
110101110110001110110001100110010
100000100110000010001110110110111
---------------------------------
101010100000011001111110100001010
100000100110000010001110110110111
---------------------------------
101000011001101111000001011110100
100000100110000010001110110110111
---------------------------------
100011111110110100111110100001100
100000100110000010001110110110111
---------------------------------
110110001101101100000101110110000
100000100110000010001110110110111
---------------------------------
101101010111011100010110000001110
100000100110000010001110110110111
---------------------------------
110111000101111001100011011100100
100000100110000010001110110110111
---------------------------------
10111100011111011101101101010011


we obtain the 32-bit remainder:
0b10111100011111011101101101010011 = 0xBC7DDB53


note: the remainder is a 32-bit number, it may start with a 1 bit or a 0 bit


XOR the remainder with 0xFFFFFFFF:
(i.e. flip the 32 bits:)
0b01000011100000100010010010101100 = 0x438224AC


reverse bits:
bit-reverse the 4 bytes (32 bits), treating them as one entity:
(e.g. 'abcdefgh ijklmnop qrstuvwx yzABCDEF'
to 'FEDCBAzy xwvutsrq ponmlkji hgfedcba':)
0b00110101001001000100000111000010 = 0x352441C2


thus the CRC-32 hash for the 'ANSI' string 'abc' is: 0x352441C2

然后总是有罗塞塔代码,它显示 crc32实现了几十种计算机语言。https://rosettacode.org/wiki/CRC-32并且有许多解释和实现的链接。

为了减少 crc32采取提醒你需要:

  1. 对每个字节进行位反转
  2. 用0xFF 表示前四个字节(这是为了避免前面的0出现错误)
  3. 在末尾添加填充(这是为了让最后4个字节参与散列)
  4. 计算提醒
  5. 再反转一次
  6. 再次得出结果。

在代码中,这是:


func CRC32 (file []byte) uint32 {
for i , v := range(file) {
file[i] = bits.Reverse8(v)
}
for i := 0; i < 4; i++ {
file[i] ^= 0xFF
}


// Add padding
file = append(file, []byte{0, 0, 0, 0}...)
newReminder := bits.Reverse32(reminderIEEE(file))


return newReminder ^ 0xFFFFFFFF
}

哪里提醒 IEEE 是 GF (2)[ x ]上的纯提醒