Функция хэширования

Функция хэширования (хэш-функция) представляет собой преобразование, на вход которого подается сообщение переменной длины М, а выходом является строка фиксированной длины h(М). Иначе говоря, хэш-функция h(.) принимает в каче­стве аргумента сообщение (документ) М произвольной длины и возвращает хэш-значение (хэш) Н = h(М) фиксированной длины (рис. 1).

Рис.1. Схема формирования хэша Н = h(М)

Хэш-значение h(М) − это дайджест сообщения М, то есть сжатое двоичное пред­ставление основного сообщения М произвольной длины. Хэш-значение h(М) фор­мируется функцией хэширования.

Функция хэширования позволяет сжать подписываемый документ М до 128 бит и более (в частности, 128 или 256 бит), тогда как М может быть размером в мега­байт или более. Следует отметить, что значение хэш-функции h(М) зависит слож­ным образом от документа М и не позволяет восстановить сам документ М.

Функция хэширования должна обладать следующими свойствами:

1. Хэш-функция может быть применена к аргументу любого размера.

2. Выходное значение хэш-функции имеет фиксированный размер.

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

4. Хэш-функция должна быть чувствительна к всевозможным изменениям в тексте М, таким как вставки, выбросы, перестановки и т.п.

5. Хэш-функция должна быть однонаправленной, то есть обладать свойством необратимости. Иными словами, задача подбора документа М’ который об­ладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима.

6. Вероятность того, что значения хэш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала; то есть для любого фиксированного х с вычислительной точки зрения невозможно найти х'≠ х, такое что h(х') = h(х).

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

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

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

Известные функции хэширования:

отечественный стандарт ГОСТ Р34.11-94. Вычисляет хэш размером 32 байт;

MD(Message Digest) − ряд алгоритмов хэширования, наиболее распростра­ненных в мире. Каждый из них вырабатывает 128-битовый хэш-код. Алгоритм MD2 − самый медленный из них, MD4 − самый быстрый. Алгоритм MD5 является модификацией MD4, при которой пожертвовали скоростью ради увеличения безопасности. Алгоритм MD5 применяется в последних версиях Microsoft Windows для преобразования пароля пользователя в 16-байтовое число;

SHA (Secure Hash Algorithm) − это алгоритм вычисления дайджеста сообщений, вырабатывающий 160-битовый хэш-код входных данных. Широко рас­пространен в мире, используется во многих сетевых протоколах защиты информации.

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

Поиск по сайту: