On local exponents of the mixing graphs for the functions realized by A5/1 type algorithms.pdf Алгоритм A5/1 [1, с. 389] -поточный шифр гаммирования, построенный на основе трёх линейных регистров сдвига (ЛРС) над GF(2) длин 19, 22 и 23. Сумма битов, снимаемых с крайних ячеек ЛРС, образует гамму. Нелинейность преобразования состояний генератора достигается за счёт самоуправляемой схемы неравномерного движения регистров (каждый такт 2 или 3 регистра сдвигаются на 1 шаг). Опишем перемешивающий граф Г для обобщения генератора A5/1. Обозначим (x1,... , xn+m+p) начальное состояние генератора, S(/) -множество номеров существенных переменных функции /. Пусть генератор состоит из трёх регистров длин n, m и p с функциями обратной связи /1, /2 и /3, чьи множества точек съёма суть S(/1) = {b1,... , bv}, S(/2) = {c1,... , cM} и S(/3) = {d1,... , dn} соответственно. Движение ЛРС на 0-1 шагов определено булевой функцией u(xt, xT, Xq) от трёх существенных переменных, где S (u) = {t, т, в}; 1 ^ t ^ n; t Е S (/1); n +1 ^ т ^ n + m; тЕ S (/2); n + m +1 ^ в ^ n + m + p; в Е S (/3). Тогда преобразование g состояний генератора задано системой булевых функций g = {g^, ... , Xn+m+p), . . . , gn+m+p(X1, ... , Xn+m+p)}, где S(gn) = S(/1) U {n} U S(u), S(gi) = {i, i + 1} U S(u), i = 1,..., n - 1, S(gn+m) = S(/2) U {n + m} U S(u), S(gi) = {i, i + 1} U S(u), i = n + 1,..., n + m - 1, (1) S(gn+m+p) = S(/з) U {n + m + p} U S(u), S(gi) = {i, i + 1} U S(u), i = n + m + 1,..., n + m + p - 1. Из равенств (1) следует, что в Г в каждой вершине имеется петля. Соответствующие ЛРС подграфы графа Г являются сильносвязными, и имеются дуги (t, s), (т, s) и (0, s) при любом s = 1,... , n+m+p. Следовательно, орграф Г сильносвязный, примитивный. Определим exp Г и локальный экспонент * J-exp Г [2] при J = {1, n + 1, n + m + 1}. Так как Г содержит n + m + p петель и дуги (t, s), (т, s) и (0, s), s = 1,..., n + m + p, то в соответствии с теоремой 2 [3] exp Г = 1 + max{ max p(i,t), max p(i,T), max p(i,0)}, (2) i=1,...,n i=n+1,...,n+m i=n+m+1,...,n+m+p где p(i, a) -длина кратчайшего пути в Г от i до а, при этом p(i, i) = 0. Пусть A С {1,..., n + m + p}, обозначим p(i, A) = minp(i, a), где p(i, A) = 0, если i G A. Тогда p(i, t) = p(i, S(/1)) + 1 + n - t при i < t, p(i, t) = i - t при i > t; (3) p(i, т) = p(i, S(/2)) + 1 + n + m - т при i < т, p(i, т) = i - т при i > т; (4) p(i, 0) = p(i, S(/3)) + 1 + n + m + p - 0 при i < 0, p(i, 0) = i - 0 при i > 0. (5) Из равенств (2)-(5) следует expT = 2 + max{n - t + max p(i,S (/1)), i=1,...,t-1 (6) n + m - т + max p(i,S (/2)),n + m + p - 0 + max p(i,S (/3))}. i=n+1,...,T-1 i=n+m+1,...,$-1 Из (6) в данных условиях получаем: 1) expT принимает наименьшее значение, равное 1 + max{[n/v], [m/^], [p/п]}, если t = n, т = n + m, 0 = n + m + p и множества S(/1), S(/2) и S(/3) разделяют приблизительно на равные отрезки соответственно числовые множества {1,..., n}, {n + 1,..., n + m} и {n + m + 1,..., n + m + p}; 2) exp Г принимает наибольшее значение, равное max{n, m,p}, если t = 1, т = n+1, 0 = n + m +1. В силу наличия в Г дуг (t, s), (т, s) и (0, s) при любом s = 1,... , n + m + p оценка локального экспонента * J-exp Г не зависит от J и совпадает с оценкой экспонента Г. В схеме генератора A5/1 n =19, m = 22, p = 23, v = 4, ^ = 2, n = 4. Расчёты показали, что * J-exp Г = 21, где J = {1, 20, 42}. Длина холостого хода генератора A5/1 (количество начальных тактов, при которых знаки гаммы игнорируются) равна 100, то есть более чем в 4 раза превышает значение экспонента. Это, по-видимому, надёжно обеспечивает зависимость каждого знака гаммы от всех знаков начального состояния генератора и делает конструктивно обоснованным выбор длины холостого хода.

Скачать электронную версию публикации