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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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