Кривель И.А.^*, Моргун А.Н.^**

^*Киевский национальный университет технологий и дизайна, Украина;

^**Черкасский институт пожарной безопасности, Украина

К вопросу о хэшировании сообщений

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

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

Интересные возможности построения хэш-функции для числовых данных предоставляет двоичное дерево Штерна-Броко [2], содержащее в качестве вершин рациональные числа в виде неотрицательных несократимых дробей.

Построению двоичного дерева Штерна-Броко (дерево SHB) предшествует получение последовательности Штерна-Броко. Рассмотрим стартовую последовательность двух дробей 0/1 и 1/0. Новую дробь 1/1 образуем, сложив числители и знаменатели стартовых. В новой последовательности 0/1, 1/1, 1/0 рассматриваем все соседние пары и вставляем в неё очередные дроби по тому же принципу. Получаем последовательность 0/1, 1/2, 1/1, 2/1, 1/0. На следующем этапе последовательность приобретает вид 0/1, 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1, 1/0. Описанный процесс можно продолжать бесконечно.

Дроби последовательности можно расположить на двоичном дереве SHB, которое для удобства обозрения представлено в виде нижеследующей таблицы. При этом вершину 1/1 будем считать корнем.

Основное свойство дерева SHB состоит в том, что в нём представлены все рациональные числа, причём каждое – только один раз. Пронумеруем вершины дерева, начиная от корня и обозначая нулями перемещения по левым ветвям, а единицами – по правым. Например, дробь 2/3 будет иметь двоичный номер 01, а дробь 3/1 – двоичный номер 11, дробь 2/5 – двоичный номер 001, дробь 5/3 – двоичный номер 101 и т.д. Таким образом, мы получили возможность сопоставлять двум числам (числителю и знаменателю дроби) одно число – номер дроби.

0/1

1/0

1/1

1/2

2/1

1/3

2/3

3/2

3/1

1/4

2/5

3/5

3/4

4/3

5/3

5/2

4/1

Одно из свойств такого сопоставления состоит в том, что номера некоторых дробей имеют в своём составе ведущие нули. В результате этого численно равные номера могут соответствовать разным дробям. Например, номера дробей 2/3 и 2/5 имеют численно равные представления 01 и 001 соответственно, дроби 3/1 и 3/4 также имеют численно равные номера 11 и 011. Благодаря этому становится невозможным однозначное обратное сопоставление и таким образом обеспечивается требование стойкости хэш-функции в смысле её обращения.

В приведённых примерах обращает на себя внимание то, что дробь не имеет в составе своего двоичного номера ведущих нулей тогда, когда её числитель больше знаменателя, то есть дробь – неправильная. Все неправильные дроби содержатся только в правом поддереве дерева SHB.

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

Дробь	Номер дроби	Десятичное представление номера
3/1	11	3
5/3	101	5
7/3	1100	12
11/7	10100	20
14/5	110111	55

Данная таблица показывет, как двум десятичным числам (числителю и знаменателю дроби) сопоставляется одно десятичное число (номер дроби в десятичном представлении). При этом суммарное количество разрядов двоичных представлений числителя и знаменателя оказывается больше количества разрядов двоичного номера. Например, компоненты дроби 11/7 имеют двоичные представления 1011 и 111 соответственно, что составляет в сумме 7 двоичных разрядов. А вот двоичное представление номера этой дроби 10100 содержит всего 5 двоичных разрядов.

На возможности сопоставить двум десятичным числам одно с меньшим количеством разрядов двоичного представления и базируется алгоритм хэш-функции на основе двоичного дерева Штерна-Броко.

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

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

7	4	5	4	5	3	3	1	8	5	4	1	4	1	3	1
11		8		5		3		10		7		7		3
18				5				19				12
58								41
307

Каждая пара соседних чисел некоторого исходного сообщения (первая строка таблицы) рассматривается как дробь, которой сопоставляется её двоичный номер. Полученный номер преобразуется в десятичное число. Процесс продолжается до получения единственного числа, которое следует рассматривать как значение хэш-функции данного сообщения. Например, воспользовавшись второй из приведённых программ, для дроби 7/4 получим двоичный номер 1011, что соответствует десятичному числу 11. Для следующей дроби 5/4 двоичный номер равен 1000, что соответствует десятичному числу 8. В свою очередь, для дроби 11/8 получим номер 10010, что равно 18, и т.д. В последней строке таблицы находится значение хэш-функции, равное десятичному числу 307.

Литература

1. Гундарь К.Ю., Гундарь А.Ю., Янишевский Д.А. Защита информации в компьютерных системах – К.: “Корнейчук”, 2000.

2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики – М.: Мир, 1998.