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




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


Рассмотрим последовательное соединение  двух КАМСИ А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) приведены результаты декодирования, которые показывают, что результаты декодирования совпадают с исходным текстом, но появляются, начиная с третьего бита, то есть, с задержкой, равной двум.




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