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

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

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

Определение: Ключи (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)).

Под Близкими ключами понимают ключи, которым при расшифрованиисоответствуют близкие в том или ином понимании открытые сообщения. Ключ (k,s) называется -близкий к (k,s) на длине l, если нормированное расстояние Хеминга: ( , A_(k,s)A_(k,s)( )),  X^l, (т.е. с p=1), и 01. В частности, при X=Y понятие -близости на длине l совпадает с понятием l-эквмвалентности. Пусть P_l- некоторое вероятностное распределение на множ-ве SX^l. введем следующую величину: d_k,k: SX^l[0,1], где d_k,k(s, )= ( , A_(k,s)A_(k,s)( ))- близость между открытым сообщением и расшифрованным с помощью k₁. Для k,kK, и ,[0,1] рассмотрим неравенства: 4* P_l(d_k,k)1-; 5* E_l(d_k,k) Определение: Ключ k- -близкий на длине l к ключу k с уровнем , если выполнено неравенство 4*; и -близкий на длине l в среднем, если выполнено неравенство 5*. Заметим, что все рассмотренные бинарные отношения на множ-ве KS или K- бинарные отношения эквивалентности, кроме отношений -близость.

Рассмотрим следующие неравенства: 6* (А)m(A)l(A) и 7* (А)m(A)l(A). Если X=Y => A=A^-1, (А)= (А), m(A)= m(A), l(A)= l(A).

Определение: длина различимости (A)-это min l: 2-х неэквивалентных ключей: (k',s') не ~ (k,s) в А существует хотя бы одно открытое сообщение длинны l, X^l, что А_(k,s)( )A_(k,s)( ). Другими словами, при l<(A)- есть хотя бы пара неэквивалентных ключей в А, которые все открытые сообщения длины l шифруют одинаково. При l<(A)- по паре: (открытое сообщение; шифрованное сообщение)- невозможно найти p=1 ключей. ] A= ; A_k- состояния S => (A)2S-1.

Определение: длина единственности l(A)- это min l 0, такое, что все входные последовательности- диагностические, т.е.  (k',s') не ~ (k,s) в А и  X^l выполняется неравенство A_(k,s)( )A_(k,s)( ). Другими словами при длине l l(A) по любому X^l и соответствующих =A_(k,s)( ) ключ (k,s) определен однозначно с точностью до эквивалентности. С другой стороны: При l<l(A) хотя бы одна пара (открытое сообщение; шифрованное сообщение), по которой вы не найдете ключа с точностью до эквивалентности. Для шифросистем: колонной замены или гаммирования – неравенства 6* и 7* обращаются в равенство => l(A)< и l(A)=(A) соответственно.

Пусть m=m(A)< (память), т.е.  : X^mY^m+1X и для (k,s) KxS, и для (y₁,…,y_l)Y^l, lm+1, выполняется неравенство x_m+1,…,x_l= M()_{(x ,…,x ,y ,…,y )} (y_m+1,…,y_l), где x₁,…,x_l=А_(k,s)(y₁,…,y_l). Начиная с m+1 такта шифратор приема можно заменить на автомат М(П):

Если мы можем реализовать такую процедуру, то говорят, что мы производим бесключевое чтение вперед. Если A- подстановочный, то память m(A') = m(revA'), - функция памяти revA; Имеем кусок открытого сообщения (x_i,...,x_i+m-1):

• Безключевое чтение назад. Для невозможности реализации этого метода необходимо, чтобы память была достаточно большой: m log_|x|(|K|x|S|).

Вопрос 36.

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

Последовательность суммарных шифров зависит только от ключа (k,s) и не зависит от открытого сообщения.

Определение1:Шифросистема (А, А)- шифросистема колонной замены, если приведенная форма шифратора передачи есть внутренне автономный автомат . При X=Y- равносильна . Получаем: 1* = =( )^-1. Шифросистемы колонной замены получили наибольшее распространение в практике т.к. они не распространяют искажение.

Теорема1. Пусть (A, A)- произвольная шифросистема, X=Y, тогда шифросистема приема A не распространяет искажений , когда (A, A)- шифросистема колонной замены(ШКЗ).

Доказательство: т.к. X=Y => A=A^-1- инъективный, по следствию (] A- инъективный автомат => А- не распространяет искажений  A/~- внутренне автономный) => нераспространение искажений инъективным автоматом А  - внутренне автономен  (1*) -внутренне автономен => (A, A)- ШКЗ по определению.

Теорема2: Пусть (A, A)- ШКЗ, Г={f_(k,s)(k,s)KS}- множ-во всех суммарных шифров шифратора передачи, тогда а) n(A) : ГⁿГ: шифратор передачи А- представляется автоматом

Причем, при n<(A) такой  не существует. б) (А)=m(A)=l(A)- если (А, А)- шифросистема гаммирования.

