Генераторы «стоп-вперед»

Схема работы выглядит следующим образом. Первый регистр движется равномерно (1 знак за 1 шаг). Если знак равен 0, то регистр 2 не движется и выдает тот знак, который у него был до этого. Если же знак равен 1, то регистр 2 сдвигается (отрабатывает) 1 такт и на выходе выдается значение функции обратной связи

«0» - оставляем, что было.

«1» - прокручиваем новое.

- суммарное число продвижений.

Из линейной последовательности строим гамму достаточно сложной зависимости. Сама же функция f довольно простая,

Слабости: По выходной последовательности можно судить о входе.

Пусть Т₁ – период первого регистра, Т₂ – второго регистра, Т – период всего генератора.

- сумма всех продвижений за период. То через НОК (S,T₂) шагов второй регистр вернется в исходное состояние. И за каждый круг первого регистра происходит продвижение на S шагов =>

Можно построить схему так, что НОД (S,T₂)=1 (взаимнопростые числа), тогда Т = Т₁ Т ₂

- линейная сложность. Равенство будет в том случае, если (m,n)=1 и Т₁=2ⁿ-1

Эта схема довольно сложная, однако генератор обладает слабым криптографическим свойством:

если , то произошел сдвиг второго регистра , таким образом можно восстановить первый регистр, набирая информацию. Чтобы исключить эти слабости, используется генератор «1-2 шага». Для этого генератора функция управления . Если , то R₂ сдвигается на 1 шаг. Если , то R₂ сдвигается на 2 шага.

Обобщением описанных моделей является генератор BRM = Binary Rate Multiplier.

Управляющая функция имеет вид: - функция от t первых координат первого регистра. . Число единиц на периоде первого регистра: .

За число импульсов на входе R₂: - оба регистра вернуться в исходное состояние.

Т.о. - период всего генератора, где - сколько кругов совершит второй регистр, пока они оба придут в начальное состояние. Можно подобрать регистры так, что , тогда - период максимален.

Вывод 1: период общей последовательности генераторов «стоп-вперед» и «1-2 шага» равен произведению периодов, входящих в них регистров.

Для линейной сложности: , где m – длина R₂. Это оценка сверху. Она достигается, если НОД(m,n)=1, а R₁ – полноцикловый.

(Преобразование А называется полноцикловым, если его граф образует один полный цикл).

Вывод 2: генераторы «1-2 шага» и «стоп-вперед» имеют следующие достоинства:

1. Большой период

2. Высокая линейная сложность

3. хорошее статистическое свойство (все - граммы, , встречаются равномерно)

Главный недостаток: если знать как работал управляющий регистр R1, легко восстановить всю выходную последовательность.