Хеш-функция

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

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

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

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

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

${\displaystyle K(x)\mod P(x)=h_{m-1}x^{m-1}+\dots +h_{1}x+h_{0}}$

${\displaystyle h(x)=h_{m-1}...h_{1}h_{0}}$

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

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

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

${\displaystyle h(K)=\left[M\left\lfloor {\frac {A}{w}}*K\right\rfloor \right]}$

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

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

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

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

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

Хеширование Пирсона — алгоритм, предложенный Питером Пирсоном (англ. Peter Pearson) для процессоров с 8-битовыми регистрами, задачей которого является быстрое преобразование строки произвольной длины в хеш-код. На вход функция получает слово ${\displaystyle W}$, состоящее из ${\displaystyle n}$ символов, каждый размером 1 байт, и возвращает значение в диапазоне от 0 до 255. При этом значение хеш-кода зависит от каждого символа входного слова.

Алгоритм можно описать следующим псевдокодом, который получает на вход строку ${\displaystyle W}$ и использует таблицу перестановок ${\displaystyle T}$:

h := 0
for each c in W loop
  index := h xor c
  h := T[index]
end loop
return h

Среди преимуществ алгоритма:

• простоту вычисления;
• отсутствие таких входных данных, для которых вероятность коллизии наибольшая;
• возможность модификации в идеальную хеш-функцию[5].

В качестве альтернативного способа хеширования ключей ${\displaystyle K}$, состоящих из ${\displaystyle l}$ символов (${\displaystyle K=x_{1}x_{2}...x_{l}}$), можно предложить вычисление

${\displaystyle h(K)=(h_{1}(x_{1})+h_{2}(x_{2})+...+h_{l}(x_{l}))\mod M}$[4]

Идеальной хеш-функцией (англ. perfect hash function) называется такая функция, которая отображает каждый ключ из набора ${\displaystyle S}$ во множество целых чисел без коллизий. В математике такое преобразование называется инъективным отображением.

1. Функция ${\displaystyle h(k)\colon U\to [m]}$ называется идеальной хеш-функцией для ${\displaystyle S\subseteq U}$, если она инъективна на ${\displaystyle S}$.
2. Функция ${\displaystyle h(k)\colon U\to [m]}$ называется минимальной идеальной хеш-функцией для ${\displaystyle S\subseteq U}$, если она является идеальной хеш-функцией и ${\displaystyle m=n=|S|}$.
3. Для целого ${\displaystyle k\geq 1}$ функция ${\displaystyle h(k)\colon U\to [m]}$ называется ${\displaystyle k}$-идеальной хеш-функцией (k-PHF) для ${\displaystyle S\subseteq U}$, если для каждого ${\displaystyle j\in [m]}$ имеем ${\displaystyle |\{x\in S|h(x)=j\}|\leq k}$.

Идеальное хеширование применяется, если требуется присвоить уникальный идентификатор ключу без сохранения какой-либо информации о ключе. Пример использования идеального (или скорее ${\displaystyle k}$-идеального) хеширования: размещение хешей, связанных с данными, хранящимися в большой и медленной памяти, в небольшой и быстрой памяти. Размер блока можно выбрать таким, чтобы необходимые данные считывались из медленной памяти за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, если представление графа не умещается в основной памяти[6].

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

Предположим, что требуется отобразить ключи из пространства ${\displaystyle U}$ в числа ${\displaystyle [m]}$. На входе алгоритм получает данные из некоторого набора ${\displaystyle S\in U}$ размерностью ${\displaystyle n}$. Набор заранее неизвестен. Как правило, алгоритм должен обеспечить наименьшее число коллизий, чего трудно добиться, используя какую-то определённую хеш-функцию. Число коллизий можно уменьшить, если каждый раз при хешировании выбирать хеш-функцию случайным образом. Хеш-функция выбирается из определённого набора хеш-функций, называемого универсальным семейством ${\displaystyle H=\{h:U\to [m]\}}$[7].

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

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

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

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

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

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

• необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных ${\displaystyle X}$, для которого ${\displaystyle H(X)=m}$;
• стойкость к коллизиям первого рода: для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N, для которого ${\displaystyle H(N)=H(M)}$;
• стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару сообщений ${\displaystyle (M,M')}$, имеющих одинаковый хеш.

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

• обратимая функция нестойка к коллизиям первого и второго рода;
• функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

Атака «дней рождения» позволяет находить коллизии для хеш-функции с длиной значений n бит в среднем за примерно ${\displaystyle 2^{n/2}}$ вычислений хеш-функции. Поэтому n-битовая хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к ${\displaystyle 2^{n/2}}$.

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

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

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

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

Платой за столь высокую скорость является отсутствие криптостойкости — возможность легко «подогнать» сообщение под заранее известную контрольную сумму. Также обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем разрядность криптографических хешей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий.

Простейшим алгоритмом вычисления контрольной суммы является деление сообщения (входных данных) на 32- или 16-битовые слова с последующим суммированием слов. Такой алгоритм применяется, например, в протоколах TCP/IP.

Как правило, алгоритмы вычисления контрольных сумм должны обнаруживать типичные аппаратные ошибки, например, должны обнаруживать несколько подряд идущих ошибочных бит до заданной длины. Семейство алгоритмов так называемых «циклических избыточных кодов» удовлетворяет этим требованиям. К ним относится, например, алгоритм CRC32, применяемый в устройствах Ethernet и в формате сжатия данных ZIP.

Контрольная сумма, например, может быть передана по каналу связи вместе с основным текстом (данными). На приёмном конце, контрольная сумма может быть рассчитана заново и может сравниваться с переданным значением. Если будет обнаружено расхождение, то при передаче возникли искажения, и можно запросить повторную передачу.

Пример применения хеширования в быту — подсчёт количества чемоданов, перевозимых в багаже. Для проверки сохранности чемоданов не требуется проверять сохранность каждого чемодана, достаточно посчитать количество чемоданов при погрузке и выгрузке. Совпадение чисел будет означать, что ни один чемодан не потерян. То есть, число чемоданов является хеш-кодом.

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

Геометрическое хеширование (англ. geometric hashing) — метод, широко применяемый в компьютерной графике и вычислительной геометрии для решения задач на плоскости или в трёхмерном пространстве, например для нахождения ближайших пар точек среди множества точек или для поиска одинаковых изображений. Хеш-функция в данном методе обычно получает на вход какое-либо метрическое пространство и разделяет его, создавая сетку из клеток. Хеш-таблица в данном случае является массивом с двумя или более индексами и называется «файлом сетки» (англ. grid file). Геометрическое хеширование применяется в телекоммуникациях при работе с многомерными сигналами[9].

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

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