Криптографическая хеш-функция. Алгоритмы хэширования в задачах на строки

Что такое хеш? Хеш-функцией называется математическое преобразование информации в короткую, определенной длины строку.

Зачем это нужно? Анализ при помощи хеш-функций часто используют для контроля целостности важных файлов операционной системы, важных программ, важных данных. Контроль может производиться как по необходимости, так и на регулярной основе.

Как это делается? Вначале определяют, целостность каких файлов нужно контролировать. Для каждого файла производится вычисления значения его хеша по специальному алгоритму с сохранением результата. Через необходимое время производится аналогичный расчет и сравниваются результаты. Если значения отличаются, значит информация содержащаяся в файле была изменена.

Какими характеристиками должна обладать хеш-функция?

должна уметь выполнять преобразования данных произвольной длины в фиксированную;
должна иметь открытый алгоритм, чтобы можно было исследовать её криптостойкость;
должна быть односторонней, то есть не должно быть математической возможности по результату определить исходные данные;
должна «сопротивляться» коллизиям, то есть не должна выдавать одинаковых значений при разных входных данных;
не должна требовать больших вычислительных ресурсов;
при малейшем изменении входных данных результат должен существенно изменяться.

Какие популярные алгоритмы хеширования? В настоящее время используются следующие хеш-функции:

CRC – циклический избыточный код или контрольная сумма. Алгоритм весьма прост, имеет большое количество вариаций в зависимости от необходимой выходной длины. Не является криптографическим!
MD 5 – очень популярный алгоритм. Как и его предыдущая версия MD 4 является криптографической функцией. Размер хеша 128 бит.
SHA -1 – также очень популярная криптографическаяфункция. Размер хеша 160 бит.
ГОСТ Р 34.11-94 – российский криптографический стандарт вычисления хеш-функции. Размер хеша 256 бит.

Когда эти алгоритмы может использовать системный администратор? Часто при скачивании какого-либо контента, например программ с сайта производителя, музыки, фильмов или другой информации присутствует значение контрольных сумм, вычисленных по определенному алгоритму. Из соображений безопасности после скачивания необходимо провести самостоятельное вычисление хеш-функции и сравнить значение с тем, что указано на сайте или в приложении к файлу. Делали ли вы когда-нибудь такое?

Чем удобнее рассчитывать хеш? Сейчас существует большое количество подобных утилит как платных, так и свободных для использования. Мне лично понравилась HashTab . Во-первых, утилита при установке встраивается в виде вкладки в свойства файлов, во-вторых, позволяет выбирать большое количество алгоритмов хеширования, а в третьих является бесплатной для частного некоммерческого использования.

Что есть российского? Как было сказано выше в России есть стандарт хеширования ГОСТ Р 34.11-94, который повсеместно используется многими производителями средств защиты информации. Одним из таких средств является программа фиксации и контроля исходного состояния программного комплекса «ФИКС». Эта программа является средством контроля эффективности применения СЗИ.

ФИКС (версия 2.0.1) для Windows 9x/NT/2000/XP

Вычисление контрольных сумм заданных файлов по одному из 5 реализованных алгоритмов.
Фиксация и последующий контроль исходного состояния программного комплекса.
Сравнение версий программного комплекса.
Фиксация и контроль каталогов.
Контроль изменений в заданных файлах (каталогах).
Формирование отчетов в форматах TXT, HTML, SV.
Изделие имеет сертификат ФСТЭК по НДВ 3 № 913 до 01 июня 2013 г.

А как на счет ЭЦП? Результат вычисленияхеш-функции вместе с секретным ключом пользователя попадает на вход криптографического алгоритма, где и рассчитывается электронно-цифровая подпись. Строго говоря, хеш-функция не является частью алгоритма ЭЦП, но часто это делается специально, для того, чтобы исключить атаку с использованием открытого ключа.

В настоящее время многие приложения электронной коммерции позволяют хранить секретный ключ пользователя в закрытой области токена (ruToken , eToken ) без технической возможности извлечения его оттуда. Сам токен имеет весьма ограниченную область памяти, измеряемую в килобайтах. Для подписания документа нет никакой возможности передать документ в сам токен, а вот передать хеш документа в токен и на выходе получить ЭЦП очень просто.

Алгоритмы хэширования строк помогают решить очень много задач. Но у них есть большой недостаток: что чаще всего они не 100%-ны, поскольку есть множество строк, хэши которых совпадают. Другое дело, что в большинстве задач на это можно не обращать внимания, поскольку вероятность совпадения хэшей всё-таки очень мала.

Определение хэша и его вычисление

Один из лучших способов определить хэш-функцию от строки S следующий:

H(S) = S + S * P + S * P^2 + S * P^3 + ... + S[N] * P^N

где P - некоторое число.

Разумно выбирать для P простое число, примерно равное количеству символов во входном алфавите. Например, если строки предполаются состоящими только из маленьких латинских букв, то хорошим выбором будет P = 31. Если буквы могут быть и заглавными, и маленькими, то, например, можно P = 53.

Во всех кусках кода в этой статье будет использоваться P = 31.

Само значение хэша желательно хранить в самом большом числовом типе - int64, он же long long. Очевидно, что при длине строки порядка 20 символов уже будет происходить переполнение значение. Ключевой момент - что мы не обращаем внимание на эти переполнения, как бы беря хэш по модулю 2^64.

Пример вычисления хэша, если допустимы только маленькие латинские буквы:

