|
|
Построение и использование хеш-функций
Под термином хеш-фунция понимается функция, отображающая электронные сообщения произвольной длины (иногда длина сообщения ограничена, но достаточно большим числом), в значения фиксированной длины. Последние часто называют хеш-кодами. Таким образом, у всякой хеш-функции h имеется большое количество коллизий, т.е. пар значений х и у таких, что h (x) =h (y).Основное требование, предъявляемое криптографическими приложениями к хеш-функциям, состоит в отсутствии эффективных алгоритмов поиска коллизий. Хеш-функция, обладающая таким свойством, называется хеш-функцией, свободной от коллизий. Кроме того, хеш-функция должна быть односторонней, т.е. функцией, по значению которой вычислительно трудно найти ее аргумент, в то же время, функцией, для аргумента которой вычислительно трудно найти другой аргумент, который давал бы то же самое значение функции [16]. Схемы электронной цифровой подписи – основная сфера применения хеш-функций. Поскольку используемые на практике схемы электронной подписи не приспособлены для подписания сообщений произвольной длины, а процедура, состоящая в разбиении сообщения на блоки и генерации подписи для каждого блока по отдельности, крайне неэффективна, единственным разумным решением представляется применение схемы подписи к хеш-коду сообщения. Таким образом, хеш-функции вместе со схемами электронной цифровой подписи предназначены для решения задач обеспечения целостности и достоверности передаваемых и хранимых на носителях информации электронных сообщений. В прикладных информационных системах требуется применение так называемых криптографически стойких хеш-функций. Под термином «криптографически стойкая хэш-функция» понимается функция h,которая является односторонней и свободной от коллизий. Введем следующие обозначения Хеш-функция h обозначается как h (α) и h (α,β) для одного и двух аргументов, соответственно. Хеш-код функции h обозначается как Н. При этом Н 0 = 1 обозначает начальное значение (вектор инициализации) хеш-функции. Под обозначением Для лучшего понимания дальнейшего материала приведем небольшой пример построения хеш-функции Предположим нам необходимо подписать при помощи заданного алгоритма электронной цифровой подписи достаточно длинное сообщение М. Вкачестве шифрующего преобразования в хеш-функции будет использоваться процедура шифра DES с ключом k. Тогда, чтобы получить хеш-код Н сообщения М при помощи хеш-функции h,необходимо выполнить следующую итеративную операцию:
где Хеш-кодом данной хеш-функции является значение Н = h (M, I)= Нп. Таким образом, на вход схемы электронной цифровой подписи вместо длинного сообщения М (как правило, несколько сотен или тысяч байтов) подается хэш-код Hn, длина которого ограничена длиной блока шифра DES, т.е. 64 битами. При этом в силу криптографической стой кости используемой хеш-функции практическая стойкость самой схемы подписи будет оставаться той же, что и при подписи сообщения М,в то время как эффективность всего процесса подписи электронного сообщения будет резко увеличена. Были предприняты попытки построения хеш-функций на базе блочного шифра с размером хеш-кода в k раз (как правило, k = 2) большим, чем размер блока алгоритма шифрования. В качестве примера можно привести хеш-функции МDС2 и MDC4 фирмы IBM. Данные хеш-функции используют блочный шифр (в оригинале DES) для получения хеш-кода, длина которого в 2 раза больше длины блока шифра. Алгоритм MDC2 работает несколько быстрее, чем MDC4, но представляется несколько менее стойким. В качестве примера хеш-функций, построенных на основе вычислительно трудной математической задачи, можно привести функцию из рекомендаций МККТТ Х.509. Криптографическая стойкость данной функции основана на сложности решения следующей труднорешаемой теоретико-числовой задачи. Задача умножения двух больших (длиной в несколько сотен битов) простых чисел является простой с вычислительной точки зрения, в то время как факторизация (разложение на простые множители) полученного произведения является труднорешаемой задачей для указанных размерностей. Следует отметить, что задача разложения числа на простые множители эквивалентна следующей труднорешаемой математической задаче. Пусть n = pq произведение двух простых чисел р и q. В этом случае можно легко вычислить квадрат числа по модулю п: x 2(mod n), однако вычислительно трудно извлечь квадратный корень по этому модулю. Таким образом, хеш-функцию МККТТ Х.509 можно записать следующим образом:
где Длина блока Mi представляется в октетах, каждый октет разбит пополам и к каждой половине спереди приписывается полуоктет, состоящий из двоичных единиц: n – произведение двух больших (512-битных) простых чисел р и q. Ниже приведен числовой пример использования данной хеш-функции в его упрощенном варианте.
Пример 9.14. Получить хеш-код для сообщения «HASHING» при помощи хеш-функции Х.509 с параметрами р = 17, q = 19. Порядок вычисления хеш-кода: а) получить значения модуля: n = pq = 323; б)представить сообщение «HASHING» в виде символов ASCII:
в) представить коды ASCII битовой строкой:
г) разбить байт пополам (разбиение октета на полуоктеты), добавить в начало полубайта единицы и получить хешируемые блоки Мi:
д) выполнить итеративные шаги: первая итерация: M 1 = 11110100
H 0 = I = 00000000 H 0 [(H 0 H 1 = 10410 = 011010002 вторая итерация: М 2 = 11111000
H 1 = 01101000 H 1 [(H 1 H 2 = 6410 = 010000002 ………… … ………. i -я итерация... Пример легко продолжить самостоятельно.
Пример 9.15 (упрощенный вариант). Хешируемое слово «ДВА». Коэффициенты р =7, q = 3. Вектор инициализации Н 0 = 1 выберем равным 6 (выбирается случайным образом). Определим n = pq = 7·3 = 21. Слово «ДВА» в числовом эквиваленте можно представить как 531 (по номеру буквы в алфавите). Тогда хеш-код сообщения 531 получается следующим образом: первая итерация: М 1 + Н 0 = 5 + 6 = 11; [ M 1 + Н 0]2 (mod n) = 112 (mod 21) = 16 = Н 1; вторая итерация: М 2 + Н 1= 3 + 16 = 19; [ M 2 + Н 1]2 (mod n) = 192 (mod 21) = 4 = Н 2; третья итерация: М 3 + Н 2 = 1 + 4 = 5; [ М 3 + Н 2]2 (mod п) = 52 (mod 21) = 4 = Н 3. В итоге получаем хеш-код сообшения «ДВА», равный 4.
  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
будет пониматься операция сложения по модулю 2 или логическая операция XOR («Исключающая ИЛИ»). Результат шифрования блока В блочным шифром на ключе k обозначается Ek (B).
сообщение М разбито на n 64-битных блока.
.
