Хэш-функции и блочные шифры

Рассмотрим один общий метод построения хэш-функций. Пусть – любая функция, V_j – векторное пространство над полем F₂

при некоторых натуральных . Требуется построить функцию

.

Сообщение разбивается на блоки

,

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

.

Функцию часто получают применением стойкого блочного шифра. Основная идея использования здесь шифра заключается в том, что трудно вычислить ключ, зная открытый текст и соответствующий ему шифртекст. То есть трудно восстановить из равенства , где известны. Иначе говоря, функция является однонаправленной при фиксированном . Пусть для дальнейшего и имеется блочный шифр . Тогда в качестве при берут

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

Общий рецепт таков. В качестве выбирать функцию, для которой трудно найти коллизию. То есть для должно выполняться условие . по-видимому, для функций (1) условие выполнено. Очевидно, что для функций

и

при постоянном это условие не выполняется.