10.2.3. Криптографические хэш-функции

Понятие хэш-функций было определено в 1979 году в работах американского математика Р. Меркля, однако еще ранее в автоматизированных системах широко использовались некриптографические хэш-функции для оптимизации размещения и поиска данных [1, 31].

Хэш функции (хэширующие функции (ХФ)) произвольного вида принадлежат к классу однонаправленных функций без потайного хода.

ХФ  отображает сообщение  произвольной длины  в последовательность символов (хэш-код ) фиксированной длины ; для снижения скорости выбирают .

Если различные сообщения  отображаются в один и тот же хэш-код, то такая ХФ допускает коллизии (склеивания) сообщений.

Основными свойствами ХФ являются чувствительность к изменениям текста сообщения, отсутствие эффективных алгоритмов поиска коллизий, однонаправленность и простота вычисления .

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

Если в процессе хэширования сообщений используется секретный ключ , то такая функция  называется криптографической ХФ с секретным ключом (рис. 10.5,а). Криптографические ХФ, не использующие секретного ключа для хэширования сообщений , называются бесключевыми криптографическими ХФ (рис. 10.5,б). Бесключевые криптографические ХФ могут быть разделены на однонаправленные ХФ и устойчивые к коллизиям ХФ.

Большинство известных бесключевых ХФ основано на разбиении произвольно длинных сообщений на блоки фиксированной длины и их последовательной обработке криптографической ХФ. Этот метод называется итеративным хэшированием. Хэшируемое сообщение  делится на  блоков от  до  длиной по  бит. Если длина сообщения не кратна длине блока, то сообщение должно дополняться до длины, кратной длине блока. Для инициализации процесса итеративного хэширования необходимо задать стартовый вектор хэширования  длиной  бит. Хэширование сообщения осуществляется на основе функции , которая образует выходное значение длиной  при задании блока исходного текста  и хэш-значения  предыдущего блока текста:

,

где    – значение хэш-кода на -й итерации хэширования.

Значение хэш-кода  всего сообщения  определяется как значение хэш-кода на последней итерации хэширования.

В настоящее время разработано много способов хэширования. В качестве примера рассмотрим однонаправленную ХФ вида:

.

(10.1)

Процедура вычисления  является рекуррентной и применяется к сообщению , разбитому на блоки :

,     ,

где    – произвольное начальное число.

Пример 10.2. Пусть , а сообщение «ДВА» представлено номерами букв в русском алфавите, т.е. . Выберем произвольно . Тогда из (10.1) получим:

,   ,   .

Сообщение после хэширования имеет вид  или «НЩЧ».

Криптографические ХФ в настоящее время широко используются для обеспечения безопасности информации (установление подлинности сообщений) и аутентификации пользователей криптографических систем и сетей.

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