Дополнение к автоматной части (Ответы на экз вопросы (Криптография)), страница 2

4. Задание автоматным отображением

Автоматы, у которых входные алфавиты совпадают- сравнимые.

Определение 2.1: Состояния sS, sS- l-эквивалентные- т.е. s s, если выходные последовательности при начальных состояниях s и s, соответственно, всегда совпадают на длине l: A_s( )=A_s( )  X^l; Если s s для l, то s и s- эквивалентны, т.е. s~s;

Определение 2.3:Фактор-автомат: =A/~=(X, S/~, Y, , )- приведенная форма автомата А, а число (А)=S/~-приведенный вес А (число нетривиальных состояний А). Если (А)=S ‘~’=’’=0, то А- минимальный (приведенный)

(у которого нет различных эквивалентных состояний). Число неэквивалентных состояний- число отображений автомата- S/~=[A]; S/~=^l[A]

Определение 2.6: Min lN₀: s,sS из условия s s следует: s~s (т.е. =~)- длина (степень) различимости: (A).

Диаметр сильносвязного автомата- число d(A)=max{l(s₁,s₂)s₁,s₂S}, Где l(s₁,s₂)- минимальная длина входной последовательности, переводящей s₁s₂ (l(s₁,s₂)=0), т.е. минимальный путь из вершины s₁ в вершину s₂ в графе автомата А.

Определение 2.12: A=(X, S, Y, h, f)- представляется автоматом А=(X, S, Y, h, f) (или А представляет А), если XX, sS sS: A_s( )=A_s( )  X*

Если А представляет А и А представляет А, то А~А, т.е. автоматы работают одинаково. X=X; Yf(S,X)=f(S,X)Y, т.е. Y=Y- т.е. подразумеваем для эквивалентных автоматов.

Определение 2.15: A и A- l-эквивалентные: A A- если sS sS: s s и наоборот, А А  ^l[A]=^l[A]

Определение 2.30: Состояния sS, sS- эквивалентные с задержкой k: s s, если для любых входных последовательностей ₁X^k и X^* выходные последовательности этих автоматов: A_s( ₁, ), A_s( ₁, )- совпадают, начиная с (k+1) знака или, другими словами: h(s, ₁)~h(s, ₁),  ₁X^k.

Определение 2.32: Минимальное l, при котором =- задержка эквивалентности А- (А).

Определение 2.37:Минимальное kN₀: для А = = -задержка совпадения А: (A)

Определение 2.38:Гомоморфизм (, , ): AA- изоморфизм с задержкой. Если , - биекции (как у любого изоморфизма), - сюръективно и sS ^-1(s) все состояния в полном прообразе совпадают с задержкой.

Определение 4.14: A- левый (правый) обратный к А- если sS sS: A_s(A_s( ))= , X^* (A_s (A_s( ))= , yY^*)

Определение: обратимый  если он имеет и левый и правый обратные.

Определение: инъективный (сюръективный) если все его автоматные отображения инъективны (сюръективны).

Определение: биективный, если он инъективный и сюръективный.

Определение 4.22: А- автомат без потери информации (БПИ), если s,sS; , X^* справедлива импликация:

s~s, h (s)=h (s), A_s( )=A_s( ) => = ;

Определение 4.23: Состояние s автомата А- состояние с потерей информации, если  2 различные входные последовательности  , для которых h (s)=h (s), A_s( )=A_s( );

Определение: Автомат – автомат БПИ-1, если он инъективен, т.е. s~s, A_s( )=A_s( ) => = (т.е. в определении 4.22 удалить 2-ую эквивалентность).

Определение: А- автомат БПИ-2, если в определении 4.22 удалить 1-ую эквивалентность.

Определение 4.32: : Y^bX^a+1Y; a,bN₀ определим автомат: M()=(X, Y^bX^a, Y, h, f), h((y₁,…,y_b,x₁,…,x_a),x)=(y₁,…,y_b,(y₁,…,y_b,x₁,…,x_a,x),x₂,…,x_a,x);

