Блочно-итерационные и шаговые функции.

Пусть X - множество сообщений (последовательности символов некоторого алфавита, как правило, двоичного). Пусть Y — множество двоичных векторов фиксированной длины.

Хэш-функциейназывается всякая функция h: X ® Y, легко вычислимая и такая, что для любого сообщения М значение h(M) = Н (свертка) имеет фиксированную битовую длину.

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

Как правило, хэш-функции строят на основе так называемых одношаговых сжимающих функций у = f(x_l, х₂) двух переменных, где х, и у - двоичные векторы длины т и п соответственно, причем п — длина свертки. Для получения значения h(M) сообщение М сначала разбивается на блоки длины т (при этом если длина сообщения не кратна т, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M₁, М₂,.., M_N применяют следующую последовательную процедуру вычисления свертки:

H₀ = v,

H_i = f(М_i, H_i-1), i = 1,...,N,

h(M) = H_N.

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

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

Бесключевые хэш-функции называются кодами обнаружения ошибок (modification detection code (MDC) или manipulation detection code, message integrity code (MIC)). Они дают возможность с помощью дополнительных средств (например, шифрования, использования защищенного канала или цифровой подписи) гарантировать целостность данных. Эти хэш-функции могут применяться в системах как с доверяющими, так и не доверяющими друг другу пользователями.