Алгоритмы хэширования в задачах на строки. Алгоритмы хеширования данных

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

Цель лекции: познакомиться с понятием "хеш-функция", а также с принципами работы таких функций.

Понятие хеш-функции

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

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

Смысл хеш-функции состоит в определении характерного признака прообраза – значения хеш-функции. Это значение обычно имеет определенный фиксированный размер, например, 64 или 128 бит. Хеш-код может быть в дальнейшем проанализирован для решения какой-либо задачи. Так, например, хеширование может применяться для сравнения данных: если у двух массивов данных хеш-коды разные, массивы гарантированно различаются; если одинаковые - массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет из-за того, что количество значений хеш-функций всегда меньше, чем вариантов входных данных. Следовательно, существует множество входных сообщений, дающих одинаковые хеш-коды (такие ситуации называются коллизиями ). Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

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

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

Например, пусть исходное сообщение, переведенное в цифровой вид, было следующим (в шестнадцатеричном формате):

Переведем сообщение в двоичный вид, запишем байты друг под другом и сложим биты в каждом столбике по модулю 2:

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Результат (0110 0101 (2) или 65 (16) ) и будет значением хеш-функции.

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

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

Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям:

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

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

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

h i =H(M i ,h i-1),

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

В результате выход хеш-функции h n является функцией от всех n блоков входного сообщения.

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

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

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

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

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

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

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

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

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

Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является относительно низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них – MD5, SHA-1, SHA-2 и ГОСТ Р 34.11-94).

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

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

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

История

Дональд Кнут приписывает первую систематическую идею хеширования сотруднику IBM Ханса Петера Луна, предложил хеш в январе 1953 года.

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

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

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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм можно описать следующим псевдокодом, который получает на вход строку и использует таблицу перестановок

h: = 0 For each c in W loop index:= h xor ch:= T End loop Return h

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

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

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

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

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

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

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

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

Данные требования зависят друг от друга:

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

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

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

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

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

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

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

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

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

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

Методы сжатия преобразуемых данных на основе однонаправленных ХЭШ-функций

Хэш-функция (hash, hash-function) – это преобразование, получающее из данных произвольной длины некое значение (свертку) фиксированной длины. Простейшими примерами являются контрольные суммы (например, crc32). Бывают:

· криптографические хэши;

· программистские хэши.

Криптографический хэш отличается от программистского следующими двумя свойствами: необратимостью и свободностью от коллизий. Обозначим:

m - исходные данные,

h(m) – хэш-функция от них.

Необратимость означает, что если известно число h0, то трудно подобрать m такое, что h(m) = h0.

Свободность от коллизий означает, что трудно подобрать такие m1 и m2, что m1 не равно m2, но h(m1) = h(m2).

Криптографические хэш-функции разделяются на два класса:

Хэш-функции без ключа (MDC (Modification (Manipulation) Detect Code) - коды),

Хэш-функции c ключом (MАC (Message Authentication Code) - коды).

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

Слабой хэш-функцией называется односторонняя функция H(x), удовлетворяющая следующим условиям:

1. аргумент х может быть строкой бит произвольной длины;

2. значение h(x) должно быть строкой бит фиксированной длины;

3. значение h(x) легко вычислить;

4. для любого фиксированного x вычислительно невозможно найти другой x" ≠ x, такой что h(x")=h(x).

Пара x" ≠ x, когда h(x")=h(x) называется коллизией хэш-функции.

Сильной хэш-функцией называется односторонняя функция h(x), удовлетворяющая условиям 1-4 для слабой хэш-функции и свойству 5:

5. вычислительно невозможно найти любую пару x" ≠ x, такую, что h(x")=h(x).
Поскольку из свойств 1-2 следует, что множество определения хэш-функции значительно шире множества значений, то коллизии должны существовать. Свойство 4 требует, чтобы найти их для заданного значения х было практически невозможно. Требование 5 говорит о том, что у сильной хэш-функции вычислительно невозможно вообще найти какую-либо коллизию.

