Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
В криптографии хэш-функции применяются для решения следующих задач:
— построения систем контроля целостности данных при их передаче или хранении,
— аутентификации источника данных.
При решении первой задачи для каждого набора данных вычисляется значение хэш-функции (называемое кодом аутентификации сообщения или имитовставкой), которое передается или хранится вместе с самими данными. При получении данных пользователь вычисляет значение свертки и
347
І лава 13
сравнивает его с имеющимся контрольным значением. Несовпадение говорит о том, что данные были изменены.
Хэш-функция, служащая для выработки имитовставки, должна позволять (в отличие от обычной контрольной суммы) осуществлять обнаружение не только случайных ошибок в наборах данных, возникающих при их хранении и передаче, но и сигнализировать об активных атаках злоумышленника, пытающегося осуществить навязывание ложной информации. Для того чтобы злоумышленник не смог самостоятельно вычислить контрольное значение свертки и тем самым осуществить успешную имитацию или подмену данных, хэш-функция должна зависеть от секретного, не известного злоумышленнику, параметра —- ключа пользователя. Этот ключ должен быть известен передающей и проверяющей сторонам. Такие хэш-функции будем называть ключевыми.
Имитовставки, формируемые с помощью ключевых хэш-функций, не должны позволять противнику создавать поддельные (сфабрикованные) сообщения (fabrication) при атаках типа имитация (impersonation) и модифицировать передаваемые сообщения (modification) при атаках типа “подмена” (substitution).
При решении второй задачи — аутентификации источника данных — мы имеем дело с не доверяющими друг другу сторонами. В связи с этим подход, при котором обе стороны обладают одним и тем же секретным ключом, уже неприменим. В такой ситуации применяют схемы цифровой подписи, позволяющие осуществлять аутентификацию источника данных. Как правило, при этом сообщение, прежде чем быть подписано личной подписью, основанной на секретном ключе пользователя, “сжимается” с помощью хэш-функции, выполняющей функцию кода обнаружения ошибок (см. далее). В данном случае хэш-функция не зависит от секретного ключа и может быть фиксирована и известна всем. Основными требованиями к ней являются гарантии невозможности подмены подписанного документа, а также подбора двух различных
348
Хэш-функции
сообщений с одинаковым значением хэш-функции (в этом случае говорят, что такая пара сообщений образует коллизию).
Формализуя сказанное, введем следующее определение. Обозначим через X множество, элементы которого будем называть сообщениями. Обычно сообщения представляют собой последовательности символов некоторого алфавита, как правило, двоичного. Пусть Y — множество двоичных векторов фиксированной длины.
Хэш-функцией называется всякая функция h: X -> Г, легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину.
Обычно число возможных сообщений значительно превосходит число возможных значений сверток, в силу чего для каждого значения свертки имеется большое множество прообразов, то есть сообщений с заданным значением хэш-функции. Заметим, что при случайном и равновероятном выборе сообщений условие равномерности распределения значений хэш-функции эквивалентно наличию одинакового числа прообразов для каждого значения свертки.
Как правило, хэш-функции строят на основе так называемых одношаговых сжимающих функций у = /(X19X2) двух переменных, где X1 и у — двоичные векторы длины т и п соответственно, причем п — длина свертки. Для получения значения h(M) сообщение M сначала разбивается на блоки длины т (при этом если длина сообщения не кратна /??, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M1, M 2M N применяют следующую последовательную процедуру вычисления свертки:
H0=V,
Н, =/(М„//,_,), і = Ii..., Nt (1)
h(M) = HN.
349
І лава 13
Здесь v — некоторый фиксированный начальный вектор. Если функция / зависит от ключа, то этот вектор можно положить равным нулевому вектору. Если же функция / не зависит от ключа, то для исключения возможности перебора коротких сообщений (при попытках обращения хэш-функции) этот вектор можно составить из фрагментов, указывающих дату, время, номер сообщения и т. п.
При таком подходе свойства хэш-функции h полностью определяются свойствами одношаговой сжимающей функции /
Особо выделяют два важных типа криптографических хэш-функций — ключевые и бесключевые. Первые применяются в системах с симметричными ключами. Ключевые хэш-функции называют кодами аутентификации сообщений (KAC) (message authentication code (MAC)). Они дают возможность без дополнительных средств гарантировать как правильность источника данных, так и целостность данных в системах с доверяющими друг другу пользователями.
Бесключевые хэш-функции называются кодами обнаружения ошибок (modification detection code (MDC) или manipulation detection code, message integrity code (MIC)). Они дают возможность с помощью дополнительных средств (например, шифрования, использования защищенного канала или цифровой подписи) гарантировать целостность данных. Эти хэш-функции могут применяться в системах как с доверяющими, так и не доверяющими друг другу пользователями. Рассмотрим их более подробно.
