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

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

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

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

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

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

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

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

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

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

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

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

• хорошая перемешиваемость данных
• быстрый алгоритм вычисления

Сверка данных

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

Проверка на наличие ошибок

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

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

Проверка парольной фразы

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

Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows XP . В них хранятся лишь хеш-значения парольных фраз из учётных записей пользователей.

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

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

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

Список алгоритмов

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• RIPEMD-160
• RIPEMD-320
• Snefru
• Tiger (Whirlpool
• IP Internet Checksum (RFC 1071)

Ссылки

Wikimedia Foundation . 2010 .

• Хэшан Мохэянь
• Хэш код

Смотреть что такое "Хэш-функция" в других словарях:

Хэш-функция - функция, осуществляющая хэширование массива данных посредством отображения значений из (очень) большого множества значений в (существенно) меньшее множество значений. По английски: Hash function См. также: Криптографические алгоритмы Финансовый… … Финансовый словарь

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

Односторонняя хэш-функция - хэш функция, являющаяся вычислительно необратимой функцией. По английски: One way hash function См. также: Криптографические алгоритмы Финансовый словарь Финам … Финансовый словарь

TIGER - хэш-функция - TIGER хэш функция, разработанная Росом Андерсоном и Эли Бихамом в 1996 году. Хэш функция TIGER является новой быстрой хэш функцией, которая призвана быть очень быстрой на современных компьютерах, в частности, на 64 разрядных компьютерах. TIGER… … Википедия

односторонняя хэш-функция - Для односторонней функции вычислительно невозможно найти два разных аргумента, для которых ее значения совпадают. [] Тематики защита информации EN one way hash function … Справочник технического переводчика

Tiger (хэш-функция) - Tiger хеш функция, разработанная Росом Андерсоном и Эли Бихамом в 1995 году. Tiger был предназначен для особенно быстрого выполнения на 64 разрядных компьютерах. Tiger не имеет патентных ограничений, может использоваться свободно как с… … Википедия

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

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

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

Коллизия хэш-функции - Коллизией хеш функции H называется два различных входных блока данных x и y таких, что H(x) = H(y). Коллизии существуют для большинства хеш функций, но для «хороших» хеш функций частота их возникновения близка к теоретическому минимуму. В… … Википедия

Нередко при скачивании торрентов или непосредственно самих файлов в описании стоит что-то наподобие «ad33e486d0578a892b8vbd8b19e28754» (например, в ex.ua), нередко с припиской «md5». Это хеш-код - результат, который выдает хэш-функция после обработки входящих данных. В переводе с английского хэш обозначает путаницу, марихуану, травку или блюдо из мелко нарезанного мяса и овощей. очень и очень сложно, можно сказать, что практически невозможно. Тогда возникает вопрос: «Зачем вообще нужны все эти они выдают непонятную абракадабру, которая еще и не поддается расшифровке?». Об этом и пойдет речь в данной статье.

Что такое хэш-функция и как она действует?

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

Зачем нужна хеш-функция?

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

Хэш-функции: какими они бываю т

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

1. Функция для проверки целостности информации

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

2. Криптографическая функция

Используется для защиты от (НД). Они позволяют проверить, не произошло ли искажение данных в результате НД во время передачи файлов по сети. Истинный хэш в этом случае общедоступен, а хэш полученного файла можно вычислить с помощью множества разных программ. У таких функций долгий и стабильный срок работы, а поиск коллизий (возможных совпадений результата от разных исходных данных) очень осложнен. Именно такие функции используют для хранения в БД паролей (SH1, SH2, MD5) и прочей ценной информации.

3. Функция, предназначенная для создания эффективной структуры данных

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

Хеширование

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

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

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

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

История

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

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

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

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

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

1. Быстро вычисляться;
2. Минимизировать количество коллизий

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

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

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

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

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

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

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

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

Мультипликативная схема хеширования

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

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

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

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

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

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

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

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

Описание

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

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

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

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

В хеш-таблицах

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Платой за столь высокую скорость является отсутствие криптостойкости - лёгкая возможность подогнать сообщение под заранее известную сумму. Также обычно разрядность контрольных сумм (типичное число: 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. -

12 мая 2010 в 01:28

Хэш-алгоритмы

• Информационная безопасность

Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.

О себе

Студент кафедры информационной безопасности.

О хэшировании

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

Хэш-функцией называется всякая функция h:X -> Y , легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину. X - множество всех сообщений, Y - множество двоичных векторов фиксированной длины.

Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x 1 , x 2) двух переменных, где x 1 , x 2 и y - двоичные векторы длины m , n и n соответственно, причем n - длина свертки, а m - длина блока сообщения.
Для получения значения h(M) сообщение сначала разбивается на блоки длины m (при этом, если длина сообщения не кратна m то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M 1 , M 2 ,.., M N применяют следующую последовательную процедуру вычисления свертки:

H o = v,
H i = f(M i ,H i-1), i = 1,.., N,
h(M) = H N

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

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

О статистических свойствах и требованиях

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

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

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

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

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

Это была теоретическая часть, которая пригодится нам в дальнейшем…

О популярных хэш-алгоритмах

Алгоритмы CRC16/32 - контрольная сумма (не криптографическое преобразование).

Алгоритмы MD2/4/5/6 . Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
Алгоритм MD6 - очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.

Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 - собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.

Российский стандарт - ГОСТ 34.11-94 .

В следующей статье

Обзор алгоритмов MD (MD4, MD5, MD6).

Литература

А. П. Алферов, Основы криптографии.

Брюс Шнайер, Прикладная криптография.

Например, мы можем подать на вход 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} или операции «исключающее или ». Одним из алгоритмов, работающих по такому принципу, является хеш-функция Пирсона.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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