On characteristics of a three-stage key generator with an alternating step modified with key generator "Stop-Forward".pdf Введение Генераторы гаммы с неравномерным движением, активно исследуемые как в России, так и за рубежом [1, гл. 18], относительно просто реализуются и обладают рядом положительных криптографических свойств: большая длина периода, высокая линейная сложность и др. К этому классу относятся двухкаскадные генераторы с перемежающимся шагом, построенные на основе двух генераторов «стоп-вперед». Для их обобщения - трёхкаскадных генераторов с перемежающимся шагом - получен ряд свойств. 1. Функционирование трёхкаскадного генератора с перемежающимся шагом Первый управляющий каскад есть фильтрующий генератор на базе ЛРС-x длины n и фильтрующей функции /(x1,...,xn), генерирующий управляющую гамму {Y^ : i = 1, 2,... }. Второй управляющий каскад состоит из ЛРС-y и ЛРС-z соответственно длины m (номера ячеек n + 1,..., n + m) и ^ (номера ячеек n + m + 1, ..., n + m + которые управляются гаммой {7i,x : i = 1, 2,... } и управляют третьим каскадом с помощью последовательности сумм знаков Yi,y Ф 7i,z, снимаемых с ячеек n + m ЛРС-y и n + m + ^ ЛРС-z соответственно. Третий генерирующий каскад состоит из ЛРС-u и ЛРС-v длин r (номера ячеек n + m + ^ + 1,..., n + m + ^ + r) и р (номера ячеек n + m + ^ + r + 1,... , n + m + ^ + r + р) соответственно, которые управляются последовательностью сумм знаков (7i,y Ф Yi,z} и вырабатывают знаки Yi,u и Yi,v, снимаемые с ячейки n + m + ^ + r ЛРС-u и с ячейки n + m + ^ + r + р ЛРС-v. Сумма этих знаков образует гамму генератора. Все ЛРС имеют примитивные характеристические многочлены. Гамма генератора есть сумма 7i=7i,u Ф Yi,v, i = 1, 2,... Схема управления движением: ЛРС-x сдвигается равномерно, на один шаг в каждом такте. Если Yi,x = 1, то ЛРС-y продвигается на один шаг, а ЛРС-z простаивает. Если Yi,x = 0, то ЛРС-y простаивает, а ЛРС-z продвигается на один шаг. Если Yi y =1, то ЛРС-u продвигается на один шаг, а ЛРС-v простаивает. Если Yiy Ф Yiz = 0, то ЛРС-u простаивает, а ЛРС-v продвигается на один шаг. Считаем, что все регистры левого сдвига. В криптографических приложениях ключом генератора является, как правило, начальное состояние всех ЛРС. 2. Криптографические свойства трёхкаскадного генератора Длина периода гаммы. Обозначим gx,gy, gz, gu,gv линейные подстановки множеств состояний соответствующих регистров, (x,y,z, u,z)-начальное состояние генератора. Тогда состояние регистра ЛРС-x в j-м такте есть gX-1 (x), j = 1, 2,..., gX(x) = x. Для определения длины периода гаммы посчитаем глубины продвижения регистров aX(i,x), ay(i,x), az(i,x), au(i, x, y, z), av(i,x,y,z) за i тактов при начальном состоянии. ЛРС-x движется равномерно, значит, aX(i,x) = i, для регистров ЛРС-y и ЛРС-z верно ay (i, x) = f (x) + ... + f (gX-1 (x)), az (i,x) = i _ ay (i,x), i = 1, 2,... Обозначим в j-м такте через yj бит, записанный в ячейке n + m ЛРС-y, и через Zj - бит, записанный в ячейке n + m + ^ ЛРС-z. Тогда для регистров ЛРС-u и ЛРС-v верно a„(i,x,y,z) = (y1 Ф Z1) + ... + (yi Ф Zi), av(i,x,y,z) = i _ a„(i,x,y,z). Пусть для определённости f (0,... , 0) = 0 и f уравновешена. Тогда при любом x ay (2n _ 1, x) = 2n-1, az (2n _ 1,x) = 2n-1 _ 1. Если (2m _ 1, 2M _ 1) = 1, то при i = (2n _ 1)(2m _ 1)(2^ _ 1) и любых y, Z имеем au((2n _ 1)(2m _ 1)(2M _ 1), x, y, z) = (2n _ 1)(2m+^-1 _ 2m-1 _ 2^-1), av((2n _ 1)(2m _ 1)(2M _ 1),x,y,Z) = (2n _ 1)(2m _ 1)(2^ _ 1)_ _(2n _ 1)(2m+M-1 _ 2m-1 _ 2M-1). Длина периода управляющей гаммы первого каскада равна 2n _ 1, второго - (2n _ 1)(2m _ 1)(2М _ 1). Теорема 1. Если числа n,m,^,r, р попарно взаимно простые и все ЛРС имеют примитивные характеристические многочлены, то длина периода генератора равна t7 = (2n _ 1)(2m _ 1)(2М _ 1)(2r _ 1)(2Р _ 1). Группа генератора. Обозначим: a = y1; b = z1, тогда подстановка g множества состояний генератора (за один такт) имеет вид g(x,y,z,u,v) = (gx(x),gf(x)(y),gf(x)®1(z),gU®b(u),g:®b®1(v)). Группа генератора циклическая, порождается подстановкой g(x, y, z, u, v). Теорема 2. Подстановка gi является линейной, если и только если число i кратно (2n - 1)(2m - 1)(2М - 1). Отсюда порядок линейной подгруппы группы генератора равен (2r - 1)(2Р - 1). Перемешивающие свойства трехкаскадного генератора. Перемешивающие свойства генератора определяются перемешивающим (p + ^-вершинным орграфом Г подстановки g(x, y, z, u, v), где p = n + m + ^ + r + p. Орграф Г состоит из вершины p+1 и компонент сильной связности Kx, , , , соединённых дугами. Компонента есть перемешивающий n-вершинный орграф подстановки gx; , , суть перемешивающие орграфы с числом вершин m, r, p подстановок gy, gz,g«,gv соответственно, к которым в каждую вершину добавлена петля (следует из свойств схемы управления «стоп-вперед»). В каждую вершину из U входит дуга, исходящая из каждой вершины множества E(f), где E(f) -множество номеров существенных переменных функции f. В каждую вершину из U входит дуга, исходящая из вершины n + m компоненты и из вершины n + m + ^ компоненты (снимаемые с этих ячеек гаммы управляют третьим каскадом). В Г также есть дуги (Р - p,p + 1) и (Р,Р + 1). Орграф Г не является сильносвязным, но является локально примитивным. Если в Г вершина j достижима из вершины i, то i, j-exp Г равен длине кратчайшего пути из i в j, проходящего через любую вершину с петлей [2, с. 187]. Отсюда верна Теорема 3. Локальные экспоненты i, (p + 1)-ехрГ равны n + 2, i = 1,..., n; i, (p + 1)-ехрГ = ^ тах^,^) + 1, i = n + 1,... n + m + тах(^ p), i = n + m + ^ + 1,..., p. Из теоремы 3 следует, что длину «холостого хода» генератора целесообразно определить не меньше чем тах^ + 2, тах(ш,, + 1, тах(^ p)}. Для генераторов с другой схемой перемежающихся шагов результаты аналогичны. Вывод: криптографические свойства генераторов с перемежающимся шагом усиливаются с ростом числа каскадов.

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