Доказательство: Пусть =(X, KS, Г, h, ); _((k,s),x)=f_(k,s);- не зависит от входа => /~ -автономен; Отношения в А и совпадают => (A)=( ) => т.к. было упражнение, где доказано, что - представляется () , без узла: y<--<--x; следует A- представляется (). Для б): Пусть X^=(A), A_(k,s)( )=A_(k,s)( ), тогда по определению шифросистемы гаммирования следует, что совпали последовательности суммарных шифров: _(k,s)( )= _(k,s)( ) => это равенство справедливо для любой последовательности xX^ , последовательность суммарных шифров не зависит от x₀ => ключи (k,s) и (k,s) эквивалентны. последовательность является диагностическим экспериментом, а l-минимальное, тогда =(A)l(A) следует в силу ранее определенного неравенства (А)m(A)l(A) теорема доказана.

При таком представлении ключами являются ( ). Их всего Гⁿ KS-налицо уменьшение трудоемкости подбора. (А)log_Г(KS), при малых длинах различимости. Из определения 1 и равенства 1* => при X=Y всякая ШКЗ (А^-1, А) может быть представлена с точностью до эквивалентности шифраторов при фиксированном долговременном ключе k в следующем виде:

блок: (1)(1) - совпадают с автономным автоматом, реализующим h_k: SS, в блоке (2)- реализуется суммарный шифр f_(k,s) в данном такте, в блоке (2)- обратное к нему биективное преобразование, т.е. f_(k,s)= f^-1_(k,s): При X=Y={0,1)  2 тождественных подстановки: => , что блоки (2) и (2) совпадают и представляются в виде:

, где , _k: SX, получаем следующее утверждение:

Утверждение: При X=Y={0,1} всякая ШКЗ (с точностью до эквивалентности шифраторов) является инволютивной шифросистемой и шифросистемой гаммирования. S={0,1}ⁿ.

Вопрос 37.

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

Шифросистема (A',A) удовлетворяет следующим условиям: X=Y и h- не зависит существенно от ключа (k,x)KX, т.е. получаем соответствие 1* h=h((k,s),x)=h(s); h: SS - это шифросистема колонной замены, т.к. h не зависит от x.

Утверждение: Если выполнено 1* h- одноцикловая подстановка множ-ва S; k₁,k_2-- два долговременных ключа; s₁,s₂ - два разовых ключа; h^d(s₁)=s₂, где d - расстояние от s₁ до s₂. Справедливы следующие утверждения: а) (k₁,s₁)~(k₂,s₂)  f_(k1)(s,x)=f_(k2)( h^d(s),x) ,s,x; б) k₁~k₂  d 0: f_(k1)(s₁,x)=f_(k2)(h^d(s),x),s,x; в) (k₁,s₁), (k₂,s₂)- изоэквивалентны  g₁: XX, g₂:YY- подстановки: f_(k1)(s,x)=g₂(f_k2(h^d(s),g₁(x))) ,s,x

Доказательство: а): (k₁,s₁)~(k₂,s₂)  выходные последовательности при начальных состояниях совпадают для любой входной последовательности  f_(k1)( hⁱ(s₁),x)= f_(k2)(hⁱ (s₂),x), i 0 ,x  f_(k1)( hⁱ(s₁),x)= f_(k2)(h^d(hⁱ(s₁)),x) i 0 ,x, а т.к. h- одноцикловая => hⁱ-пробегает все S => f_(k1)(s,x)= f_(k2)(h^d(s),x); x,s. Эквивалентность ключей - разовое состояние между ними.

б) по определению понятия эквивалентности долговременных одноцикловых ключей, получаем, что k₁~k₂  s₁,s₂: (k₁,s₁)~(k₂,s₂) => (а) для некоторого d.

в) Определение изоэквивалентности для рассматриваемого ШС означает: g₂(f_(k2)(hⁱ (s₂),g₁(x)))=f_(k1)( hⁱ(s1),x) i 0,x; далее точно также как и в доказательстве пункта а) приходим к равенству: g₂(f_(k2)(h^d (s),g₁(x)) = f_(k1)(x) x,s.

Вопрос 38.

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

Пусть P_l- равномерное распределение на множ-ве SX^l; P_l(s,x)=S^-1*X^-l; f_k(s,x)=g_{ (s)}(x); _k: SГ; {f_(k,s)(k,s)KS}={g_Г}; g_g_’, . Пусть (A^-1, A)- шифросистема гаммирования, т.е. различные суммарные шифры g_ не имеют одинаковых переходов, => для  X^l, sS, k,kK выполняется равенство: ( ,A^-1_(k,s)A_(k,s)( ))={A^-1_(k,s),A_(k,s)- биективны}=( A_(k,s)( ),A_(k,s)( ))= (()_k(h^-1(s)),_k(h^i-1(s))) => если h- биективна, то среднее значение k - E_ld_kk=S^-1(_k,_k); где - расстояние Хэмминга: (_k,_k)={sS_k(s)_k(s) };

Утверждение: Для шифрсистемы гаммироваания при условии h=h((k,s),x)=h(s) с биективной функцией h и функцией выходов, представленной в виде: f_k(s,x)=g_{ (s)}(x); {g_g_’, }: Следующие свойства равносильны для k,kK, {0,1} и  длины lN:

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

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