Хеш-функция ( от — «превращать в фарш», «мешанина»), или функция свёртки — функция, преобразующая массив входных данных произвольного размера в выходную битовую строку определённого (установленного) размера в соответствии с определённым алгоритмом. Преобразование, выполняемое хеш-функцией, называется хешированием. Исходные (входные) данные называются входным массивом, «ключом», «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения», «свёрткой».
Хеш-функции применяются в следующих случаях: при построении ассоциативных массивов; при поиске дубликатов в последовательностях наборов данных; при построении уникальных идентификаторов для наборов данных; при вычислении контрольных сумм от данных (сигнала) для последующего обнаружения в данных ошибок (возникших случайно или внесённых намеренно), возникающих при хранении и/или передаче данных; при сохранении паролей в системах защиты в виде хеш-кода; при создании (выработке) электронной подписи (на практике подпись часто создаётся не для сообщения, а для «хеш-образа» сообщения); и в других случаях.
В общем случае (согласно принципу Дирихле) не существует однозначного соответствия между выходными данными (хеш-кодом, значениями, возвращёнными хеш-функцией) и входными данными (исходными данными). Выходные данные (возвращаемые хеш-функцией значения) менее разнообразны, чем входные данные (значения входного массива). Случай, при котором хеш-функция преобразует более чем одни входные данные (один массив входных данных) в одинаковые выходные данные (сводки), называется «коллизией». Вероятность возникновения коллизий используется для оценки качества хеш-функций.
Существует множество алгоритмов хеширования, различающихся свойствами. Примеры свойств: разрядность; вычислительная сложность; криптостойкость.
Выбор той или иной хеш-функции определяется спецификой решаемой задачи.
История
Шифровка сообщений без возможности однозначной расшифровки, а только с целью подтверждения авторского приоритета, применялась издавна.
Галилео Галилей наблюдал кольца Сатурна, которые принял за «ушки». Не будучи уверен, но желая утвердить свой приоритет, Галилей опубликовал сообщение с перестановленными буквами: smaismrmilmepoetaleumibunenugttauiras. В 1610 году Галилей раскрыл исходную фразу: Altissimum planetam tergeminum obseruaui, что в переводе с латинского языка означает «высочайшую планету тройною наблюдал». Таким образом, на момент публикации первого сообщения исходная фраза не была раскрыта, но была создана возможность подтвердить её позже.
В середине 1650-х Христиан Гюйгенс разглядел кольца и опубликовал сообщение с буквами, расставленными по алфавиту: aaaaaaacccccdeeeeeghiiiiiiillllmmnnnnnnnnnooooppqrrstttttuuuuu. Через некоторое время была опубликована и исходная фраза: Annulo cingitur, tenui plano, nusquam cohaerente, ad eclipticam inclinato — «Окружён кольцом тонким, плоским, нигде не подвешенным, наклонённым к эклиптике». От применения хеш-функции, включая и цель позднее подтвердить некоторое нераскрытое сообщение, данный случай отличается только тем, что выходное сообщение не имеет фиксированного размера, а определяется размером входного сообщения. Фактически, расстановка букв исходного сообщения по алфавиту является некоторой хеш-функцией, но только с результатом нефиксированного размера.
В январе 1953 года (сотрудник фирмы IBM) предложил «хеш-кодирование». Дональд Кнут считает, что Ханс первым выдвинул систематическую идею «хеширования».
В 1956 году в своей работе «Computers and automation» первым описал идею «хеширования» такой, какой её знает большинство программистов в настоящее время. Думи рассматривал «хеширование» как решение «проблемы словаря», предложил использовать в качестве «хеш-адреса» остаток от деления на простое число.
В 1957 году в журнале «IBM Journal of Research and Development» была опубликована статья о поиске текста в больших файлах. Эта работа считается первой «серьёзной» работой по «хешированию». В статье Уэсли определил «открытую адресацию», указал на уменьшение производительности при удалении. Спустя шесть лет была опубликована работа , в которой было проведено обширное исследование «хеш-функций». В течение нескольких последующих лет «хеширование» широко использовалось, но никаких значимых работ не публиковалось.
В 1967 году «хеширование» в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем»Herbert Hellerman. Digital Computer System Principles. N.Y.: McGraw-Hill, 1967, 424 pp.. В 1968 году опубликовал в журнале «Communications of the ACM» большой обзор по «хешированию». Эта работа считается вводящей понятие о «хешировании» в научный оборот и закрепившей термин «хеш», ранее применявшийся только специалистами (жаргон).
До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Петровича Ершова использовалось слово «расстановка», а «коллизия» называлась словом «конфликт» (А. П. Ершов использовал «расстановку» с 1956 года). В русскоязычном издании книги Никлауса Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка». Предлагалось также назвать метод другим русским словом: «окрошка». Однако ни один из этих вариантов не прижился, и в русской литературе используется преимущественно термин «хеширование».
Виды «хеш-функций» «Хорошая» хеш-функция должна удовлетворять двум свойствам: быстрое вычисление; минимальное количество «коллизий».
Введём обозначения: — количество «ключей» (входных данных); — любой из «ключей» (входных данных); — хеш-функция, имеющая не более различных значений (выходных данных). То есть: .
В качестве примера «плохой» хеш-функции можно привести функцию с , которая десятизначному натуральному числу сопоставляет три цифры, выбранные из середины двадцатизначного квадрата числа . Казалось бы, значения «хеш-кодов» должны равномерно распределяться между «000» и «999», но для «реальных» данных это справедливо лишь в том случае, если «ключи» не имеют «большого» количества нулей слева или справа.
Рассмотрим несколько простых и надёжных реализаций «хеш-функций».
«Хеш-функции», основанные на делении
1. «Хеш-код» как остаток от деления на число всех возможных «хешей» Хеш-функция может вычислять «хеш» как остаток от деления входных данных на :
,
где — количество возможных «хешей» (выходных данных).
При чётном и при чётном значение функции будет чётным. При чётном и при нечётном значение функции будет нечётным. Не следует использовать в качестве степень основания системы счисления компьютера, так как «хеш-код» (выходные данные) будет зависеть только от нескольких цифр числа (входных данных), расположенных справа, что приведёт к большому количеству коллизий. На практике в качестве обычно выбирают простое число; в большинстве случаев этот выбор вполне удовлетворителен.
2. «Хеш-код» как набор коэффициентов получаемого полинома Хеш-функция может выполнять деление входных данных на полином по модулю два. Тогда должна являться степенью двойки. Бинарные ключи () представляются в виде полиномов. В качестве «хеш-кода» «берутся» значения коэффициентов полинома, полученного как остаток от деления входных данных на заранее выбранный полином степени :
При правильном выборе гарантируется отсутствие коллизий между почти одинаковыми ключами.
«Хеш-функции», основанные на умножении Обозначим символом количество чисел, представимых машинным словом. Например, для 32-разрядных компьютеров, совместимых с IBM PC, .
Выберем некую константу так, чтобы была взаимно простой с . Тогда хеш-функция, использующая умножение, может иметь следующий вид:
.
В этом случае на компьютере с двоичной системой счисления является степенью двойки, и будет состоять из старших битов правой половины произведения .
Одним из преимуществ хеш-функций, основанных на делении и умножении, является выгодное использование неслучайности реальных ключей. Например, если ключи представляют собой арифметическую прогрессию (например, последовательность имён «Имя 1», «Имя 2», «Имя 3»), хеш-функция, использующая умножение, отобразит арифметическую прогрессию в приближённо арифметическую прогрессию различных хеш-значений, что уменьшит количество коллизий по сравнению со случайной ситуацией.
Одной из хеш-функций, использующих умножение, является хеш-функция, использующая хеширование Фибоначчи. Хеширование Фибоначчи основано на свойствах числа — золотого сечения. В качестве константы здесь выбирается целое число, ближайшее к и взаимно простое с .
Хеширование строк переменного размера Вышеизложенные методы применимы и при необходимости рассматривать ключи, состоящие из нескольких слов, или ключи переменного размера.
Например, можно скомбинировать слова в одно при помощи сложения по модулю или операции «исключающее или». Одним из алгоритмов, работающих по такому принципу, является алгоритм Пирсона (хеширование Пирсона).
Алгоритм Пирсона — алгоритм, предложенный Питером Пирсоном () для процессоров с 8-битовыми регистрами и предназначенный для быстрого преобразования строки произвольного размера в хеш-код. Реализован хеш-функцией Пирсона, получает слово , состоящее из 1-байтовых символов, и возвращает значение в диапазоне от 0 до 255. При этом значение хеш-кода зависит от каждого символа входного слова.
Алгоритм можно описать следующим псевдокодом, где строка — входные данные, — таблица перестановок: h := 0 for each c in W loop index := h xor c h := T[index] end loop return h Преимущества алгоритма: простота вычисления; отсутствие таких входных данных, для которых вероятность коллизии наибольшая; возможность преобразования в идеальную хеш-функцию.
В качестве альтернативного способа хеширования ключей , состоящих из символов (), можно предложить вычисление
Идеальное хеширование Идеальная хеш-функция () — такая хеш-функция, которая отображает каждый ключ из набора во множество целых чисел без коллизий. В математике такое преобразование называется инъективным отображением.
Описание Функция называется идеальной хеш-функцией для , если инъективна на . Функция называется минимальной идеальной хеш-функцией для , если является идеальной хеш-функцией и . Для целого функция называется -идеальной хеш-функцией (k-PHF) для , если для каждого имеем .
Идеальное хеширование применяется, если требуется присвоить уникальный идентификатор ключу без сохранения информации о ключе. Пример использования идеального (или скорее -идеального) хеширования: размещение хешей, связанных с данными, хранящимися в большой и медленной памяти, в небольшой и быстрой памяти. Размер блока можно выбрать таким, чтобы необходимые данные считывались из медленной памяти за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, если представление графа не умещается в основной памяти.
Универсальное хеширование Универсальное хеширование — хеширование, при котором используется не одна конкретная хеш-функция, а некоторая хеш-функция, выбираемая из заданного семейства хеш-функций по случайному алгоритму. Обычно отличается малым числом коллизий. Применяется, например, при реализации хеш-таблиц и в криптографии.
Описание Предположим, что требуется отобразить ключи из пространства в числа . На входе алгоритм получает данные из некоторого набора размерностью . Набор заранее неизвестен. Как правило, алгоритм должен обеспечить наименьшее число коллизий, чего трудно добиться, используя какую-то определённую хеш-функцию. Число коллизий можно уменьшить, если каждый раз при хешировании выбирать хеш-функцию случайным образом. Хеш-функция выбирается из определённого набора хеш-функций, называемого универсальным семейством .
Методы борьбы с коллизиями
Коллизией (иногда конфликтом или столкновением) называется случай, при котором одна хеш-функция для разных входных данных (блоков) возвращает одинаковые выходные данные (хеш-коды).