КАМСИ-композиция и КАМСИ-примитив - часть 4

Докажем еще одно не тривиальное утверждение.

Утверждение 7. Если существует две композиции

где:

- четыре разных примитива,

- композиция примитивов

, которая выполняет операцию

– множество примитивов y-го типа, то есть с одинаковым числом состояний и величиной µ,

(где

- закодированный композициями
, соответственно,

текст Р), то

и
.

Доказательство. Допустим, что

, то есть
. Примем, что в таблицах переходов примитивов
и
:

Форм. 21

где

фрагмент

соответствует переходу примитива из состояния S в состояние Q, если на его входе P=0. При этом на выходе устанавливается значение t (ноль или единица).

Принятое выше допущение

является условием эквивалентности композиций
и
. Другими словами, при обходе всех состояний таблиц переходов
и
на их выходах появляется одинаковая последовательность битов.

Допустим, что

и
эквивалентны, а для
и
существует состояние S, которое имеет вид Форм. 21 (см. Ошибка! Источник ссылки не найден., стр. 61).

Допустим, на входы

и
подан поток битов, который перевел оба автомата в состояние S. Из Форм. 21 следует, что при очередном изменении на входах
и
один из автоматов перейдет в состояние Q, а другой – в F (это зависит от значения Р). Но так как Q не эквивалентно F, то при продолжении эксперимента на выходах
и
появятся разные последовательности битов.

Не трудно показать, что ситуация не изменится, если операция, описанная в «Ошибка! Источник ссылки не найден.» будет применена к разному числу примитивов композиций

и
.

Из этого следует, что имея набор двух-трех типов примитивов, можно организовать криптографический алгоритм на базе КАМСИ, при котором:

Отпадает необходимость строить КАМСИ, применяя описанные выше тестирующие процедуры;

Отпадает необходимость обеспечивать секретность принятому набору типов примитивов.

Рассмотрим далее процесс формирования кортежей.

Двоичная запись чисел, поставленных в соответствие примитиву в Ошибка! Источник ссылки не найден., показывает способ, как из компоненты с номером 000 (назовем ее базовой ([46])) получить компоненту, соответствующую заданному числу.

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