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

       

Какова же сложность построения КАМСИ-декодера?


Выше было показано, что для КАМСИ применим один из способов инвертирования: непосредственный  и метод декомпозиции.

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

Все ли так просто?

Обратимся к  примеру КАМСИ-композиции, который мы рассматривали выше.

Пример 5

В Ошибка! Источник ссылки не найден. показаны примитивы

 и 
?  - их КАМСИ-композиция
 и инверторы примитивов: для
 -  SS1, а для
 - SS2.

P,E1



P=0

P=1

A

B,0

A,0

B

A,1

B,1

(a)

Е1,E2

P=0

P=1

C

C,1

D,1

D

D,0

C,0

(b)

?

P,E2

P=0

P=1

1

2

3

AC

BC,1

AC,1

AD

BD,0

AD,0

BC

AD,1

BD,1

BD

AC,0

BC,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)

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

(e)

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

(f)

(g)

(h)

Table 17

В Ошибка! Источник ссылки не найден.(g) показана структура кодера КАМСИ-композиции, на вход которого подан поток битов Р, а на выходе получается шифр Е2, который передается по каналу связи.

В Ошибка! Источник ссылки не найден.(h) показан процесс кодирования композицией ? потока битов Р в поток битов Е2 и декодирования его декодерами в порядке SS2=> SS1. Последняя строка Ошибка! Источник ссылки не найден.(h) показывает, что декодированное сообщение получено с  задержкой  µ=4. Из этого можно сделать вывод, что ? обладает задержкой µ=4.

P

1

1

0

0

0

1

0

1

0

1

1

0

1

0

0

 

 

 

?

A

A

A

C

B

D

C

B

B

D

C

D

A

A

C

B

 

 

E2

1

1

1

1

0

0

1

0

0

0

1

0

1

1

1

 

 

SS2

 

S0

S2

S4

S4

S4

S3

S1

S2

S3

S1

S1

S2

S3

S2

S4

S4

 

0

1

0

0

0

1

0

1

1

0

0

1

1

1

0

SS1

 

S0

S1

S2

S3

S1

S1

S2

S3

S2

S4

S3

S1

S2

S4

S4

S3

 

 

1




1



0



0



1



1



0



0



0



1



0



1



0



1



1









 








?



P,E2



P=0



P=1



1



2



3



AC



BC,1



AC,1



AD



BD,0



AD,0



BC



AD,1



BD,1



BD



AC,0



BC,0

 

(a)

 







?



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

 

(b)

 



 



?



 





 



 



AC



 



AC/BC



AD



AD/BD



 



BC



 



AD/BD



BD



AC/BC



 



AC/BC



 



(AC/AD)(AC/BD)

(AD/BC)(BC/BD)



AD/BD



(AC/AD)(AC/BD)

(AD/BC)(BC/BD)



 



AC/AD



 



 



AC/BD



 



 



AD/BC



 



 



BC/BD



 



 

 

(c)

 







?



 



 



 



A



 



AC



B



BD



 



C



 



BD



D



AC



 



AC



 



(AB)(AD)

(BC)(CD)



BD



(AB)(AD)

(BC)(CD)



 



AB



 



 



AD



 



 



BC



 



 



CD



 



 

 

 





Table 18

В Ошибка! Источник ссылки не найден. показан процесс построения тестирующего графа композиции ?. Как это видно из графа, его l=1, следовательно µ= l+2=3.

То есть, КАМСИ-композиция, в соответствии с тестирующим графом имеет  µ=3, а «ведет себя», как µ=4 (см. Ошибка! Источник ссылки не найден.(h)).



Более того, для КАМСИ-композиции невозможно построить описанным в литературе способом инвертор. Это видно из Ошибка! Источник ссылки не найден.(b), где выходные последовательности 1101 и 1110 не могут появиться на выходе кодера, но инвертор должен быть определен на них (см. Ошибка! Источник ссылки не найден.(b) строки  A1100 и A1111).

С другой стороны, так как известны  инверсии КАМСИ
 и
 (SS1, SS2), то можно построить инверсию автомата ? в виде композиции автоматов SS2=>SS1. В Ошибка! Источник ссылки не найден. показан процесс построения композиции
,
а в Ошибка! Источник ссылки не найден. показан процесс кодирования-декодирования, который совпадает с процессом, показанным в Ошибка! Источник ссылки не найден.(h).

Информация, приведенная в этом разделе требует проведения дополнительных исследований.

Тем не менее, даже та информация, которая приведена, позволяет сделать следующие выводы:

   





A



B



C



D



0000





+







0001





+







0010





+







0011





+







0100









+



0101









+



0110









+



0111









+



1000







+





1001







+





1010







+





1011







+





1100



+









1101











1110











1111



+

















(a)











P=0



P=1



(A1100)



(A1100),1



(A1101),1



(A1111)



(C1110),0



(A1111),1



(B0000)



(B0000),1



(B0001),1



(B0001)



(B0000),1



(B0001),1



(B0010)



(B0010),1



