Зсувні регістри зі зворотним зв'язком. Теоретичні основи роботи Лінійний зворотний зв'язок
Регістр лінійного зсуву 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
Реєстр зсуву із зворотним зв'язкомскладається з двох частин: регістру зсуву та функції зворотнього зв'язку.
Рис 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. Період такого регістру буде максимальним, циклічно проходячи всі 232 - 1 значень до їх повторення. Найчастіше використовуються проріджені многочлени, тобто. які мають лише деякі коефіцієнти. Найбільш популярні тричлени.
Важливим параметромгенератора на базі РСЛОС, є лінійна складність. Вона визначається як довжина nнайкоротшого РСЛОС, який може імітувати вихід генератора. Лінійна складність важлива, оскільки за допомогою простого алгоритму Берленкемп-Мессіможна відтворити такий РСЛОС, перевіривши всього 2 nбітів гами. З визначенням необхідного РСЛОС потоковий шифр практично зламується.
Зсувний регістр зі зворотним зв'язком ( 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 = ((((ShiftRegister >> 31)
^ (ShiftRegister >> 6)
^ (ShiftRegister >> 4)
^ (ShiftRegister >> 2)
^ (ShiftRegister >> 1)
^ ShiftRegister)
& 0x00000001)<<31)
| (ShiftRegister >> 1);
return ShiftRegister & 0x00000001;
Програмні реалізації LFSR досить повільні і швидше працюють, якщо вони написані на асемблері, а не на С. Одним із рішень є використання паралельно 16-ти LFSR (або 32 залежно від довжини слова в архітектурі конкретного комп'ютера). У такій схемі використовується масив слів, розмір якого дорівнює довжині LFSR, а кожен юіт слова масиву відноситься до свого LFSR. За умови, що використовуються однакові номери відвідних послідовностей, це може дати помітний виграш у продуктивності.
З 
хему зворотний зв'язок також можна модифікувати. При цьому генератор не матиме більшої криптостійкості, але його буде легше реалізувати програмно. Замість використання для генерації нового крайнього лівого біта бітів відвідної послідовності виконується XOR кожного біта відвідної послідовності з виходом генератора і заміна його результатом цієї дії, потім результат генератора стає новим крайнім лівим бітом (Error: Reference source not found).
Цю модифікацію називають конфігурацією Галуа. На мові С це виглядає так:
static unsigned long ShiftRegister = 1;
void seed_LFSR (unsigned long seed)
ShiftRegister=seed;
int Galua_LFSR (void)
if (ShiftRegister & 0x00000001) (
ShiftRegister=(ShiftRegister^ mask >> 1) | 0x8000000;
ShiftRegister >>=1;
Виграш полягає в тому, що всі XOR виконуються за одну операцію. Ця схема також може бути розпаралелена.
Самі по собі LFSR є хорошими генераторами псевдовипадкових послідовностей, але вони мають деякі небажані невипадкові властивості. Послідовні біти лінійні, що робить їх непотрібними для шифрування. ДляLFSRдовжини nвнутрішній стан є попередніми nвихідних бітів генератора Навіть якщо схема зворотного зв'язку зберігається в секреті, то вона може бути визначена за 2 nвихідним бітам генератора з допомогою спеціальних алгоритмів. Крім того, великі випадкові числа, що генеруються з використанням бітів цієї послідовності, що йдуть підряд, сильно кореловані і для деяких типів додатків не є випадковими. Незважаючи на це, LFSR часто використовуються для створення алгоритмів шифрування. Для цього використовуються кілька LFSR, зазвичай з різними довжинами та номерами відвідних послідовностей. Ключ є початковим станом регістрів. Щоразу, коли потрібен новий біт, всі регістри зсуваються. Ця операція називається тактуванням. Біт виходу є функцією, бажано нелінійною, деяких бітів LFSR. Ця функція називається комбінуючою, а генератор загалом – комбінуючим генератором. Багато з таких генераторів досі безпечні.
Реєстр зсуву з лінійним зворотним зв'язком(РСЛОС, анг. linear feedback shift register, LFSR ) - регістр зсуву бітових слів, у якого значення вхідного (всувається) біта дорівнює лінійній булевій функції від значень інших бітів регістру до зсуву. Можливо організований як програмними, і апаратними засобами. Застосовується для генерації, псевдовипадкових, послідовностей, бітів, що знаходить застосування, зокрема, у криптографії.
Опис
Управління регістром в апаратних реалізаціях проводиться подачею зсуву імпульсу (інакше званого тактовимабо синхроімпульсом) на всі осередки. Управління регістром у програмних реалізаціях проводиться виконанням циклу. На кожній ітерації циклу обчислюється функція зворотний зв'язок і виконується зсув бітів у слові.
Принцип роботи
Лінійна складність
Кореляційна незалежність
Намагаючись отримати високу лінійну складність послідовності, що генерується, криптографи нелінійно поєднують виходи декількох регістрів зсуву. При цьому одна або кілька вихідних послідовностей (або навіть виходи окремих РСЛОС) можуть бути пов'язані загальним потоком та розкриті криптоаналітиком. Злом на основі такої вразливості називають кореляційним розтином. Основна ідея такого злому полягає у виявленні деякої кореляції між виведенням генератора та висновками його складових частин. Потім, спостерігаючи вихідну послідовність, можна отримати інформацію про ці проміжні висновки, і, таким чином, зламати генератор. Томас Сігенталер показав, що можна точно визначити кореляційну незалежність, і що є компроміс між кореляційною незалежністю та лінійною складністю.
Програмна реалізація
Програмні реалізації РСЛОС досить повільні та працюють швидше, якщо вони написані на асемблері. Одне з рішень - паралельне використання 16-ти РСЛОС (або 32-х, залежно від довжини слова в архітектурі комп'ютера). У такій схемі використовується масив слів, розмір якого дорівнює довжині регістру зсуву, а кожен біт слова відноситься до свого РСЛОС. Оскільки використовуються однакові номери відвідних послідовностей, це може дати помітний виграш у продуктивності генератора .
Конфігурація Фібоначчі
Розглянемо 32-бітовий зсувний регістр. Для нього є відвідна послідовність (32, 31, 30, 28, 26, 1) (\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\right)). Це означає, що для генерації нового біта необхідно за допомогою операції XOR підсумувати 31, 30, 29, 27, 25 і 0 біти. Отриманий РСЛОС має максимальний період 2 32 − 1 (\displaystyle 2^(32)-1). Код для такого регістру мовою Сі наступний:
int LFSR_Fibonacci (void ) ( static unsigned long S = 0x00000001 ; S = ((((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25 ) ^ S ) & 0x00000001 )<< 31 ) | (S >> 1); return S&0x00000001; )
Конфігурація Галуа
Даний генератор не має більшої криптостійкості, але він дає виграш у продуктивності: всі операції XOR за допомогою розпаралелювання можна виконати за одну дію, а не послідовно одна за одною, як у конфігурації Фібоначчі. Ця схематакож дасть виграш за апаратної реалізації.
Код для регістру зсуву довжини 32 біт мовою Сі наступний:
int LFSR_Galois ( void ) ( static unsigned long ;
Варто зазначити, що цикл із фіксованого числа викликів функції LFSR_Galois в конфігурації Галуа виконується приблизно в 2 рази швидше, ніж функція LFSR_Fibonacci в конфігурації Фібоначчі (компілятор MS VS 2010 на Intel Core 5).
Приклад послідовності, що генерується
Конфігурація Фібоначчі
Нехай РСЛОС задається характеристичним багаточленом x 3 + x + 1 (\displaystyle x^(3)+x+1). Це означає, що бітами відведення будуть 2-й та 0-й, а одиниця у формулі багаточлена означає, що 0-й біт – вхідний. Функція зворотного зв'язку має вигляд S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). Припустимо, початковим станом регістру зсуву була послідовність . Подальші стани регістру наведено в таблиці нижче:
| Номер кроку | Стан | Генерований біт |
|---|---|---|
| 0 | [ 0 , 0 , 1 ] (\displaystyle \left) | 1 |
| 1 | 0 | |
| 2 | 0 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 0 | |
| 7 | [ 0 , 0 , 1 ] (\displaystyle \left) | 1 |
Оскільки внутрішній стан на сьомому кроці повернувся до вихідного, то, починаючи з наступного кроку, йтиме повтор бітів. Тобто послідовність, що генерується, така: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] (\displaystyle \left)(Порядок біт у послідовності відповідає порядку їх генерації РСЛОС). Таким чином, період послідовності дорівнює 7, тобто максимально можливе значення, що сталося в силу примітивності заданого многочлена.
Конфігурація Галуа
Візьмемо той самий характеристичний багаточлен, тобто c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c 2 = 0 (\displaystyle c_(2)=0). З вихідним бітом складається лише 1-й біт. Початковий стан той самий. Подальші стани регістру:
| Номер кроку | Стан | Генерований біт |
|---|---|---|
| 0 | [ 0 , 0 , 1 ] (\displaystyle \left) | - |
| 1 | [ 1 , 0 , 0 ] (\displaystyle \left) | 0 |
| 2 | [ 0 , 1 , 1 ] (\displaystyle \left) | 1 |
| 3 | [ 1 , 0 , 1 ] (\displaystyle \left) | 1 |
| 4 | [ 1 , 1 , 1 ] (\displaystyle \left) | 1 |
| 5 | [ 1 , 1 , 0 ] (\displaystyle \left) | 0 |
| 6 | [ 0 , 1 , 0 ] (\displaystyle \left) | 0 |
| 7 | [ 0 , 0 , 1 ] (\displaystyle \left) | 1 |
Внутрішній стан регістру на сьомому кроці повернулося до вихідного, отже, його період також дорівнює 7. На відміну від Фібоначчі, внутрішні стани регістру вийшли інші, але генерована послідовність та ж, тільки зсунута на 4 такти : [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\displaystyle \left)(Порядок біт у послідовності відповідає порядку їх генерації РСЛОС).
Генерація примітивних багаточленів
| Біти, n (\displaystyle n) | Примітивний багаточлен | Період, 2 n − 1 (\displaystyle 2^(n)-1) | Число примітивних багаточленів |
|---|---|---|---|
| 2 | x 2 + x + 1 (\displaystyle x^(2)+x+1) | 3 | 1 |
| 3 | x 3 + x 2 + 1 (\displaystyle x^(3)+x^(2)+1) | 7 | 2 |
| 4 | x 4 + x 3 + 1 (\displaystyle x^(4)+x^(3)+1) | 15 | 2 |
| 5 | x 5 + x 3 + 1 (\displaystyle x^(5)+x^(3)+1) | 31 | 6 |
| 6 | x 6 + x 5 + 1 (\displaystyle x^(6)+x^(5)+1) | 63 | 6 |
| 7 | x 7 + x 6 + 1 (\displaystyle x^(7)+x^(6)+1) | 127 | 18 |
| 8 | x 8 + x 6 + x 5 + x 4 + 1 (\displaystyle x^(8)+x^(6)+x^(5)+x^(4)+1) | 255 | 16 |
| 9 | x 9 + x 5 + 1 (\displaystyle x^(9)+x^(5)+1) | 511 | 48 |
| 10 | x 10 + x 7 + 1 (\displaystyle x^(10)+x^(7)+1) | 1023 | 60 |
| 11 | x 11 + x 9 + 1 (\displaystyle x^(11)+x^(9)+1) | 2047 | 176 |
| 12 | x 12 + x 11 + x 10 + x 4 + 1 (\displaystyle x^(12)+x^(11)+x^(10)+x^(4)+1) | 4095 | 144 |
| 13 | x 13 + x 12 + x 11 + x 8 + 1 (\displaystyle x^(13)+x^(12)+x^(11)+x^(8)+1) | 8191 | 630 |
| 14 | x 14 + x 13 + x 12 + x 2 + 1 (\displaystyle x^(14)+x^(13)+x^(12)+x^(2)+1) | 16383 | 756 |
| 15 | x 15 + x 14 + 1 (\displaystyle x^(15)+x^(14)+1) | 32767 | 1800 |
| 16 | x 16 + x 14 + x 13 + x 11 + 1 (\displaystyle x^(16)+x^(14)+x^(13)+x^(11)+1) | 65535 | 2048 |
| 17 | x 17 + x 14 + 1 (\displaystyle x^(17)+x^(14)+1) | 131071 | 7710 |
| 18 | x 18 + x 11 + 1 (\displaystyle x^(18)+x^(11)+1) | 262143 | 7776 |
| 19 | x 19 + x 18 + x 17 + x 14 + 1 (\displaystyle x^(19)+x^(18)+x^(17)+x^(14)+1) | 524287 | 27594 |
| 20 - 168 | |||
| 2 - 786, 1024, 2048, 4096 | |||
Переваги і недоліки
Переваги
- висока швидкодія криптографічних алгоритмів, створюваних на основі РСЛОС (наприклад потокових шифрів);
- застосування тільки найпростіших бітових операцій складання та множення, апаратно реалізованих практично у всіх обчислювальних пристроях;
- хороші криптографічні властивості (РСЛОС можуть генерувати послідовності великого періоду з добрими статистичними властивостями);
- завдяки своїй структурі, РСЛОС легко аналізуються з використанням методів алгебри.
Недоліки
Способи поліпшення криптостійкості послідовностей, що генеруються.
Генератори з кількома регістрами зсуву
Генератор такого типу складається з декількох регістрів зсуву з лінійним зворотним зв'язком, які генерують біти x 1 , i , x 2 , i , … , x M , i (\displaystyle x_(1,i),\;x_(2,i),\;\dots ,\;x_(M,i))відповідно. Далі, біти, що генеруються, перетворюються деякою булевою функцією f (x 1 , i , x 2 , i , … , x M , i) (\displaystyle f(x_(1,i),\;x_(2,i),\;\dots ,\;x_(M ,i))). Необхідно відзначити, що у генераторів такого типу довжини регістрів L i (\displaystyle L_(i)), i = 1 , 2 , … , M (\displaystyle i=1,\;2,\;\dots ,\;M), взаємно-прості між собою.
Період даного генератора дорівнює T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 LM − 1) ≲ 2 L (\displaystyle T=(2^(L_(1))-1)\cdot (2^( L_(2))-1)\cdots (2^(L_(M))-1)\lesssim 2^(L)), де L = ∑ i = 1 M L i (\displaystyle L=\sum \limits _(i=1)^(M)L_(i))- загальна кількість осередків. Отже, використання декількох РСЛОС збільшує період послідовності, що генерується в порівнянні з одним регістром, що збільшує криптостійкість генератора. Також збільшується лінійна складність або довжина найкоротшого регістру, що відповідає даному генератору. Такий регістр знаходиться за допомогою алгоритму Берлекемпа-Мессі по генерованої послідовності. В найкращому випадкуйого довжина співмірна з періодом послідовності, що генерується.
Генератори з нелінійними перетвореннями
Структурна схема такого генератора нічим відрізняється від схеми попереднього генератора. Головна відмінність полягає в тому, що пристрій перетворення задано нелінійною бульовою функцією f (x 1 , x 2 , … , x M) (\displaystyle f(x_(1),x_(2),\dots ,x_(M))). В якості такої функції береться, наприклад, поліном Жегалкіна (згідно з теоремою Жегалкіна, всяка бульова функціяєдиним чином може бути представлена поліномом Жегалкіна).
Нелінійний генератор може бути також реалізований на регістрі зсуву з нелінійним зворотним зв'язком. Він може дати 2 2 L − 1 − L (\displaystyle 2^(2^(L-1)-L))варіантів послідовностей, максимального періоду, що більше, ніж у РСЛОС.
Криптостійкість даного генератора підвищується за рахунок нелінійності використовуваної функції. Визначення стану регістрів по послідовності бітів, що генерується, є складним математичним завданням, тому що не відомий алгоритм, що відновлює вихідні стани.
Цей метод використовується, наприклад, в генераторі Геффаі узагальненому генераторі Геффа, однак такі генератори можуть бути зламані кореляційним розкриттям .
Генератори з різним тактуванням регістрів зсуву
Генератор "стоп-пішов"
Генератор "стоп-пішов"(англ. Stop-and-Go , Both-Piper ) використовує виведення РСЛОС-1 для управління тактовою частотою РСЛОС-2, так що РСЛОС-2 змінює свій стан у певний момент часу, тільки якщо вихід РСЛОС-1 в момент часу дорівнював одиниці. Дана схема не встояла перед кореляційним розкриттям.
З метою збільшення криптостійкості було запропоновано генератор, що чергується, «стоп-пішов». У ньому використовуються три регістри зсуву різної довжини. Тут РСЛОС-1 управляє тактовою частотою 2-го і 3-го регістрів, тобто РСЛОС-2 змінює свій стан, коли вихід РСЛОС-1 дорівнює одиниці, а РСЛОС-3 - коли вихід РСЛОС-1 дорівнює нулю. Виходом генератора є операція складання по модулю два виходів РСЛОС-2 і РСЛОС-3. Даний генератор має великий період і велику лінійну складність. Існує спосіб кореляційного розтину РСЛОС-1, але це не сильно послаблює криптографічні властивості генератора.
Ускладнена схема тактування використана в двосторонньому генераторі «стоп-пішов», В якому використовуються 2 регістри зсуву однакової довжини. Якщо вихід РСЛОС-1 у певний момент часу t i − 1 (\displaystyle t_(i-1))- одиниці, то РСЛОС-2 не тактується на момент часу t i (\displaystyle t_(i)). Якщо вихід РСЛОС-2 у момент часу t i − 1 (\displaystyle t_(i-1))дорівнює нулю, а в момент часу t i − 2 (\displaystyle t_(i-2))- одиниці, і якщо цей регістр тактується на момент часу t i (\displaystyle t_(i)), то в цей момент РСЛОС-1 не тактується. Лінійна складність даної схеми приблизно дорівнює періоду послідовності, що генерується.
Самопроріджуючий генератор
Багатошвидкісний генератор із внутрішнім твором
Даний генератор використовує два регістри зсуву РСЛОС-1 та РСЛОС-2. Тактова частотаРСЛОС-2 d (\displaystyle d)разів більше, ніж у РСЛОС-1. Певні біти цих регістрів перемножуються одна з одною операцією AND. Результати множень підсумовуються операцією XOR і виходить вихідна послідовність. Цей генератор має високу лінійну складність і має хороші статистичні властивості. Однак його стан може бути визначений за довжиною вихідної послідовності L 1 + L 2 + log 2 d (\displaystyle L_(1)+L_(2)+\log _(2)(d)), де L 1 (\displaystyle L_(1))і L 2 (\displaystyle L_(2))- довжини РСЛОС-1 та РСЛОС-2 відповідно, а d (\displaystyle d)- Відношення їх тактових частот.
Каскад Голлманна
Дана схема є покращеною версією генератора «стоп-пішов». Він складається з послідовності РСЛОС, тактування кожного з яких керується попереднім РСЛОС. Якщо виходом РСЛОС-1 у момент часу t i (\displaystyle t_(i))є 1, то тактується РСЛОС-2. Якщо виходом РСЛОС-2 у момент часу t i (\displaystyle t_(i))є 1 тортується РСЛОС-3, і так далі. Вихід останнього РСЛОС є виходом генератора. Якщо довжина всіх РСЛОС однакова і дорівнює L (\displaystyle L), то період системи з M (\displaystyle M)РСЛОС дорівнює (2 L − 1) M (\displaystyle (2^(L)-1)^(M)), а лінійна складність - L (S) = L (2 L − 1) M − 1 (\displaystyle L(S)=L(2^(L)-1)^(M-1)) .
Ця ідея проста і може бути використана для генерації послідовностей з величезними періодами, великими лінійними складнощами та добрими статистичними властивостями. Але, на жаль, вони чутливі до розтину, званого замиканням(англ. lock-in), коли
Реєстр зсуву із зворотним зв'язкомскладається з двох частин: регістру зсуву та функції зворотнього зв'язку.
Рис 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. Період такого регістру буде максимальним, циклічно проходячи всі 232 - 1 значень до їх повторення. Найчастіше використовуються проріджені многочлени, тобто. які мають лише деякі коефіцієнти. Найбільш популярні тричлени.
Важливим параметром генератора на базі РСЛОС є лінійна складність. Вона визначається як довжина nнайкоротшого РСЛОС, який може імітувати вихід генератора. Лінійна складність важлива, оскільки за допомогою простого алгоритму Берленкемп-Мессіможна відтворити такий РСЛОС, перевіривши всього 2 nбітів гами. З визначенням необхідного РСЛОС потоковий шифр практично зламується.
Крім РСЛОС застосовуються і регістри зсуву з нелінійним зворотним зв'язком, зворотним зв'язком з перенесення та ін.
Ряд генераторів розроблений на основі теоретико-числового підходу (генератори Блюма-Мікалі, RSA, BBS, стискаючі, адитивні генератори та ін.).
Математичне забезпечення синтезу потокових криптографічних алгоритмів розроблено повніше і докладніше проти блочними криптоалгоритмами. Тим не менш, для створення потокових шифрів часто використовують блокові криптоалгоритми в режимах OFB або CFB.
