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


         

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


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

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




где:

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

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

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

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

текст Р), то
 
и
.


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


Форм. 21



где

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

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

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

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

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


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

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


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


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

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


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