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

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

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

Определение: А- внутренний самовосстанавливающийся с задержкой n, если h(s, )=h(s, ) s, sS; Xⁿ, причем n- минимальное. Другими словами это определение равносильно следующим условиям:  =1- все состояния А совпадают с задержкой и =n –задержка совпадения.

Теорема (описание автоматов внутреннего самовосстановления): пусть A- автомат внутреннего самовосстановления с задержкой n, определим _A,n: Xⁿ⁺¹Y; _A,n: XⁿS равенствами: _A,n(x₁,…,x_n+1)=f(h(x₁,…,x_n),x_n+1), _A,n(x₁,…,x_n)=h(s,(x₁,…,x_n)), для x₁,…,x_n; s.=>  _A,n: R₀(_A,n)A- внутренний гомоморфизм, причем образ этого гомоморфизма равен А^[c]. Вывод: всякий автомат внутреннего самовосстановления можно заменить на ПЛЗ.

Вопрос 35.

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

Процесс передачи информации в системе шифрованной связи состоит из 3-х последовательных этапов: 1) зашифрование; 2)передача шифрованной информации по КС; 3) расшифрование. Эти процессы могут быть либо разделены во времени, либо происходить одновременно.Условная схема шифрованной связи:

, где X^*. Если нет помех, то такую схему для дискретной информации можно записать как последовательное соединение автоматов: A <-\ A. Тогда ТА-модель выглядит следующим образом: A=(X, KS, Y, h, f), A=(Y, KS, X, h, f) - автоматы, которые удовлетворяют следующим условиям: а) А- инъективен; б) h((k,s),x)=(k,s) k, s, x , т.е. в процессе работы автомата левая координата состояния, не меняется от такта к такту; в) А- стандартный левый обратный к А; г) h((k,s),x)=(k,s) k, s, x, т.е. аналогично б). Из ранее доказанной теоремы (Следующие свойства равносильны: а) А имеет левый обратный; б) А-инъективный; в) sS, f_s: XY- инъективна; если в свойствах а), б), в)- левый заменить на правый, а инъективный на сюръективный, то полученные свойства будут равносильны) =>, что для А с а) и б) =>  A с в) и г), причем, при X=Y => A- определен однозначно и А=А^-1;

Определение: При условиях а), б), в), г) пара автоматов: (A, A)- автоматная шифр. система (ШС). Опишем ранее известные параметры на языке ШС: X- открытый шифр; Y- шифр. алфавит; (KS)- множ-во ключей; K- множ-во долговременных ключей; S- множ-во разовых ключей; A- шифратор передачи; A- шифратор приема; f_(k,s): XY- частичные функции- суммарный шифр при ключе (k,s), т.е. f_{(k,s )}(x_i)=y_i. Процесс шифрования открытого сообщения X^* происходит следующим образом: для шифраторов А и А в качестве начальных состояний устанавливается один и то же ключ: (k,s) при этом шифраторы синхронизируются. Далее открытое сообщение подается на вход шифратора передачи – А и перерабатывается в криптограмму - вых. последовательность А при начальном состоянии (k,s). через КС подается на вход шифратора приема - А и расшифровывается в открытое сообщение: =A_(k,s)( )=A_(k,s)(A_(k,s)( )). При этом необходимо сделать некоторые замечания: 1) реальная шифроаппаратура может работать в разных режимах: -шифрования (основной режим); - синхронизация; далее будем рассматривать только режим шифрования. 2) -открытое сообщение (открытая информация+служебная информация). В реальной ситуации далеко не все последовательности из X^*- могут быть открытыми сообщениями, т.е. 0X^*, но это очень усложняет рассуждения => предпологаем, что X^*. 3) Обобщая введенную модель, можно отказаться от условий в) и г) и считать А- произвольным левым обратным к А (не обязательно стандартный), однако, в наиболее интересных случаях: X=Y =>  левый обратный к А- стандартный обратный к А + ключи на приеме и передаче совпадают => не обобщаем. 4) Во введенной модели предполагается, что некоторая часть ключа (k,s)- может быть несекретной, т.е. вообще передаваться в КС. 5) При использовании в шифраторах приема узлов с большой вероятностью самовосстановления (А-самовосстановления) соответствующие этим блокам части разовых ключей на приеме и передаче могут быть различены в какие-то моменты времени, т.к. через небольшое кол-во тактов они станут одинаковы с большой вероятностью. (т.е. эту часть можно не синхронизировать).

Долговременный ключ от текста к тексту не меняется => kK A_k- внутренний подавтомат А с множ-вом состояний: {k}S; A_k- внутренний подавтомат А с множ-вом состояний: {k}S - это корректно в силу б) и г), тогда А= ; А= , причем: A_k- стандартный левый обратный к А_k, тогда A_k- шифратор передачи при долговременном ключе k, A_k- шифратор приема при долговременном ключе k =>, а А_k- стандартный правый обратный к А_k, тогда шифраторы приема/передачи представляются в виде:

