Криптографические хеш-функции

Мы уже встречались с понятием хеш-функции (hash function) в главе 4 при рассмотрении методов генерации электронной подписи. Там хеш-функции использовались в качестве «представителей» подписываемых сообщений, т.е. подпись реально вычислялась только для значения хеш-функции, но предполагалось, что это значение существенным образом зависит от всех символов сообщения и никто не может изменить сообщение так, чтобы это значение сохранилось. В этом разделе мы более точно сформулируем основные требования к криптографически стойким хеш-функциям и рассмотрим один из способов их вычисления.

Определение 5.2. Хеш-функцией называется любая функция

y=h (x ₁ x ₂… х_п),

которая строке (сообщению) x ₁ х_2…x_п произвольной длины п ставит в соответствие целое число фиксированной длины.

Примером хеш-функции может служить контрольная сумма для сообщения. В этом случае

h (x ₁ x ₂… х_п)=(х ₁ +х₂ +…+ х_п) mod 2 ^w,

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

Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям. Пусть х - некоторая строка (сообщение). Тогда

1) для любого заданного х вычисление h (x) должно выполняться относительно быстро;

2) при известном у должно быть трудно (практически невозможно) найти х, для которого у = h (x);

3) при известном сообщении х должно быть трудно найти другое сообщение х'х, такое, что h (x') =h (x);

4) должно быть трудно найти какую-либо пару различных сообщений х и х', для которых h (x') =h (x).

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

Разработка хеш-функции, удовлетворяющей всем четырем требованиям - задача непростая. В настоящее время предложены и практически используются хеш-функции (например, MD5, SHA-1, RIPEMD-160 и др., см., например, [23, 28]), которые считаются отвечающими перечисленным выше требованиям (хотя это строго не доказано). Описание этих и подобных им функций усложнено в деталях и громоздко. Мы рассмотрим универсальный способ построения хеш-функций на базе блоковых шифров, который представляет практический интерес, хотя получаемые хеш-функции и не являются очень быстро вычислимыми. Именно такой подход использован в российском стандарте на криптографическую хеш-функцию (ГОСТ Р34.11-94 [7]).

Пусть дан блоковый шифр Е, который для заданного блока X и ключа К формирует шифротекст Y,

Y=E _K(X).

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

В алгоритме сообщение вначале представляется в виде последовательности блоков Х ₁, Х ₂ ,…,Х_п. Последний блок при необходимости дополняется нулями, иногда в последний блок приписывают длину сообщения в виде двоичного числа. Значение хеш-функции h получается как результат выполнения следующего итерационного процесса:

h 0;

FOR i= 1,2, ...,п DO '

hE_h (X_i) X_i.

В качестве начального значения h можно использовать не нуль, а какое-либо «магическое» число, но это не имеет большого значения. В данном алгоритме значение h, полученное на предыдущей итерации, используется в качестве ключа шифра в следующей итерации. Поэтому неявно полагается, что длина ключа в шифре равна длине блока. Однако, как мы видели при изучении шифра RC6, длина ключа может значительно превышать размер блока (в RC6 при максимальной длине блока 256 бит длина ключа может достигать 255 байт, или 2040 бит).

Дата добавления: 2014-01-11