Метод защиты файлов программ посредством инкрементального алгоритма маркирования
Метод защиты файлов программ посредством инкрементального алгоритма маркирования
Основные определения. Пусть АУТ(m) обычный алгоритм аутентификации сообщений и АУТa(m) функция маркирования сообщения m, индуцированная схемой АУТ с ключом аутентификации a. Пусть ВЕРa(m,β) соответствующий алгоритм верификации, где β={true, false} предикат корректности проверки.
Далее будут использоваться деревья поиска и, следовательно, необходимо напомнить, что 23дерево имеет все концевые узлы (листья) на одном и том же самом уровне/высоте (как и в случае сбалансированных двоичных деревьев) и каждая внутренняя вершина имеет или 2, или З дочерних узла [2]. В данном случае 23дерево подобно двоичному дереву является упорядоченным деревом и, таким образом, концевые узлы являются упорядоченными. Пусть Vh определяет множество всех строк длины не больше h, ассоциированных очевидным способом с вершинами сбалансированного 23дерева высоты h. Маркированное дерево может рассматриваться как функция Т: Vh >{0,1}*, которая приписывает аутентификационный признак (АП) каждой вершине.
Пусть совокупный аутентификационный признак файла F получен посредством использования 2Здерева аутентификационных признаков каждого из блоков файла F=F[1],...,F[l] (далее такое дерево будет называться маркированным деревом). Каждая вершина w ассоциирована с меткой, которая состоит из АП (аутентифицирующих дочерние узлы) и счетчика, представляющего число узлов в поддереве с корнем w.
Алгоритм маркирования. Алгоритм создания 23дерева аутентификационных признаков (алгоритм маркирования) работает следующим образом:
- для каждого i, пусть T(w)=АУТα(F[i]), где w iтый концевой узел;
- для каждого не концевого узла w, пусть Т(w)=АУТα((L1,L2,L3),рзм), где Li метка iтого дочернего узла w (в случае, если w имеет только два дочерних узла, то L3=γ) и рзм число узлов в поддереве с корнем w);
- для корня дерева Т(λ)=АУТα((L1,L2,L3),Id,счт), где Id название документа и счт соответствующее показание счетчика (связанное с этим документом).
Инкрементальный алгоритм маркирования. Предположим, что файл F, аутентифицированный маркированным деревом, подвергается операции замены, то есть jтый блок файла F заменен блоком F(σ). Сначала необходимо проверить, что путь от требуемого текущего значения до корня дерева корректен. Для этого необходимо выполнить следующий алгоритм.
Пусть u0,...uh путь из корня u0=λ к jтому концевому узлу обозначается как uh. Тогда:
- проверить, что ВЕРα принимает Т(λ) как корректный АП строки Т(λ)=АУТa((L1,L2,L3),Id,счт), где Id название документа и счт текущее значение счетчика (связанного с этим документом);
- для i=1,...,h1 проверить, что ВЕРα принимает Т(ui) как корректный АП строки ((L1,L2,L3),рзм), где Li метка iтого дочернего узла w (в случае, если w имеет только два дочерних узла, то L3=γ) и рзм число узлов в поддереве с корнем w));
- проверить, что ВЕРα принимает Т(uh) как корректный АП блока F[j] .
Если все эти проверки успешны, тогда совокупный АП файла F получается следующим образом:
- установить Т(uh):=АУТ(F(σ));
- для i=h1,...,1 установить Т(ui):=АУТ(Т(ui1),Т(ui2),Т(ui3));
- установить Т(λ):=АУТ((Т(ui0),Т(ui1),Т(ui1)),Id,счт+1).
Следует отметить, что предлагаемая инкрементальная схема маркирования имеет дополнительное свойство, заключающееся в том, что она безопасна даже для противника который может "видеть" как отдельные аутентификационные признаки, так и все маркированное дерево и может даже "вмешиваться" в эти признаки. Для каждого файла, пользователь должен хранить в локальной безопасной памяти ключ x схемы подписи, имя файла и текущее значение счетчика. Всякий раз, когда пользователь хочет проверить целостность файла, он проверяет корректность маркированного дерева открытым образом.
Наиболее эффективным является использование инкрементального алгоритма маркирования для защиты программ, использующих постоянно обновляющие структуры данных, например, файл с исходными данными или итерационно изменяемыми переменными.
4/04/10 - 
