checksum - 增量校验和

Question

我正在寻找一种校验和算法，其中对于大块数据，校验和等于所有较小组件块的校验和之和。我发现的大部分内容来自提供此功能的 RFC 1624/1141。有没有人对这些校验和技术或类似技术有任何经验？

Answer 1

如果只是快速组合较小块的校验和以获得较大消息的校验和（不一定通过简单的求和），您可以使用 CRC 类型（或类似）算法来做到这一点。

CRC-32 算法就这么简单：

uint32_t update(uint32_t state, unsigned bit)
{
    if (((state >> 31) ^ bit) & 1) state = (state << 1) ^ 0x04C11DB7;
    else                           state = (state << 1);
    return state;
}

在数学上，该状态表示域 GF2 上的多项式，该多项式始终以生成多项式为模减少。给定一个新位b，旧状态会像这样转换为新状态

state --> (state * x^1 + b * x^32) mod G

其中 G 是生成多项式，加法在 GF2 (xor) 中完成。从某种意义上说，此校验和是线性M的，您可以将消息写为消息 A、B、C 的总和（异或）......就像这样

  10110010 00000000 00000000 = A =    a     00000000 00000000
  00000000 10010001 00000000 = B = 00000000    b     00000000
  00000000 00000000 11000101 = C = 00000000 00000000    c
-------------------------------------------------------------
= 10110010 10010001 11000101 = M =    a        b        c

具有以下属性

         M  =          A  +          B  +          C
checksum(M) = checksum(A) + checksum(B) + checksum(C)

同样，我的意思是+在 GF2 中，您可以使用二进制 XOR 来实现。

最后，可以checksum(B)根据checksum(b)和子块b相对于的位置进行计算B。简单的部分是前导零。前导零根本不影响校验和。所以checksum(0000xxxx)是一样的checksum(xxxx)。如果要在给定未填充消息的校验和的情况下计算零填充（右侧->尾随零）消息的校验和，则要复杂一些。但没那么复杂：

zero_pad(old_check_sum, number_of_zeros)
  := ( old_check_sum *  x^{number_of_zeros}        ) mod G
   = ( old_check_sum * (x^{number_of_zeros} mod G) ) mod G

因此，获取零填充消息的校验和只需将非填充消息的“校验和多项式”与其他x^{number_of_zeros} mod G仅取决于要添加的零数量的多项式 ( ) 相乘。您可以在表格中预先计算，或使用平方和乘法算法快速计算此功率。

Suggested reading: Painless Guide to CRC Error Detection Algorithms

Answer 2

我只使用了如您所描述的那样工作的 Adler/ Fletcher校验和。

这里对加密++哈希/校验和实现进行了很好的比较。

Answer 3

要回答 Amigable Clark Kent 的赏金问题，出于文件身份的目的，您可能需要一个加密哈希函数，它试图保证任何两个给定文件产生相同值的可能性极低，而不是通常用于校验和仅错误检测，并且可能为两个非常不同的文件提供相同的值。

许多加密哈希函数，例如MD5和SHA-1，使用Merkle-Damgård 构造，其中有一个计算将数据块压缩成固定大小，然后将其与前一个块的固定大小值组合（或第一个块的初始化向量）。因此，它们能够以流模式工作，随着它们的进行增量计算。