Хеш-функции (hash functions) находят широкое применение в криптографии, особенно при построении систем цифровой подписи и различных криптографических протоколов. В этом разделе мы сформулируем основные требования к криптографически стойким хеш-функциям и рассмотрим один из способов их вычисления.
Хеш-функцией называется любая функция %%у = h(x_1 x_2...x_n)%%, которая строке (сообщению) %%x_1 x_2...x_n%% произвольной длины n ставит в соответствие целое число фиксированной длины.
Примером хеш-функции может служить контрольная сумма для сообщения. В этом случае %%h(x_1 x_2...x_n) = (х_1 + х_2 + ... + х_n) mod\, 2^w%%, где %%w%% — размер машинного слова.
Длина слова, получаемого как значение этой хеш-функции, составляет w бит независимо от длины сообщения. Контрольные суммы очень часто используются для обнаружения непреднамеренных ошибок в сообщении (при изменении одного символа контрольная сумма изменится).
Однако очень легко внести преднамеренную ошибку в сообщение и сохранить при этом значение контрольной суммы. Если бы такая хеш-функция использовалась, например, при генерации электронной подписи, то было бы очень легко изменить содержание подписанного сообщения. Поэтому рассмотренная хеш-функция не годится для криптографических применений.
Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям. Пусть х — некоторая строка (сообщение). Тогда
Отметим, что первое требование должно выполняться всегда, в противном случае хеш-функция теряет какое-либо практическое значение. Остальные требования важны для тех или иных приложений. Например, если пароли для входа в систему хранятся в виде значений соответствующих им хеш-функций, то хеш-функция должна удовлетворять второму требованию. В схеме электронной подписи актуально третье требование. Четвертое требование важно в некоторых криптографических протоколах. Заметим, что четвертое требование более сильное, чем третье (т.е. при выполнении четвертого автоматически выполняется и третье).
Разработка хеш-функции, удовлетворяющей всем четырем требованиям — задача непростая. В настоящее время предложены и практически используются хеш-функции (например, MD5, SHA-1, RIPEMD160 и др.), которые считаются отвечающими перечисленным выше требованиям (хотя это строго не доказано). Описание этих и подобных им функций усложнено в деталях и громоздко. Мы рассмотрим универсальный способ построения хешфункций на базе блоковых шифров, который представляет практический интерес, хотя получаемые хеш-функции и не являются очень быстро вычислимыми. Именно такой подход использован в российском стандарте на криптографическую хеш-функцию (ГОСТ).
Пусть дан блоковый шифр Е, который для заданного блока %%X%% и ключа К формирует шифротекст %%Y%%, %%У = Е_К(Х)%%. Мы представим два алгоритма, для которых длина слова, получаемого как значение хеш-функции, равна размеру блока в шифре, но отметим, что известны конструкции, позволяющие получать хешфункции с длинами слов, кратными размеру блока.
В первом алгоритме сообщение вначале представляется в виде последовательности блоков %%Х_1, Х_2,..., Х_n%%. Последний блок при необходимости дополняется нулями, иногда в последний блок приписывают длину сообщения в виде двоичного числа. Значение хеш-функции h получается как результат выполнения следующего итерационного процесса:
%%h%%←%%0;%%
%%FOR i = 1,2, ...,n \; DO %%
%%h%% ← %%E_h(X_i) + X_i%%
В качестве начального значения h можно использовать не нуль, а какое-либо «магическое» число, но это не имеет большого значения. В данном алгоритме значение h, полученное на предыдущей итерации, используется в качестве ключа шифра в следующей итерации. Поэтому неявно полагается, что длина ключа в шифре равна длине блока.
Однако, как мы видели при изучении шифра RC6, длина ключа может значительно превышать размер блока (в RC6 при максимальной длине блока 256 бит длина ключа может достигать 255 байт, или 2040 бит). В таких случаях более эффективен другой алгоритм. В этом алгоритме сообщение вначале представляется в виде последовательности %%X_1, X_2,..., Х_n%%, в которой размер каждого элемента равен длине ключа в шифре. Последний элемент заполняется так же, как и в первом алгоритме. Значение хеш-функции h вычисляется следующим образом:
%%h%%←%%0;%%
%%FOR \;i = 1,2, ...,m\; DO %%
%%h%% ← %%E_{X_i}(h) + h%%
Здесь уже элементы сообщения выполняют роль ключей в шифре.
Представленные алгоритмы вычисления хеш-функций удовлетворяют всем четырем требованиям, предъявляемым к криптографическим хеш-функциям, в предположении стойкости используемых блоковых шифров.
| Хеш-функции | Закон «Об электронной подписи» |