Решенные билеты (1085496), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

а) k,k- -близкие ключи на длине l в среднем.

б) S^-1*(_k,_k).

Вопрос 39.

Теоретико-автоматная характеризация шифросистем самовосстановления.

Определение: Шифрсистема (ШС) (А, А)- ШС самовосстановления (самосинхронизирующаяся) с задержкой n, если для  долговременного ключа kK шифратор приема A_k является автоматом самовосстановления и n= (A_k); Процесс синхронизации можно упростить, если в шифраторе приема искать шифры с большой вероятностью самовосстановления. Они не требуют установки начальных тактов. Идеальный случай- когда весь шифратор приема- автомат самовосстановления.

Теорема1: Для  ШС: (A, A) следующие утверждения равносильны: а) (А, А)- ШС самовосстановления с задержкой n; б) Для kK сюръективная по (n+1)-й переменной функция: Yⁿ⁺¹->X, такая, что A_k (A'_k)~R₀(_k); Обозначения: A_k- шифратор приема при ключе k; (A_k)- существенный подавтомат А_k; R₀(_k)- ПЛЗ с выходной функцией _k; Если |X|=|Y|, то при условии б) следует все n - достижимые состояния приведенной формы шифратора передачи - существенны и существенный подавтомат шифратора передачи A_k^[c]~R(^-1_k), где: A_k^[c]- существенный подавтомат; R(^-1_k)- регистр сдвига; ^-1_k- функция обратной связи, которая обратна к _k по (n+1)-ой переменной.

Доказательство:Равносильность а) и б) следует из определения, доказанного ранее следствия(для А, nN₀ следующие свойства равносильны: а) А- автомат самовосстановления с задержкой не более n; б) A R₀() для некоторого , т.е.  : Xⁿ⁺¹Y; в) A A^[c]~R₀() для некоторого ) и сюръективности автомата А_k. Далее предположим, пусть выполнено б) и X=Y => A_k=A^-1_k, поскольку (A^-1_k)^[c]=(A_k^[c])^-1, то A_k^[c]=(( A_k^[c])^-1)^-1=(( A_k^-1)^[c])^-1 ~ R₀(_k)^-1=R(^-1_k); Поскольку =( )^-1, то все n- достижимые состояния приведенной формы - также существенны.

Эта теорема позволяет сделать следующий вывод: приX=Y любую ШС самовосстановления с задержкой не более n можно, исключая несущественные состояния в шифраторах, представить шифросистемой: R=(A^-1, A), у которой множество разовых ключей S=Yⁿ и для kK шифратор приема есть A_k^-1=R₀(_k), шифратор передачи есть A_k=R(_k), а функция _k: Yⁿ⁺¹X- функция, биективная по (n+1)-ой переменной _k^-1: YⁿXY, функция обратная по (n+1)ой переменной к _k. Другими словами шифросистема R имеет следующий вид:

Вопрос 40.

Характеризация эквивалентности ключей шифросистем самовостановления.

Утверждение:Для ШС самовосстановления R и k,kK справедливы следующие утверждения: а) для s,sYⁿ следующие свойства равносильны: 1. (k,s)(k,s) эквивалентны с задержкой в А^-1 ; 2. долговременные ключи k~k - эквивалентны. 3. _k=_k - совпадают.

б) Следующие свойства равносильны: 1. существуют разовые ключи s,sYⁿ, такие, что ключи (k,s) и (k,s)- изоэквивалентны. 2. шифратор приема при ключе k A_k^-1 изоморфен шифратору приема при ключе k' A_k^-1, т.е. A_k^-1 A_k^-1 (изоморфны). 3. существуют подстановки g₁: XX и g₂: YY, такие, что _k=g₁_k'g₂^x(n+1), где g₂^x(n+1): (y₁,…,y_n) g₂(y₁),…,g₂(y_n).

в) (А^-1)n – длина различимости шифратора приема.

