Архитектура хэш-функций

Две основных архитектуры – последовательная и древовидная.

Хэш-функция с последовательной архитектурой представлена на рис.3.2.

Для вычисления Н_М сообщение М разбивают на N блоков фиксированной длины (если длина сообщения М не кратна m, то оно специальным образом дополняется, причем в дополнение обязательно включается длина сообщения LM (MD –усиление)), а затем к полученным блокам М₁,М₂, …, М_N, М_N+1 последовательно применяют следующую процедуру

h_i = f (M_i, h_i-1), i=1,..., N+1

H_M = h (M) = h_N+1,

где

Н0 – фиксированный начальный вектор (стартовый вектор хэширования);

f – однонаправленная функция сжатия.

Область применения – системы связи, файлы с последовательным доступом.

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

Рис. 3.2. Хэш-функция с последовательной архитектурой

Свойства хэш-функции полностью определяются свойствами одношаговой сжимающей функции y = f (x1, x2), то есть хэш-функция является устойчивой к коллизиям, если этим свойством обладает и используемая однонаправленная функция сжатия

y = f (m1, m2),

где

m1,m2 – двоичные вектора длины х1 и х2 соответственно;

y – двоичный вектор длины L= (х1 или х2).

Требования к однонаправленной функции сжатия:

- зная m1 и m2 легко вычислить у;

- зная у вычислительно сложно определить m1 или m2;

- зная у и (m1 или m2) вычислительно сложно найти неизвестный аргумент;

- стойкость к коллизиям.

Функция сжатия может строиться на базе нелинейных битовых логических преобразований (МDx, SHA-x, RIPEMD-х) или на базе блочного симметричного шифра (ГОСТ Р34.11-94).

Дата добавления: 2013-12-13