Электронная цифровая подпись и функция хэширования

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

Как видно из схемы на рис. 5.7, в качестве исходного значения для вычисления ЭЦП берется не сам электронный документ, а его хэш-значение, или дайджест.

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

Рис. 5.8. Схема формирования хэша H=h(M)

Рис. 5.8. Схема формирования хэша H=h(M)

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

Функция хэширования должна обладать следующими свойствами:
1. Хэш-функция может быть применена к аргументу любого размера.
2. Выходное значение хэш-функции имеет фиксированный размер.
3. Хэш-функцию h(x) достаточно просто вычислить для любого х. Скорость вычисления хэш-функции должна быть такой, чтобы скорость выработки и проверки ЭЦП при использовании хэш-функции была значительно больше, чем при использовании самого сообщения.
4. Хэш-функция должна быть чувствительна к всевозможным изменениям в тексте М, таким как вставки, выбросы, перестановки и т. п.
5. Хэш-функция должна быть однонаправленной, т. е. обладать свойством необратимости, иными словами, задача подбора документа М’, который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима.
6. Вероятность того, что значения хэш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала; т. е. для любого фиксированного х с вычислительной точки зрения невозможно найти х’ ^ х, такое, что h(x’)h(x).

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

Свойство 5 эквивалентно тому, что h() является односторонней функцией. Свойство 6 гарантирует, что не может быть найдено другое сообщение, дающее ту же свертку. Это предотвращает фальсификацию сообщения.

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

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

Известные алгоритмы хэширования:
• отечественный стандарт ГОСТ P34.11—94. Вычисляет хэш размером 32 байта;
• MD (Message Digest) — ряд алгоритмов хэширования, наиболее распространенных в мире. Например, алгоритм MD5 применяется в последних версиях Microsoft Windows для преобразования пароля пользователя в 16-байтное число;
• SHA-1 (Secure Hash Algorithm) — это алгоритм вычисления дайджеста сообщений, вырабатывающий 160-битовый хэш-код входных данных, широко распространен в мире, используется во многих сетевых протоколах защиты информации.

Хэш-функции широко используются также для аутентификации пользователей.


Страницы: 1 2 3

Эта статья была опубликована Вторник, 11 августа, 2009 at 19:58 в рубрике Принципы криптографической защиты информации. Вы можете следить за ответами через RSS 2.0 feed.

Написать ответ