Const int p = 31; long long hash = 0, p_pow = 1; for (size_t i=0; i

В большинстве задач имеет смысл сначала вычислить все нужные степени P в каком-либо массиве.

Пример задачи. Поиск одинаковых строк

Уже теперь мы в состоянии эффективно решить такую задачу. Дан список строк S, каждая длиной не более M символов. Допустим, требуется найти все повторяющиеся строки и разделить их на группы, чтобы в каждой группе были только одинаковые строки.

Обычной сортировкой строк мы бы получили алгоритм со сложностью O (N M log N), в то время как используя хэши, мы получим O (N M + N log N).

Алгоритм. Посчитаем хэш от каждой строки, и отсортируем строки по этому хэшу.

Vector s (n); // ... считывание строк... // считаем все степени p, допустим, до 10000 - максимальной длины строк const int p = 31; vector p_pow (10000); p_pow = 1; for (size_t i=1; i > hashes (n); for (int i=0; i

Хэш подстроки и его быстрое вычисление

Предположим, нам дана строка S, и даны индексы I и J. Требуется найти хэш от подстроки S.

По определению имеем:

H = S[I] + S * P + S * P^2 + ... + S[J] * P^(J-I)

H * P[I] = S[I] * P[I] + ... + S[J] * P[J], H * P[I] = H - H

Полученное свойство является очень важным.

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

Единственная возникающая проблема - это то, что нужно уметь делить на P[I]. На самом деле, это не так просто. Поскольку мы вычисляем хэш по модулю 2^64, то для деления на P[I] мы должны найти к нему обратный элемент в поле (например, с помощью Расширенного алгоритма Евклида), и выполнить умножение на этот обратный элемент.

Впрочем, есть и более простой путь. В большинстве случаев, вместо того чтобы делить хэши на степени P, можно, наоборот, умножать их на эти степени .

Допустим, даны два хэша: один умноженный на P[I], а другой - на P[J]. Если I < J, то умножим перый хэш на P, иначе же умножим второй хэш на P. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать.

Например, код, который вычисляет хэши всех префиксов, а затем за O (1) сравнивает две подстроки:

String s; int i1, i2, len; // входные данные // считаем все степени p const int p = 31; vector i2 && h1 == h2 * p_pow) cout << "equal"; else cout << "different";

Применение хэширования

Вот некоторые типичные применения хэширования:

Определение количества различных подстрок за O (N^2 log N) (см. ниже)
Определение количества палиндромов внутри строки

Определение количества различных подстрок

Пусть дана строка S длиной N, состоящая только из маленьких латинских букв. Требуется найти количество различных подстрок в этой строке.

Для решения переберём по очереди длину подстроки: L = 1 .. N.

Для каждого L мы построим массив хэшей подстрок длины L, причём приведём хэши к одной степени, и отсортируем этот массив. Количество различных элементов в этом массиве прибавляем к ответу.

Реализация:

String s; // входная строка int n = (int) s.length(); // считаем все степени p const int p = 31; vector p_pow (s.length()); p_pow = 1; for (size_t i=1; iH (s.length()); for (size_t i=0; i hs (n-l+1); for (int i=0; i

В самых различных отраслях информационных технологий находят свое применение хэш-функции. Они предназначены для того, чтобы, с одной стороны, значительно упростить обмен данными между пользователями и обработку файлов, используемых в тех или иных целях, с другой — оптимизировать алгоритмы обеспечения контроля доступа к соответствующим ресурсам. Хэш-функция — один из ключевых инструментов обеспечения парольной защиты данных, а также организации обмена документов, подписанных с помощью ЭЦП. Существует большое количество стандартов, посредством которых может осуществляться кэширование файлов. Многие из них разработаны российскими специалистами. В каких разновидностях могут быть представлены хэш-функции? Каковы основные механизмы их практического применения?

Что это такое?

Для начала исследуем понятие хэш-функции. Под данным термином принято понимать алгоритм преобразования некоторого объема информации в более короткую последовательность символов посредством математических методов. Практическую значимость хэш-функции можно проследить в самых разных областях. Так, их можно задействовать при проверке файлов и программ на предмет целостности. Также криптографические хеш-функции задействуются в алгоритмах шифрования.

Характеристики

Рассмотрим ключевые характеристики исследуемых алгоритмов. В числе таковых:

наличие внутренних алгоритмов преобразования данных исходной длины в более короткую последовательность символов;
открытость для криптографической проверки;
наличие алгоритмов, позволяющих надежно шифровать изначальные данные;
адаптированность к расшифровке при задействовании небольших вычислительных мощностей.

В числе иных важнейших свойств хэш-функции:

способность обрабатывать изначальные массивы данных произвольной длины;
формировать хешированные блоки фиксированной длины;
распределять значения функции на выходе равномерно.

Рассматриваемые алгоритмы также предполагают чувствительность к данным на входе на уровне 1 бита. То есть даже если, условно говоря, в исходном документе изменится хотя бы 1 буква, то хэш-функция будет выглядеть иначе.

Требования к хэш-функциям

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

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

Структура

Изучим то, какой может быть структура рассматриваемых функций. Как мы отметили выше, в числе главных требований к рассматриваемым алгоритмам — обеспечение однонаправленности шифрования. Человек, имеющий в распоряжении только хэш, практически не должен иметь возможности получить на его основе исходный документ.

В какой структуре может быть представлена используемая в подобных целях хеш-функция? Пример ее составления может быть таким: H (hash, то есть, хэш) = f (T (текст), H1), где H1 — алгоритм обработки текста T. Данная функция хеширует T таким образом, что без знания H1 открыть его как полноценный файл будет практически невозможно.

Использование хэш-функций на практике: скачивание файлов

Изучим теперь подробнее варианты использования хэш-функций на практике. Задействование соответствующих алгоритмов может применяться при написании скриптов скачивания файлов с интернет-серверов.

В большинстве случаев для каждого файла определяется некая контрольная сумма — это и есть хэш. Она должна быть одинаковой для объекта, располагающегося на сервере и скачанного на компьютер пользователя. Если это не так, то файл может не открыться либо запуститься не вполне корректно.

Хэш-функция и ЭЦП

Использование хэш-функций распространено при организации обмена документами, содержащими электронно-цифровую подпись. Хэшируется в данном случае подписываемый файл, для того чтобы его получатель мог удостовериться в том, что он подлинный. Хотя формально хэш-функция не входит в структуру электронного ключа, она может фиксироваться во флеш-памяти аппаратных средств, с помощью которых подписываются документы, таких как, например, eToken.

Электронная подпись представляет собой шифрование файла при задействовании открытого и закрытого ключей. То есть к исходному файлу прикрепляется зашифрованное с помощью закрытого ключа сообщение, а проверка ЭЦП осуществляется посредством открытого ключа. Если хэш-функция обоих документов совпадает — файл, находящийся у получателя, признается подлинным, а подпись отправителя распознается как верная.

Хеширование, как мы отметили выше, не является непосредственно компонентом ЭЦП, однако позволяет весьма эффективно оптимизировать алгоритмы задействования электронной подписи. Так, шифроваться может, собственно, только хэш, а не сам документ. В итоге скорость обработки файлов значительно возрастает, одновременно становится возможным обеспечивать более эффективные механизмы защиты ЭЦП, так как акцент в вычислительных операциях в этом случае будет ставиться не на обработке исходных данных, а на обеспечении криптографической стойкости подписи. Хэш-функция к тому же делает возможным подписывать самые разные типы данных, а не только текстовые.

Проверка паролей

Еще одна возможная область применения хеширования — организация алгоритмов проверки паролей, установленных для разграничения доступа к тем или иным файловым ресурсам. Каким образом при решении подобных задач могут быть задействованы те или иные виды хеш-функций? Очень просто.

Дело в том, что на большинстве серверов, доступ к которым подлежит разграничению, пароли хранятся в виде хэшированных значений. Это вполне логично — если бы пароли были представлены в исходном текстовом виде, хакеры, получившие доступ к ним, могли бы запросто читать секретные данные. В свою очередь, на основе хэш вычислить пароль непросто.

Каким образом осуществляется проверка доступа пользователя при задействовании рассматриваемых алгоритмов? Пароль, вводимый пользователем, сверяется с тем, что зафиксирован в хэш-функции, что хранится на сервере. Если значения текстовых блоков совпадают — пользователь получает необходимый доступ к ресурсам.

В качестве инструмента проверки паролей может быть задействована самая простая хэш-функция. Но на практике IT-специалисты чаще всего используют комплексные многоступенчатые криптографические алгоритмы. Как правило, они дополняются применением стандартов передачи данных по защищенному каналу — так, чтобы хакеры не смогли обнаружить либо вычислить пароль, передаваемый с компьютера пользователя на сервера — до того, как он будет сверяться с хешированными текстовыми блоками.

Коллизии хэш-функций

В теории хэш-функций предусмотрено такое явление, как коллизия. В чем его сущность? Коллизия хэш-функции — ситуация, при которой два разных файла имеют одинаковый хэш-код. Это возможно, если длина целевой последовательности символов будет небольшой. В этом случае вероятность совпадения хэша будет выше.

Для того чтобы избежать коллизии, рекомендуется, в частности, задействовать двойной алгоритм под названием "хеширование хеш-функции". Он предполагает формирование открытого и закрытого кода. Многие программисты при решении ответственных задач рекомендуют не применять хэш-функции в тех случаях, когда это необязательно и всегда тестировать соответствующие алгоритмы на предмет наилучшей совместимости с теми или иными ключами.

История появления

Основоположниками теории хэш-функций можно считать исследователей Картера, Вегмана, Симонсона, Биербрауера. В первых версиях соответствующие алгоритмы задействовались в качестве инструментария для формирования уникальных образов последовательностей символов произвольной длины с последующей целью их идентификации и проверки на предмет подлинности. В свою очередь, хэш, в соответствии с заданными критериями, должен был обладать длиной 30-512 бит. В качестве особенно полезного свойства соответствующих функций рассматривалась ее приспособленность для задействования в качестве ресурса быстрого поиска файлов, либо их сортировки.

Особенности алгоритма SHA

Применение хэш-функций, базирующихся на стандарте SHA, чаще всего осуществляется в области разработки средств цифровой подписи документов DSA. Как мы отметили выше, алгоритм SHA поддерживает хэш 160 бит (обеспечивая так называемый «дайджест» последовательности символов). Изначально рассматриваемый стандарт делит массив данных на блоки по 512 бит. При необходимости, если длина последнего блока не дотягивает до указанной цифры, структура файла дополняется 1 и необходимым количеством нулей. Также в конце соответствующего блока вписывается код, фиксирующий длину сообщения. Рассматриваемый алгоритм задействует 80 логических функций, посредством которых обрабатывается 3 слова, представленные в 32 разрядах. Также в стандарте SHA предусмотрено использование 4 констант.

Сравнение алгоритмов хеширования

Изучим то, как соотносятся свойства хэш-функций, относящихся к разным стандартам, на примере сопоставления характеристик российского стандарта ГОСТ Р 34.11-94 и американского SHA, который мы рассмотрели выше. Прежде всего, следует отметить то, что алгоритм, разработанный в РФ, предполагает осуществление 4 операций по шифрованию в расчете на 1 цикл. Это соответствует 128 раундам. В свою очередь, в течение 1 раунда при задействовании SHA предполагается вычисление порядка 20 команд, при том что всего раундов 80. Таким образом, использование SHA позволяет в течение 1 цикла обработать 512 бит исходных данных. В то время как российский стандарт способен осуществить операции за цикл в 256 бит данных.

Специфика новейшего российского алгоритма

Выше мы отметили, что стандарт ГОСТ Р 34.11-94 был заменен более новым — ГОСТ Р 34.11-2012 «Стрибог». Исследуем его специфику подробнее.

Посредством данного стандарта могут быть реализованы, как и в случае с алгоритмами, рассмотренными выше, криптографические хеш-функции. Можно отметить, что новейший российский стандарт поддерживает блок входных данных в объеме 512 бит. Основные преимущества ГОСТ Р 34.11-2012:

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

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

Специфика криптографических хэш-функций

Рассмотрим более подробно, каким образом исследуемые нами типы алгоритмов могут задействоваться в сфере криптографии. Ключевое требование к соответствующим функциям — стойкость к коллизиям, о которых мы сказали выше. То есть не должны формироваться повторяющиеся значения хеш-функции, если значения эти уже присутствуют в структуре соседствующего алгоритма. Прочим отмеченным выше критериям криптографические функции также должны соответствовать. Понятно, что всегда есть некая теоретическая возможность восстановления исходного файла на основе хэша, особенно если в доступе есть мощный вычислительный инструмент. Однако подобный сценарий предполагается свести к минимуму, благодаря надежным алгоритмам шифрования. Так, вычислить хэш-функцию будет очень сложно, если ее вычислительная стойкость соответствует формуле 2^{n/2}.

Другой важнейший критерий криптографического алгоритма — изменение хэша в случае корректировки изначального массива данных. Выше мы отметили, что стандарты шифрования должны обладать чувствительностью на уровне 1 бита. Так, данное свойство — ключевой фактор обеспечения надежной парольной защиты доступа к файлам.

Итеративные схемы

Изучим теперь то, каким образом могут быть выстроены криптографические алгоритмы хеширования. В числе самых распространенных схем решения данной задачи — задействование итеративной последовательной модели. Она основана на использовании так называемой сжимающей функции, при которой количество входных бит существенно больше, чем тех, что фиксируются на выходе.

Разумеется, сжимающая функция обязана соответствовать необходимым критериям криптостойкости. При интеративной схеме первая операция по обработке потока входных данных делится на блоки, размер которых исчисляется в битах. Соответствующий алгоритм также задействует временные переменные величиной в заданном количестве бит. В качестве первого значения задействуется общеизвестное число, в то время как последующие блоки данных объединяются со значением рассматриваемой функции на выходе. Значением хэша становятся выходные показатели бит для последней итерации, в которых учитывается весь входной поток, включая первое значение. Обеспечивается так называемый «лавинный эффект» хеширования.

Основная сложность, характеризующая реализуемое в виде итерационной схемы хеширование, — хэш-функции иногда сложно построить в том случае, если входной поток не является идентичным размеру блока, на который делится изначальный массив данных. Но в этом случае в стандарте хеширования могут быть прописаны алгоритмы, посредством которых исходный поток может быть расширен тем или иным образом.

В некоторых случаях в процессе обработки данных в рамках итерационной схемы могут быть задействованы так называемые многопроходные алгоритмы. Они предполагают формирование еще более интенсивного «лавинного эффекта». Подобный сценарий предполагает формирование повторных массивов данных, и только во вторую очередь идет расширение.

Блочный алгоритм

Сжимающая функция может быть также основана на блочном алгоритме, посредством которого осуществляется шифрование. Так, с целью повышения уровня безопасности можно задействовать блоки данных, что подлежат хешированию на текущей итерации, в качестве ключа, а результат операций, полученный в ходе выполнения сжимающей функции до этого — в качестве входа. В результате последняя итерация обеспечит выход алгоритма. Безопасность хеширования будет коррелировать с устойчивостью задействуемого алгоритма.

Однако, как мы отметили выше, рассматривая различные виды хеш-функций, блочные алгоритмы часто сопровождаются необходимостью задействования больших вычислительных мощностей. Если они недоступны — скорость обработки файлов может быть недостаточной для решения практических задач, связанных с использованием хэш-функций. Вместе с тем требуемую криптостойкость можно реализовать и при небольшом количестве операций с потоками исходных данных, в частности к решению подобных задач приспособлены рассмотренные нами алгоритмы — MD5, SHA, российские стандарты криптографического шифрования.

Например, мы можем подать на вход 128-битной хеш-функции роман Льва Толстого в шестнадцатеричном виде или число 1. В результате на выходе мы в обоих случаях получим разные наборы псевдослучайных шестнадцатеричных цифр вида: «c4ca4238a0b923820dcc509a6f75849b».

При изменении исходного текста даже на один знак результат хеш-функции полностью меняется.

Это свойство хеш-функций позволяет применять их в следующих случаях:

при построении ассоциативных массивов ;
при поиске дубликатов в сериях наборов данных;
при построении уникальных идентификаторов для наборов данных;
при вычислении контрольных сумм от данных (сигнала) для последующего обнаружения в них ошибок (возникших случайно или внесённых намеренно), возникающих при хранении и/или передаче данных;
при сохранении паролей в системах защиты в виде хеш-кода (для восстановления пароля по хеш-коду требуется функция, являющаяся обратной по отношению к использованной хеш-функции);
при выработке электронной подписи (на практике часто подписывается не само сообщение, а его «хеш-образ»);
и др.

Виды «хеш-функций»

«Хорошая» хеш-функция должна удовлетворять двум свойствам :

быстрое вычисление;
минимальное количество «коллизий ».

Введём обозначения:

∀ k ∈ (0 ; K) : h (k) < M {\displaystyle \forall k\in (0;\,K):h(k).

В качестве примера «плохой» хеш-функции можно привести функцию с M = 1000 {\displaystyle M=1000} , которая десятизначному натуральному числу K {\displaystyle K} сопоставляет три цифры, выбранные из середины двадцатизначного квадрата числа K {\displaystyle K} . Казалось бы, значения «хеш-кодов» должны равномерно распределяться между «000 » и «999 », но для «реальных » данных это справедливо лишь в том случае, если «ключи » не имеют «большого» количества нулей слева или справа .

Рассмотрим несколько простых и надёжных реализаций «хеш-функций».

«Хеш-функции», основанные на делении

1. «Хеш-код» как остаток от деления на число всех возможных «хешей»

Хеш-функция может вычислять «хеш» как остаток от деления входных данных на M {\displaystyle M} :

h (k) = k mod M {\displaystyle h(k)=k\mod M} ,

где M {\displaystyle M} - количество всех возможных «хешей» (выходных данных).

При этом очевидно, что при чётном M {\displaystyle M} значение функции будет чётным при чётном k {\displaystyle k} и нечётным - при нечётном k {\displaystyle k} . Также не следует использовать в качестве M {\displaystyle M} степень основания системы счисления компьютера , так как «хеш-код» будет зависеть только от нескольких цифр числа k {\displaystyle k} , расположенных справа, что приведёт к большому количеству коллизий . На практике обычно выбирают простое M {\displaystyle M} ; в большинстве случаев этот выбор вполне удовлетворителен.

2. «Хеш-код» как набор коэффициентов получаемого полинома

Хеш-функция может выполнять деление входных данных на полином по модулю два. В данном методе M {\displaystyle M} должна являться степенью двойки, а бинарные ключи ( K = k n − 1 k n − 2 . . . k 0 {\displaystyle K=k_{n-1}k_{n-2}...k_{0}} ) представляются в виде полиномов , в качестве «хеш-кода» «берутся» значения коэффициентов полинома , полученного как остаток от деления входных данных K {\displaystyle K} на заранее выбранный полином P {\displaystyle P} степени m {\displaystyle m} :

K (x) mod P (x) = h m − 1 x m − 1 + ⋯ + h 1 x + h 0 {\displaystyle K(x)\mod P(x)=h_{m-1}x^{m-1}+\dots +h_{1}x+h_{0}} h (x) = h m − 1 . . . h 1 h 0 {\displaystyle h(x)=h_{m-1}...h_{1}h_{0}}

При правильном выборе P (x) {\displaystyle P(x)} гарантируется отсутствие коллизий между почти одинаковыми ключами .

«Хеш-функции», основанные на умножении

Обозначим символом w {\displaystyle w} количество чисел, представимых машинным словом . Например, для 32-разрядных компьютеров, совместимых с IBM PC , w = 2 32 {\displaystyle w=2^{32}} .

Выберем некую константу A {\displaystyle A} так, чтобы A {\displaystyle A} была взаимно простой с w {\displaystyle w} . Тогда хеш-функция, использующая умножение, может иметь следующий вид:

h (K) = [ M ⌊ A w ∗ K ⌋ ] {\displaystyle h(K)=\left}

В этом случае на компьютере с двоичной системой счисления M {\displaystyle M} является степенью двойки, и h (K) {\displaystyle h(K)} будет состоять из старших битов правой половины произведения A ∗ K {\displaystyle A*K} .

Среди преимуществ хеш-функций, основанных на делении и умножении, стоит отметить выгодное использование неслучайности реальных ключей. Например, если ключи представляют собой арифметическую прогрессию (например, последовательность имён «Имя 1», «Имя 2», «Имя 3»), хеш-функция, использующая умножение, отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшит количество коллизий по сравнению со случайной ситуацией .

Одной из хеш-функций, использующих умножение, является хеш-функция, использующая хеширование Фибоначчи . Хеширование Фибоначчи основано на свойствах золотого сечения . В качестве константы A {\displaystyle A} здесь выбирается целое число, ближайшее к φ − 1 ∗ w {\displaystyle \varphi ^{-1}*w} и взаимно простое с w {\displaystyle w} , где φ {\displaystyle \varphi } - это золотое сечение .

Хеширование строк переменной длины

Вышеизложенные методы применимы и в том случае, если необходимо рассматривать ключи, состоящие из нескольких слов, или ключи переменной длины.

Например, можно скомбинировать слова в одно при помощи сложения по модулю w {\displaystyle w} или операции «исключающее или ». Одним из алгоритмов, работающих по такому принципу, является хеш-функция Пирсона.

Универсальное хеширование

Методы борьбы с коллизиями

Коллизией (иногда конфликтом или столкновением) называется случай, при котором одна хеш-функция для разных входных блоков возвращает одинаковые хеш-коды.

Методы борьбы с коллизиями в хеш-таблицах

Большинство первых работ, описывающих хеширование, посвящено методам борьбы с коллизиями в хеш-таблицах. Тогда хеш-функции применялись при поиске текста в файлах большого размера. Существует два основных метода борьбы с коллизиями в хеш-таблицах:

метод цепочек (метод прямого связывания);
метод открытой адресации.

При использовании метода цепочек в хеш-таблице хранятся пары «связный список ключей» - «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; если хеш-код был получен ранее (для другого ключа), ключ добавляется в существующий список ключей, парный хеш-коду; иначе создаётся новая пара «список ключей» - «хеш-код», и ключ добавляется в созданный список. В общем случае, если имеется N {\displaystyle N} ключей и M {\displaystyle M} списков, средний размер хеш-таблицы составит N M {\displaystyle {\frac {N}{M}}} . В этом случае при поиске по таблице по сравнению со случаем, в котором поиск выполняется последовательно, средний объём работ уменьшится примерно в M {\displaystyle M} раз.

При использовании метода открытой адресации в хеш-таблице хранятся пары «ключ» - «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; пара «ключ» - «хеш-код» сохраняется в таблице. В этом случае при поиске по таблице по сравнению со случаем, в котором используются связные списки, ссылки не используются, выполняется последовательный перебор пар «ключ» - «хеш-код», перебор прекращается после обнаружения нужного ключа. Последовательность, в которой просматриваются ячейки таблицы, называется последовательностью проб .

Криптографическая соль

Применение хеш-функций

Хеш-функции широко используются в криптографии.

Хеш используется как ключ во многих структурах данных - хеш-таблицаx , фильтрах Блума и декартовых деревьях .

Криптографические хеш-функции

Среди множества существующих хеш-функций принято выделять криптографически стойкие , применяемые в криптографии , так как на них накладываются дополнительные требования. Для того, чтобы хеш-функция H {\displaystyle H} считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

Данные требования не являются независимыми.

Рассмотренные нами алгоритмы поиска обычно основаны на абстрактной операции сравнения. Из этого ряда существенно выделяется метод распределяющего поиска, описанный в "Таблицы символов и деревья бинарного поиска" , при котором элемент с ключом i хранится в i-ой позиции таблицы, что позволяет обратиться к нему непосредственно. При распределяющем поиске значения ключей используются в качестве индексов массива, а не операндов операции сравнения; сам метод основан на том, что ключи являются различными целыми числами из того же диапазона, что и индексы таблицы. В этой главе мы рассмотрим хеширование ( hashing ) - расширенный вариант распределяющего поиска, применяемый в более типичных приложениях поиска, где ключи не обладают столь удобными свойствами. Конечный результат применения данного подхода совершенно не похож на методы, основанные на сравнении - вместо перемещения по структурам данных словаря с помощью сравнения ключей поиска с ключами в элементах, мы пытаемся обратиться к элементам в таблице непосредственно, выполняя арифметическое преобразование ключей в адреса таблицы.

Алгоритмы поиска, использующие хеширование , состоят из двух отдельных частей. Первый шаг - вычисление хеш-функции ( hash function ), которая преобразует ключ поиска в адрес в таблице. В идеале различные ключи должны были бы отображаться на различные адреса, но часто два или более различных ключа могут дать один и тот же адрес в таблице. Поэтому вторая часть поиска методом хеширования - процесс разрешения коллизий ( collision resolution ), который обрабатывает такие ключи. В одном из методов разрешения конфликтов, который мы рассмотрим в этой главе, используются связные списки, поэтому он находит непосредственное применение в динамических ситуациях, когда трудно заранее предугадать количество ключей поиска. В других двух методах разрешения коллизий достигается высокая производительность поиска, поскольку элементы хранятся в фиксированном массиве. Мы рассмотрим способ усовершенствования этих методов, позволяющий использовать их и в тех случаях, когда нельзя заранее предсказать размеры таблицы.

Хеширование - хороший пример баланса между временем и объемом памяти. Если бы не было ограничения на объем используемой памяти, любой поиск можно было бы выполнить с помощью всего лишь одного обращения к памяти, просто используя ключ в качестве адреса памяти, как при распределяющем поиске. Однако обычно этот идеальный случай недостижим, поскольку для длинных ключей может потребоваться огромный объем памяти. С другой стороны, если бы не было ограничений на время выполнения , можно было бы обойтись минимальным объемом памяти, пользуясь методом последовательного поиска. Хеширование представляет собой способ использования приемлемого объема как памяти, так и времени, и достижения баланса между этими двумя крайними требованиями. В частности, можно поддерживать любой баланс, просто меняя размер таблицы, а не переписывая код и не выбирая другие алгоритмы.

Хеширование - одна из классических задач компьютерных наук: его различные алгоритмы подробно исследованы и находят широкое применение. Мы увидим, что при совсем не жестких допущениях можно надеяться на поддержку операций найти и вставить в таблицах символов с постоянным временем выполнения, независимо от размера таблицы.

Это ожидаемое значение - теоретический оптимум производительности для любой реализации таблицы символов, но хеширование все же не является панацеей по двум основным причинам. Во-первых, время выполнения зависит от длины ключа, которая в реальных приложениях, использующих длинные ключи, может быть значительной. Во-вторых, хеширование не обеспечивает эффективные реализации других операций с таблицами символов, таких, как выбрать или сортировать. В этой главе мы подробно рассмотрим эти и другие вопросы.

Хеш-функции

Прежде всего необходимо решить задачу вычисления хеш-функции, преобразующей ключи в адреса таблицы. Обычно реализация этого арифметического вычисления не представляет сложности, но все же необходимо соблюдать осторожность, чтобы не нарваться на различные малозаметные подводные камни. При наличии таблицы, которая может содержать M элементов, нужна функция, преобразующая ключи в целые числа в диапазоне . Идеальная хеш-функция должна легко вычисляться и быть похожей на случайную функцию: для любых аргументов результаты в некотором смысле должны быть равновероятными.

Хеш-функция зависит от типа ключа. Строго говоря, для каждого возможного вида ключей требуется отдельная хеш-функция. Для повышения эффективности обычно желательно избегать явного преобразования типов, обратившись вместо этого к идее рассмотрения двоичного представления ключей в машинном слове в виде целого числа, которое можно использовать в арифметических вычислениях. Хеширование появилось до языков высокого уровня - на ранних компьютерах было обычным делом рассматривать какое-либо значение то как строковый ключ, то как целое число. В некоторых языках высокого уровня затруднительно создавать программы, которые зависят от представления ключей в конкретном компьютере, поскольку такие программы, по сути, являются машинно-зависимыми, и поэтому их трудно перенести на другой компьютер. Обычно хеш-функции зависят от процесса преобразования ключей в целые числа, поэтому в реализациях хеширования бывает трудно одновременно обеспечить и машинную независимость, и эффективность. Как правило, простые целочисленные ключи или ключи типа с плавающей точкой можно преобразовать с помощью всего одной машинной операции, но строковые ключи и другие типы составных ключей требуют больших затрат и большего внимания к эффективности.

Вероятно, простейшей является ситуация, когда ключами являются числа с плавающей точкой из фиксированного диапазона. Например, если ключи - числа, большие 0 и меньшие 1, их можно просто умножить на M, округлить результат до меньшего целого числа и получить адрес в диапазоне между 0 и M - 1 ; такой пример показан на рис. 14.1 . Если ключи больше s и меньше t, их можно масштабировать, вычтя s и разделив на t-s , в результате чего они попадут в диапазон значений между 0 и 1, а затем умножить на M и получить адрес в таблице.

Рис. 14.1.

Для преобразования чисел с плавающей точкой в диапазоне между 0 и 1 в индексы таблицы, размер которой равен 97, выполняется умножение этих чисел на 97. В данном примере произошло три коллизии: для индексов, равных 17, 53 и 76. Хеш-значения определяются старшими разрядами ключа, младшие разряды не играют никакой роли. Одна из целей разработки хеш-функции - устранение такого дисбаланса, чтобы во время вычисления учитывался каждый разряд.

Если ключи являются w-разрядными целыми числами, их можно преобразовать в числа с плавающей точкой и разделить на 2 w для получения чисел с плавающей точкой в диапазоне между 0 и 1, а затем умножить на M, как в предыдущем абзаце. Если операции с плавающей точкой занимают много времени, а числа не столь велики, чтобы привести к переполнению, этот же результат может быть получен с помощью целочисленных арифметических операций: нужно ключ умножить на M, а затем выполнить сдвиг вправо на w разрядов для деления на 2 w (или, если умножение приводит к переполнению, выполнить сдвиг, а затем умножение). Такие методы бесполезны для хеширования, если только ключи не распределены по диапазону равномерно, поскольку хеш-значение определяется только ведущими цифрами ключа.

Более простой и эффективный метод для w-разрядных целых чисел - один из, пожалуй, наиболее часто используемых методов хеширования - выбор в качестве размера M таблицы простого числа и вычисление остатка от деления к на M, т.е. h(k) = k mod M для любого целочисленного ключа k. Такая функция называется модульной хеш-функцией. Ее очень просто вычислить (k % M в языке C++), и она эффективна для достижения равномерного распределения значений ключей между значениями, меньшими M. Небольшой пример показан на рис. 14.2 .

Рис. 14.2.

В трех правых столбцах показан результат хеширования 16-разрядных ключей, приведенных слева, с помощью следующих функций:

v % 97 (слева)

v % 100 (в центре) и

(int) (a * v) % 100 (справа),

где a = .618033 . Размеры таблицы для этих функций соответственно равны 97, 100 и 100. Значения выглядят случайными (поскольку случайны ключи). Вторая функция (v % 100 ) использует лишь две крайние правые цифры ключей и поэтому для неслучайных ключей может показывать низкую производительность.

Модульное хеширование применимо и к ключам с плавающей точкой. Если ключи принадлежат небольшому диапазону, можно масштабировать их в числа из диапазона между 0 и 1, 2 w для получения w-разрядных целочисленных значений, а затем использовать модульную хеш-функцию. Другой вариант - просто использовать в качестве операнда модульной хеш-функции двоичное представление ключа (если оно доступно).

Модульное хеширование применяется во всех случаях, когда имеется доступ к битам, из которых состоят ключи, независимо от того, являются ли они целыми числами, представленными машинным словом, последовательностью символов, упакованных в машинное слово, или представлены любым другим возможным вариантом. Последовательность случайных символов, упакованная в машинное слово - не совсем то же, что случайные целочисленные ключи, поскольку не все разряды используются для кодирования. Но оба эти типа (и любой другой тип ключа, закодированный так, чтобы уместиться в машинном слове) можно заставить выглядеть случайными индексами в небольшой таблице.

Основная причина выбора в качестве размера M хеш-таблицы простого числа для модульного хеширования показана на рис. 14.3 . В этом примере символьных данных с 7-разрядным кодированием ключ трактуется как число с основанием 128 - по одной цифре для каждого символа в ключе. Слово now соответствует числу 1816567, которое может быть также записано как

поскольку в ASCII-коде символам n, o и w соответствуют числа 1568 = 110 , 1578 = 111 и 1678 = 119 . Выбор размера таблицы M = 64 для этого типа ключа неудачен, поскольку добавление к х значений, кратных 64 (или 128), не меняет значение х mod 64 - для любого ключа значением хеш-функции является значение последних 6 разрядов этого ключа. Безусловно, хорошая хеш-функция должна учитывать все разряды ключа, особенно для символьных ключей. Аналогичные ситуации могут возникать, когда M содержит множитель, являющийся степенью 2. Простейший способ избежать этого - выбрать в качестве M простое число.

Рис. 14.3.

В каждой строке этой таблицы приведены: 3-буквенное слово, представление этого слова в ASCII-коде как 21-битовое число в восьмеричной и десятичной формах и стандартные модульные хеш-функции для размеров таблиц 64 и 31 (два крайних справа столбца). Размер таблицы 64 приводит к нежелательным результатам, поскольку для получения хеш-значения используются только самые правые разряды ключа, а буквы в словах обычного языка распределены неравномерно. Например, всем словам, оканчивающимся на букву у, соответствует хеш-значение 57. И, напротив, простое значение 31 вызывает меньше коллизий в таблице более чем вдвое меньшего размера.

Модульное хеширование очень просто реализовать, за исключением того, что размер таблицы должен быть простым числом. Для некоторых приложений можно довольствоваться небольшим известным простым числом или же поискать в списке известных простых чисел такое, которое близко к требуемому размеру таблицы. Например, числа равные 2 t - 1, являются простыми при t = 2, 3, 5, 7, 13, 17, 19 и 31 (и ни при каких других значениях t < 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.

Рис. 14.4.

Эта таблица наибольших простых чисел, меньших 2 n , для , может использоваться для динамического распределения хеш-таблицы, когда нужно, чтобы размер таблицы был простым числом. Для любого данного положительного значения в охваченном диапазоне эту таблицу можно использовать для определения простого числа, отличающегося от него менее чем в 2 раза.

Другой вариант обработки целочисленных ключей - объединение мультипликативного и модульного методов: нужно умножить ключ на константу в диапазоне между 0 и 1, а затем выполнить деление по модулю M. Другими словами, необходимо использовать функцию . Между значениями , M и эффективным основанием системы счисления ключа существует взаимосвязь, которая теоретически могла бы привести к аномальному поведению, но если использовать произвольное значение a, в реальном приложении вряд ли возникнет какая-либо проблема. Часто в качестве a выбирают значение ф = 0,618033... (золотое сечение).

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

Во многих приложениях, в которых используются таблицы символов, ключи не являются числами и не обязательно являются короткими; чаще это алфавитно-цифровые строки, которые могут быть весьма длинными. Ну и как вычислить хеш-функцию для такого слова, как averylongkey?

В 7-разрядном ASCII-коде этому слову соответствует 84-разрядное число \begin{align*} 97 \cdot 128^{11} &+ 118 \cdot 128^{10} + 101 \cdot 128^{9} + 114 \cdot 128^{8} + 121 \cdot 128^{7}\\ &+ 108 \cdot 128^{6} + 111 \cdot 128^{5} + 110 \cdot 128^{4} + 103 \cdot 128^{3}\\ &+ 107 \cdot 128^{2} + 101 \cdot 128^{1} + 121 \cdot 128^{0}, \end{align*},

которое слишком велико, чтобы с ним можно было выполнять обычные арифметические функции в большинстве компьютеров. А зачастую требуется обрабатывать и гораздо более длинные ключи.

Чтобы вычислить модульную хеш-функцию для длинных ключей, они преобразуются фрагмент за фрагментом. Можно воспользоваться арифметическими свойствами функции модуля и использовать алгоритм Горнера (см. раздел 4.9 "Абстрактные типы данных"). Этот метод основан на еще одном способе записи чисел, соответствующих ключам. Для рассматриваемого примера запишем следующее выражение: \begin{align*} ((((((((((97 \cdot 128^{11} &+ 118) \cdot 128^{10} + 101) \cdot 128^{9} + 114) \cdot 128^{8} + 121) \cdot 128^{7}\\ &+ 108) \cdot 128^{6} + 111) \cdot 128^{5} + 110) \cdot 128^{4} + 103) \cdot 128^{3}\\ &+ 107) \cdot 128^{2} + 101) \cdot 128^{1} + 121. \end{align*}

То есть десятичное число, соответствующее символьной кодировке строки, можно вычислить при просмотре ее слева направо, умножая накопленное значение на 128, а затем добавляя кодовое значение следующего символа. В случае длинной строки этот способ вычисления в конце концов приведет к числу, большему того, которое вообще можно представить в компьютере. Однако это число и не нужно, поскольку требуется только (небольшой) остаток от его деления на M. Результат можно получить, даже не сохраняя большое накопленное значение, т.к. в любой момент вычисления можно отбросить число, кратное M - при каждом выполнении умножения и сложения нужно хранить только остаток от деления по модулю M. Результат будет таким же, как если бы у нас имелась возможность вычислить длинное число, а затем выполнять деление (см. упражнение 14.10). Это наблюдение ведет к непосредственному арифметическому способу вычисления модульных хеш-функций для длинных строк - см. программу 14.1. В этой программе используется еще одно, последнее ухищрение: вместо основания 128 в ней используется простое число 127. Причина этого изменения рассматривается в следующем абзаце.

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

Программа 14.1. Хеш-функция для строковых ключей

M = 96 и a = 128 (вверху),

M = 97 и a = 128 (в центре) и

M = 96 и a = 127 (внизу)

Неравномерное распределение в первом случае является результатом неравномерного употребления букв и сохранения неравномерности из-за того, что и размер таблицы, и множитель кратны 32. Два других примера выглядят случайными, поскольку размер таблицы и множитель являются взаимно простыми числами.

В программе 14.1 показан один из способов сделать это: использование простого основания вместо степени 2 и целого числа, соответствующего ASCII-представлению строки. На рис. 14.5 рис. 14.5 показано, как это изменение улучшает распределение для типичных строковых ключей. Теоретически хеш-значения, созданные программой 14.1, могут давать плохие результаты для размеров таблицы, которые кратны 127 (хотя на практике это, скорее всего, будет почти незаметно); для создания рандомизированного алгоритма можно было бы выбрать значение множителя наугад. Еще более эффективный подход - использование случайных значений коэффициентов в вычислении и различных случайных значений для каждой цифры ключа. Такой подход дает рандомизированный алгоритм, называемый универсальным хешированием (universal hashing).

Теоретически идеальная универсальная хеш-функция - это функция, для которой вероятность коллизии между двумя различными ключами в таблице размером M в точности равна 1/M. Можно доказать, что использование в качестве коэффициента а в программе 14.1 не фиксированного произвольного значения, а последовательности случайных различных значений преобразует модульное хеширование в универсальную хеш-функцию. Однако затраты на генерирование нового случайного числа для каждого символа в ключе обычно неприемлемы. На практике можно достичь компромисса, показанного в программе 14.1, не храня массив различных случайных чисел для каждого символа ключа, а варьируя коэффициенты с помощью генерации простой псевдослучайной последовательности.

Подведем итоги: чтобы для реализации абстрактной таблицы символов использовать хеширование, сначала необходимо расширить интерфейс абстрактного типа, включив в него операцию hash, которая отображает ключи на неотрицательные целые числа, меньшие размера таблицы M.