(B0011),1



(B0011)



(B0010),1



(B0011),1



(C1000)



(C1000),1



(C1001),0



(C1001)



(C1000),0



(C1001),0



(C1010)



(C1010),1



(C1011),0



(C1011)



(C1010),1



(C1011),0



(D0100)



(D0100),1



(D0101),0



(D0101)



(D0100),1



(D0101),0



(D0110)



(D0110),1



(D0111),0



(D0111)



(D0110),1



(D0111),0

Ситуации A1101 и C1110 отсутствуют

(b)

Table 19

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




  • Единственный, известный способ построения инвертора – это перебор в пространстве кортежей. Сложность такого перебора можно определить по Ошибка! Источник ссылки не найден. и Ошибка! Источник ссылки не найден. (
    , см. стр. Ошибка! Закладка не определена.). Следует иметь ввиду, что Ошибка! Источник ссылки не найден. и Ошибка! Источник ссылки не найден. получены при допущении, что размер кортежа m

    известен криптоаналитику.










  • 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

     







    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

     

     





     

    SS2=>SS1



    E,P





    E=0



    E=1



    S0



    S0S0



    S1S1,1



    S2S1,1



    S1



    S0S1



    S1S1,1



    S2S1,1



    S2



    S0S2



    S1S3,0



    S2S3,0



    S3



    S0S3



    S1S1,0



    S2S1,0



    S4



    S0S4



    S1S3,1



    S2S3,1



    S5



    S1S0



    S1S1,1



    S2S1,1



    S6



    S1S1



    S1S1,1



    S2S1,1



    S7



    S1S2



    S1S3,0



    S2S3,0



    S8



    S1S3



    S1S1,0



    S2S1,0



    S9



    S1S4



    S1S3,1



    S2S3,1



    S10



    S2S0



    S3S2,1



    S4S2,1



    S11



    S2S1



    S3S2,1



    S4S2,1



    S12



    S2S2



    S3S4,0



    S4S4,0



    S13



    S2S3



    S3S2,0



    S4S2,0



    S14



    S2S4



    S3S4,1



    S4S4,1



    S15



    S3S0



    S1S2,1



    S2S2,1



    S16



    S3S1



    S1S2,1



    S2S2,1



    S17



    S3S2



    S1S4,0



    S2S4,0



    S18



    S3S3



    S1S2,0



    S2S2,0



    S19



    S3S4



    S1S4,1



    S2S4,1



    S20



    S4S0



    S3S1,1



    S4S1,1



    S22



    S4S1



    S3S1,1



    S4S1,1



    S23



    S4S2



    S3S3,0



    S4S3,0



    S24



    S4S3



    S3S1,0



    S4S1,0



    S25



    S4S4



    S3S3,1



    S4S3,1









    E,P





    E=0



    E=1



    S0



    S0S0



    S6,1



    S11,1



    S1



    S0S1



    S6,1



    S11,1



    S2



    S0S2



    S8,0



    S13,0



    S3



    S0S3



    S6,0



    S11,0



    S4



    S0S4



    S8,1



    S13,1



    S5



    S1S0



    S1,1



    S11,1



    S6



    S1S1



    S6,1



    S11,1



    S7





    S1S2



    S8,0



    S13,0



    S8



    S1S3



    S6,0



    S11,0



    S9



    S1S4



    S8,1



    S13,1



    S10



    S2S0



    S17,1



    S23,1



    S11



    S2S1



    S17,1



    S23,1



    S12



    S2S2



    S19,0



    S25,0



    S13



    S2S3



    S17,0



    S23,0



    S14



    S2S4



    S19,1



    S25,1



    S15



    S3S0



    S7,1



    S12,1



    S16



    S3S1



    S7,1



    S12,1



    S17



    S3S2



    S9,0



    S14,0



    S18



    S3S3



    S7,0



    S12,0



    S19



    S3S4



    S9,1



    S14,1



    S20



    S4S0



    S16,1



    S22,1



    S22



    S4S1



    S16,1



    S22,1



    S23



    S4S2



    S18,0



    S24,0



    S24



    S4S3



    S16,0



    S22,0



    S25



    S4S4



    S18,1



    S24,1

    Table 20



    P



    1



    1



    0



    0



    0



    1



    0



    1



    0



    1



    1



    0



    1



    0



    0



     



     



    ?



    A



    A



    A



    C



    B



    D



    C



    B



    B



    D



    C



    D



    A



    A



    C



    B



     



    E2



     



    1



    1



    1



    1



    0



    0



    1



    0



    0



    0



    1



    0



    1



    1



    1



     







     



    S0



    S11



    S23



    S24



    S22



    S16



    S7



    S13



    S17



    S9



    S8



    S11



    S17



    S14



    S25



    S24



     



     



     



    1



    1



    0



    0



    1



    1



    0



    0



    0



    1



    0



    1



    0



    1



    1



    P



     



     



     



     



     



     



    1



    1



    0



    0



    0



    1



    0



    1



    0



    1



    1

    Table 21


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