Какой алгоритм хеширования выбрать
- MD5: 16 байт (время до хэша 500 МБ: 1462 МС)
- SHA1: 20 байт (1644 МС)
- SHA256: 32 байта (5618 МС)
- SHA384: 48 байт (3839 МС)
- SHA512: 64 байта (3820 МС)
- RIPEMD: 20 байт (7066 МС)
каждая из этих функций выполняет по-разному; MD5 является самым быстрым, а RIPEMD - самый медленный.
MD5 имеет то преимущество, что он вписывается во встроенный тип Guid. Что делает его очень простым в использовании для идентификации.
MD5 однако уязвим для Таранов, SHA1 также уязвим, но в меньшей степени.
MD5 / SHA1/Sha2xx не имеют случайных столкновений
все хэш-функции имеют коллизии, это факт жизни. Попадание на эти столкновения случайно эквивалентно победу в межгалактической лотерее. То есть, никто не выигрывает в межгалактической лотерее, Ее просто не так, как работает лотерея. Вы никогда не столкнетесь с случайным хэшем MD5/SHA1/SHA2XXX. Каждое слово в каждом словаре, в каждом язык, хэши к другому значению. Каждое имя пути на каждой машине на всей планете имеет другой хэш MD5/SHA1/SHA2XXX. Откуда мне знать, спросите вы. Как я уже говорил, никто никогда не выигрывает в межгалактической лотерее.
Все хэш-функции "сломаны"
на принципу Дирихле говорит, что старайтесь изо всех сил, вы не можете поместиться больше, чем 2 голубей в 2 отверстия (если вы не режете голубей). Точно так же вы не можете поместить 2^128 + 1 номера в 2^128 слотов. Все хэш-функции приводят к хэшу конечного размера, это означает, что вы всегда можете найти столкновение, если вы ищете последовательности "конечного размера" + 1. Это просто невозможно сделать. Не MD5 и не Лялька.
При каких условиях следует использовать какой алгоритм хеширования?
конкретные вопросы, на которые мне действительно интересно получить ответ:
нельзя ли доверять MD5? В обычных ситуациях, когда вы используете алгоритм MD5 без злого умысла, и ни одна третья сторона не имеет злого умысла, вы ожидаете каких-либо столкновений (то есть два произвольных байта [], производящих один и тот же хэш)
насколько лучше RIPEMD, чем SHA1? (если его лучше) его 5 раз медленнее вычислять, но размер хэша такой же, как SHA1.
каковы шансы получить не злонамеренные коллизии при хэшировании имен файлов (или других коротких струны)? (Напр. 2 случайные имена файлов с тем же хэшем MD5) (с MD5 / SHA1 / SHA2xx) в общем, каковы шансы на не злонамеренные столкновения?
Это тест, который я использовал:
в криптографии хэш-функции предоставляют три отдельные функции.
Это был показано, что MD5 не устойчив к столкновениям, однако, что не исключает его использования в приложениях, не требующих сопротивления столкновению. Действительно, MD5 часто все еще используется в приложениях, где меньший размер и скорость ключа полезны. Тем не менее, из-за его недостатков исследователи рекомендуют использовать другие хэш-функции в новых сценариях.
SHA1 имеет недостаток, который позволяет обнаруживать коллизии теоретически намного меньше, чем 2^80 шагов безопасной хэш-функции его длины потребовать. Атака постоянно пересматривается и в настоящее время может быть выполнена в ~2^63 шага - едва ли в пределах текущей области вычисляемости. По этой причине NIST постепенно прекращает использование SHA1, заявив, что семейство SHA2 должно использоваться после 2010 года.
SHA2-это новое семейство хэш-функций, созданных после SHA1. В настоящее время нет известных атак на функции SHA2. SHA256, 384 и 512 все часть семьи SHA2, как раз используя различные ключевые длины.
RIPEMD я не могу комментировать слишком много, за исключением того, что он не так часто используется, как семьи SHA, и поэтому не был тщательно изучен криптографическими исследователями. Только по этой причине я бы рекомендовал использовать функции SHA над ним. В реализации, которую вы используете, он также кажется довольно медленным, что делает его менее полезным.
В заключение, нет одной лучшей функции - все зависит от того, для чего она вам нужна. Помните о недостатках с каждым и вы сможете лучше всего выбрать правильную хэш-функцию для код сценарий.
Раздел 1: Что такое хэширование и плагин crypto
Хэш (хеш) — это криптографическая функция, которая представляет собой математический алгоритм, преобразующий произвольный массив данных (информацию) в строку фиксированной длины, состоящую из цифр и букв.
Как работает процесс хэширования:
Вначале определяют, целостность каких файлов нужно контролировать. Для каждого файла производится вычисления значения его хэша по специальному алгоритму с сохранением результата. Через необходимое время производится аналогичный расчет и сравниваются результаты. Если значения отличаются, значит информация содержащаяся в файле была изменена.
Основная особенность хэш-функций — это то, что их нельзя расхэшировать, невозможно вернуть единожды хэшированную строку данных в обратный читабельный вид.
Где используется:
Анализ при помощи хэш-функций часто используется для контроля целостности и сверки уникальности важных файлов операционной системы, программ, а также с целью защиты личных данных на просторах сети Интернет, таких как пароль, ключ или иное значение, которое не требует обратной расшифровки, но требует контроля/сравнения значений.
Какими характеристиками должна обладать хэш-функция:
Должна уметь выполнять преобразования данных произвольной длины в фиксированную.
Должна иметь открытый алгоритм, чтобы можно было исследовать её криптостойкость.
Должна быть односторонней, то есть не должно быть математической возможности по результату определить исходные данные.
Должна "сопротивляться" коллизиям, т.е. не должна выдавать одинаковых значений при разных входных данных.
Не должна требовать больших вычислительных ресурсов.
При малейшем изменении входных данных результат должен существенно изменяться.
Чтобы рассмотреть процесс хэширование во всей его красе, мы будем использовать сопутствующий плагин для фреймворка Flutter:
crypto — сборник криптографических хэш-функций, написанный на чистом языке Dart, поддерживает такие платформы как Android, iOS, Linux, macOS, Windows, Web.
Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.
О себе
Студент кафедры информационной безопасности.
О хэшировании
Здесь v — некоторая константа, часто ее называют инициализирующим вектором. Она выбирается
из различных соображений и может представлять собой секретную константу или набор случайных данных (выборку даты и времени, например).
При таком подходе свойства хэш-функции полностью определяются свойствами одношаговой сжимающей функции.
О статистических свойствах и требованиях
Как я уже говорил основным требованием к хэш-функциям является равномерность распределения их значений при случайном выборе значений аргумента. Для криптографических хеш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось. Это называется лавинным эффектом.
К ключевым функциям хэширования предъявляются следующие требования:
— невозможность фабрикации,
— невозможность модификации.
К бесключевым функциям предъявляют требования:
— однонаправленность,
— устойчивость к коллизиям,
— устойчивость к нахождению второго прообраза.
Это была теоретическая часть, которая пригодится нам в дальнейшем…
О популярных хэш-алгоритмах
Алгоритмы CRC16/32 — контрольная сумма (не криптографическое преобразование).
Алгоритмы MD2/4/5/6. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
Алгоритм MD6 — очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.
Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 — собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.
Одним из ключевых слов, которые новички слышат, когда узнают о блокчейне, являются понятия хэша и алгоритма хэширования, которые кажутся распространёнными для безопасности. Запуск децентрализованной сети и консенсуса, такой как биткойн или сеть эфириум с десятками тысяч узлов, соединенных через p2p, требует, как “надежности”, так и эффективности проверки. То есть, эти системы нуждаются в способах кодирования информации в компактном формате, позволяющем обеспечить безопасную и быструю проверку ее участниками
Криптографические хэши используются везде, от хранения паролей до систем проверки файлов. Основная идея состоит в том, чтобы использовать детерминированный алгоритм (алгоритмический процесс, который выдает уникальный и предопределенный результат для задачи входных данных), который принимает один вход и создает строку фиксированной длины каждый раз. То есть, использование одного и того же ввода всегда приводит к одному и тому же результату. Детерминизм важен не только для хэшей, но и для одного бита, который изменяется во входных данных, создавая совершенно другой хэш. Проблема с алгоритмами хэширования - неизбежность коллизий. То есть, тот факт, что хэши являются строкой фиксированной длины, означает, что для каждого ввода, который мы можем себе представить, есть другие возможные входы, которые приведут к тому же хэшу. Коллизия - это плохо. Это означает, что, если злоумышленник может создавать коллизии, он может передавать вредоносные файлы или данные, как имеющие правильный и неправильный хэш и скрываться под правильным хешем. Цель хорошей хэш-функции состоит в том, чтобы сделать чрезвычайно сложным для злоумышленников найти способы генерации входных данных, которые хешируются с одинаковым значением. Вычисление хэша не должно быть слишком простым, так как это облегчает злоумышленникам искусственное вычисление коллизий. Алгоритмы хэширования должны быть устойчивы к «атакам нахождения прообраза». То есть, получая хеш, было бы чрезвычайно сложно вычислить обратные детерминированные шаги, предпринятые для воспроизведения значения, которое создало хэш (т.е нахождение прообраза).
Напомним, что «хорошие» алгоритмы хэширования имеют следующие свойства:
- Изменение одного бита во входных данных должно создать эффект изменения всего хеша;
- Вычисления хеша не должно быть слишком простым, высокая сложность нахождения прообраза;
- Должен иметь очень низкую вероятность коллизии;
Вы когда-нибудь слышали о том, что если вы поместите 23 человека в комнату, есть 50% шанс, что у двух из них будет один и тот же день рождения? Доведение числа до 70 человек в комнате дает вам 99,9% шанс. Если голуби рассажены в коробки, причем число голубей больше числа коробок, то хотя бы в одной из клеток находится более одного голубя. То есть фиксированные ограничения на выход означают, что существует фиксированная степень перестановок, на которых можно найти коллизию.
На самом деле MD5 настолько слаб к сопротивлению к коллизиям, что простой бытовой Процессор Pentium 2,4 ГГц может вычислить искусственные хэш-коллизии в течение нескольких секунд. Кроме того, его широкое использование в более ранние дни текущей сети создало тонны утечек MD5 предварительных прообразов в интернете, которые можно найти с помощью простого поиска Google их хэша.
NSA (Агентство национальной безопасности) уже давно является пионером стандартов алгоритмов хэширования, с их первоначальным предложением алгоритма Secure Hashing Algorithm или SHA1, создающий 160-битные выходы фиксированной длины. К сожалению, SHA1 просто улучшил MD5, увеличив длину вывода, количество однонаправленных операций и сложность этих односторонних операций, но не дает каких-либо фундаментальных улучшений против более мощных машин, пытающихся использовать различные атаки. Так как мы можем сделать что-то лучше?
В 2006 году Национальный институт стандартов и технологий (NIST) запустил конкурс, чтобы найти альтернативу SHA2, которая будет принципиально отличаться в своей архитектуре, чтобы стать стандартом. Таким образом, SHA3 появился как часть большой схемы алгоритмов хэширования, известной как KECCAK (произносится Кетч-Ак). Несмотря на название, SHA3 сильно отличается своим внутренним механизмом, известным как «конструкция губки», которая использует случайные перестановки для «Впитывания» и «Выжимания» данных, работая в качестве источника случайности для будущих входов, которые входят в алгоритм хэширования.
Когда дело дошло до интеграции алгоритма хеширования в блокчейн протоколы, биткоин использовал SHA256, в то время как Ethereum использовал модифицированный SHA3 (KECCAK256) для своего PoW. Однако важным качеством выбора хэш-функции для блокчейна с использованием доказательства работы является эффективность вычислений указанного хэша. Алгоритм хеширования биткойна SHA256 может быть вычислен достаточно просто с помощью специализированного оборудования, известного как специализированные интегральные схемы (или ASIC). Много было написано об использовании ASIC в майнинг пуле и о том, как они делают протокол направленным на централизацию вычислений. То есть доказательство работы стимулирует группы вычислительно эффективных машин объединяться в пулы и увеличивать то, что мы обозначаем “хэш-мощностью”, или мерой количества хэшей, которые машина может вычислить за интервал времени. Ethereum, выбрал модифицированный SHA3 известный как KECCAK 256. Кроме того, алгоритм PoW в Ethereum - Dagger-Hashimoto, должен был быть трудно вычисляемым для аппаратного обеспечения.
SHA3 не был единственным прорывом, который вышел из конкурса хеширования NIST в 2006 году. Несмотря на то, что SHA3 выиграл, алгоритм, известный как BLAKE, занял второе место. Для реализации шардинга Ethereum 2.0 использует более эффективное. Алгоритм хэширования BLAKE2b, который является высокоразвитой версией BLAKE от конкурентов, интенсивно изучается за его фантастическую эффективность по сравнению с KECCAK256 при сохранении высокой степени безопасности. Вычисление BLAKE2b фактически в 3 раза быстрее, чем KECCAK на современном процессоре.
Кажется, что независимо от того, что мы делаем, мы просто либо (1) увеличиваем сложность внутренних хеш-операций, либо (2) увеличиваем длину хеш-выхода, надеясь, что компьютеры атакующих не будут достаточно быстрыми, чтобы эффективно вычислять ее коллизию. Мы полагаемся на двусмысленность предварительных прообразов односторонних операций для обеспечения безопасности наших сетей. То есть цель безопасности алгоритма хеширования состоит в том, чтобы сделать как можно более сложным для любого, кто пытается найти два значения, которые хешируются на один и тот же вывод, несмотря на то, что существует бесконечное количество возможных столкновений. «Как насчет будущего квантовых компьютеров? Будут ли алгоритмы хэширования безопасными?» Короткий ответ и текущее понимание заключаются в том, что да, алгоритмы хэширования выдержат испытание временем против квантовых вычислений. То, что квантовые вычисления смогут сломать, - это те проблемы, которые имеют строгую математическую структуру, основанную на аккуратных трюках и теории, такой как шифрование RSA. С другой стороны, алгоритмы хэширования имеют менее формальную структуру во внутренних конструкциях. Квантовые компьютеры действительно дают повышенную скорость в вычислении неструктурированных проблем, таких как хэширование, но в конце концов, они все равно будут грубо атаковать так же, как компьютер сегодня попытается это сделать. Независимо от того, какие алгоритмы мы выбираем для наших протоколов, ясно, что мы движемся к вычислительно-эффективному будущему, и мы должны использовать наше лучшее суждение, чтобы выбрать правильные инструменты для работы и те, которые, мы надеемся, выдержат испытание временем.
Дмитриев Марк - Технический аналитик и управляющий криптоактивами инвестиционного фонда GT Blockchain Investments
Содержание
Вступление
Данная статья будет повествовать о том, что такое хэширование и какие алгоритмы хэширования используются в плагине crypto, а также будет приведена сравнительная таблица, в которой можно будет увидеть и сравнить характеристики тех или иных алгоритмов хэширования, поддерживаемых данным плагином.
При каких условиях следует использовать какой алгоритм хеширования?
конкретные вопросы, на которые мне действительно интересно получить ответ:
нельзя ли доверять MD5? В обычных ситуациях, когда вы используете алгоритм MD5 без злого умысла, и ни одна третья сторона не имеет злого умысла, вы ожидаете каких-либо столкновений (то есть два произвольных байта [], производящих один и тот же хэш)
насколько лучше RIPEMD, чем SHA1? (если его лучше) его 5 раз медленнее вычислять, но размер хэша такой же, как SHA1.
каковы шансы получить не злонамеренные коллизии при хэшировании имен файлов (или других коротких струны)? (Напр. 2 случайные имена файлов с тем же хэшем MD5) (с MD5 / SHA1 / SHA2xx) в общем, каковы шансы на не злонамеренные столкновения?
Это тест, который я использовал:
в криптографии хэш-функции предоставляют три отдельные функции.
Это был показано, что MD5 не устойчив к столкновениям, однако, что не исключает его использования в приложениях, не требующих сопротивления столкновению. Действительно, MD5 часто все еще используется в приложениях, где меньший размер и скорость ключа полезны. Тем не менее, из-за его недостатков исследователи рекомендуют использовать другие хэш-функции в новых сценариях.
SHA1 имеет недостаток, который позволяет обнаруживать коллизии теоретически намного меньше, чем 2^80 шагов безопасной хэш-функции его длины потребовать. Атака постоянно пересматривается и в настоящее время может быть выполнена в ~2^63 шага - едва ли в пределах текущей области вычисляемости. По этой причине NIST постепенно прекращает использование SHA1, заявив, что семейство SHA2 должно использоваться после 2010 года.
SHA2-это новое семейство хэш-функций, созданных после SHA1. В настоящее время нет известных атак на функции SHA2. SHA256, 384 и 512 все часть семьи SHA2, как раз используя различные ключевые длины.
RIPEMD я не могу комментировать слишком много, за исключением того, что он не так часто используется, как семьи SHA, и поэтому не был тщательно изучен криптографическими исследователями. Только по этой причине я бы рекомендовал использовать функции SHA над ним. В реализации, которую вы используете, он также кажется довольно медленным, что делает его менее полезным.
В заключение, нет одной лучшей функции - все зависит от того, для чего она вам нужна. Помните о недостатках с каждым и вы сможете лучше всего выбрать правильную хэш-функцию для код сценарий.
Но. MD5-это сломанный
иногда тот факт, что его сломали не важно.
тем не менее, Текущая рекомендация RSA не использовать MD5, если вам нужно сопротивление предварительного изображения. Люди склонны ошибаться в сторону осторожности, когда дело доходит до алгоритмов безопасности.
- используйте MD5, если вам нужна скорость / размер и не заботитесь о нападениях на день рождения или атаках до изображения.
повтори это за мной,нет никаких шансов столкновения MD5, вредоносные столкновения могут быть тщательно спроектированы. Несмотря на то, что на сегодняшний день на MD5 нет известных атак до изображения, линия от экспертов по безопасности заключается в том, что MD5 не следует использовать там, где вам нужно защищаться от атак до изображения. тоже касается В SHA1.
имейте в виду, что не все алгоритмы должны защищаться от атак предварительного изображения или столкновения. Возьмите тривиальный случай первого поиска дубликатов файлов на вашем HD.
- используйте функцию на основе SHA2XX, если вы хотите криптографически безопасную хэш-функцию.
никто никогда не находил столкновения SHA512. КОГДА-ЛИБО. Они очень старались. Если на то пошло, никто никогда не находил столкновения SHA256 или 384. .
- не используйте SHA1 или RIPEMD, если это не для сценария совместимости.
SHA1 атаки столкновения до 2^52, его не будет слишком долго, пока Столкновения SHA1 происходят в дикой природе.
для получения актуальной информации о различных хэш-функциях посмотрите на хэш-функция zoo.
Но подождите, есть больше
имеющего быстро хэш-функция может быть проклятием. Например: очень распространенным использованием хэш-функций является хранение паролей. По сути, вы вычисляете хэш пароля в сочетании с известной случайной строкой (чтобы препятствовать атакам rainbow) и сохраняете этот хэш в база данных.
проблема в том, что если злоумышленник получает дамп базы данных, он может довольно эффективно взлома паролей с помощью грубой силы. Каждая комбинация, которую он пробует, занимает лишь долю миллисекунды, и он может опробовать сотни тысяч паролей в секунду.
Начинаем неделю с полезного материала приуроченного к запуску курса «Алгоритмы для разработчиков». Приятного прочтения.
Хеширование — отличный практический инструмент, с интересной и тонкой теорией. Помимо использования в качестве словарной структуры данных, хеширование также встречается во многих различных областях, включая криптографию и теорию сложности. В этой лекции мы опишем два важных понятия: универсальное хеширование (также известное как универсальные семейства хеш-функций) и идеальное хеширование.
Материал, освещенный в этой лекции, включает в себя:
- Формальная постановка и общая идея хеширования.
- Универсальное хеширование.
- Идеальное хеширование.
Мы рассмотрим основную проблему со словарем, которую мы обсуждали до этого, и рассмотрим две версии: статическую и динамическую:
- Статическая: дано множество элементов S, мы хотим хранить его таким образом, чтобы можно было быстро выполнять поиск.
- Например, фиксированный словарь.
- Динамическая: здесь у нас есть последовательность запросов на вставку, поиск и, возможно, удаление. Мы хотим сделать все это эффективно.
3. Основы хеширования
Формальная постановка для хеширования заключается в следующем.
- Ключи принадлежат некоторому большому множеству U. (Например, представьте, что U — набор всех строк длиной не более 80 символов ascii.)
- Есть некоторое множество ключей S в U, которое нам на самом деле нужно (ключи могут быть как статическими, так и динамическими). Пусть N = |S|. Представьте, что N гораздо меньше, чем размер U. Например, S — это множество имен учеников в классе, которое намного меньше, чем 128^80.
- Мы будем выполнять вставки и поиск с помощью массива A некоторого размера M и хеш-функции h: U → . Дан элемент x, идея хеширования состоит в том, что мы хотим хранить его в A[h(x)]. Обратите внимание, что если бы U было маленьким (например, 2-символьные строки), то можно было бы просто сохранить x в A[x], как в блочной сортировке. Проблема в том, что U большое, поэтому нам нужна хеш-функция.
- Нам нужен метод для разрешения коллизий. Коллизия — это когда h(x) = h(y) для двух разных ключей x и y. В этой лекции мы будем обрабатывать коллизии, определяя каждый элемент A как связанный список. Есть ряд других методов, но для проблем, на которых мы сосредоточимся здесь, это самый подходящий. Этот метод называется методом цепочек. Чтобы вставить элемент, мы просто помещаем его в начало списка. Если h — хорошая хеш-функция, то мы надеемся, что списки будут небольшими.
Желательные свойства. Основные желательные свойства для хорошей схемы хеширования:
- Ключи хорошо рассредоточены, чтобы у нас не было слишком много коллизий, так как коллизии влияют на время выполнения поиска и удаления.
- M = O(N): в частности, мы бы хотели, чтобы наша схема достигла свойства (1) без необходимости, чтобы размер таблицы M был намного больше, чем число элементов N.
- Функция h должна быстро вычисляться. В нашем сегодняшнем анализе мы будем рассматривать время для вычисления h(x) как константу. Тем не менее, стоит помнить, что она не должна быть слишком сложной, потому что это влияет на общее время выполнения.
Доказательство: по принципу Дирихле. В частности, чтобы рассмотреть контрапозиции, если бы каждое местоположение имело не более N — 1 элементов U, хэширующих его, то U мог бы иметь размер не более M (N — 1).
Вот ключевая идея: давайте использовать рандомизацию в нашей конструкции h, по аналогии с рандомизированной быстрой сортировкой. (Само собой разумеется, h будет детерминированной функцией). Мы покажем, что для любой последовательности операций вставки и поиска (нам не нужно предполагать, что набор вставленных элементов S является случайным), если мы выберем h таким вероятностным способом, производительность h в этой последовательности будет хорошо в ожидании. Таким образом, это та же самая гарантия, что и в рандомизированной быстрой сортировке или ловушках. В частности, это идея универсального хеширования.
Как только мы разработаем эту идею, мы будем использовать ее для особенно приятного приложения под названием «идеальное хеширование».
4. Универсальное хеширование
Определение 1. Рандомизированный алгоритм H для построения хеш-функций h: U →
универсален, если для всех x != y в U имеем
Мы также можем сказать, что множество H хеш-функций является универсальным семейством хеш-функций, если процедура «выбрать h ∈ H наугад» универсальна. (Здесь мы отождествляем множество функций с равномерным распределением по множеству.)
Теорема 2. Если H универсален, то для любого множества S ⊆ U размера N, для любого x ∈ U (например, который мы могли бы искать), если мы строим h случайным образом в соответствии с H, ожидаемое число коллизий между х и другими элементами в S не более N/M.
Доказательство: у каждого y ∈ S (y != x) есть не более 1 / M шанса столкновения с x по определению «универсального». Так,
- Пусть Cxy = 1, если x и y сталкиваются, и 0 в противном случае.
- Пусть Cx обозначает общее количество столкновений для x. Итак, Cx = Py∈S, y != x Cxy.
- Мы знаем, что E [Cxy] = Pr (x и y сталкиваются) ≤ 1 / M.
- Таким образом, по линейности ожидания E [Cx] = Py E [Cxy]
Следствие 3. Если H универсален, то для любой последовательности операций L вставки, поиска и удаления, в которых в системе одновременно может быть не более M элементов, ожидаемая общая стоимость L операций для случайного h ∈ H равна только O (L) (просмотр времени для вычисления h как константы).
Доказательство: для любой данной операции в последовательности ее ожидаемая стоимость постоянна по теореме 2, поэтому ожидаемая общая стоимость L операций равна O (L) по линейности ожидания.
Вопрос: можем ли мы на самом деле построить универсальную H? Если нет, то это все довольно бессмысленно. К счастью, ответ — да.
4.1. Создание универсального хеш-семейства: матричный метод
Допустим, ключи имеют длину u-бит. Скажем, размер таблицы M равен степени 2, поэтому индекс длиной b-битов с M = 2b.
Что мы сделаем, это выберем h в качестве случайной матрицы 0/1 b-by-u и определим h (x) = hx, где мы добавим mod 2. Эти матрицы короткие и толстые. Например:
Утверждение 4. Для x != y Prh [h (x) = h (y)] = 1 / M = 1 / 2b.
Доказательство: во-первых, что означает умножение h на x? Мы можем думать об этом как о добавлении некоторых из столбцов h (делая векторное сложение mod 2), где 1 бит в x указывает, какие из них добавить. (например, мы добавили 1-й и 3-й столбцы h выше)
Теперь возьмем произвольную пару ключей x, y такую, что x != y. Они должны где-то отличаться, так что, скажем, они различаются по i-й координате, а для конкретности скажем xi = 0 и yi = 1. Представьте, что сначала мы выбрали все h, кроме i-го столбца. По оставшимся выборкам i-го столбца h (x) является фиксированным. Однако каждая из 2b различных настроек i-го столбца дает различное значение h (y) (в частности, каждый раз, когда мы переворачиваем бит в этом столбце, мы переворачиваем соответствующий бит в h (y)). Таким образом, есть точно 1 / 2b шанс, что h (x) = h (y).
Существуют и другие методы построения универсальных хеш-семейств, основанных также на умножении простых чисел (см. Раздел 6.1).
Следующий вопрос, который мы рассмотрим: если мы исправим множество S, сможем ли мы найти хеш-функцию h такую, что все поиски будут иметь постоянное время? Ответ — да, и это приводит к теме идеального хеширования.
5. Идеальное хеширование
Мы говорим, что хеш-функция является идеальной для S, если все поиски происходят за O(1). Вот два способа построения идеальных хеш-функций для заданного множества S.
5.1 Метод 1: решение в пространстве O(N2)
Скажем, мы хотим иметь таблицу, размер которой квадратичен по размеру N нашего словаря S. Тогда вот простой метод построения идеальной хеш-функции. Пусть H универсален и M = N2. Тогда просто выберите случайный h из H и попробуйте! Утверждение состоит в том, что есть по крайней мере 50% шанс, что у нее не будет коллизий.
Утверждение 5. Если H универсален и M = N2, то Prh∼H (нет коллизий в S) ≥ 1/2.
• Сколько пар (x, y) есть в S? Ответ:
• Для каждой пары вероятность их столкновения составляет ≤ 1 / M по определению универсальности.
• Итак, Pr (существует коллизия) ≤ / M
Это как другая сторона «парадокса дня рождения». Если количество дней намного больше, чем количество людей в квадрате, то есть разумный шанс, что ни у одной пары не будет одинакового дня рождения.
Итак, мы просто выбираем случайную h из H, и если возникают какие-либо коллизии, мы просто выбираем новую h. В среднем нам нужно будет сделать это только дважды. Теперь, что если мы хотим использовать только пространство O(N)?
5.2 Метод 2: решение в пространстве O(N)
Вопрос о том, можно ли достичь идеального хеширования в пространстве O(N), был в течение некоторого времени открытым: «Должны ли таблицы быть отсортированы?». То есть для фиксированного набора можно получить постоянное время поиска только с линейным пространством? Была серия все более и более сложных попыток, пока, наконец, она не была решена с использованием хорошей идеи универсальных хеш-функций в двухуровневой схеме.
Способ заключается в следующем. Сначала мы будем хэшировать в таблицу размера N, используя универсальное хеширование. Это приведет к некоторым коллизиям (если только нам не повезет). Однако затем мы перехешируем каждую корзину, используя метод 1, возводя в квадрат размер корзины, чтобы получить нулевые коллизии. Таким образом, схема состоит в том, что у нас есть хеш-функция первого уровня h и таблица A первого уровня, а затем N хеш-функций второго уровня h1,…, hN и N таблицы второго уровня A1,…, А.Н… Чтобы найти элемент x, мы сначала вычисляем i = h (x), а затем находим элемент в Ai [hi (x)]. (Если бы вы делали это на практике, вы могли бы установить флаг так, чтобы вы делали второй шаг, только если на самом деле были коллизии с индексом i, а в противном случае просто помещали бы сам x в A [i], но давайте не будем об этом беспокоиться здесь .)
Скажем, хеш-функция h хеширует n элементов S в местоположение i. Мы уже доказывали (анализируя метод 1), что мы можем найти h1,…, hN, так что общее пространство, используемое во вторичных таблицах, равно Pi (ni) 2. Осталось показать, что мы можем найти функцию первого уровня h такую, что Pi (ni) 2 = O (N). На самом деле, мы покажем следующее:
Теорема 6. Если мы выберем начальную точку h из универсального множества H, то
Теперь, хитрый трюк заключается в том, что один из способов подсчитать это количество — подсчитать количество упорядоченных пар, у которых возникает коллизия, включая коллизии с самим собой. Например, если корзина имеет , то у d возникнет коллизия с каждым из , у e возникнет коллизия с каждым из , и у f возникнет коллизия с каждым из , поэтому мы получаем 9. Итак, мы имеем:
6. Дальнейшее обсуждение
6.1 Еще один метод универсального хеширования
Вот еще один метод построения универсальных хеш-функций, который немного более эффективен, чем матричный метод, приведенный ранее.
В матричном методе мы рассматривали ключ как вектор битов. В этом методе вместо этого мы будем рассматривать ключ x как вектор целых чисел [x1, x2,…, xk] с единственным требованием, чтобы каждый xi находился в диапазоне . Например, если мы хешируем строки длиной k, то xi может быть i-м символом (если размер нашей таблицы не менее 256) или i-й парой символов (если размер нашей таблицы не менее 65536). Кроме того, мы будем требовать, чтобы размер нашей таблицы M был простым числом. Чтобы выбрать хеш-функцию h, мы выберем k случайных чисел r1, r2,…, рк из и определить:
Доказательство того, что этот метод универсален, строится точно так же, как доказательство матричного метода. Пусть x и y два разных ключа. Мы хотим показать, что Prh (h (x) = h (y)) ≤ 1 / M. Поскольку x != y, должен быть случай, когда существует некоторый индекс i такой, что xi != yi. Теперь представьте, что сначала вы выбрали все случайные числа rj для j != i. Пусть h ′ (x) = Pj6 = i rjxj. Итак, выбрав ri, мы получим h (x) = h ′ (x) + rixi. Это означает, что у нас возникает коллизия между x и y именно тогда, когда
Поскольку M — простое, деление на ненулевое значение mod M является допустимым (каждое целое число от 1 до M −1 имеет мультипликативный обратный по модулю M), что означает, что существует ровно одно значение ri по модулю M, для которого выполняется приведенное выше уравнение истина, а именно ri = (h ′ (y) — h ′ (x)) / (xi — yi) mod M. Таким образом, вероятность этого происшествия равна точно 1 / M.
6.2 Другое использование хеширования
Предположим, у нас есть длинная последовательность элементов, и мы хотим увидеть, сколько разных элементов находятся в списке. Есть ли хороший способ сделать это?
Одним из способов является создать хеш-таблицу, а затем сделать один проход по последовательности, сделав для каждого элемента поиск и затем вставку, если его еще нет в таблице. Количество отдельных элементов — это просто количество вставок.
А теперь, что если список действительно огромен и у нас нет места для его хранения, но нам подойдёт приблизительный ответ. Например, представьте, что мы являемся маршрутизатором и наблюдаем, как проходит много пакетов, и мы хотим (приблизительно) увидеть, сколько существует различных IP-адресов источника.
Вот хорошая идея: скажем, у нас есть хеш-функция h, которая ведет себя как случайная функция, и давайте представим, что h (x) — действительное число от 0 до 1. Одна вещь, которую мы можем сделать, это просто отслеживать минимальный хеш стоимость произведена до сих пор (поэтому у нас не будет таблицы вообще). Например, если ключи 3,10,3,3,12,10,12 и h (3) = 0,4, h (10) = 0,2, h (12) = 0,7, то мы получим 0,2.
Дело в том, что если мы выберем N случайных чисел в [0, 1], ожидаемое значение минимума будет 1 / (N + 1). Кроме того, есть хороший шанс, что он довольно близок (мы можем улучшить нашу оценку, запустив несколько хеш-функций и взяв медиану минимумов).
Вопрос: зачем использовать хеш-функцию, а не просто выбирать случайное число каждый раз? Это потому, что мы заботимся о количестве различных элементов, а не только об общем количестве элементов (эта проблема намного проще: просто используйте счетчик. ).
Что такое и с какой целью необходимо использовать хэширование? Основные виды хэширования.
Читайте также: