Хеширование

Процедура хеширования информации применяется при решении широкого круга разнообразных задач: в программировании при построении ассоциативных массивов, поиска дубликатов в данных, определение контрольной суммы для защиты при передаче информации [2]. В последние годы проведено много исследований по разработке новых и совершенствованию уже существующих методов хеширования. Например, Лужецкий В.А. и Барышев Ю. В. разработали конструкцию многоканального хеширования, что позволило обобщить и усовершенствовать известные подходы повышения устойчивости хеширования к мультиколлизиям[3]. Бойко А. А. и Горбенко И. Д. предложили критерии, показатели и методика оценки функций хешировния с повышенным быстродействием [4]. При этом повышение быстродействия достигается за счет распараллеливания вычислений. Еще одним направлением является применение нейронных сетей для решения задач защиты информации [6], включается-кая и хеширования данных. Значительный вклад в развитие алгоритмов хеширования также внесли Д. Кнут, В. Питерсон, и Ханс Петер Лун.
1.2. Основные понятия о хешировании
Хеширования (хеширования, англ. Hashing) - преобразование входного массива данных произвольной длины в выходной битовый строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свертывания, а их результаты называют хэшем, хэш-кодом, хэш-суммой, или дайджестом сообщения (англ. Message digest).
Хэш-функция [1], или хеш-функция [2] [3] - функция, преобразует входные данные любого (как правило большого) размера в данные фиксированного размера.
Хеш-функция используется в том числе в структурах данных - хеш-таблицах, широко применяемых в программном обеспечении для быстрого поиска данных. Хеш-функции используются для оптимизации таблиц и баз данных за счет того, что в одинаковых записях одинаковые значения хэш-функции. Такой подход поиска дубликатов эффективен в файлах большого размера. Примером этого будет нахождение подобных участков в последовательностях ДНК. Криптографическая хеш-функция позволяет легко проверить, что некоторые входные данные сопоставляются с заданным значением хеша, но, если входные данные неизвестны, намеренно трудно восстановить входное значение (или эквивалентную альтернативу), зная сохранено значение хеш-функции. Это используется для обеспечения целостности передаваемых данных и является строительным блоком для HMACs, которые обеспечивают аутентификацию сообщений.
Хеш-функции связаны (и их часто путают) с контрольной суммой, контрольными цифрами, отпечатками пальцев, рандомизации функций, кодами, исправляют ошибки, и с шифрами. Хотя эти понятия в определенной степени совпадают, каждый из них имеет свою собственную область применения и требования и является разработанным и оптимизированным по-разному.

Рисунок 1. Пример работы хеш-функции
Хэш-функция ставит в соответствие именам целое число от 0 до 15. Есть противоречие (коллизия) между «John Smith» и «Sandra Dee», которым соответствует одинаковое значение.
1.3. История возникновения хеш-функций
Дональд Кнут приписывает первую систематическую идею хеширования сотруднику IBM Ханса Петера Луна [en], который предложил хеш-кодирование в январе 1953 года.
В 1956 году Арнольд Думы [en] в своей работе «Computers and automation» первым представил концепцию хеширования такой, какой ее знает большинство программистов в наше время. Думы рассматривал хеширования, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адрес остаток от деления на простое число. [4]
Первой значительной работой, которая была связана с поиском в больших файлах, была статья Уэсли Питерсона в IBM Journal of Research and Development в 1957 году, в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Через шесть лет была опубликована работа Вернера Бухгольца, в которой в значительной степени исследовались хеш-функции. В течение нескольких последующих лет хеширования широко использовалось, однако не было опубликовано ни одной значительной работы.
В 1967 году хеширования в современном смысле упомянуто в книге Херберта Хеллерман «Принципы цифровых вычислительных систем» [5]. В 1968 году Роберт Моррис опубликовал в Communications of the ACM большой обзор о хеширования. Эта работа считается публикацией, вводящий понятие о хеширования в научный оборот и окончательно закрепляет среди специалистов термин «хеш».
К началу 1990-х годов эквивалентом термина «хеширования», благодаря работам Андрея Ершова, использовалось слово рус. «Расстановка», а для коллизий использовался термин рус. «Конфликт» (Ершов использовал «расстановки» с 1956, а также в русскоязычном издании книги Никлауса Вирта 'Алгоритмы и структуры данных» (1989) используется этот термин). Однако ни один из этих вариантов не прижился, и в литературе используется преимущественно термин «хеширования». [6]
Хеширования применяется для построения ассоциативных массивов, поиска дубликатов в сериях наборов данных, построения уникальных идентификаторов для наборов данных, контрольного суммирования с целью выявления случайных или преднамеренных ошибок при хранении или передаче для хранения паролей в системах защиты (в этом случае доступ к области памяти ' памяти, где находятся пароли, не позволяет восстановить сам пароль), при выработке электронной подписи (на практике часто подписывается не самое сообщение, а его хеш-образ).
В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем число вариантов значений входного массива. Существует множество массивов с разным содержимым, которые дают одинаковые хеш-коды - так называемые коллизии. Вероятность возникновения коллизий играет важную роль в оценке качества хеш-функций.