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

Алгоритм построения КАМСИ-композиции


Выше, в Table 5 показан процесс последовательного кодирования и декодирования двух последовательно включенных КАМСИ А1 и А2. Рассмотрим теперь способ построения автомата, эквивалентного последовательному включению двух автоматов.

Алгоритм построения КАМСИ–композиции  из компонентов КАМСИ рассмотрим на примере  композиции двух автоматов.

Пример 3

Пусть заданы две КАМСИ

 и
 (см. Table 7(а) и (b)). Следует построить таблицу переходов автомата ?, эквивалентного последовательному соединению  КАМСИ 
.

P,E1



P=0

P=1

A

B,0

A,0

B

A,1

B,1

(a)

Е1,E2

P=0

P=1

A

A,1

B,1

B

B,0

A,0

(b)

?

P,E2

P=0

P=1

1

2

3

AA

BA,1

AA,1

AB

BB,0

AB,0

BA

AB,1

BB,1

BB

AA,0

BA,0

(c)

?

P,E2

P=0

P=1

A

C,1

A,1

B

D,0

B,0

C

B,1

D,1

D

A,0

C,0

(d)

Table 7

P

1

1

0

1

0

0

1

1

0

0

1

0

0

1

1

1

(a)

?

A

A

A

C

D

A

C

D

C

B

D

C

B

D

C

D

C

(b)

1

1

1

1

0

1

1

0

1

0

0

1

0

0

1

0

(c)

SS2

S0

S2

S4

S4

S4

S3

S2

S4

S3

S2

S3

S1

S2

S3

S1

S2

S3

(d)

0

1

0

0

0

1

1

0

1

1

1

0

1

1

0

1

(e)

SS1

S0

S1

S2

S3

S1

S1

S2

S4

S3

S2

S4

S4

S3

S2

S4

S3

S2

(f)

1

1

0

0

1

1

0

1

0

0

1

1

0

0

1

0

(g)

Table 8

Выполним следующую последовательность операций:

  • построить таблицу переходов, содержащую 2х2=4 ([33]) строки;
  • в первом столбце вписать все сочетания по два состояний КАМСИ
     и
     (первым стоит обозначение состояния
    , а вторым –
    );
  • на пересечении АА (см. Table 7(с))  и столбца Р=0 записать:

  • символ В (переход при Р=0 в КАМСИ
     из А в В, Е1=0);


  • символ А (переход при Е1=0 в КАМСИ
     из А в А, Е2=1);


  • через запятую записать значение Е2 равное 1; Аналогично заполнить остальные клетки столбцов 2 и 3.


  • построить Table 7(d). Для этого АА из Table 7(с) заменить: АА на А, АВ на В, ВА на С и ВВ на D ([34]).


  • Приведенный пример показывает, что если число компонентов КАМСИ  в композиции равно m, таблица переходов i-го  автомата имеет
     состояний, то общее число N состояний композиции равно: N=n1…?ni…?nm;.

    Примеры на стр. 43 и  46 позволяют сформулировать следующее утверждение:

    Утверждение 2: «Последовательное соединение m компонентов КАМСИ эквивалентно КАМСИ-композиции, которая имеет µ-порядок, равный 

    ?= ?(1)… +.. ?(i)…+… ?(m);  (i:=1,m)

    и таблицу переходов с N=n1…?ni…?nm; состояниями».

    Доказательство этого Утверждения можно провести по индукции, если считать, что примеры на стр. 43 и  46 позволяют доказать  его для m=2. Далее, можно продолжить доказательство, увеличивая m на единицу.

    Утверждение 2 позволяет сделать выводы, о том, что не всякая КАМСИ является КАМСИ-композицией, а только та, которая может быть представлена последовательностью компонент КАМСИ, отвечающих приведенному Утверждению.


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