Кривель И.А.*, Моргун А.Н.**
*Киевский национальный университет
технологий и дизайна, Украина;
**Черкасский институт пожарной
безопасности, Украина
К вопросу о хэшировании сообщений
В соответствии с [1],
хэш-функцией h(m) в
криптографии называется некоторый алгоритм, в результате применения которого
исходное сообщение m произвольной длины преобразуется в
последовательность фиксированного числа байт. Одно из основных применений
хэш-функции состоит в образовании сжатого образа данного сообщения, используемого
для его цифровой подписи.
Хэш-функция должна быть
стойкой как в смысле её обращения, так и в смысле возникновения коллизий при её
вычислении. Первое из указанных требований означает, что по известному значению
хэш-функции h(m) должно
быть невозможно (достаточно сложно) определить значение её аргумента
m. В соответствии со вторым
требованием, для данного аргумента m должно быть невозможно (достаточно
маловероятно) найти другой аргумент m1 такой, что h(m) = h(m1).
Интересные возможности построения
хэш-функции для числовых данных предоставляет двоичное дерево Штерна-Броко [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.