Общий вид алгоритма
Для того чтобы изменение одного бита (или группы битов) воздействовало на все остальные, поступим следующим образом: будем вычислять сигнатуру двоичной последовательности и одновременно некоторой функцией преобразовывать биты, сигнатура для которых уже рассчитана. Естественно, эта функция должна иметь соответствующую ей обратную функцию для восстановления исходного текста. Преобразовывать можно как один бит, так сразу и группу битов. Шаг алгоритма может быть длиной как в один бит, так и в несколько бит.
Для простоты понимания рассмотрим алгоритм, с функцией, преобразующий один бит, и шагом в один бит.
k – длина последовательности, бит;
m – старшая степень полинома для расчёта сигнатуры, а также количество бит в элементах памяти (prev и next), хранящих сигнатуру;
сигнатура(предыдущая сигнатура, новый бит) – функция, осуществляющая сжатие последовательности в сигнатуру;
f(x, ai) – функция, осуществляющая преобразование бита ai некоторым числом x;
ai – i-ый бит последовательности.
Базовое преобразование (прямой ход) будет выглядеть так:
(3.1)
prev = 0;
для i от 1 до k
{
next = сигнатура(prev, ai);
ai = f(prev, ai);
prev = next;
}
Обратное преобразование (прямой ход) будет выглядеть так:
(3.2)
prev = 0;
для i от 1 до k
{
ai = f
-1(prev, ai);
prev = сигнатура(prev, ai);
}
Как видим, изменение бита ai воздействует на все последующие биты, и вероятность того, что изменение этого бита отразиться на последующих, очень близка к единице. А что же делать с битами, предшествующими ai, ведь изменение их не затронет? Поступим просто – совершим такое же преобразование повторно, но в обратном направлении.
Базовое преобразование, обратный ход:
(3.3)
prev = 0;
для i от k до 1
{
next = сигнатура(prev, ai);
ai = f(prev, ai);
prev = next;
}
Обратное преобразование, обратный ход:
(3.4)
prev = 0;
для i от k до 1
{
ai = f
-1(prev, ai);
prev = сигнатура(prev, ai);
}
Преобразования (3.1) и (3.3) разносят изменения в любой точке последовательности на всю последовательность целиком таким образом, что каждый бит становится связанным со всеми остальными, и его изменение повлечёт изменение остальных битов с вероятностью, очень близкой к единице. Для восстановления исходного текста надо применить последовательно преобразования (3.2) и (3.4).
Но вышеописанное обеспечивает полноценное воздействие изменений только при преобразовании исходного текста в зашифрованный, при обратном преобразовании воздействие изменений в зашифрованном тексте на восстанавливаемый исходный будет слабо. Решается это просто – вводим дополнительно после (3.1) и (3.3) преобразования, аналогичные (3.2) и (3.4), только используем не f –1(x, y), а f(x, y).
Выглядеть это будет так:
