Однонаправленная функция с секретом на базе КАМСИ

       

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


В  Table 16 показан процесс последовательного кодирования и декодирования с помощью  двух последовательно включенных КАМСИ-автоматов А1 и А2.

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

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

Пример 2

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

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



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 18

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)

E

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 19

Для построения композиции выполним последовательность операций:


  • создать таблицу переходов, содержащую 2х2=4 ([14]) строки;


  • в первом столбце вписать все сочетания по два состояний КАМСИ  ?1

    и ?2  при этом необходимо, чтобы первым стояло обозначение состояния ?1, а вторым –  ?2;


  • на пересечении АА (см. первую строку  Table 18(с))  и столбца Р=0 записать:


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


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


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


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


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

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

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


    и таблицу переходов с



    состояниями».

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

    Далее, можно продолжить доказательство, увеличивая m на единицу.

    Сформулируем еще одно Утверждение:

    Утверждение 7. Для md  КАМСИ-автоматов декомпозиции ([16]) КАМСИ, всегда выполняется условие ?d  ?  ?, где: µd

    -  µ-порядок последовательного соединения КАМСИ-компонентов, равный:
    , а  µ - µ-порядок исходной КАМСИ-композиции.

    Допустим обратное, то есть условие Утверждения  не выполняется, то есть ?d  >  ?. Если это так, то, в соответствии с «Утверждение 6» композиция этих  mdk

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

    Из приведенных Утверждений можно сделать следующие выводы.

    Следствие  1. Если композиция КАМСИ состоит из минимизированных компонентов КАМСИ, то ее таблица переходов не имеет эквивалентных состояний.

    Введем определение:

    Определение. 9 КАМСИ, которая является компонентом  композиции, называется КАМСИ-примитивом ([17]).

    Примером КАМСИ-примитива являются КАМСИ ?1 или ?2, приведенные  в Table 18(a), (b) , а КАМСИ-композиция показанная  в  Table 18(d) -  ?.


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