Что такое хэш функция
Криптографические хэш-функции распространены очень широко. Они используются для хранения паролей при аутентификации, для защиты данных в системах проверки файлов, для обнаружения вредоносного программного обеспечения, для кодирования информации в блокчейне (блок — основной примитив, обрабатываемый Биткойном и Эфириумом). В этой статье пойдет разговор об алгоритмах хеширования: что это, какие типы бывают, какими свойствами обладают.
В наши дни существует много криптографических алгоритмов. Они бывают разные и отличаются по сложности, разрядности, криптографической надежности, особенностям работы. Алгоритмы хеширования — идея не новая. Они появилась более полувека назад, причем за много лет с принципиальной точки зрения мало что изменилось. Но в результате своего развития хеширование данных приобрело много новых свойств, поэтому его применение в сфере информационных технологий стало уже повсеместным.
Что такое хеш (хэш, hash)?
Хеш или хэш — это криптографическая функция хеширования (function), которую обычно называют просто хэшем. Хеш-функция представляет собой математический алгоритм, который может преобразовать произвольный массив данных в строку фиксированной длины, состоящую из цифр и букв.
Основная идея используемых в данном случае функций — применение детерминированного алгоритма. Речь идет об алгоритмическом процессе, выдающем уникальный и предопределенный результат при получении входных данных. То есть при приеме одних и тех же входных данных будет создаваться та же самая строка фиксированной длины (использование одинакового ввода каждый раз приводит к одинаковому результату). Детерминизм — важное свойство этого алгоритма. И если во входных данных изменить хотя бы один символ, будет создан совершенно другой хэш.
Убедиться в этом можно на любом онлайн-генераторе. Набрав слово «Otus» и воспользовавшись алгоритмом sha1 (Secure Hashing Algorithm), мы получим хеш 7576750f9d76fab50762b5987739c18d99d2aff7. При изменении любой буквы изменится и результат, причем изменится полностью. Мало того, если просто поменять регистр хотя бы одной буквы, итог тоже будет совершенно иным: если написать «otus», алгоритм хэш-функции отработает со следующим результатом: 1bbd70dc1b6fc84e5617ca8703c72c744b3b4fc1. Хотя общие моменты все же есть: строка всегда состоит из сорока символов.
В предыдущем примере речь шла о применении хэш-алгоритма для слова из 4 букв. Но с тем же успехом можно вставить слово из 1000 букв — все равно после обработки данных на выходе получится значение из 40 символов. Аналогичная ситуация будет и при обработке полного собрания сочинений Льва Толстого.
Криптостойкость функций хеширования
Говоря о криптостойкости, предполагают выполнение ряда требований. То есть хороший алгоритм обладает несколькими свойствами: — при изменении одного бита во входных данных, должно наблюдаться изменение всего хэша; — алгоритм должен быть устойчив к коллизиям; — алгоритм должен быть устойчив к восстановлению хешируемых данных, то есть должна обеспечиваться высокая сложность нахождения прообраза, а вычисление хэша не должно быть простым.
Проблемы хэшей
Одна из проблем криптографических функций хеширования — неизбежность коллизий. Раз речь идет о строке фиксированной длины, значит, существует вероятность, что для каждого ввода возможно наличие и других входов, способных привести к тому же самому хешу. В результате хакер может создать коллизию, позволяющую передать вредоносные данные под видом правильного хэша.
Цель хороших криптографических функций — максимально усложнить вероятность нахождения способов генерации входных данных, хешируемых с одинаковым значением. Как уже было сказано ранее, вычисление хэша не должно быть простым, а сам алгоритм должен быть устойчив к «атакам нахождения прообраза». Необходимо, чтобы на практике было чрезвычайно сложно (а лучше — невозможно) вычислить обратные детерминированные шаги, которые предприняты для воспроизведения созданного хешем значения.
Если S = hash (x), то, в идеале, нахождение x должно быть практически невозможным.
Алгоритм MD5 и его подверженность взлому
Атака дня рождения
Если поместить 23 человека в одну комнату, можно дать 50%-ную вероятность того, что у двух человек день рождения будет в один и тот же день. Если же количество людей довести до 70-ти, вероятность совпадения по дню рождения приблизится к 99,9 %. Есть и другая интерпретация: если голубям дать возможность сесть в коробки, при условии, что число коробок меньше числа голубей, окажется, что хотя бы в одной из коробок находится более одного голубя.
Вывод прост: если есть фиксированные ограничения на выход, значит, есть и фиксированная степень перестановок, на которых существует возможность обнаружить коллизию.
Когда разговор идет о сопротивлении коллизиям, то алгоритм MD5 действительно очень слаб. Настолько слаб, что даже бытовой Pentium 2,4 ГГц сможет вычислить искусственные хеш-коллизии, затратив на это чуть более нескольких секунд. Всё это в ранние годы стало причиной утечки большого количества предварительных MD5-прообразов.
SHA1, SHA2, SHA3
Secure Hashing Algorithm (SHA1) — алгоритм, созданный Агентством национальной безопасности (NSA). Он создает 160-битные выходные данные фиксированной длины. На деле SHA1 лишь улучшил MD5 и увеличил длину вывода, а также увеличил число однонаправленных операций и их сложность. Однако каких-нибудь фундаментальных улучшений не произошло, особенно когда разговор шел о противодействии более мощным вычислительным машинам. Со временем появилась альтернатива — SHA2, а потом и SHA3. Последний алгоритм уже принципиально отличается по архитектуре и является частью большой схемы алгоритмов хеширования (известен как KECCAK — «Кетч-Ак»). Несмотря на схожесть названия, SHA3 имеет другой внутренний механизм, в котором используются случайные перестановки при обработке данных — «Впитывание» и «Выжимание» (конструкция «губки»).
Что в будущем?
Вне зависимости от того, какие технологии шифрования и криптографические новинки будут использоваться в этом направлении, все сводится к решению одной из двух задач: 1) увеличению сложности внутренних операций хэширования; 2) увеличению длины hash-выхода данных с расчетом на то, что вычислительные мощности атакующих не смогут эффективно вычислять коллизию.
И, несмотря на появление в будущем квантовых компьютеров, специалисты уверены, что правильные инструменты (то же хэширование) способны выдержать испытания временем, ведь ни что не стоит на месте. Дело в том, что с увеличением вычислительных мощностей снижается математическая формализация структуры внутренних алгоритмических хэш-конструкций. А квантовые вычисления наиболее эффективны лишь в отношении к вещам, имеющим строгую математическую структуру.
Как обычные, так и криптографические хэш-функции являются детерминированными. Быть детерминированным означает, что до тех пор, пока входные данные не изменяются, алгоритм хеширования всегда будет выдавать один и тот же результат (также известный как дайджест или хэш).
Алгоритмы хеширования в криптовалютах разработаны таким образом, что их функция работает в одностороннем порядке, это означает, что данные не могут быть возвращены в обратном порядке без вложения большого количества времени и ресурсов для осуществления вычислений. Другими словами, довольно легко создать выход из входных данных, но относительно трудно осуществить процесс в обратном направлении (сгенерировать вывод на основе входных данных). Чем сложнее найти входное значение, тем более безопасным считается алгоритм хеширования.
Как работает хэш-функция?
Различные виды хэш-функций производят вывод разной величины, но возможный размер данных на выходе для каждого из алгоритмов хеширования всегда является постоянным. Например, алгоритм SHA-256 может производить вывод исключительно в формате 256-бит, в то время как SHA-1 всегда генерирует 160-битный дайджест.
Чтобы проиллюстрировать это, давайте пропустим слова “Binance“ и “binance” через алгоритм хеширования SHA-256 (тот, который используется в биткоин).
Результат (256 бит)
Обратите внимание, что незначительное изменение (регистр первой буквы) привело к совершенно другому значению хэша. Поскольку мы используем SHA-256, данные на выходе всегда будут иметь фиксированный размер в 256 бит (или 64 символа), независимо от величины ввода. Помимо этого, не имеет значения какое количество раз мы пропустим эти два слова через алгоритм, два выхода не будут видоизменяться, поскольку они являются постоянными.
Таким же образом, если мы пропустим одни и те же входные данные с помощью алгоритма хеширования SHA-1, мы получим следующие результаты:
Результат (160 бит)
Стоит отметить, что акроним SHA расшифровывается как Secure Hash Algorithms (безопасный алгоритм хеширования). Он относится к набору криптографических хэш-функций, который включает такие алгоритмы как SHA-0 и SHA-1 вместе с группами SHA-2 и SHA-3. SHA-256 является частью группы SHA-2, наряду с SHA-512 и другими аналогами. В настоящее время, только группы SHA-2 и SHA-3 считаются безопасными.
Почему это имеет значение?
Хеширование демонстрирует весь свой потенциал при работе с огромным количеством информации. Например, можно пропустить большой файл или набор данных через хэш-функцию, а затем использовать вывод для быстрой проверки точности и целостности данных. Это возможно благодаря детерминированной природе хэш-функций: вход всегда будет приводить к упрощенному сжатому выходу (хэшу). Такой метод устраняет необходимость хранить и запоминать большие объемы данных.
Хеширование является в особенности полезным в отношении технологии блокчейн. В блокчейне биткоина осуществляется несколько операций, которые включают себя хеширование, большая часть которого заключается в майнинге. По факту, практически все криптовалютные протоколы полагаются на хеширование для связывания и сжатия групп транзакций в блоки, а также для создания криптографической взаимосвязи и эффективного построения цепочки из блоков.
Криптографические хэш-функции
Опять же обращаем ваше внимание на то, что хэш-функция, которая использует криптографические методы, может быть определена как криптографическая хэш-функция. Для того, чтобы ее взломать потребуется бесчисленное множество попыток грубого подбора чисел. Чтобы реверсировать криптографическую хэш-функцию, потребуется подбирать входные данные методом проб и ошибок, пока не будет получен соответствующий вывод. Тем не менее, существует возможность того, что разные входы будут производить одинаковый вывод, в таком случае возникает коллизия.
С технической точки зрения, криптографическая хэш-функция должна соответствовать трем свойствам, чтобы считаться безопасной. Мы можем описать их как: устойчивость к коллизии, и устойчивость к поиску первого и второго прообраза.
Прежде чем начать разбирать каждое свойство, обобщим их логику в трех коротких предложениях.
Устойчивость к коллизии: невозможно найти два разных входа, которые производят хэш, аналогичный выводу.
Устойчивость к поиску первого прообраза: отсутствие способа или алгоритма обратного восстановления хэш-функцию (нахождение входа по заданному выходу).
Устойчивость к поиску второго прообраза: невозможно найти любой второй вход, который бы пересекался с первым.
Устойчивость к коллизии
Как упоминалось ранее, коллизия происходит, когда разные входные данные производят одинаковый хэш. Таким образом, хэш-функция считается устойчивой к коллизиям до тех пор, пока кто-либо не обнаружит коллизию. Обратите внимание, что коллизии всегда будут существовать для любой из хэш-функций, в связи с бесконечным количеством входных данных и ограниченным количеством выводов.
Таким образом, хэш-функция устойчива к коллизии, когда вероятность ее обнаружения настолько мала, что для этого потребуются миллионы лет вычислений. По этой причине, несмотря на то, что не существует хэш-функций без коллизий, некоторые из них на столько сильные, что могут считаться устойчивыми (например, SHA-256).
Среди различных алгоритмов SHA группы SHA-0 и SHA-1 больше не являются безопасными, поскольку в них были обнаружены коллизии. В настоящее время только группы SHA-2 и SHA-3 считаются самыми безопасными и устойчивыми к коллизиям.Устойчивость к поиску первого прообраза
Данное свойство тесно взаимосвязано с концепцией односторонних функций. Хэш-функция считается устойчивой к поиску первого прообраза, до тех пор, пока существует очень низкая вероятность того, что кто-то сможет найти вход, с помощью которого можно будет сгенерировать определенный вывод.
Обратите внимание, что это свойство отличается от предыдущего, поскольку злоумышленнику потребуется угадывать входные данные, опираясь на определенный вывод. Такой вид коллизии происходит, когда кто-то находит два разных входа, которые производят один и тот же код на выходе, не придавая значения входным данным, которые для этого использовались.
Устойчивость к поиску второго прообраза
Для упрощения вашего понимания, можно сказать, что данный вид устойчивости находится где-то между двумя другими свойствами. Атака нахождения второго прообраза заключается в нахождении определенного входа, с помощью которого можно сгенерировать вывод, который изначально образовывался посредством других входных данных, которые были заведомо известны.
Другими словами, атака нахождения второго прообраза включает в себя обнаружение коллизии, но вместо поиска двух случайных входов, которые генерируют один и тот же хэш, атака нацелена на поиск входных данных, с помощью которых можно воссоздать хэш, который изначально был сгенерирован с помощью другого входа.
Следовательно, любая хэш-функция, устойчивая к коллизиям, также устойчива и к подобным атакам, поскольку последняя всегда подразумевает коллизию. Тем не менее, все еще остается возможность для осуществления атаки нахождения первого прообраза на функцию устойчивую к коллизиям, поскольку это предполагает поиск одних входных данных посредством одного вывода.
Майнинг
В майнинге присутствует множество этапов, которые осуществляются с помощью хэш-функций, они включают в себя проверку баланса, связывание входов и выходов транзакций и хеширование всех операций в блоке для формирования дерева Меркла. Но одна из основных причин, по которой блокчейн биткоина является безопасным, заключается в том, что майнеры должны выполнить как можно большее количество операций связанных с хешированием, чтобы в конечном итоге найти правильное решение для следующего блока. Майнер должен пытаться подобрать несколько разных входных данных при создании хэша для своего блока-кандидата. Проверить блок можно будет только в том случае, если правильно сгенерирован вывод в виде хэша начинается с определенного количества нулей. Количество нулей определяет сложность майнинга и она меняется в зависимости от хешрейта сети.В этом случае, хешрейт представляет собой количество мощности вашего компьютера, которое вы инвестируете в майнинг биткоинов. Если хешрейт начинает увеличиваться, протокол биткоина автоматически отрегулирует сложность майнинга так, чтобы среднее время необходимое для добычи блока составляло не более 10 минут. Если несколько майнеров примут решение прекратить майнинг, что приведет к значительному снижению хешрейта, сложность добычи будет скорректирована таким образом, чтобы временно облегчить вычислительную работу (до тех пор, пока среднее время формирования блока не вернется к 10 минутам).
Обратите внимание, что майнерам не нужно искать коллизии, в связи с некоторым количеством хэшей, которые они могут генерировать в качестве валидного выхода (начинающегося с определенного количества нулей). Таким образом, существует несколько возможных решений для определенного блока и майнеры должны найти только одно из них, в соответствии с порогом, который определяется сложностью майнинга.
Поскольку майнинг биткоина является столь затратной задачей, у майнеров нет причин обманывать систему, так как это приведет к значительным финансовым убыткам. Соответственно, чем больше майнеров присоединяется к блокчейну, тем больше и сильнее он становится.
Заключение
Нет сомнений в том, что хэш-функции являются одним из основных инструментов информатики, особенно при работе с огромными объемами данных. В сочетании с криптографией, алгоритмы хеширования могут быть весьма универсальными, предлагая безопасность и множество способов аутентификации. Таким образом, криптографические хеш-функции жизненно важны практически для всех криптовалютных сетей, поэтому понимание их свойств и механизмов работы, безусловно полезно для всех, кто интересуется технологией блокчейн.
Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, защиту файлов и даже обнаружение зловредного ПО. Как они работают и где применяются?
Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, проверку целостности данных, защиту файлов и даже обнаружение зловредного ПО. Существует масса алгоритмов хеширования, отличающихся криптостойкостью, сложностью, разрядностью и другими свойствами. Считается, что идея хеширования принадлежит сотруднику IBM, появилась около 50 лет назад и с тех пор не претерпела принципиальных изменений. Зато в наши дни хеширование обрело массу новых свойств и используется в очень многих областях информационных технологий.
Что такое хеш?
Если коротко, то криптографическая хеш-функция, чаще называемая просто хешем, — это математический алгоритм, преобразовывающий произвольный массив данных в состоящую из букв и цифр строку фиксированной длины. Причем при условии использования того же типа хеша длина эта будет оставаться неизменной, вне зависимости от объема вводных данных. Криптостойкой хеш-функция может быть только в том случае, если выполняются главные требования: стойкость к восстановлению хешируемых данных и стойкость к коллизиям, то есть образованию из двух разных массивов данных двух одинаковых значений хеша. Интересно, что под данные требования формально не подпадает ни один из существующих алгоритмов, поскольку нахождение обратного хешу значения — вопрос лишь вычислительных мощностей. По факту же в случае с некоторыми особо продвинутыми алгоритмами этот процесс может занимать чудовищно много времени.
Как работает хеш?
Например, мое имя — Brian — после преобразования хеш-функцией SHA-1 (одной из самых распространенных наряду с MD5 и SHA-2) при помощи онлайн-генератора будет выглядеть так: 75c450c3f963befb912ee79f0b63e563652780f0. Как вам скажет, наверное, любой другой Брайан, данное имя нередко пишут с ошибкой, что в итоге превращает его в слово brain (мозг). Это настолько частая опечатка, что однажды я даже получил настоящие водительские права, на которых вместо моего имени красовалось Brain Donohue. Впрочем, это уже другая история. Так вот, если снова воспользоваться алгоритмом SHA-1, то слово Brain трансформируется в строку 97fb724268c2de1e6432d3816239463a6aaf8450. Как видите, результаты значительно отличаются друг от друга, даже несмотря на то, что разница между моим именем и названием органа центральной нервной системы заключается лишь в последовательности написания двух гласных. Более того, если я преобразую тем же алгоритмом собственное имя, но написанное уже со строчной буквы, то результат все равно не будет иметь ничего общего с двумя предыдущими: 760e7dab2836853c63805033e514668301fa9c47.
Впрочем, кое-что общее у них все же есть: каждая строка имеет длину ровно 40 символов. Казалось бы, ничего удивительного, ведь все введенные мною слова также имели одинаковую длину — 5 букв. Однако если вы захешируете весь предыдущий абзац целиком, то все равно получите последовательность, состоящую ровно из 40 символов: c5e7346089419bb4ab47aaa61ef3755d122826e2. То есть 1128 символов, включая пробелы, были ужаты до строки той же длины, что и пятибуквенное слово. То же самое произойдет даже с полным собранием сочинений Уильяма Шекспира: на выходе вы получите строку из 40 букв и цифр. При всем этом не может существовать двух разных массивов данных, которые преобразовывались бы в одинаковый хеш.
Вот как это выглядит, если изобразить все вышесказанное в виде схемы:
Для чего используется хеш?
Отличный вопрос. Однако ответ не так прост, поскольку криптохеши используются для огромного количества вещей.
Для нас с вами, простых пользователей, наиболее распространенная область применения хеширования — хранение паролей. К примеру, если вы забыли пароль к какому-либо онлайн-сервису, скорее всего, придется воспользоваться функцией восстановления пароля. В этом случае вы, впрочем, не получите свой старый пароль, поскольку онлайн-сервис на самом деле не хранит пользовательские пароли в виде обычного текста. Вместо этого он хранит их в виде хеш-значений. То есть даже сам сервис не может знать, как в действительности выглядит ваш пароль. Исключение составляют только те случаи, когда пароль очень прост и его хеш-значение широко известно в кругах взломщиков. Таким образом, если вы, воспользовавшись функцией восстановления, вдруг получили старый пароль в открытом виде, то можете быть уверены: используемый вами сервис не хеширует пользовательские пароли, что очень плохо.
Еще один пример, покруче. Не так давно по тематическим сайтам прокатилась новость о том, что популярный облачный сервис Dropbox заблокировал одного из своих пользователей за распространение контента, защищенного авторскими правами. Герой истории тут же написал об этом в твиттере, запустив волну негодования среди пользователей сервиса, ринувшихся обвинять Dropbox в том, что он якобы позволяет себе просматривать содержимое клиентских аккаунтов, хотя не имеет права этого делать.
Впрочем, необходимости в этом все равно не было. Дело в том, что владелец защищенного копирайтом контента имел на руках хеш-коды определенных аудио- и видеофайлов, запрещенных к распространению, и занес их в список блокируемых хешей. Когда пользователь предпринял попытку незаконно распространить некий контент, автоматические сканеры Dropbox засекли файлы, чьи хеши оказались в пресловутом списке, и заблокировали возможность их распространения.
Как при помощи хеша ловить вирусы?
Криптографические хеш-функции также могут использоваться для защиты от фальсификации передаваемой информации. Иными словами, вы можете удостовериться в том, что файл по пути куда-либо не претерпел никаких изменений, сравнив его хеши, снятые непосредственно до отправки и сразу после получения. Если данные были изменены даже всего на 1 байт, хеш-коды будут отличаться, как мы уже убедились в самом начале статьи. Недостаток такого подхода лишь в том, что криптографическое хеширование требует больше вычислительных мощностей или времени на вычисление, чем алгоритмы с отсутствием криптостойкости. Зато они в разы надежнее.
Кстати, в повседневной жизни мы, сами того не подозревая, иногда пользуемся простейшими хешами. Например, представьте, что вы совершаете переезд и упаковали все вещи по коробкам и ящикам. Погрузив их в грузовик, вы фиксируете количество багажных мест (то есть, по сути, количество коробок) и запоминаете это значение. По окончании выгрузки на новом месте, вместо того чтобы проверять наличие каждой коробки по списку, достаточно будет просто пересчитать их и сравнить получившееся значение с тем, что вы запомнили раньше. Если значения совпали, значит, ни одна коробка не потерялась.
В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше , чем вариантов входного массива; существует множество массивов с разным содержимым, но дающих одинаковые хеш-коды — так называемые коллизии . Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.
Существует множество алгоритмов хеширования с различными свойствами (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC.
История
Дональд Кнут относит первую систематическую идею хеширования к сотруднику IBM Хансу Петеру Луну (нем. Hans Peter Luhn ), предложившему хеш-кодирование в январе 1953 года.
В 1956 году Арнольд Думи (англ. Arnold Dumey ) в своей работе «Computers and automation» первым представил концепцию хеширования таковой, какой её знает большинство программистов сейчас. Думи рассматривал хеширование, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адреса остаток деления на простое число. [1]
Первой серьёзной работой, связанной с поиском в больших файлах, была статья Уэсли Питерсона (англ. W. Wesley Peterson ) в IBM Journal of Research and Development 1957 года, в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца (нем. Werner Buchholz ), в которой проведено обширное исследование хеш-функций. В течение нескольких последующих лет хеширование широко использовалось, однако не было опубликовано никаких значимых работ.
В 1967 году хеширование в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис (англ. Robert Morris ) опубликовал в Communications of the ACM большой обзор по хешированию, эта работа считается ключевой публикацией, вводящей понятие о хешировании в научный оборот и закрепившей ранее применявшийся только в жаргоне специалистов термин «хеш».
До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Ершова использовалось слово «расстановка», а для коллизий использовался термин "конфликт" (Ершов использовал «расстановку» с 1956 года, в русскоязычном издании книги Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка»). Предлагалось также назвать метод русским словом «окрошка». Однако ни один из этих вариантов не прижился, и в русскоязычной литературе используется преимущественно термин «хеширование». [3]
Виды хеш-функций
Хорошая хеш-функция должна удовлетворять двум свойствам:
- Быстро вычисляться;
- Минимизировать количество коллизий
Предположим, для определённости, что количество ключей , а хеш-функция имеет не более различных значений:
В качестве примера «плохой» хеш-функции можно привести функцию с , которая десятизначному натуральном числу сопоставляет три цифры выбранные из середины двадцатизначного квадрата числа . Казалось бы значения хеш-кодов должны равномерно распределиться между «000» и «999», но для реальных данных такой метод подходит лишь в том случае, если ключи не имеют большого количества нулей слева или справа. [3]
Однако существует несколько более простых и надежных методов, на которых базируются многие хеш-функции.
Хеш-функции, основанные на делении
Первый метод заключается в том, что мы используем в качестве хеша остаток от деления на , где - это количество всех возможных хешей:
При этом очевидно, что при чётном значение функции будет чётным, при чётном , и нечётным — при нечётном, что может привести к значительному смещению данных в файлах. Также не следует использовать в качестве степень основания счисления компьютера, так как хеш-код будет зависеть только от нескольких цифр числа , расположенных справа, что приведет к большому количеству коллизий. На практике обычно выбирают простое — в большинстве случаев этот выбор вполне удовлетворителен.
Ещё следует сказать о методе хеширования, основанном на делении на полином по модулю два. В данном методе также должна являться степенью двойки, а бинарные ключи (k_. k_" />
) представляются в виде полиномов. В этом случае в качестве хеш-кода берутся значения коэффциентов полинома, полученного как остаток от деления на заранее выбранный полином степени :
При правильном выборе такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами. [3]
Мультипликативная схема хеширования
Второй метод состоит в выборе некоторой целой константы , взаимно простой с , где — количество представимых машинным словом значений (в компьютерах IBM PC " />
). Тогда можем взять хеш-функцию вида:
В этом случае, на компьютере с двоичной системой счисления, является степенью двойки и будет состоять из старших битов правой половины произведения .
Среди преимуществ этих двух методов стоит отметь, что они выгодно используют то, что реальные ключи неслучайны, например в том случае если ключи представляют собой арифметическую прогрессию (допустим последовательность имён «ИМЯ1», «ИМЯ2», «ИМЯ3»). Мультипликативный метод отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшает количество коллизий по сравнению со случайной ситуацией. [3]
Одной из вариаций данного метода является хеширование Фибоначчи, основанное на свойствах золотого сечения. В качестве здесь выбирается ближайшее к *w" />
целое число, взаимно простое с
Хеширование строк переменной длины
Вышеизложенные методы применимы и в том случае, если нам необходимо рассматривать ключи, состоящие из нескольких слов или ключи переменной длины. Например можно скомбинировать слова в одно при помощи сложения по модулю или операции «исключающее или». Одним из алгоритмов, работающих по такому принципу является хеш-функция Пирсона.
Алгоритм можно описать следующим псевдокодом, который получает на вход строку и использует таблицу перестановок
Среди преимуществ алгоритма следует отметить:
- Простоту вычисления;
- Не существует таких входных данных, для которых вероятность коллизии наибольшая;
- Возможность модификации в идеальную хеш-функцию.
В качестве альтернативного способа хеширования ключей, состоящих из символов (x_. x_" />
), можно предложить вычисление
Идеальное хеширование
Идеальной хеш-функцией (англ. Perfect hash function ) называется такая функция, которая отображает каждый ключ из набора в множество целых чисел без коллизий. В математических терминах это инъективное отображение.
Описание
Идеальное хеширование применяется в тех случаях, когда мы хотим присвоить уникальный идентификатор ключу, без сохранения какой-либо информации о ключе. Одним из наиболее очевидных примеров использования идеального (или скорее k-идеального) хеширования является ситуация, когда мы располагаем небольшой быстрой памятью, где размещаем значения хешей, связанных с данными хранящимися в большой, но медленной памяти. Причем размер блока можно выбрать таким, что необходимые нам данные, хранящиеся в медленной памяти, будут получены за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, в тех случаях, когда представление графа не умещается в основной памяти.
Универсальное хеширование
Универсальным хешированием (англ. Universal hashing ) называется хеширование, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Использование универсального хеширования обычно обеспечивает низкое число коллизий. Универсальное хеширование имеет множество применений, например, в реализации хеш-таблиц и криптографии.
Описание
Предположим, что мы хотим отобразить ключи из пространства в числа . На входе алгоритм получает некоторый набор данных и размерностью , причем неизвестный заранее. Как правило целью хеширования является получение наименьшего числа коллизий, чего трудно добиться используя какую-то определенную хеш-функцию.
![H = \< h : U \to [m] \></p>
<p>В качестве решения такой проблемы можно выбирать функцию случайным образом из определенного набора, называемого универсальным семейством](http://upload.wikimedia.org/math/4/f/5/4f541cb630b1b1301c0aecfc337b0844.jpg)
.
Читайте также: