Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Построение и использование хеш-функций





 

Под термином хеш-фунция понимается функция, отображающая электронные сообщения произвольной длины (иногда длина сообщения ограничена, но достаточно большим числом), в значения фиксированной длины. Последние часто называют хеш-кодами. Таким образом, у всякой хеш-функции h имеется большое количество коллизий, т.е. пар значений х и у таких, что h(x)=h(y).Основное требование, предъявляемое криптографическими приложениями к хеш-функциям, состоит в отсутствии эффективных алгоритмов поиска коллизий. Хеш-функция, обладающая таким свойством, называется хеш-функцией, свободной от коллизий. Кроме того, хеш-функция должна быть односторонней, т.е. функцией, по значению которой вычислительно трудно найти ее аргумент, в то же время, функцией, для аргумента которой вычислительно трудно найти другой аргумент, который давал бы то же самое значение функции [16].

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



Введем следующие обозначения Хеш-функция h обозначается как h(α) и h(α,β) для одного и двух аргументов, соответственно. Хеш-код функции h обозначается как Н. При этом Н0 = 1 обозначает начальное значение (вектор инициализации) хеш-функции. Под обозначением будет пониматься операция сложения по модулю 2 или логическая операция XOR («Исключающая ИЛИ»). Результат шифрования блока В блочным шифром на ключе k обозначается Ek(B).

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

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

где сообщение М разбито на n 64-битных блока.

Хеш-кодом данной хеш-функции является значение Н = h(M,I)= Нп.

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

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

В качестве примера можно привести хеш-функции МDС2 и MDC4 фирмы IBM. Данные хеш-функции используют блочный шифр (в оригинале DES) для получения хеш-кода, длина которого в 2 раза больше длины блока шифра. Алгоритм MDC2 работает несколько быстрее, чем MDC4, но представляется несколько менее стойким.

В качестве примера хеш-функций, построенных на основе вычислительно трудной математической задачи, можно привести функцию из рекомендаций МККТТ Х.509.

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

Следует отметить, что задача разложения числа на простые множители эквивалентна следующей труднорешаемой математической задаче. Пусть n = pq произведение двух простых чисел р и q. В этом случае можно легко вычислить квадрат числа по модулю п: x2(mod n), однако вычислительно трудно извлечь квадратный корень по этому модулю.

Таким образом, хеш-функцию МККТТ Х.509 можно записать следующим образом:

где .

Длина блока Mi представляется в октетах, каждый октет разбит пополам и к каждой половине спереди приписывается полуоктет, состоящий из двоичных единиц: n – произведение двух больших (512-битных) простых чисел р и q.

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

 

Пример 9.14.Получить хеш-код для сообщения «HASHING» при помощи хеш-функции Х.509 с параметрами р = 17, q = 19.

Порядок вычисления хеш-кода:

а) получить значения модуля: n = pq = 323;

б)представить сообщение «HASHING» в виде символов ASCII:

в) представить коды ASCII битовой строкой:

г) разбить байт пополам (разбиение октета на полуоктеты), добавить в начало полубайта единицы и получить хешируемые блоки Мi:

 

 

д) выполнить итеративные шаги:

первая итерация:

M1 = 11110100

H0 = I = 00000000

H0 M1 = 111101002 = 24410

[(H0 M1)]2(mod 323) = 2442(mod323) = 104

H1 = 10410 = 011010002

вторая итерация:

М2 = 11111000

H1 = 01101000

H1 М2 = 100100002 = 14410

[(H1 М2)]2(mod 323) = I442(mod323) = 64

H2 = 6410 = 010000002

………… … ……….

i-я итерация...

Пример легко продолжить самостоятельно.

Пример 9.15 (упрощенный вариант).Хешируемое слово «ДВА». Коэффициенты р =7, q = 3. Вектор инициализации Н0 = 1 выберем равным 6 (выбирается случайным образом). Определим n = pq = 7·3 = 21. Слово «ДВА» в числовом эквиваленте можно представить как 531 (по номеру буквы в алфавите). Тогда хеш-код сообщения 531 получается следующим образом:

первая итерация:

М1 + Н0 = 5 + 6 = 11; [M1 + Н0]2 (mod n) = 112 (mod 21) = 16 = Н1;

вторая итерация:

М2 + Н1= 3 + 16 = 19; [M2 + Н1]2 (mod n) = 192 (mod 21) = 4 = Н2;

третья итерация:

М3 + Н2 = 1 + 4 = 5; [М3 + Н2]2 (mod п) = 52 (mod 21) = 4 = Н3.

В итоге получаем хеш-код сообшения «ДВА», равный 4.

 









Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2021 zdamsam.ru Размещенные материалы защищены законодательством РФ.