(1)(1) – реализуют h_k автомата А_k; (2) и (2)- автоматы БП, реализующие f_k, f_k. На процесс шифрования можно смотреть как на процесс выработки суммарных шифров: в i-ом такте вырабатывается f_{(k,s )}(x_i)=y_i. В соответствии с теоремой1: все суммарные шифры - инъективные отображения, а при X=Y- биекции и f_(k,s)=f^-1_(k,s). Рассмотрим один из подходов к реализации f и f: Пусть Г- некоторое множ-во, Г<, и пусть : KSГ- отображение из множ-ва ключей в Г, пусть G: ГXY, причем G- инъективная по x функция. =>  G: ГYX: G(,G(,x))=x, ,x {обратная слева к G по второй переменной} => Блоки (2) и (2) строятся следующим образом:

Блоки G и G' - шифрующие блоки. При X=Y={0,1} => f=f- всегда совпадают и f_k(s,x)=_k(s)x. Пусть X=Y; X>2. Метод построения шифрующих блоков (метод образующих) состоит из следующих этапов: а) выбираем L=(Z, X, g)- автомат без выхода, подстановочный; б) фиксируем: lN- достаточно большое; в) выбираем: _k:KSГ, где Г=Z^l;- эти вектора- управляющие комбинации, а l- длина управляющей комбинации; г) f_k(s,x)=g_{ (s)}(x)=g_z … g_z (x);- финальное состояние автомата L при начальном состоянии x и входной последовательности (z₁,…,z_l), тогда _k(x)=(z₁,…,z_l), f_k(s,x)= g_z … g_z (x)- финальное состояние реверса автомата L при начальном состоянии x и подаче на вход управляющей комбинации в обратной последовательности:

Наибольшее распределение получил случай, когда: X=Y={0,1}; Z={0,1}; Z=R().

Определение: Шифросистема (А, А) -называется ШС гаммирования, если ее суммарные шифры обладают следующим свойством: (k,s), (k,s)KS: (f_(k,s) f_(k,s)) => f_(k,s)(x) ₎f_(k,s)(x) xX, => для таких шифросистем, зная один только переход, например, f_(k,s)(x)=y, т.е. xy, тогда f_(k,s)- определяется однозначно и { f_(k,s)(k,s)KS}Y; всего f_(k,s)- число размещений из YпоX: (Y!) / (Y-X)!.

Определение: шиифросистема инволютивная (обратимая) -если шифраторы приема и передачи совпадают.

Утверждение(критерий инвалютивности ШС):Шифросистема (А, А)- инволютивна  X=Y, (k,s)KS, xX: а) f^-1_(k,s)=f_(k,s) (т.е. все суммарные шифры- инволюции, т.е. f²=e, т.е. порядок подстановки 2 (т.е. из циклов длины 1 или 2)); б) h((k,s),f((k,s),x))=h((k,s),x). Доказательство:"<=" : Из а), б), и условия => А=А^-1, т.к. X=Y, а из свойств а) и б) – по построению стандартного обратного => A^-1=A; "=>" : Если А=А, то X=Y => A=A^-1- стандартный обратный к А, а по построению стандартного обратного из свойства инволютивности шифросистемы => а) и б).

Для (k,s), (k,s)KS: рассмотрим следующие утверждения: 1* - (k,s)~ (k,s) в А; 2* - (k,s)~ (k,s) в А 3* - А_(k,s)A_(k,s)=E_X* (E_X*- тождественное преобразование множ-ва X^*). Очевидны следующие импликации: 1* => 3* (из определения левого (правого) обратного), 2* => 3*. При X=Y- все 3 свойства равносильны (т.к. А=А^-1).

Определение: Ключи (k,s), (k,s)- эквивалентные на передаче, если выполнено свойство 1*; эквивалентные на приеме, если выполнено 2*; и, если выполнено 3*, то (k,s)- ключ расшифрования для (k,s). Число (А)- число неэквивалентных ключей на передаче; Число (А)- число неэквивалентных ключей на приеме, при этом, если X=Y, то ‘на приеме’ и ’на пердаче’ можно опустить.

Определение:Долговременные ключи k, k шифросистемы (А, А)- эквивалентные на передаче (приеме), если A_k~A_k (A_k~A_k). Если в двух предшествующих определниях заменить ‘~’ на ‘’, то приходим к более общему понятию - эквивалентность ключей с задержкой, которое представляет особый интерес для шифраторов с блоками- автоматами самовосстановления.

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

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