Регістр лінійного зсуву c зворотним зв'язком (Linear Feedback Shift Register - LFSR) - механізм створення псевдослучайной послідовності двійкових бітів. Регістр (рис. 1) складається з ряду осередків, які встановлюються вектором ініціалізації (найчастіше секретним ключем). Робота регістра визначається наявністю або відсутністю зв'язку від кожного розряду до зворотного зв'язку. Відводи регістра зі зворотним зв'язком не фіксовані, а є частиною ключа. На черговому кроці вміст осередків регістра зсувається на одну позицію вправо, а один біт, що залишився в результаті операції XOR вільним, поміщається в крайню ліву клітинку.
Мал. 1. Лінійний регістр зсуву зі зворотним зв'язком
Для досягнення максимального періоду гами шифру число розрядів mзсувного регістру вибирається рівним одному з простих чисел Мерсенна (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), а внутрішні зв'язки регістра повинні вибиратися відповідно з непріводімимі примітивними многочленами зі старшою ступенем m. У цьому випадку період гами шифру може досягати (2 m-1).
LFSR швидко працює і легко реалізується як програмно, так і апаратно. При грамотному виборі бітів зворотного зв'язку генеруються послідовності мають хороші статистичні властивості. LFSR використовується як базовий елемент для побудови високо захищених систем.
Каскад регістрів - набір LFSR, пов'язаних таким чином, що поведінка одного регістра LFSR залежить від поведінки попереднього регістру LFSR в каскаді. Таке «залежне» поведінку зазвичай організовується для управління за допомогою першого LFSR лічильником зрушень наступного за ним LFSR.
Наприклад, регістр зсувається на один крок, якщо значення попереднього регістру - 1, а якщо значення 0, то регістр зсувається на два кроки або якось інакше. Велика кількість подібних поєднань дозволяє забезпечити досить високу безпеку.
Найбільш криптостійкі послідовності дає стискає генератор (shrinking generator), заснований на простому взаємодії між результатами двох регістрів LFSR. Біти одного результату визначають, чи будуть відповідні біти другого результату використовуватися як частина повного «потокового ключа». Стискає генератор простий, масштабується і має хороші захисні властивості. Його недолік полягає в тому, що швидкість генерації «потокового ключа" не буде постійною, якщо не вжити деяких запобіжних заходів.
Метод Фібоначчі з запізнюваннямиОдин з широко поширених фібоначчійовий генераторів грунтується на наступній итеративной формулою:
де Y k - речові числа з діапазону
Мал. 2. Циклічна шифрування
Режим зворотного зв'язку по виходу DES може застосовуватися для генерації псевдовипадкових чисел, аналогічно тому, як він використовується для поточного шифрування. Виходом кожної стадії шифрування є 64-бітове значення, з якого тільки старші j бітів подаються назад для шифрування. 64-бітові виходи становлять послідовність псевдовипадкових чисел з хорошими статистичними властивостями.
Генератор псевдовипадкових чисел, описаний в стандарті ANSI X9.17, є одним з найбільш криптостійкі генераторів псевдовипадкових чисел. У число додатків, що використовують цю технологію, входять додатки фінансової безпеки і PGP.
Генератор ANSI X9.17 складається з наступних частин (рис. 3):
1. Вхід: генератором керують два псевдовипадкових входу. Перший вхід є 64-бітовим представленням поточних дати і часу ( DT i), Які змінюються кожного разу при створенні числа. Другий вхід є 64-бітовим початковим значенням, яке инициализируется деяким довільним значенням і змінюється в ході генерації послідовності псевдовипадкових чисел ( V i).
2. Ключі: генератор використовує три модулі потрійного DES з двома ключами K 1, K 2. Всі три використовують одну і ту ж пару 56-бітних ключів, яка повинна триматися в секреті і застосовуватися тільки для генерації псевдовипадкового числа.
| EDE |
| EDE |
| EDE |
| + |
| + |
| K 1, K 2 |
| DT i |
| V i |
| R i |
| V i + 1 |
3. Вихід: вихід складається з 64-бітного псевдослучайного числа R i і 64-бітного значення, яке буде використовуватися в якості початкового значення при створенні наступного числа ( V i +1) .
Мал. 3. Генератор псевдовипадкових чисел ANSI X9.17
У регістрі зсуву з лінійної зворотним зв'язком виділяють дві частини (модуля): власне регістразсуву і схеми (або підпрограми) обчислює значення всувають біта. Регістр складається з функціональних осередків (або бітів машинного слова або кількох слів), в кожній з яких зберігається поточний стан одного біта. Кількість осередків, називають довжиною регістра. Біти (осередки) зазвичай нумеруються числами, кожна з яких здатна зберігати біт, причому в осередок відбувається в русі обчисленого біта, а з осередку витягується висувається черговий згенерований біт. Обчислення всувають біта зазвичай проводиться до зсуву регістра, і тільки після зсуву значення обчисленого біта поміщається в комірку.
Періодом регістразсуву називають мінімальну довжину одержуваної послідовності до початку її повторення. Так як регістр з бітових осередків має тільки різних ненульових станів, то, принципово, період регістра не може перевищувати це число. Якщо період регістра дорівнює цьому числу, то такий регістр називають регістром максимального періоду.
Для РСЛОС функція зворотного зв'язку є лінійною булевої функцією від станів всіх або деяких бітів регістра. Наприклад, сума по модулю два або її логічна інверсія є лінійної булевої функцією (операція XOR, в формулах позначають як) і найбільш часто застосовується в таких регістрах.
При цьому ті біти, які є змінними функції зворотного зв'язку, прийнято називати відводами.
Управління регістром в апаратних реалізаціях здійснюється шляхом здачі сдвигающего імпульсу (інакше званого тактового або синхроимпульса) На всі осередки, в програмних - виконанням програмного циклу, що включає обчислення функції зворотного зв'язку і зсуву бітів в слові.
Протягом кожного такту часу виконуються наступні операції:
Регістр зсуву з лінійної зворотним зв'язком
Таким чином, в якості опції зворотного зв'язку береться логічна операція XOR (виключає АБО), тобто:
Властивості примітивних многочленів
властивості
Властивості видається РСЛОС послідовності тісно пов'язані з властивостями асоційованого многочлена. Його ненульові коефіцієнти називаються відводами, Як і відповідні осередки регістру, які постачають значення аргументів функції зворотного зв'язку.
лінійна складність
Лінійна складність бінарної послідовності - одна з найважливіших характеристик роботи РСЛОС. Введемо наступні позначення:
визначенняЛінійної складністю нескінченної двійковій послідовності називається число, яке визначається наступним чином:
Лінійної складністю кінцевої двійковій послідовності називається число, яке дорівнює довжині найкоротшого РСЛОС, який генерує послідовність, що має в якості перших членів.
Властивості лінійної складності
Нехай і - виконавчі послідовності. тоді:
кореляційний незалежність
Щоб отримати високу лінійну складність криптографи намагаються нелінійно об'єднати результати декількох вихідних послідовностей. При цьому небезпека полягає в тому, що одна або кілька вихідних послідовностей (часто навіть виходи окремих РСЛОС) можуть бути пов'язані спільним ключовим потоком і розкриті за допомогою лінійної алгебри. Злом на основі такої вразливості називають кореляційним розкриттям. Томас Сігенталер показав, що можна точно визначити кореляційну незалежність, і що існує компроміс між кореляційної незалежністю і лінійної складністю.
Основна ідея такого злому полягає в виявленні певної кореляції між висновком генератора і висновком однієї з його складових частин. Потім, спостерігаючи вихідну послідовність, можна отримати інформацію про це проміжному висновку. Використовуючи цю інформацію і інші кореляції, можна збирати дані про інших проміжні висновки до тих пір поки генератор НЕ буде зламаний.
Проти багатьох генераторів потоку ключів на базі регістра зсуву з лінійної зворотним зв'язком успішно використовувалися кореляційні розтину або з варіації, такі як швидкі кореляційні розтину, які передбачають компроміс між обчислювальною складністю та ефективністю.
приклад
Для РСЛОС з асоційованим многочленом генерується послідовність має вигляд. Припустимо, перед початком процесу в регістрі записана послідовність, тоді період генерується потоку бітів буде дорівнює 7 з такою послідовністю:
| номер кроку | стан | генерується біт |
| 0 | - | |
| 1 | 1 | |
| 2 | 1 | |
| 3 | 0 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 1 | |
| 7 | 0 |
Оскільки внутрішній стан на сьомому кроці повернулося до вихідного, то, починаючи з наступного кроку, буде йти повтор. Іншими словами, період послідовності виявився дорівнює 7, що сталося через примітивності многочлена.
Алгоритми генерації примітивних многочленів
готові таблиці
Обчислення примітивності многочлена - досить складна математична задача. Тому існують готові таблиці, в яких наведені номери відвідних послідовностей, які забезпечують максимальний період генератора. Наприклад, для 32-бітового зсувного регістру є послідовність. Це означає, що для генерації нового біта необхідно за допомогою функції XOR підсумувати 31-й, 30-й, 29-й, 27-й, 25-й і 0-й біти. Код для такого РСЛОС на мові Сі наступний:
Int LFSR (void) (static unsigned long S \u003d 1; S \u003d ((((S \u003e\u003e 31) ^ (S \u003e\u003e 30) ^ (S \u003e\u003e 29) ^ (S \u003e\u003e 27) ^ (S \u003e\u003e 25) ^ S) & 1)<< 31 ) | (S>\u003e 1); return S & 1; )
Програмні реалізації РСЛОС генераторів досить повільні і швидше працюють, якщо вони написані на асемблері, а не на мові Сі. Одним з рішень є використання паралельно 16-ти РСЛОС (або 32, залежно від довжини слова в архітектурі конкретного комп'ютера). У такій схемі використовується масив слів, розмір якого дорівнює довжині РСЛОС, а кожен біт слова масиву ставиться до свого РСЛОС. За умови, що використовуються однакові номери відвідних послідовностей, то це може дати помітний виграш в продуктивності. [потрібен приклад коду] (Див .: bitslice).
конфігурація Галуа
Конфігурація Галуа регістразсуву з лінійної зворотним зв'язком
Схему зворотного зв'язку також можна модифікувати. При цьому генератор не володітиме більшою криптостійкості, але його буде легше реалізовувати програмно. Замість використання для генерації нового крайнього лівого біта бітів відвідної послідовності виконується XOR кожного біта відвідної послідовності з виходом генератора і заміна його результатом цієї дії, потім результат генератора стає новим лівим крайнім бітом. На мові Сі це виглядає наступним чином:
Int LFSR (void) (static unsigned long Q \u003d 1; Q \u003d (Q \u003e\u003e 1) ^ (Q & 1? 0x80000057: 0); return Q & 1;)
Виграш полягає тому, що все XOR виконуються за одну операцію.
- можна довести, що наведена першої конфігурація Фібоначчі і наведена тут конфігурація Галуа дають однакові послідовності (довжиною 2 32 -1), але зміщені по фазі одна від одної
- цикл з фіксованого числа викликів функції LFSR в конфігурації Галуа виконується приблизно в два рази швидше, ніж в конфігурації Фібоначчі (компілятор MS VS 2010 року на Intel Core i5)
- зверніть увагу, що в конфігурації Галуа порядок біт в слові, визначає зворотний зв'язок, зворотний в порівнянні з конфігурацією Фібоначчі
приклади генераторів
Генератори «стоп-пішов»
Чергується генератор «стоп-пішов»
Цей генератор використовує висновок одного РСЛОС для управління тактовою частотою іншого РСЛОС. Тактовий вихід РСЛОС-2 управляється виходом РСЛОС-1, так що РСЛОС-2 може змінювати свій стан в момент часу t, тільки якщо вихід РСДОС-1 в момент часу t-1 був дорівнює одиниці. Але ця схема не встояла перед кореляційним розкриттям.
Тому було запропоновано покращений генератор, заснований на цій же ідеї. Його називають чергується генератор «стоп-пішов». У ньому використовуються три РСЛОС різної довжини. РСЛОС-2 тактується, коли вихід РСЛОС-1 дорівнює одиниці, а РСЛОС-3, коли вихід РСЛОС-1 дорівнює нулю. Виходом генератора є сума по модулю 2 РСЛОС-2 і РСЛОС-3. У даного генератора великий період і велика лінійна складність. Його автори показали також спосіб кореляційного розтину РСЛОС-1, але це не сильно послаблює генератор.
каскад Голлманна
каскад Голлманна
Каскад Голлманна є посилену версію генератора «стоп-пішов». Він складається з послідовності РСЛОС, тактирование кожного з яких управляється попереднім РСЛОС. Якщо виходом РСЛОС-1 в момент часу t є 1, то тактується РСЛОС-2. Якщо виходом РСЛОС-2 в момент часу t є 1, то тактується РСЛОС-3, і так далі. Вихід останнього РСЛОС є виходом генератора. Якщо довжина всіх РСЛОС однакова і дорівнює n, то лінійна складність системи з k РСЛОС дорівнює.
Ця ідея проста і може бути використана для генерації послідовностей з величезними періодами, більшими лінійними складнощами і хорошими статистичними властивостями. Але, на жаль, вони чутливі до розтину, званому «замиканням» (lock-in). Для більшої стійкості рекомендується використовувати k не менше 15. Причому краще використовувати більше коротких РСЛОС, чим менше довгих РСЛОС.
граничний генератор
граничний генератор
Цей генератор намагається обійти проблеми безпеки, характерні для попередніх генераторів за допомогою змінного числа регістрів зсуву. У теорії при застосуванні більшого числа зсувних регістрів складність шифру зростає, що і було зроблено в даному генераторі.
Цей генератор складається з великого числа регістрів зсуву, висновки яких надходять на функцію мажорірованія. Якщо число одиниць на виходах регістрів більше половини, то генератор видає одиницю. Якщо число нулів на виходах більше половини, то генератор видає нуль. Для того щоб порівняння число нулів і одиниць було можливим, кількість регістрів зсуву повинно бути непарним. Довжини всіх регістрів повинні бути взаємно прості, а многочлени зворотного зв'язку - примітивні, щоб період генерується послідовності був максимальний.
Для випадку трьох регістрів зсуву генератор можна уявити як:
Цей генератор схожий на генератор Геффена за винятком того, що граничний генератор має більшу лінійної складністю. Його лінійна складність дорівнює:
де,, - довжини першого, другого і третього регістрів зсуву.
Його недоліком є \u200b\u200bте, що кожен вихідний біт дає деяку інформацію про стан зсувного регістру. А точніше 0.189 біта. Тому даний генератор може не встояти перед кореляційним розкриттям.
інші види
Самопрорежівающіе
Самопрорежівающімі називаються генератори, які керують власною частотою. Було запропоновано два типи таких генераторів. Перший складається з регістра зсуву зі зворотним лінійним зв'язком і деякої схеми, яка тактирует цей регістр, в залежності від того якими виходять вихідні значення регістра зсуву. Якщо вихід РСЛОС дорівнює одиниці, то регістр тактується d раз. Якщо вихід дорівнює нулю, то регістр тактується k раз. Другий має практично ту ж конструкцію, але дещо модифіковану: в схемі тактирования на вхід, як перевірки на 0 або 1, надходить не сам вихідний сигнал, а XOR певних бітів регістра зсуву з лінійної зворотним зв'язком. На жаль, цей вид генератора не безпечний.
Багатошвидкісний генератор з внутрішнім твором
Цей генератор використовує два регістри зсуву з лінійної зворотним зв'язком з різними тактовими частотами: РСЛОС-1 і РСЛОС-2. Тактова частота РСЛОС-2 в d разів більше ніж РСЛОС-1. Окремі біти цих регістрів об'єднуються операцією AND. Потім з виходами операції AND виконується операція XOR. З цього блоку XOR знімається вихідна послідовність. Знову ж і цей генератор не бездоганний (Він не вистояв перед розкриттям лінійної узгодженості. Якщо - довжина РСЛОС-1, - довжина РСЛОС-2, а d - відношення тактових частот, то внутрішній стан генератора може бути отримано за вихідний послідовності довжиною), але він має високу лінійну складність і має чудові статистичними характеристиками.
Найпростішим видом функції зворотного зв'язку є лінійна функція, наприклад, сума по модулю 2 вмісту певних розрядів. Такий регістр називається зсувними регістром з лінійної зворотним зв'язком (Linear Feedback Shift Register, скорочено LFSR). У загальному випадку лінійна функція зворотного зв'язку задається формулою. тут c k\u003d 1, якщо k-й розряд використовується в функції зворотного зв'язку, і c k\u003d 0 в іншому випадку. Символ Å позначає складання по модулю 2 (виключає АБО).
Для прикладу розглянемо LFSR з функцією зворотного зв'язку (див. Малюнок).
Якщо початковим станом регістра є 1111, то в наступних тактах він буде приймати наступний ряд станів: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110, 1111, ...
Вихідна послідовність формується з молодшого (крайнього правого) розряду регістра. Вона буде виглядати наступним чином: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Видно, що генерується бітова послідовність цілком визначається початковим станом регістра і функцією зворотного зв'язку. Оскільки число всіляких станів регістра звичайно (воно дорівнює 2 L), То, рано чи пізно, ключова послідовність почне повторюватися. Максимальна довжина є повторюваною частини ключовий послідовності називається її періодом T. Період залежить від функції зворотного зв'язку. Максимально можливий період дорівнює T max \u003d 2 L-1 (реєстр вживає всіх можливих стану, крім 0000 ... 0). Вихідна послідовність LFSR, що володіє максимальним періодом, називається М-послідовністю.
Щоб з'ясувати умови, при яких LFSR буде володіти максимальним періодом, функції зворотного зв'язку ставлять у відповідність характеристичний поліном. Так, регістру, наведеним вище як приклад, відповідає поліном. Теоретичний аналіз показує, що LFSR буде володіти максимальним періодом тоді і тільки тоді, коли поліном P(x) є примітивним. Нижче наведені деякі примітивні поліноми, рекомендовані до застосування на практиці. У таблиці вказані ступеня змінної xв запису полінома. Наприклад, запис (31, 3) відповідає полиному.
| № | P(x) | № | P(x) | № | P(x) |
| (39, 16, 23, 35) | (38, 5, 6, 27) | (32, 2, 7, 16) | |||
| (30, 6, 4, 1) | (31, 6) | (31, 7) | |||
| (31, 13) | (31, 25, 23, 8) | (33, 13) | |||
| (35, 2) | (47, 5) | (48, 9, 7, 4) | |||
| (47, 11, 24, 32) | (46, 18, 31, 40) | (53, 6, 2, 1) | |||
| (55, 24) | (57, 7) | (58, 19) | |||
| (59, 7, 4, 2) | (41, 27, 31, 32) | (61, 5, 2, 1) | |||
| (42, 30, 31, 34) | (51, 15, 24, 46) | (50, 17, 31, 34) |
Спочатку LFSR були розроблені для апаратної реалізації у вигляді набору цифрових схем. Програмні реалізації LFSR зазвичай програють по швидкості апаратним. Для збільшення швидкодії стан регістра вигідно зберігати в вигляді цілого L-розрядним числа, окремі біти якого відповідають двійковим розрядам регістра. Тоді для доступу до окремих бітам використовуються порозрядні операції (зрушення, маскування і т.д.).
Зсувний регістр зі зворотним зв'язком ( FSR ) складається з двох частин: зсувного регістру і функції зворотного зв'язку .
Зсувний регістр (Error: Reference source not found) являє собою послідовність бітів. Коли потрібно витягти біт, все біти зсувного регістру зсуваються вправо на 1 позицію. Новий крайній лівий біт є значенням функції зворотного зв'язку від інших бітів регістра. періодом зсувного регістру називається довжина одержуваної послідовності до початку її повторення.
Найпростішим видом зсувного регістру зі зворотним зв'язком є лінійний зсувний регістр зі зворотним зв'язком (LFSR
–
Left
Feedback
Shift
Register)
(Error: Reference source not found). Зворотній зв'язок є простоXORнекоторих бітів р 
егістра, перелік цих бітів називається відвідної послідовністю.
n-бітовийLFSRможет перебувати в одному з 2 n -1 внутрішніх станів. Це означає, що теоретично такий регістр може генерувати псевдослучайную послідовність з періодом 2 n -1 бітів. Число внутрішніх станів і період рівні, тому що заповнення регістра нулями призведе до того, що він буде видавати нескінченну послідовність нулів, що абсолютно марно. Тільки за певних відвідних последовательностяхLFSRцікліческі пройде через всі 2 n -1 внутрішніх станів. ТакіеLFSRназиваются LFSR з максимальним періодом.
Для того щоб конкретний LFSRімел максимальний період, многочлен, утворений з відвідної послідовності і константи 1 повинен бути примітивним по модулю 2 .
Обчислення примітивності многочлена - досить складна математична задача. Тому існують готові таблиці, в яких наведені номери відвідних послідовностей, які забезпечують максимальний період генератора. Наприклад, для 32-х бітового зсувного регістру можна знайти такий запис: (32,7,5,3,2,1,0) . Це означає, що для генерації нового біта необхідно за допомогою функцііXORпросумміровать тридцять другому, сьомий, п'ятий, третій, другий, і перший біти.
Код для такого LFSRна мовою С ++ буде таким:
// Будь-яке значення крім нуля
ShiftRegister \u003d ((((ShiftRegister \u003e\u003e 31)
^ (ShiftRegister \u003e\u003e 6)
^ (ShiftRegister \u003e\u003e 4)
^ (ShiftRegister \u003e\u003e 2)
^ (ShiftRegister \u003e\u003e 1)
^ ShiftRegister)
& 0x00000001)<<31)
| (ShiftRegister \u003e\u003e 1);
return ShiftRegister & 0x00000001;
Програмні реалізації LFSRдостаточно повільні і швидше працюють, якщо вони написані на асемблері, а не на С. Одним з рішень є використання паралельно 16-тіLFSR (або 32 в залежності від довжини слова в архітектурі конкретного комп'ютера). У такій схемі використовується масив слів, розмір якого дорівнює длінеLFSR, а кожен ЮІТ слова масиву відноситься до своемуLFSR. За умови, що використовуються однакові номери відвідних послідовностей, то це може дати помітний виграш в продуктивності.
З 
хему зворотного зв'язку також можна модифікувати. При цьому генератор не володітиме більшою криптостійкості, але його буде легше реалізувати програмно. Замість використання для генерації нового крайнього лівого біта бітів відвідної послідовності виполняетсяXORкаждого біта відвідної послідовності з виходом генератора і заміна його результатом цієї дії, потім результат генератора стає новим лівим крайнім бітом (Error: Reference source not found).
Цю модифікацію називають конфігурацією Галуа. Мовою С це виглядає наступним чином:
static unsigned long ShiftRegister \u003d 1;
void seed_LFSR (unsigned long seed)
ShiftRegister \u003d seed;
int Galua_LFSR (void)
if (ShiftRegister & 0x00000001) (
ShiftRegister \u003d (ShiftRegister ^ mask \u003e\u003e 1) | 0x8000000;
ShiftRegister \u003e\u003e \u003d 1;
Виграш полягає тому, що все XORвиполняются за одну операцію. Ця схема також може бути распараллелена.
Самі по собі LFSRявляются хорошими генераторами псевдовипадкових послідовностей, але вони мають деякі небажаними невипадковими властивостями. Послідовні біти лінійні, що робить їх марними для шифрування. ДляLFSRдліни nвнутрішній стан являє собою попередні nвихідних бітів генератора. Навіть якщо схема зворотного зв'язку зберігається в секреті, то вона може бути визначена по 2 nвихідним бітам генератора за допомогою спеціальних алгоритмів. Крім того, великі випадкові числа, що генеруються з використанням йдуть підряд бітів цієї послідовності, сильно корельовані і для деяких типів додатків не є випадковими. Незважаючи на це, LFSRчасто використовуються для створення алгоритмів шифрування. Для цього використовуються несколькоLFSR, зазвичай з різними довжинами і номерами відвідних послідовностей. Ключ є початковим станом регістрів. Кожен раз, коли необхідний новий біт, все регістри зсуваються. Ця операція називається тактуванням. Біт виходу являє собою функцію, бажано нелінійну, деяких бітовLFSR. Ця функція називається комбінує, А генератор в цілому - комбінує генератором. Багато з таких генераторів безпечні досі.
Регістр зсуву зі зворотним зв'язком складається з двох частин: регістразсуву і функції зворотного зв'язку.
Рис 19. Регістр зсуву зі зворотним зв'язком.
У загальному випадку регістр зсуву являє собою послідовність деяких елементів кільця або поля. Найбільш часто застосовуються бітові регістри зсуву. Довжина такого регістра виражається числом бітів. При кожному вилученні біта все біти регістра зсуваються вправо на одну позицію. Новий старший біт розраховується як функція всіх інших бітів регістра. Виходом зазвичай є молодший значущий біт. Періодом регістразсуву називають довжину вихідної послідовності до початку її повторення.
Найпростіший тип регістрів зсуву - регістр зсуву з лінійним зворотним зв'язком (РСЛОС або АРС). Зворотній зв'язок - проста операція XOR над деякими бітами регістра. Перелік цих бітів визначається характеристичним многочленом і називається послідовністю відводів. Іноді таку схему називають конфігурацією Фібоначчі.
Рис.20. РСЛОС конфігурації Фібоначчі.
При програмної реалізації РСЛОС користуються модифікованої схемою: для генерації нового значущого біта замість використання бітів послідовності відводів над кожним її бітом виконується операція XOR з виходом генератора, замінюючи старий біт послідовності відводів. Таку модифікацію іноді називають конфігурацією Галуа.
Рис.21. РСЛОС конфігурації Галуа.
n-бітовий РСЛОС може перебувати в одному з 2 n - 1 внутрішніх станів. Це означає, що теоретично такий регістр може генерувати псевдослучайную послідовність з періодом 2 n - 1 бітів (заповнення нулями абсолютно марно). Проходження всіх 2 n - 1 внутрішніх станів можливо тільки за певних послідовностях відводів. Такі регістри називають РСЛОС з максимальним періодом. Для забезпечення максимального періоду РСЛОС необхідно, щоб його характеристичний многочлен був примітивним по модулю 2. Ступінь многочлена є довжиною регістразсуву. Примітивний многочлен ступеня n - це такий непріводімий многочлен, який є дільником, але не є дільником x d + 1 для всіх d, Є дільниками 2 n - 1. (Під час обговорення многочленів термін просте число замінюється терміном непріводімий многочлен). Характеристичний многочлен наведених на малюнках РСЛОС:
x 32 + x 7 + x 5 + x 3 + x 2 + x + 1
примітивний по модулю 2. Період такого регістра буде максимальним, циклічно проходячи всі 2 32 - 1 значень до їх повторення. Найбільш часто використовуються зріджені многочлени, тобто у яких є тільки деякі коефіцієнти. найбільш популярні Трехчлен.
Важливим параметром генератора на базі РСЛОС, є лінійна складність. Вона визначається як довжина n найкоротшого РСЛОС, який може імітувати вихід генератора. Лінійна складність важлива, оскільки за допомогою простого алгоритму Берленкемпа-Мессі можна відтворити такий РСЛОС, перевіривши всього 2 n бітів гами. З визначенням потрібного РСЛОС потоковий шифр фактично зламуються.
