Теория и практика защиты программ
М мы получаем зашифрованную форму
При замене Е1 на Е'
и при исключении первых l
изменений в М мы получаем зашифрованную форму текущего документа. Следует подчеркнуть, что в такой модели вычислений все эти операции могут выполняться за константное временя. Наконец необходимо отметить, что алгоритм работает в периодах, каждый состоящий из l
изменений. В каждом периоде, алгоритм модифицирует шифртекст для сравнения с изменениями, выполненными в предыдущем периоде.
Выше мы предположили, что пользователь может хранить промежуточные результаты (которые требуют памяти размером О(l)) в локальной памяти, невидимой противником. Это предположение нереалистично в некоторых сценариях и несовместимо с вышеприведенными определениями для схем инкрементального шифрования. Далее мы используем вышеупомянутые идеи без этого предположения (идеи берутся из [GO,O], см. предыдущую главу). Для этого нам необходимо шифровать данные, используя три последовательности, обозначаемые Е1,Е2 и Е3. Первые две последовательности Е1
и Е2, является точно такими же, как определенные выше. Их достаточно для дешифрования данных. Дополнительная последовательность Е3
– является «шифрованием рабочей области» и обозначается как W=W[1]...W[2l].
Далее мы опишем операции, выполняемые в одном периоде. В нашем описании, мы не упоминаем явно операции шифрования, и, таким образом, всякий раз, когда мы говорим, что мы устанавливаем элемент последовательности W, это должно означать, что соответствующий шифртекст получен и сохранен.
Сначала, мы устанавливаем элементы последовательности W следующим образом: W[i]:=(i+D[i]) для i£l и W[i]:=M[i-l] для l+1£i£2l. Здесь мы предполагаем, что записи изменений имеют форму (i,d), где i – номер ячейки памяти и d
символ, который размещен в этой ячейке. Затем, мы сортируем пары из W по их левым элементам в соответствии с так называемыми ключами сортировки
так, что, если два ключа сортировки равны, тогда соответствующие пары хранятся упорядоченными.
