Другие методы построения ГСП

Генераторы с неравномерным движением

Одним из широко обсуждаемых способов усложнения аналитической зависимости знаков гаммы от ключевых элементов является неравномерность смены состояний (движения информации) в определенных узлах генератора.

Эффект неравномерности движения обеспечивается с помощью внешнего управления узлами генератора гаммы либо с помощью самоуправления.

Генераторы «stop-go»

Данный тип генератора состоит из фильтрующего генератора на базе линейного регистра сдвига (ЛРС-1) длины п с фильтром f (x 1,…, х_п) (управляющий регистр сдвига) и линейного регистра сдвига (ЛРС-2) длины т, с ячейки которого снимается выходная гамма (генерирующий ЛРС).

При этом генерирующий ЛРС в зависимости от управляющего знака производит смену своего состояния а или S раз. Такой автомат называют «генератором S — а шагов» (генератором «стопвперед» при S = 0, а = 1).

Если обозначить состояния ЛРС-1 и ЛРС-2 в j-м такте как ^xj = (^xj, i,^xj,2,? ? •) ^xj, n) и Vj = • • •, Уз, т). то уравнения гаммообразован ия имеют вид.

Таким образом, A(j) соответствует суммарному числу тактов «продвижки» ЛРС-2 в начальные j тактов работы ЛРС-1.

Пусть Tj — период ЛРС-j. Известно, что при НОД (А (Т1), Т2) = 1 период выходной гаммы равен произведению Т = ТуТ}. Кроме того, для данного класса схем получены^[1] оценки линейной сложности:

Данная оценка достигается, в частности, для генератора «stopgo», если Т = 2″ — 1 и НОД (п, m) = 1, а также для генератора «1−2» шага, если оба Л PC идентичны и максимального периода.

В случае ЛРС-2 максимального периода в гамме генератора «1- 2» шага число появления s-грамм на периоде при s ^ (ш+1)/2 равно их числу на периоде ЛРС-2 при обычном равномерном движении. Что касается генератора «stop-go», у него имеется очевидная слабость, а именно: если 7j + 7^+1 = 1, то f (xj) = 1. Это упрощает задачу определения начального состояния ЛРС-1 по выходной гамме.

Генератор с чередующимся шагом

Данный генератор состоит из управляющего ЛРС-1 длины п и двух генерирующих: ЛРС-2 (длины гп) и ЛРС-3 (длины г). При этом (в зависимости от знака с ЛРС-1) если ЛРС-2 продвигается, то ЛРС-3 простаивает, и наоборот. Гамма генератора есть сумма гамм с ЛРС-2 и ЛРС-3.

Обозначив состояния ЛРС-1, ЛРС-2, ЛРС-3 в такте j соответственно через.

уравнение гаммообразования имеет вид.

Через Тг обозначим период ЛРС-г. Известно'^[2], что период выходной гаммы будет максимальным и равным Т — Т1Т2Т3, если.

• [1] См. Beth Т., Piper F. The stop-and-go generator. Lecture Notes in ComputerScience 209, Advances in Cryptology: Proc. Eurocrvpt, 84. Berlin: Springer-Verlag, 1985. Vogel K. On the linear complexity of cascaded sequences. Lecture Notes inComputer Science 209; Advances in Cryptology: Proc. EuroCrypt, 84, Springer Verlag, 1985.
• [2] См. Gunther C.G. Alternating step generators controlled by de Bruijn sequences. Lecture Notes in Computer Science 330. Berlin: Springer-Verlag, 1988.