Доказательство: а) импликация (1) => (3)- следует из ранее доказанного утверждения ("о единственности ПЛЗ":] hN₀; _i: Xⁿ⁺¹Y, i=1,2; и некоторое состояние R₀(₁) эквивалентно некоторому состоянию R₀(₂) => ₁=₂);импликация (3) => (2)- из определения (долговременные ключи k, k шифросистемы (А, А)- эквивалентные на передаче (приеме), если A_k~A_k (A_k~A_k)), а (2) => (1)- из того, что все состояния ПЛЗ эквивалентны с задержкой.

б) (1) => (3)- очевидна в силу определения о изоэквивалентных ключах (ключи (k,s), (k,s)- изоэквивалентные (эквивалентные на приеме с точностью до простой замены), если биекции g₁: XX, g₂: YY:g₁^*A_(k,s)g₂^*=A_(k,s), где g^*(y₁,…,y_l)=(g(y₁),…,g(y_l))) и определения шифросистемы R. Если выполняется (3), то тройка (g₁^-1,g₂^xn,g₂): R₀(_k)R₀(_k)- изоморфизм(по определению изоморфизма), т.е. (2)- доказано; импликация (2) => (1)- очевидно по определению и из эквивалентности.

в) т.к. A_k^-1=R₀(_k),то n- эквивалентность совпадает с эквивалентностью (свойство ПЛЗ), и по определению длинны различимости ((A^-1)n) в) выполнимо.

Вопрос 41.

Характеризация близости ключей шифросистем самовосстановления.

Вопрос о близости ключей шифросистемы R рассмотрим для случая равномерное распределение на множ-ве SX^l: 1* - P_l(s, )=X^-(l+n); ( ,A^-1_(k,s) A_(k,s)( )){-растояние Хэминга, заменим A_(k,s)( ) на } = (A^-1_(k,s)( ),A^-1_(k,s)( ))= (_k(y_i,…,y_i+n),_k(y_i,…,y_i+n)), где (y₁,…,y_n)=S, а (y_n+1,…,y_n+l)=A_(k,s)( );

E_ld_k,k= X^-(l+n) (_k(y_i,…,y_i+n),_k(y_i,…,y_i+n))=

X^-(l+n) (_k(y_i,…,y_i+n),_k(y_i,…,y_i+n))= =|{ | }|, отсюда получаем следующее утверждение:

Утверждение: Для ШС самовосстановления R при условии 1* следующие свойства равносильны для k,kK, {0,1}, lN: а) k, k- -близкие ключи на длине l в среднем; б) X^-(n+1)(_k,_k). В случае когда X=Y={0,1} функция _k представляется в виде: _k=_k^-1= (x₁,…,x_n)x_n+1, и величина 2^-(n+1)(_k,_k)=2^-n ;

Покажем, что при некоторых довольно слабых ограничениях, шифраторы шифросистем самовосстановления имеют бесконечную память и бесконечную длину единственности. Предположим, что выполнено следующее условие: k,kK: _k_k, но _k(y₁,…,y)=_k(y₁,…,y) для некоторого yY, тогда в силу утверждения(:для ШС самовосстановления R и k,kK справедливы следующие утверждения: а) для s,sYⁿ следующие свойства равносильны: 1. (k,s)(k,s) эквивалентны с задержкой в А^-1 ; 2. долговременные ключи k~k - эквивалентны. 3. _k=_k - совпадают. ) => ключи (k,s) не ~ (k,s), для s,sS, но A_{(k,(y ,…,y))}(y₁,…,y)= A_{(k,(y ,…,y))}(y₁,…,y) l, это означает, что последовательность из одних y для таких ключей не является установочным экспериментом => память автомата А совпадает с памятью стандартного обратного и равна .

Литература:

[1] Т.В. Кузьминов “Криптографические методы защиты информации”.

[2] В.И. Нечаев “Элементы криптографии. Основы теории защиты информации”.

[3] А.С. Кузьмин “Основы криптографии”.

[4] http://virlib.eunnet.net/books/numbers/text/22.html

[5] http://www.pl-computers.ru/article.cfm?Id=286&Page=5

Курс лекций по квантовой криптографии. Арбеков И.М.

Курс лекций по Теории автоматов. Солодовников В.И.

Характеристики

Список файлов ответов (шпаргалок)