Однонаправленная ХЕШ-функция

Хеш-функция предназначена для сжатия подписываемого документа до 10-100 бит

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

Обычно хешированная информация является сжатым 2-ным представлением произвольной длины.

Значение h(M) сложным образом зависит от документа М и не позволяет определить этот самый документ по значению функции.

h-функция должна соответствовать условиям:

- Чувствительна к любым изменениям в М

- Обладать свойством необратимости, то есть задачи подбора некоего документа М’, который обладал бы требуемым значением h-функции была бы вычислительно неразрешима.

- Вероятность того, что значение h-функции 2 различных документов совпадут должна быть ничтожно мала.

Большинство h-функций строится на основе однонаправленной функции f, которая образует выходное значение длиной M при заданных 2х входных значениях длиной N. Этими входными значениями является n-блок исходного текста M(i) и хеш-значение h-1 предыдущего блока.

H(i) = f (M_i, H_i-1 )

Хешированное значение вычисляется при вводе последовнего блока текста, оно становится h-значением всего сообщения M.

В результате однонаправленная h-функция всегда формирует выход фиксированной длины N, независимо от длины входного текста.

Основы построения h-функции - h(.):

Общепринятым построением h(.) является интерактивная последовательная схема.

Ядром алгоритма является преобразование k бит в n бит, где n – разрядность результата хеширования, а k >> n производное значение.

Базовое преобразование должно обладать всеми свойствами h(.), то есть необратимостью и невозможностью инвариантного изменения входных данных. Хеширование производится с помощью промежуточной вспомогательной переменной разрядностью n, в качестве которой выбирают произвольное, всем известное значение, например a.

Входные данные разбиваются на блоки по k-n бит.

На каждой итерации хеширования со значением промежуточной величины, полученной из предыдущей итерации объединяется очередная k-n битная порция входных данных и над получившимся k блоком производятся преобразования.

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

Кроме более полупроходных алгоритмов хеширования существуют многопроходные.

Однонаправленные h(.) на основе суммирующих блочных элементов.

Однонаправленные h(.) можно построить используя симметричный блочный алгоритм.

Наиболее явный подход: шифровать сообщение М посредством блочного алгоритма CBC, CFB с помощью фиксированного ключа и некоторого вектора инициализации IV.

Начальное значение – H₀

Случайное значение – Iн

H₀=Iн

Последний блок шифротекста можно использовать в качестве хеш-значения сообщения М. Наиболее безопасен вариант h(.) можно получить используя блок сообщения в качестве ключа. Предыдущее хеш-значение в качестве входа, а текущее - в качестве выхода.

Реальные h(.) проектируются значительно более сложно. Длина блока обычно определятеся длиной ключа, а длина h-значения совпадает с длиной блока. Схема h-значения, у которой длина h-значения = длине блока.

ABC могут принимать значения *

Переменные A, B, C могут принимать любое из 4-х значений. Общее число значений 64. Из них 52 варианта тривиальны (слабые). Из остальных 12 правильно 4:

Недостатком h(.), спроектированных на основе алгоритмов является заниженная скорость работы.