Асимметричный криптографический алгоритм на базе Конечно-Автоматной Модели


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


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

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

где:

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

 

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

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

и

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

текст Р), то

 и
.

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

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

Форм. 21

где

фрагмент

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

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

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

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

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

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

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

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

и
.

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

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

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

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




Начало  Назад  Вперед



Книжный магазин