Насколько более вероятны коллизии хешей, если я хеширую кучу хешей? - PullRequest
2 голосов
/ 10 ноября 2009

Скажем, я использую хеш для идентификации файлов, поэтому мне не нужно, чтобы он был безопасным, мне просто нужно минимизировать коллизии. Я думал, что смогу ускорить хэш, запустив четыре хэша параллельно, используя SIMD, а затем хэшируя конечный результат. Если хеш рассчитан на 512-битный блок, я просто пошагово просматриваю файл, берущий блоки 4x512 бит за один раз и генерирую из этого четыре хэша; затем в конце файла я хеширую четыре результирующих хэша вместе.

Я почти уверен, что этот метод даст худшие хэши ... но насколько беднее? Любая обратная сторона расчетов конверта?

1 Ответ

4 голосов
/ 10 ноября 2009

Идея о том, что вы можете читать блоки файла с диска быстрее, чем вы можете их хэшировать, является, конечно, непроверенным предположением? Дисковый ввод-вывод - даже SSD - на много порядков медленнее, чем ОЗУ, которое происходит при хешировании.

Обеспечение низких коллизий является критерием проектирования для всех хэшей, и все основные хэши делают это хорошо - просто используйте основной хэш, например, MD5.

Специфично для решения, которое рассматривает плакат, но не учитывая, что параллельное хеширование ослабляет хеш. Существуют хэши, специально разработанные для параллельного хеширования блоков и объединения результатов, как сказал автор, хотя, возможно, пока они еще не получили широкого распространения (например, MD6 , который был отменен из SHA3)

В более общем смысле, есть основные реализации функций хеширования, которые используют SIMD. Реализаторы хеширования очень осведомлены о производительности , и им требуется время для оптимизации их реализаций; у вас будет тяжелая работа, равная их усилиям. Лучшее программное обеспечение для хеширования strong составляет от 6 до 10 циклов / байт. Аппаратное ускорение Хэширование также доступно, если хэширование является реальным узким местом.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...