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

       

Свойства последовательного соединения КАМСИ


Рассмотрим последовательное соединение  двух КАМСИ А1 и А2 (см. Рис. 8, стр. 26).

До сих пор мы рассматривали последовательное соединение двух КАМСИ, кодера и декодера, которые соединены информационным каналом,  и поэтому их нельзя заменить одним автоматом.

Теперь мы рассмотрим такое объединение конечных автоматов, которое интересует нас постольку, поскольку его можно заменить эквивалентным конечным автоматом.

Рассмотрим  способ построения такого автомата,  его свойства и параметры.

Рис. 8

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

Утверждение 5.  Композиция  двух последовательно соединенных  КАМСИ А1=>А2 (Рис. 8) является КАМСИ, которая имеет порядок ?(A1+A2)=?(A1)+?(A2), где ?(A1) и ?(A2) - ?-порядки КАМСИ А1 и А2, соответственно

Доказательство.

Из определения КАМСИ следует, что ?(A1) символов входного потока битов (Р)поданных на вход КАМСИ А1 достаточно, чтобы определить первый символ Р на выходе Е1. Однако, на выходе Е2 он может появиться только через ?(A2)  битов

Е1 на входе КАМСИ

А2. Отсюда следует, что первый символ Р на выходе Е2 может быть получен после  ?(A1+A2)=?(A1)+?(A2) символов, поданных на вход Р, то есть, композиция  КАМСИ А1,А2

также является КАМСИ и имеет порядок ?=?(A1)+?(A2).



Пример 1

 В Table 13(a) и (b) приведены таблицы переходов КАМСИ А1 и А2

µ-порядка 2, а в  Table 13(c) и (d) – инверсные им автоматы SS1

и SS2, соответственно ([12]).

 

А1

P,E

P=0

P=1

A

B,0

A,0

B

A,1

B,1

(a)

 

А2

P,E

P=0

P=1

A

A,1

B,1

B

B,0

A,0

(b)

 

?(A1)=2

?(A2)=2

 

 

SS1

P,E

E=0

E=1

S0

S1,1

S2,1

S1

S1,1

S2,1

S2

S3,0

S4,0

S3

S1,0

S2,0

S4

S3,1

S4,1

(c)

 

SS2

P,E

E=0

E=1

S0

S1,0

S2,0

S1

S1,0

S2,0

S2

S3,1

S4,1

S3

S1,1

S2,1

S4

S3,0

S4,0

(d)

 

Table 13

Обозначим через А1 и SS1 кодер и декодер, соответственно, (аналогично А2 и SS2). В Table 14 и в Table 15 (строка (а))  приведен один и тот же поток бит Р (кодируемый текст, который известен только отправителю, см. Table 14(а)). В строках (b) таблиц приведены состояния, в которые переходят автоматы А1 и А2, соответственно. В  строках (с) – значения на выходе – закодированный текст, который может быть известен всем (например, передаваться по незащищенному каналу). В строках (d) и (e) приведены результаты декодирования, которые показывают, что результаты декодирования совпадают с исходным текстом, но появляются, начиная с третьего бита, то есть, с задержкой, равной двум.


Table 16

P
1
1
0
1
0
0
1
1
0
0
1
0
0
1
1
1
A1
A
A
A
B
B
A
B
B
B
A
B
B
A
B
B
B
B
E1
0
0
0
1
1
0
1
1
1
0
1
1
0
1
1
1
A2
A
A
A
A
B
A
A
B
A
B
B
A
B
B
A
B
A
E2
1
1
1
1
0
1
1
0
1
0
0
1
0
0
1
0
SS1
S0
S2
S4
S4
S4
S3
S2
S4
S3
S2
S3
S1
S2
S3
S1
S2
S3
E`
1
0
1
1
1
0
0
1
0
0
0
1
0
0
1
0
SS2
S0
S2
S3
S2
S4
S3
S1
S1
S2
S3
S1
S1
S2
S3
S1
S2
S3
P`
0
1
1
1
0
1
0
0
1
1
0
0
1
1
0
1
Table 17

На основании «Утверждение 5» (см. стр. 26) и «Утверждение 6» (см. стр. 30) можно сделать вывод: если последовательность автоматов состоит из  m  КАМСИ-компонентов, то они представляют собой КАМСИ-композицию  µ-порядка, равного
                                                                              Форм. 2.

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