CRC32是否满足加性？

Question

我在几个地方读到crc32是可加的，即：CRC(A xor B) = CRC(A) xor CRC(B)。

但上述结论被我写下的以下代码所证伪：

import zlib
def crc32(data):
        return zlib.crc32(data) & 0xffffffff

print crc32(chr(ord("A") ^ ord("B")))
print crc32("A") ^ crc32("B")

程序输出：

1259060791
2567524794

能否有人提供一份正确的代码来证明这个理论，或指出我哪里做错了吗？

- Ryan82

---

一开始我误解了这句话 - 我以为，嗯，当然我经常使用CRC32，但我随时可以戒掉...真的，我可以... - Joe Enos

你能否提供一些来源来证明 crc(A ^ B) = crc(A) ^ crc(B) 这个等式，因为谷歌上没有找到相关内容。 - Hyperboreus

你难道没有通过证明假设失败来回答自己的问题吗？ - Jordan

CRC对于消息的连接是“可加性”的：CRC(A || B, iv) == CRC(B, CRC(A, iv))，其中A和B是消息的两个部分，||是相应的连接运算符，iv是CRC计算的“初始化向量”，例如常见的0xffffffff。这意味着，仅给出消息A和消息B的CRC值，就可以轻松地计算出CRC(A || B)，而无需参考实际的消息A。 - JimmyB

Answer 1

CRC在数学上是可加的，因为CRC散列只是从所有数据（视为一个巨大的整数）除以多项式常数的无进位除法的余数值。使用您的示例，类似于以下内容：

7 mod 5 = 2

6 mod 5 = 1

(7 mod 5) + (6 mod 5) = 3

(7 + 6) mod 5 = 3

在这个比喻中，“5”是我们的CRC多项式。

下面是一个可以玩耍的示例（基于gcc）：

#include <stdio.h>
#include <x86intrin.h>

int main(void)
{
        unsigned int crc_a = __builtin_ia32_crc32si( 0, 5);
        printf( "crc(5) = %08X\n", crc_a );
        unsigned int crc_b = __builtin_ia32_crc32si( 0, 7);
        printf( "crc(7) = %08X\n", crc_b );
        unsigned int crc_xor = crc_a ^ crc_b;
        printf( "crc(5) XOR crc(7) = %08X\n", crc_xor );
        unsigned int crc_xor2 = __builtin_ia32_crc32si( 0, 5 ^ 7);
        printf( "crc(5 XOR 7) = %08X\n", crc_xor2 );

        return 0;
}

输出结果与预期相符：

plxc15034> gcc -mcrc32 -Wall -O3 crctest.c
plxc15034> ./a.out
crc(5) = A6679B4B
crc(7) = 1900B8CA
crc(5) XOR crc(7) = BF672381
crc(5 XOR 7) = BF672381

因为该代码使用了x86 CRC32指令，所以只能在英特尔i7或更新的设备上运行。内部函数将正在运行的CRC哈希作为第一个参数，新数据作为第二个参数进行累加。返回值是新的运行CRC。

上述代码中0的初始运行CRC值非常关键。如果使用任何其他初始值，则CRC在实际意义上不是“可加性”的，因为您已经丢失了有关要分割的整数的信息。这正是您的示例中发生的情况。CRC函数从不将初始运行CRC值初始化为零，而通常为-1。原因是将CRC初始化为0允许任何数量的前导0在数据中简单地通过而不改变运行CRC值，其仍为0。因此，将CRC初始化为0在数学上是合理的，但在计算哈希的实际目的上，它是您最不想要的事情。

- srking

Answer 2

CRC-32算法基于多项式除法，并加入了一些额外的步骤。纯多项式余数是可加的。

也就是说：mod(poly1 + poly2, poly3) = mod(mod(poly1, poly3) + mod(poly2, poly3), poly3)

CRC-32算法建立在此基础上，是非可加的。计算字节数组m的CRC-32值：

1. 将前4个字节与0xFFFFFFFF异或。
2. 将早期字节视为更高的多项式幂，并将低阶位视为更高的多项式幂。例如，字节0x01 0x04将是多项式x^15 + x^3。
3. 将多项式乘以x^32。
4. 取该多项式除以CRC-32多项式0x104C11DB7的余数。余数多项式的次数小于32。
5. 将更低的幂视为更高的位序。例如，多项式x^2将是32位整数0x40000000。
6. 将结果与0xFFFFFFFF异或。

纯多项式余数运算在第4步中进行。第1步和第6步使CRC-32算法不可加。因此，如果您撤消步骤#1和#6的影响，则可以修改CRC-32算法以使其可加。

（另请参见：Python CRC-32 woes）

- Nayuki

Answer 3

如果a、b和c的长度相同，则CRC（a）xor CRC（b）xor CRC（c）等于CRC（a xor b xor c）。回到您最初的公式，这意味着CRC（a xor b）等于CRC（a）xor CRC（b）xor CRC（z），其中z是与另外两个序列长度相同的零序列。

- supercat

---

我可以确认 CRC(A ⊕ B) = CRC(A) ⊕ CRC(B) 是不正确的，但是 CRC(A ⊕ B ⊕ C) = CRC(A) ⊕ CRC(B) ⊕ CRC(C)，因此 CRC(A ⊕ B ⊕ C ⊕ D ⊕ E) = CRC(A) ⊕ CRC(B) ⊕ CRC(C) ⊕ CRC(D) ⊕ CRC(E)（如果你将 C 改为 C ⊕ D ⊕ E）。有没有什么原因它适用于奇数个操作数，而不适用于偶数个操作数？ - Victor

如果CRC32使用0x00000000的初始化向量，则“CRC（A ⊕ B）= CRC（A）⊕ CRC（B）”将成立，但它对前导零不敏感。CRC通常使用0xFFFFFFFF的初始化向量（使其表现为与FF异或的前四个字节序列的零初始化CRC）。如果定义CRCZ为使用零初始化向量执行的CRC，则“CRC（X）= CRCZ（x ⊕ FFFFFFFF00 ..）”，并且“CRC（X ⊕ Y）= CRCZ（x ⊕ y ⊕ FFFFFFFF00 ...）”。两个元素的表达式“CRC（X）⊕ CRC（Y）”... - supercat

相当于 CRCZ(x ⊕ FFFFFFFF00...) ⊕ CRCZ(y ⊕ FFFFFFFF00...)，进一步等价于 CRCZ(x ⊕ Y ⊕ FFFFFFFF00... ⊕ FFFFFFFF00...)，因此等于 CRCZ(x ⊕ Y) [这不等于 CRCZ(x ⊕ Y ⊕ FFFFFFFF00...)，也不等于 CRC(x ⊕ Y)]。用数学类比，定义 f(x)=-x，并使用乘法而非异或运算。那么 f(x·y·z) = -(x·y·z) = (-x)(-y)(-z) = f(x)·f(y)·f(z)，但 f(x·y) = -(x·y) = -((-x)·(-y)) = -(f(x)·f(y))。 - supercat

Answer 4

这意味着CRC结果的每个位位置仅由输入中相应的位位置驱动。考虑B == 0的示例。

您所描述的关系更可能适用于某些基本的异或或加法校验算法。

- janm