Существует несколько алгоритмов вычисления хэш-функций

MD2 (Message Digest) – алгоритм криптографической свертки. Порождает блок длиной 128 бит от сообщения произвольной длины. Общая схема работы MD2:

a. дополнение текста сообщений до длины, кратной 128 бит;

b. вычисление 16-битной контрольной суммы, старшие разряды отбрасываются;

c. добавление контрольной суммы к тексту;

d. повторное вычисление контрольной суммы.

Алгоритм MD2 очень медленный, поэтому чаще применяются MD4, MD5, SHA (Secure Hash Algorithm). Результирующий хэш имеет длину 160 бит.

ГОСТ Р34.11-94. Российский алгоритм. Длина свертки - 256 бит (очень удобно для формирования по паролю ключа для ГОСТ 28147-89).

Национальный институт стандартов и технологий (НИСТ) США на своем веб-сайте http://www.nist.gov/sha/ опубликовал спецификации новых алгоритмов хеширования SHA-256, SHA-384 и SHA-512, цель которых - обеспечить уровень криптостойкости хэша, соответствующий длинам ключей нового стандарта шифрования DES.

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

До настоящего времени наиболее популярными хеш-функциями были созданные Райвистом MD4 и MD5, генерирующие хэш-коды длиной n=128, и алгоритм SHA-1, разработанный в АНБ США и порождающий хэш-код длиной n=160.

ГОСТ Р34.10-94 «Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма».

Приложений.

Энциклопедичный YouTube

1 / 5

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

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

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

Принципы построения

Итеративная последовательная схема

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

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

Сжимающая функция на основе симметричного блочного алгоритма

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

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

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

Применения

Электронная подпись

Пусть некий клиент, с именем name , производит аутентификацию по парольной фразе, pass , на некоем сервере. На сервере хранится значение хеш-функции H (pass , R 2) , где R 2 - псевдослучайное, заранее выбранное число. Клиент посылает запрос (name , R 1 ), где R 1 - псевдослучайное, каждый раз новое число. В ответ сервер посылает значение R 2 . Клиент вычисляет значение хеш-функции H (R 1 , H (pass , R 2)) и посылает его на сервер. Сервер также вычисляет значение H (R 1 , H (pass , R 2)) и сверяет его с полученным. Если значения совпадают - аутентификация верна.

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

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

Коллизией для функции h называется пара значений x, y, x ≠ y , такая, что h(x) = h(y) . Т.о. хеш-функция должна обладать следующими свойствами:

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

Для данного аргумента x невозможно найти другой аргумент y такой, что h(x) = h(y) . Такие хеш-функции называют стойкими в смысле вычисления коллизий или стойкими в слабом смысле .

В случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то это значение называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой .

На практике хеш-функции используют в следующих целях:

Для ускорения поиска данных в БД;

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

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

Рис.10.1. Процедура вычисления значения хеш-функции

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

2) Для инициализации процедуры хеширования используется синхропосылка y 0 .

3) Прообраз X разбивается на n блоков x i (i = 1 .. n) фиксированной длины L бл , над которыми выполняется однотипная процедура хеширования f(y i-1 , x i) , зависящая от результата хеширования предыдущего блока y i-1 .

4) Хеш-образом h(T) исходного сообщения Т будет результат процедуры хеширования y n , полученный после обработки последнего блока x n .

10.2. MD5

MD5 (англ. Message Digest 5) – 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 г. Является улучшенной в плане безопасности версией MD4 .

Ниже приведен алгоритм вычисления хеша.

1. Выравнивание потока.

В конец исходного сообщения, длиной L , дописывают единичный бит, затем необходимое число нулевых бит так, чтобы новый размер L" был сравним с 448 по модулю 512 (L’ mod 512 = 448). Добавление нулевых бит выполняется, даже если новая длина, включая единичный бит, уже сравнима с 448.

2. Добавление длины сообщения.

