Безопасность программного обеспечения компьютерных систем


Криптопрограммирование - часть 5


Основные определения. Пусть АУТ(m) - обычный алгоритм аутентификации сообщений и АУТa(m)- функция маркирования сообщения m, индуцированная схемой АУТ с ключом аутентификации a. Пусть ВЕРa(m,?) - соответствующий алгоритм верификации, где ?={true, false} - предикат корректности проверки.

Далее будут использоваться деревья поиска и, следовательно, необходимо напомнить, что 2-3-дерево имеет все концевые узлы (листья) на одном и том же самом уровне/высоте (как и в случае сбалансированных двоичных деревьев) и каждая внутренняя вершина имеет или 2, или З дочерних узла []. В данном случае 2-3-дерево подобно двоичному дереву является упорядоченным деревом и, таким образом, концевые узлы являются упорядоченными. Пусть Vh - определяет множество всех строк длины не больше h, ассоциированных очевидным способом с вершинами сбалансированного 2-3-дерева высоты h. Маркированное дерево может рассматриваться как функция Т: Vh - >{0,1}*, которая приписывает аутентификационный признак (АП) каждой вершине.

Пусть совокупный аутентификационный признак файла F получен посредством использования 2-З-дерева аутентификационных признаков каждого из блоков файла F=F[1],...,F[l] (далее такое дерево будет называться маркированным деревом). Каждая вершина w ассоциирована с меткой, которая состоит из АП (аутентифицирующих дочерние узлы) и счетчика, представляющего число узлов в поддереве с корнем w.

Алгоритм маркирования. Алгоритм создания 2-3-дерева аутентификационных признаков (алгоритм маркирования) работает следующим образом:

  • для каждого i, пусть T(w)=АУТ?(F[i]), где w - i-тый концевой узел;

  • для каждого не - концевого узла w, пусть Т(w)=АУТ?((L1,L2,L3),рзм), где Li - метка i-того дочернего узла w (в случае, если w имеет только два дочерних узла, то L3=?) и рзм - число узлов в поддереве с корнем w);

  • для корня дерева Т(?)=АУТ?((L1,L2,L3),Id,счт), где Id - название документа и счт - соответствующее показание счетчика (связанное с этим документом).

Инкрементальный алгоритм маркирования.




Начало  Назад  Вперед



Книжный магазин