Алгоритмы хэширования

Алгоритмы хэширования

Криптографическими методами можно обеспечить не только конфиденциальность, но и проконтролировать целостность передаваемых или хранимых данных. Контроль целостности в основном осуществляется путем расчета некоторой "контрольной суммы" данных. На сегодняшний день известно множество алгоритмов, рассчитывающих контрольные суммы передаваемых данных. Проблема простых алгоритмов вычисления контрольной суммы состоит в том, что достаточно легко подобрать несколько массивов данных, имеющих одинаковую контрольную сумму. Криптографически стойкие контрольные суммы вычисляются как результат применения к исходному тексту так называемой хэш-функции. Под этим термином понимаются функции, отображающие сообщения произвольной длины (иногда длина сообщения ограничена, но достаточно велика) в значения фиксированной длины [212]. Последние часто называют хэш-кодами, или дайджестами, сообщений. Хэш-функции - это необходимый элемент ряда криптографических схем.

Главными свойствами "хорошей" в криптографическом смысле хэш-функции являются свойство необратимости, свойство стойкости к коллизиям и свойство рассеивания. Необратимость означает, что вычисление обратной функции (то есть восстановление значения аргумента по известному значению функции) оказывается невозможно теоретически или (в крайнем случае) невозможно вычислительно. Свойство стойкости к коллизиям хэш-функции H выражается в невозможности найти два разных сообщения T₁ и T₂ с одинаковым результатом преобразования H(T₁) = H(T₂). Хэш-код может быть повторно получен для того же сообщения любым пользователем, но практически невозможно создать разные сообщения для получения одного и того же хэш-кода сообщения. Значение хэш-функции всегда имеет фиксированную длину, а на длину исходного текста не накладывается никаких ограничений. Свойство рассеивания требует, чтобы минимальные изменения текста, подлежащего хэшированию, вызывали максимальные изменения в значении хэш-функции [37].

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

Хэш-функция может использоваться для создания так называемого кода аутентификации сообщения на основе вычисления хэша HMAC (Hash Message Authentication Checksum). Если отправитель посылает сообщение и его HMAC получателю, то последний может повторно вычислить HMAC, чтобы проверить, не были ли данные случайно изменены при передаче. Сторонний наблюдатель может перехватить сообщение отправителя и заменить его на новое, но, не зная секретного ключа, не имеет возможности рассчитать соответствующий HMAC. Если получатель доверяет отправителю, то принимает HMAC как подтверждение подлинности его сообщения.

Обычно коды HMAC используются только для быстрой проверки того, что содержимое не было изменено при передаче. Для создания уникальной, подлежащей проверке подписи необходим другой способ - он заключается в шифровании хэш-кода сообщения при помощи секретного ключа лица, поставившего подпись. В этом случае хэш-функция используется в схемах электронной цифровой подписи (ЭЦП). Поскольку применяемые на практике схемы электронной подписи не приспособлены для подписания сообщений произвольной длины, а процедура разбиения сообщения на блоки и генерации подписи для каждого блока по отдельности крайне неэффективна, - схему подписи применяют к хэш-коду сообщения. Очевидно, что наличие эффективных методов поиска коллизий для хэш-функции подрывает стойкость протокола электронной подписи [212]. Хэш-функции используются также в некоторых протоколах аутентификации для снижения их коммуникационной сложности, то есть для уменьшения длин пересылаемых сообщений, а также в некоторых других криптографических протоколах.

Существует множество алгоритмов, реализующих хэш-функции. К ним относятся алгоритмы вычисления хэш-кодов, созданные Роном Ривестом (MD2, MD5), SHA и его вариант SHA1, российский алгоритм, описываемый стандартом ГОСТ Р 34.11-94 [15].