Такой хэш не существует. Хэш-функция: что это такое, зачем нужна и какой бывает
Хеширование - это специальный метод адресации данных (некоторый алгоритм расстановки) по их уникальным ключам ( key ) для быстрого поиска нужной информации..
Базовые понятия
Хеш-таблица
Хеш-таблица представляет собой обычный массив со специальной адресацией, задаваемой некоторой функцией (Хеш-функция).
Хеш-функция
Функция, которая преобразует ключ элемента данных в некоторый индекс в таблице (хеш-таблица ), называетсяфункцией хеширования илихеш-функцией :
i = h (key );
где key - преобразуемый ключ,i - получаемый индекс таблицы, т.е. ключ отображается во множестве, например, целых чисел (хеш-адреса ), которые впоследствии используются для доступа к данным.
Хеширование таким образом – это способ, который подразумевает использование значения ключа для определения его позиции в специальной таблице..
Однако функция расстановки может для нескольких уникальных значений ключа давать одинаковое значение позицииi в хеш-таблице. Ситуация, при которой два или более ключа получают один и тот же индекс (хеш-адрес) называетсяколлизией (конфликтом) при хешировании.. Поэтому схема хеширования должна включатьалгоритм разрешения конфликтов , определяющий порядок действий, если позицияi =h (key ) оказывается уже занятой записью с другим ключом.
Имеется множество схем хеширования, различающихся и используемой хешфункцией h (key ) и алгоритмами разрешения конфликтов.
Наиболее распространенный метод задания хеш-функции: Метод деления.
Исходными данными являются: - некоторый целый ключ key и размер таблицыm . Результатом данной функции является остаток от деления этого ключа на размер таблицы. Общий вид такой функции на языке программирования С/С++:
int h (int key , int m ) {
Для m = 10 хеш-функция возвращает младшую цифру ключа.
Для m= 100 хеш-функция возвращает две младших цифры ключа.
В рассмотренных примерах хеш-функция i =h (key ) только определяет позицию, начиная с которой нужно искать (или первоначально - поместить в таблицу) запись с ключомkey . Далее необходимо воспользоваться какой – либо схемой (алгоритмом) хеширования.
Схемы хеширования
В большинстве задач два и более ключей хешируются одинаково, но они не могут занимать в хеш-таблице одну и ту же ячейку. Существуют два возможных варианта: либо найти для нового ключа другую позицию, либо создать для каждого индекса хеш-таблицы отдельный список, в который помещаются все ключи, отображающиеся в этот индекс.
Эти варианты и представляют собой две классические схемы хеширования:
хеширование методом открытой адресацией с линейным опробыванием - linear probe open addressing .
хеширование методом цепочек (со списками), или так называемое, многомерное хеширование - chaining with separate lists ;
Метод открытой адресацией с линейным опробыванием . Изначально все ячейки хеш-таблицы, которая является обычным одномерным массивом, помечены как не занятые. Поэтому при добавлении нового ключа проверяется, занята ли данная ячейка. Если ячейка занята, то алгоритм осуществляет осмотр по кругу до тех пор, пока не найдется свободное место («открытый адрес»).
Т.е. элементы с однородными ключами размещают вблизи полученного индекса.
В дальнейшем, осуществляя поиск, сначала находят по ключу позицию i в таблице, и, если ключ не совпадает, то последующий поиск осуществляется в соответствии с алгоритмом разрешения конфликтов, начиная с позицииi . .
Метод цепочек является доминирующей стратегией. В этом случаеi , полученной из выбранной хеш-функциейh (key )=i , трактуется как индекс в хеш-таблице списков, т.е. сначала ключkey очередной записи отображается на позициюi = h (key ) таблицы. Если позиция свободна, то в нее размещается элемент с ключомkey , если же она занята, то отрабатывается алгоритм разрешения конфликтов, в результате которого такие ключи помещаются в список, начинающийся вi -той ячейке хеш-таблицы. Например
В итоге имеем таблицу массива связных списков или деревьев.
Процесс заполнения (считывания) хеш-таблицы прост, но доступ к элементам требует выполнения следующих операций:
Вычисление индекса i ;
Поиск в соответствующей цепочке.
Для улучшения поиска при добавлении нового элемента можно использовать алгоритма вставки не в конец списка, а - с упорядочиванием, т.е. добавлять элемент в нужное место.
Пример реализации метода прямой адресации с линейным опробыванием . Исходными данными являются 7 записей (для простоты информационная часть состоит только из целочисленных данных), объявленного структурного типа:
int key; // Ключ
int info; // Информация
{59,1}, {70,3}, {96,5}, {81,7}, {13,8}, {41,2}, {79,9}; размер хеш-таблицы m=10.
Хеш-функцияi =h (data ) =data .key %10; т.е. остаток от деления на 10 -i .
На основании исходных данных последовательно заполняем хеш-таблицу.
Хеширование первых пяти ключей дает различные индексы (хеш-адреса):
Первая коллизия возникает между ключами 81 и 41 - место с индексом 1 занято. Поэтому просматриваем хеш-таблицу с целью поиска ближайшего свободного места, в данном случае - это i = 2.
Следующий ключ 79 также порождает коллизию: позиция 9 уже занята. Эффективность алгоритма резко падает, т.к. для поиска свободного места понадобилось 6 проб (сравнений), свободным оказался индекс i = 4.
Общее число проб такого метода от1 до n-1 пробы на элемент, гдеn- размер хеш-таблицы..
Реализация метода цепочек для предыдущего примера. Объявляем структурный тип для элемента списка (однонаправленного):
int key; // Ключ
int info; // Информация
zap*Next; // Указатель на следующий элемент в списке
На основании исходных данных последовательно заполняем хеш-таблицу, добавляя новый элемент в конец списка, если место уже занято.
Хеширование первых пяти ключей, как и в предыдущем случае, дает различные индексы (хеш-адреса): 9, 0, 6, 1, и 3.
При возникновении коллизии, новый элемент добавляется в конец списка. Поэтому элемент с ключом 41, помещается после элемента с ключом 81, а элемент с ключом 79 - после элемента с ключом 59.
Индивидуальные задания
1. Бинарные деревья. Используя программу датчик случайных чисел получить 10 значений от 1 до 99 и построить бинарное дерево.
Сделать обход:
1.а Обход слева направо: Left-Root-Right: сначала посещаем левое поддерево, затем - корень и, наконец, правое поддерево.
(Или наоборот, справа налево: Right -Root- Left)
1.б Обход сверху вниз: Root-Left-Right: посещаем корень до поддеревьев.
1.в Обход снизу вверх: Left-Right-Root: посещаем корень после поддеревьев
Приложений.
Энциклопедичный 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)) и сверяет его с полученным. Если значения совпадают - аутентификация верна.
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).
Литература
А. П. Алферов, Основы криптографии.
Брюс Шнайер, Прикладная криптография.
Аннотация: В этой лекции сформулировано понятие хеш-функции, а также приведен краткий обзор алгоритмов формирования хеш-функций. Кроме того, рассмотрена возможность использования блочных алгоритмов шифрования для формирования хеш-функции.
Цель лекции: познакомиться с понятием "хеш-функция", а также с принципами работы таких функций.
Понятие хеш-функции
Хеш-функцией (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).Хеш-функция – легко вычислимая функция, преобразующая исходное сообщения произвольной длины (прообраз) в сообщение фиксированное длины (хеш-образ), для которой не существует эффективного алгоритма поиска коллизий.
Коллизией для функции 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 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 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 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 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).
Рис.10.4. Схема алгоритма DES в режиме сцепления блоков шифра
Последний зашифрованный блок C n и есть хеш-образ сообщения T = {T 1 , T 2 , …, T n } .
1 ГОСТ 34.11-94 «Информационная технология. Криптографическая защита информации. Функция хэширования».
2 ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».
Вопросы для самопроверки
1. Дайте определение понятиям: « », « », « ».
Загрузка...
