Какой алгоритм контрольной суммы я должен использовать?

Я создаю систему, которая должна быть в состоянии найти, если обновлено blobs байтов. Вместо того, чтобы хранить весь блок (они могут быть до 5 МБ), я думаю, что я должен вычислить контрольную сумму, сохранить это и вычислить одну и ту же контрольную сумму немного позже, чтобы узнать, обновлен ли блог.

Цель состоит в том, чтобы свести к минимуму следующее (в этом порядке):

размер контрольной суммы
время для вычисления
вероятность столкновений (2 идентичные контрольные суммы происходят, даже если содержимое было изменено).

Для нашей системы приемлемо иметь столкновение не более 1/1 000 000. Проблема заключается не в безопасности, а просто при обновлении/обнаружении ошибок, поэтому редкие столкновения в порядке. (Вот почему я старался свести к минимуму).

Кроме того, мы не можем самостоятельно изменять кадры текста.

Конечно, md5, crc или sha1 приходят на ум, и если бы я хотел быстрое решение, я бы пошел на это. Однако, более чем быстрое решение, я ищу, что может быть сравнение различных методов, а также плюсы и минусы.

Ответ 1

Я предлагаю вам взглянуть на эту страницу SO, CRC и MD5/SHA1.
Скорость и столкновения обсуждаются в этой другой теме.
И как всегда Wikipedia - ваш друг.

Если бы мне пришлось выбирать, есть важный вопрос: хотите ли вы, чтобы в любом случае не было столкновений - или, по крайней мере, вероятность была настолько низкой, что она близка к вероятности того, что Луна сталкивается с Землей в течение следующих 5 минут?

Если да, выберите семейство SHA.
В вашем случае я бы изменил способ проверки обновлений.
Например, инкрементное число может быть связано с блобом и отправляться вместо хэша, запрос на обновление потребуется, если число отличается с другой стороны. Вероятность столкновения в этом случае идет от ~ 10 ^ -18 до ~ 0 (в основном 0 + вероятность ошибки)...

Изменить следующие комментарии

Нашел этот алгоритм, Alder-32, который хорош для длинных сообщений (MB) с CRC из 32 бит, то есть около ~ 1/10 ^ 9 (MD5 имеет длину 128 бит).
Он быстро вычисляется.
Adler-32. В нижней части есть образец (ссылка).

Ответ 2

Blake2 - самая быстрая хеш-функция, которую вы можете использовать, и которая в основном используется:

BLAKE2 не только быстрее других хороших хеш-функций, это даже быстрее, чем MD5 или SHA-1 Источник

Победителем конкурса SHA-3 был алгоритм Keccak, но пока еще популярная реализация не используется по умолчанию в дистрибутивах GNU/Linux. Вместо этого Blake2, который был кандидатом на конкурс SHA-3, быстрее, чем Keccak, и является частью GNU coreutils. Итак, на вашем дистрибутиве GNU/Linux вы можете использовать b2sum для использования алгоритма хеширования Blake2.