f((y₁,…,y_b,x₁,…,x_a),x) =(y₁,…,y_b,x₁,…,x_a,x). В частности, при b=0 M()=R₀()- проходная линия задержки длины a. При а=0 M()=R()

Определение 4.33: Функция памяти А- всякая функция : sS, =x₁,…,x_tX^t, t1+max{a,b}; A_s( )=y₁,…,y_t => y_t=(y_t-b,…,y_t-1,x_t-a,…,x_t) => Память автомата А- число m(A)= max{a,b};

Если , то m(A)= иначе m(А)<; Если m(A)<, то А- автомат с конечной памятью

Определение 4.37: Входная последовательность X^*- диагностическая для А, если s,sS справедлива импликация: A_s( )=A_s( ) => s~s и последовательность - установочная, если A_a( )=A_s( ) => h(s, )~h(s, ) (эквивалентность финальных).

Определение 4.43: Длина единственности- l(A)- минимальное lN₀:  входная последовательность X^l- диагностическая для А. l(A)=, если таких l не существует.

Определение: Если в КС были искажены k знаков, то в случае, когда в последовательности число искажений >k => произошло распространение искажений, иначе- искажения не распространились.

] : X^*Y^*, сохраняя длины, т.е. (X^l)Y^l, l ( , )- количество номеров несовпадающих членов в этих последовательностях, т.е. ( , )= {i= x_i x_i },  , X^l (( , ) - метрика Хемпинга)

Определение4.59 : Отображение , сохраняющее длины слов- распространяющее искажения не более чем в k раз, если lN; , X^l выполняется неравенство: (( ),( ))k*( , ) ; Если k=1 => - отображение, нераспространяющее искажений.

Шифр колонной замены- порожденный множ-вом подстановок {g_l,tl,tN_, tl}, g_l,tG(X)S_x- (симметрическая группа подстановок), называется отображение : X^*X^*, определяемое по формуле:

(x₁,…,x_l)= g_l,1(x₁),…,g_l,l(x₁); (( )( ))=( , )

Шифр перестановки- порожденный множ-вом подстановок {p_llN}, p_lS_l, преобразование : X^*X^*, определяется равенством: (x₁,…,x_l)= ,…, ; (( ),( ))=( , ); {=> - тоже не распространяет искажений}

Определение 4.65: А- не распространяющее искажений по , если для sS, lN, =(x₁,…,x_l), =(x₁,…,x_l)X^l: x_ix_i, i выполняется неравенство: (A_s( ),A_s( ))( , ) {При =x² => автомат А- нераспространяющий искажений}

Самовосстановление в автоматах: - процесс перехода этого автомата из произвольных 2-х или более состояний в эквивалентные (т.е. в один и тот же класс эквивалентности) под действием одной и той же входной последовательности. Чем больше вероятность такого события- тем устойчивее автомат к случайным сбоям (во входной последовательности, в функции перехода…)

Определение: Матрица переходных состояний k-грамм- матрица вида B_k=(P( ), которая определяется так: - матрица размера S^kS^k ; - строки и столбцы- занумерованы векторами состояний длины k: ^k={ }; - на пересечении строки =(s₁,…,s_k) и столбца =(s₁,…,s_k) стоит вероятность: P( )=X^-1{xXh(s_i,x)=s_i)} i,k.

Определение: (A): = -l₀, a); -, б); - задержка самовосстановления в А

Определение 4.68: А- самовосстановления с задержкой n, если h(s, )~h(s, ) s,sS, Xⁿ, причем, n- минимальное такое. Здесь n- задержка самовосстановления автомата А.

Определение 4.71: Два автомата: A и A с одним и тем же входным алфавитом- эквивалентные с задержкой n: A A, если для s автомата А s автомата А: s s и наоборот.

Определение: Внутреннее самовосстановление- (т.е. вместо ~,=)- это процесс перехода из 2-х состояний: s, s в одинаковые под действием одной и той же : h(s, )=h(s, )

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