Инкрементные контрольные суммы

Ответ 1

Я использовал только контрольные суммы Adler/Fletcher, которые работают, как вы описываете.

Существует хорошее сравнение реализаций хешей/контрольной суммы crypto ++ здесь.

Ответ 2

Если это просто вопрос быстрого комбинирования контрольных сумм меньших блоков для получения контрольных сумм большего сообщения (не обязательно простым суммированием), вы можете сделать это с помощью 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 как сумму (xor) сообщений 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), который зависит только от количества нулей добавить. Вы можете прекомпилировать это в таблице или использовать алгоритм с квадратным умножением, чтобы быстро вычислить эту мощность.

Рекомендуемое чтение: Безболезненное руководство по алгоритмам обнаружения ошибок CRC

Ответ 3

Чтобы ответить на вопрос Amigable Clark Kent bounty, для целей идентификации файлов вы, вероятно, хотите использовать криптографическую хеш-функцию, которая пытается гарантировать, что любые два заданных файла имеют чрезвычайно низкую вероятность создания одинакового значения, в отличие от контрольной суммы, которая является обычно используется только для обнаружения ошибок и может предоставлять одинаковое значение для двух очень разных файлов.

Многие криптографические хэш-функции, такие как MD5 и SHA-1, используйте конструкцию Merkle-Damgård, в которой есть расчет, чтобы сжать блок данных в фиксированный размер, а затем объединить это значение с фиксированным размером из предыдущего блока (или вектором инициализации для первого блока). Таким образом, они могут работать в потоковом режиме, постепенно вычисляя по мере их продвижения.