增量校验和

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,...的总和(xor),就像这样

  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)

同样,我的意思是+你可以用二进制XOR实现GF2.

最后,可以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)相乘,该多项式()仅取决于要添加的零的数量.您可以在表格中对此进行预计算,或使用square-and-multiply算法快速计算此功率.

推荐阅读:CRC错误检测算法的无痛指南

Answer 2

我只使用了Adler/Fletcher校验和,它可以按照您的描述工作.

有加密哈希++ /校验实现的一个很好的对比在这里.