Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
122
Добавлен:
02.05.2014
Размер:
142.85 Кб
Скачать

Лекция 19. Хэш-функции и генераторы псч

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

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

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

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

Значение хэш-функции называется хэш-кодом.

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

Эти функции являются вектор-функциями от двух переменных вида , где аргументы являются двоичными векторами размерности m, а значение функции – вектор размерности n. Величина n< m является длиной хэш-кода.

Для вычисления хэш-кода сообщение M дополняется тем или иным образом до длины кратной m и разбивается на блоки . Затем вычисляется последовательность итераций: , , , где - фиксированный вектор (т.н. вектор инициализации).

В качестве хэш-кода принимается значение .

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

Встречается также название – ключевая хэш-функция. В этом случае значение хэш-кода называется кодом аутенификации сообщения и имеет общепринятую аббревиатуру МАС.

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

, , , .

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

, .

Вторая функция называется функцией Девис-Мейера.

В ряде случаев вместо блоков размера m используются блоки вида размера n, где n – длина ключа K, например:

- функция Матиас-Мейера-Осеаса,

- функция Миагуччи-Принеля.

В реальных хэш-функциях, например, MD-5, SHA-1 применяются сложные одношаговые функции сжатия.

19.2. Алгоритм нмас.

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

В компьютерных системах и сетях используется типовой алгоритм вычисления кода МАС, с использованием произвольной встроенной функции хэширования h. Исходными данными является сообщение М и ключ К (рассматриваемые как битовые строки.

Алгоритм вычисления кода МАС можно выразить формулой

.

В правой части запятая означает конкатенацию битовых строк.

В сообщение М входят биты дополнения, требуемые встроенной функцией хэширования. Пусть количество b битов в блоке сообщения М кратно восьми и n – размер хэш-кода функции h, n<b. Используются ключи с длиной не меньше n. Если длина ключа К превосходит n, то используется ключ h(K).

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

Строка получается с помощью гаммирования расширенного ключа двоичной периодической гаммой g.

При этом g1=00110110, g2=01011010.

Соседние файлы в папке Лекции по криптологии