Теория и практика защиты программ


         

Определяющим является то, что сортировка


Определяющим является то, что сортировка выполняется посредством использования эффективной сети сортировки такой, например, как сеть сортировки Батчера [BGG]. Следует подчеркнуть, что всякий раз, когда две пары сравниваются и переставляются (или нет), тогда они заново шифруются посредством Е

(так что противник не может «понять» были ли они переставлены или нет). Это гарантирует то, что вся процедура сортировки не дает никакой информация противнику. Как только сортировка завершена, алгоритм просматривает W для нахождения всех мест нахождения элементов с одним и тем же ключом сортировки и сохраняет последнее (которое является новым), в  большом фиктивном значении (l+1,...). Теперь, мы посредством ключа сортировки заново сортируем пары из W и получаем последовательность, в которой первые l

элементов содержат модифицированный документ D'. В заключение, мы устанавливаем Е1 для хранения в ней зашифрованного блока данных D' и исключаем первые l элементов последовательности  Е2.

При использовании AKS-сети сортировки [BGG] вышеприведенная реализация инкрементального алгоритма шифрования требует O(llog l) шагов (в то время как, если мы используем сеть Батчера, то получаем сумму из О(l)+(llоg2l) шагов). Эти шаги могут быть распределены равномерно среди l операций модификации, обеспечивающих желаемую сложность.

Как было упомянуто выше, каждый из рассматриваемых алгоритмов можно адаптировать для реализации схемы инкрементального шифрования для операций вставки/удаления (единственного символа), которая является эффективной в строгом смысле. Для этого длина открытых данных устанавливается в некоторых предопределенных пределах (например, между l/2 и 2l). А именно, схема инкрементального шифрования состоит из трех последовательностей Е1, Е2 и Е3, где Е1 и Е2 – определены выше, а Е3 - шифрование рабочей области для некоторого забывающего моделирующего устройства (см. предыдущую главу).Также как и как выше, алгоритм работает в периодах, состоящих из l изменений каждый. В каждом периоде, инкрементальный алгоритм выполняет l

изменений предыдущего периода. Это делается посредством моделирования RAM-программы, которая содержит структуру данных, обеспечивающую эффективное выполнение операций вставки/удаления, например, 2-3-дерево.


Содержание  Назад  Вперед