Добавочные контрольные суммы

Я ищу алгоритм контрольной суммы, где для большого блока данных контрольная сумма равна сумме контрольных сумм из всех меньших блоков компонентов. Большая часть того, что я нашел, взята из RFC 1624/1141, которые предоставляют эту функциональность. У кого-нибудь есть опыт работы с этими методами контрольной суммы или подобным?

Источник

3 ответа

Решение

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

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

Источник

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

Источник

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

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

Источник
Другие вопросы по тегам