Подход к созданию трудноанализируемых шифров

       

Общий вид алгоритма


Для того чтобы изменение одного бита (или группы битов) воздействовало на все остальные, поступим следующим образом: будем вычислять сигнатуру двоичной последовательности и одновременно некоторой функцией преобразовывать биты, сигнатура для которых уже рассчитана. Естественно, эта функция должна иметь соответствующую ей обратную функцию для восстановления исходного текста. Преобразовывать можно как один бит, так сразу и группу битов. Шаг алгоритма может быть длиной как в один бит, так и в несколько бит.

Для простоты понимания рассмотрим алгоритм, с функцией, преобразующий один бит, и шагом в один бит.

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).

Выглядеть это будет так:


Содержание раздела