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

Question

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

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

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

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

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

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

Answer 1

Предлагаю вам взглянуть на this SO page, CRC против MD5/SHA1.
Скорость и столкновения обсуждаются в this other thread.
И как всегда Wikipedia - твой друг.

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

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

Редактировать Следующие комментарии

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

Answer 2

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

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

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