К модифицированному сообщению дописывают 64-битное представление длины данных (количество бит в сообщении). Т.е. длина сообщения T становится кратной 512 (T mod 512 = 0). Если длина исходного сообщения превосходит 2 64 - 1, то дописывают только младшие 64 бита. Кроме этого, для указанного 64-битного представления длины вначале записываются младшие 32 бита, а затем старшие 32 бита.

3. Инициализация буфера.

Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения (шестнадцатеричное представление):

A = 67 45 23 01;
B = EF CD AB 89;
C = 98 BA DC FE;
D = 10 32 54 76.

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

4. Вычисление хеша в цикле.

Исходное сообщение разбивается на блоки T , длиной 512 бит. Для каждого блока в цикле выполняется процедура, приведенная на рис.10.2. Результат обработки всех блоков исходного сообщения в виде объединения 32-битных значений переменных ABCD и будет являться хешем.

Рис.10.2. Шаг основного цикла вычисления хеша

В каждом раунде над переменными ABCD и блоком исходного текста Т в цикле (16 итераций) выполняются однотипные преобразования по следующей схеме.

Рис.10.3. Одна итерация цикла раунда

Условные обозначения.

1) RF - раундовая функция, определяемая по следующей таблице.

Таблица 10.1. Раундовые функции RF

2) t j - j-ая 32-битовая часть блока исходного сообщения Т с обратным порядком следования байт;

3) k i - целая часть константы, определяемой по формуле

k i = 2 32 * | sin(i + 16 * (r - 1)) |, (10.1)

где i – номер итерации цикла (i = 1..16);
r – номер раунда (r = 1..4).

Аргумент функции sin измеряется в радианах.

4) ⊞ – сложение по модулю 2 32 .

5) <<< s i – циклический сдвиг влево на s i разрядов.

Используемая 32-битовая часть блока исходного сообщения t j и величина циклического сдвига влево s i зависят от номера итерации и приведены в следующей таблице.

Таблица 10.2. Величины, используемые на шаге цикла раунда

№ итерации		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Раунд 1	t j	t 1	t 2	t 3	t 4	t 5	t 6	t 7	t 8	t 9	t 10	t 11	t 12	t 13	t 14	t 15	t 16
Раунд 1	s i	7	12	17	22	7	12	17	22	7	12	17	22	7	12	17	22
Раунд 2	t j	t 2	t 7	t 12	t 1	t 6	t 11	t 16	t 5	t 10	t 15	t 4	t 9	t 14	t 3	t 8	t 13
Раунд 2	s i	5	9	14	20	5	9	14	20	5	9	14	20	5	9	14	20
Раунд 3	t j	t 6	t 9	t 12	t 15	t 2	t 5	t 8	t 11	t 14	t 1	t 4	t 7	t 10	t 13	t 16	t 3
Раунд 3	s i	4	11	16	23	4	11	16	23	4	11	16	23	4	11	16	23
Раунд 4	t j	t 1	t 8	t 15	t 6	t 13	t 4	t 11	t 2	t 9	t 16	t 7	t 14	t 5	t 12	t 3	t 10
Раунд 4	s i	6	10	15	21	6	10	15	21	6	10	15	21	6	10	15	21

После 4 раундов новое (модифицированное) значение каждой из переменных ABCD складывается (⊞ ) с исходным (значением переменной до 1-го раунда).

5. Перестановка байт в переменных ABCD . После обработки всех блоков исходного сообщения для каждой переменной выполняется обратная перестановка байт.

Поиск коллизий.

В 2004 г. китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии.

10.3. Применение шифрования для получения хеш-образа

Для выработки устойчивого к коллизиям хеш-образа могут применяться специальные режимы, предусмотренные в блочных шифрах (например, сцепление блоков шифра у ), или в самой хеш-функции, как составная часть, может использоваться один из режимов блочного шифра (например, составной часть хеш-функции по ГОСТ 34.11-94 1 является режим простой замены алгоритма криптографического преобразования по 2).

Напомним что в случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то хеш-образ называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой .

В качестве примера приведем режим (сцепление блоков шифра - Cipher Block Chaining).