Инкрементальный алгоритм маркирования
Предположим, что файлF, аутентифицированный маркированным деревом, подвергается операции замены, то есть j-тый блок файла F заменен блоком F(s). Сначала необходимо проверить, что путь от требуемого текущего значения до корня дерева корректен. Для этого необходимо выполнить следующий алгоритм.
Алгоритм ИАМ2-3
Пусть u0,...uh - путь из корня u0=l
к j-тому концевому узлу обозначается как uh. Тогда:
1. Проверить, что алгоритм ВЕРa
при верификации принимает Т(l) как корректный АП строки (a,(L1,L2,L3),Id,счт)АУТ=Т(l), где Id - название документа и счт - текущее значение счетчика (связанного с этим документом).
2. Для i=1,...,h-1 проверить, что ВЕРa
принимает Т(ui) как корректный АП строки ((L1,L2,L3),рзм), где Li
- метка i-того дочернего узла w (в случае, если w имеет только два дочерних узла, то L3=g) и рзм - число узлов в поддереве с корнем w)).
3. Проверить, что ВЕРa
принимает Т(uh) как корректный АП блока F[j].
4. Если все эти проверки успешны, тогда совокупный АП файла F получается следующим образом.
4.1. Установить Т(uh):=АУТ(F(s)).
4.2. Для i=h-1,...,1 установить Т(ui):=АУТ(Т(ui1),Т(ui2),Т(ui3)).
4.3. Установить Т(l):=АУТ((Т(ui0),Т(ui1),Т(ui1)),Id,счт+1).
Следует подчеркнуть, что значения Т на всех других вершинах (то есть, не стоящих на пути u0,...,uh) остаются неизменяемыми.
Следует также отметить, что предлагаемая инкрементальная схема маркирования имеет дополнительное свойство, заключающееся в том, что она безопасна даже для противника, который может «видеть» как отдельные аутентификационные признаки, так и все маркированное дерево и может даже «вмешиваться» в эти признаки. Для каждого файла, пользователь должен хранить в локальной безопасной памяти ключ x схемы подписи, имя файла и текущее значение счетчика. Всякий раз, когда пользователь хочет проверить целостность файла, он проверяет корректность маркированного дерева открытым образом.
Наиболее эффективным является использование инкрементального алгоритма маркирования для защиты программ, использующих постоянно обновляющие структуры данных, например, файл с исходными данными для программ или итерационно изменяемыми переменными.
