Комбінування регістрів зсуву. Регістри з контрольованим рухом.

Опис роботи РЗЛЗЗ у матричних позначеннях.

Нехай - рекуррентная послідовність, генерируемая РЗЛЗЗ з початковим заповненням . Послідовність зручно розглядати у виді послідовності станів регістра, тобто послідовності векторів.

Введемо матрицю , , .

Очевидно, матриця оборотна і .

Таким чином, для послідовних станів регістра виконується співвідношення , тому , . Звідси випливає, що якщо , то (послідовності додаються поелементно).

Нехай - рядок одиничної матриці порядку . З попереднього випливає, що .

Підписавши послідовності одне під одним, ми одержимо матрицю , що складається з рядків і нескінченного числа стовпців . Легко бачити, що послідовність єрекурентою, яка задовольняє те ж співвідношенню, що і . Початковим заповненням є послідовність стовпців . За побудовою, ці стовпці є стовпцями одиничної матриці, таким чином, ми завжди можемо обчислити кожний з векторів .

В термінах стовпців матриці , елемент послідовності дорівнює , де - координати вектора . Якщо ми розглянемо вираз як функцію від з коефіцієнтами і позначимо її , то , .

Номера координат вектора , що дорівнюють одиниці, вказують, які компоненти вектора брали участь у виразі .

Таким чином, ми можемо сказати, сумою яких елементів початкового заповнення є будь-як елемент рекурентної послідовності .

Крім регістрів зсуву з лінійними зворотним зв'язком, в криптографії використовуються регістри зсуву з нелінійними функціями зворотного зв'язку, у тому числі не обов'язково з двійковими елементами. У найбільш загальному випадку функція зворотного зв'язку задається таблично.

При побудові криптосхем застосовуються різні комбінації регістрів зсуву з лінійними зворотними зв'язками. Найбільше часто зустрічаються вузли, які називаються комбінуючими генераторами і (нелінійними) фільтр-генераторами.

Укомбінуючих генераторів в кожному такті роботи чергові елементи послідовностей, що виробляються кожним з декількох регістрів зсуву, надходять на вхід деякої функції. Значення цієї функції є виходом генератора (елементом гами).

Нелінійні фільтр-генератори генерують вихідну послідовність як нелінійну функцію від станів того самого регістра.

При об'єднанні в криптосхему, цілі вузли, або їхні частини можуть впливати один на одного, змінюючи заповнення інших регістрів, а також керуючи їхнім рухом. Звичайно регістри зсуву змінюють свій стан регулярно, просуваючись по орбіті на один крок протягом такту роботи генератора. Якщо ж рух регістра протягом такту роботи генератора залежить від стану схеми, то такий рух називається керованим. Нерівномірний рух регістрів, як правило, істотно ускладнює вихідну послідовність.