Хеш-функция

Хеш-функция (англ. hash function от hash — «превращать в фарш», «мешанина»), или функция свёртки — функция, преобразующая массив входных данных произвольного размера в выходную битовую строку определённого (установленного) размера в соответствии с определённым алгоритмом. Преобразование, выполняемое хеш-функцией, называется хешированием. Исходные (входные) данные называются входным массивом, «ключом», «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения», «свёрткой».

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

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

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

Существует множество алгоритмов хеширования, различающихся свойствами. Примеры свойств:

• разрядность;
• вычислительная сложность;
• криптостойкость.

Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшим примером хеш-функции может служить «обрамление» данных циклическим избыточным кодом (англ. CRC, cyclic redundancy code).

История

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

Галилео Галилей наблюдал кольца Сатурна, которые принял за «ушки». Не будучи уверен, но желая утвердить свой приоритет, Галилей опубликовал сообщение с перестановленными буквами: smaismrmilmepoetaleumibunenugttauiras. В 1610 году Галилей раскрыл исходную фразу: Altissimum planetam tergeminum obseruaui, что в переводе с латинского языка означает «высочайшую планету тройною наблюдал». Таким образом, на момент публикации первого сообщения исходная фраза не была раскрыта, но была создана возможность подтвердить её позже.

В середине 1650-х Христиан Гюйгенс разглядел кольца и опубликовал сообщение с буквами, расставленными по алфавиту: aaaaaaacccccdeeeeeghiiiiiiillllmmnnnnnnnnnooooppqrrstttttuuuuu. Через некоторое время была опубликована и исходная фраза: Annulo cingitur, tenui plano, nusquam cohaerente, ad eclipticam inclinato — «Окружён кольцом тонким, плоским, нигде не подвешенным, наклонённым к эклиптике». От применения хеш-функции, включая и цель позднее подтвердить некоторое нераскрытое сообщение, данный случай отличается только тем, что выходное сообщение не имеет фиксированного размера, а определяется размером входного сообщения. Фактически, расстановка букв исходного сообщения по алфавиту является некоторой хеш-функцией, но только с результатом нефиксированного размера.

В январе 1953 года Ханс Петер Лун (нем. Hans Peter Luhn) (сотрудник фирмы IBM) предложил «хеш-кодирование». Дональд Кнут считает, что Ханс первым выдвинул систематическую идею «хеширования».

В 1956 году Арнольд Думи (англ. Arnold Dumey) в своей работе «Computers and automation» первым описал идею «хеширования» такой, какой её знает большинство программистов в настоящее время. Думи рассматривал «хеширование» как решение «проблемы словаря», предложил использовать в качестве «хеш-адреса» остаток от деления на простое число.

В 1957 году в журнале «IBM Journal of Research and Development» была опубликована статья Уэсли Питерсона (англ. W. Wesley Peterson) о поиске текста в больших файлах. Эта работа считается первой «серьёзной» работой по «хешированию». В статье Уэсли определил «открытую адресацию», указал на уменьшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца (нем. Werner Buchholz), в которой было проведено обширное исследование «хеш-функций». В течение нескольких последующих лет «хеширование» широко использовалось, но никаких значимых работ не публиковалось.

В 1967 году «хеширование» в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис (англ. Robert Morris) опубликовал в журнале «Communications of the ACM» большой обзор по «хешированию». Эта работа считается вводящей понятие о «хешировании» в научный оборот и закрепившей термин «хеш», ранее применявшийся только специалистами (жаргон).

До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Петровича Ершова использовалось слово «расстановка», а «коллизия» называлась словом «конфликт» (А. П. Ершов использовал «расстановку» с 1956 года). В русскоязычном издании книги Никлауса Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка». Предлагалось также назвать метод другим русским словом: «окрошка». Однако ни один из этих вариантов не прижился, и в русской литературе используется преимущественно термин «хеширование».

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

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

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

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

• $K$ — количество «ключей» (входных данных);
• $k$ — любой из «ключей» (входных данных);
• $h(k)$ — хеш-функция, имеющая не более $M$ различных значений (выходных данных).

То есть:

$\forall k\in [0;\,K):h(k)<M$.

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

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

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

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

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

$h(k)=k\mod M$,

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

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

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

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

$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}$

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

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

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

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

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

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

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

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

Хеширование строк переменного размера

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

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

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

Алгоритм можно описать следующим псевдокодом, где строка $W$ — входные данные, $T$ — таблица перестановок:

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

Преимущества алгоритма:

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

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

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

Идеальное хеширование

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

Описание

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

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

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

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

Описание

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

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

Основная статья: Коллизия хеш-функции

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

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

Основная статья: Хеш-таблица

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

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

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

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

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

Основная статья: Соль (криптография)

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

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

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

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

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

Основная статья: Криптографическая хеш-функция

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

• необратимость: для заданных выходных данных (значения) out должно быть вычислительно неосуществимо найти входные данные (блок данных) in, для которых $H(in)=out$;
• стойкость к коллизиям первого рода: для заданных входных данных (сообщения) in1 должно быть вычислительно неосуществимо подобрать другие входные данные (сообщение) in2, для которых $H(in1)=H(in2)$;
• стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару таких входных данных (сообщений) $(in1,in2)$, которые имеют одинаковые выходные данные (хеш): $H(in1)=H(in2)$.

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

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

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

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

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

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

Контрольные суммы

Основная статья: Контрольная сумма

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

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

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

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

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

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

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

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

Геометрическое хеширование

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

Ускорение поиска данных

Основная статья: Хеш-таблица

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

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

Литература

• Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — М.: Триумф, 2002. — ISBN 5-89392-055-4.
• Дональд Кнут. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е издание. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
• Никлаус Вирт. Алгоритмы и структуры данных. — М.: «Мир», 1989. — ISBN 5-03-001045-9.
• Никлаус Вирт. Алгоритмы и структуры данных. Новая версия для Оберона. — М.: «ДМК Пресс», 2010. — ISBN 978-5-94074-584-6.

Ссылки

• Информация по электронной цифровой подписи