Регістр зсуву з лінійним зворотним зв'язком. Теоретичні основи роботи Лінійний регістр зсуву

Реєстр зсуву з зворотним зв'язком складається з двох частин: регістру зсуву та функції зворотного зв'язку.

Рис 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бітів гами. З визначенням необхідного РСЛОС потоковий шифр практично зламується.

дешифрування - p i = D (ki, c i), як показує рис. 7.21.

Мал. 7.21.

Шифри потоку швидше, ніж блокові шифри. Апаратна реалізація шифру потоку також простіша. Коли ми повинні зашифрувати двійкові потоки та передати їх на постійній швидкості, кращий вибір- Використовувати шифр потоку. Шифри потоку мають більший захист проти спотворення бітів протягом передачі.

У сучасному шифрі потоку кожне r -бітове слово в потоці вихідного тексту зашифровано, використовуючи r -бітове слово у ключовому потоці, щоб створити відповідне r -бітове слово у потоці зашифрованого тексту.

Мал. 7.22.

Одноразовий блокнот – ідеальний шифр. Він досконалий. Немає методу, який дав би противнику можливість розпізнати ключ або статистику зашифрованого та вихідного тексту. Немає жодних співвідношень між вихідним та зашифрованим текстами. Іншими словами, зашифрований текст – справжній випадковий потік бітів, навіть якщо одержати деякі зразки вихідного тексту. Єва не може порушити шифр, якщо вона не спробує всі можливі випадкові ключові потоки, які були б 2 n якщо розмір вихідного тексту - n -бітовий. Однак є проблема. Передавач та приймач для того, щоб спільно використовувати одноразовий блокнот ключів, повинні встановити з'єднання щоразу, коли вони хочуть обмінятися інформацією. Вони повинні так чи інакше домовитися про випадковий ключ. Тому цей досконалий і ідеальний шифр дуже важко реалізувати.

Приклад 7.17

Який вигляд має зашифрований текст при використанні одноразового шифру блокнота в кожному з наступних випадків?

а. Вихідний текст складається з n нулів.

б. Початковий текст складається з n одиниць.

в. Вихідний текст складається з нулів і одиниць, що чергуються.

м. Вихідний текст - випадковий рядок біт.

Рішення

a. Оскільки то потік зашифрованого тексту збігається з ключовим потоком. Якщо ключ є випадковим, зашифрований текст також випадковий. Уривки вихідного тексту у зашифрованому тексті не зберігаються.

b. Оскільки де є доповненням, потік зашифрованого тексту - доповнення ключового потоку. Якщо ключовий потік є випадковим, то зашифрований текст також випадковий, уривки вихідного тексту не зберігаються в зашифрованому тексті.

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

d. В даному випадку зашифрований текст явно випадковий, тому що проведення операції ВИКЛЮЧАЄ АБО двох випадкових бітів в результаті дає випадковий потік біт.

Реєстр зсуву із зворотним зв'язком

Одне вдосконалення до одноразового блокнота - (FSR - Feedback Shift Register). FSR може бути реалізований або в програмне забезпечення, або в апаратних засобах, але для простоти ми розглянемо апаратну реалізацію. Реєстр зсуву із зворотним зв'язкомскладається з регістру зсуву та функції зворотного зв'язку, Як показано на рис. 7.23.

Мал. 7.23.

Регістр зсуву – послідовність з m осередків від b 0 до b m-1 де кожна комірка призначена для збереження єдиного біта. Осередки розглядаються як n-бітове слово, зване на початку "початкове значення" або джерело. Щоразу, коли необхідно отримати біт на виході (наприклад, по сигналу в визначений час), кожен біт зрушується однією осередок вправо. Це означає, що значення кожного осередку присвоюється правому сусідньому осередку і набуває значення лівого осередку. Найправіша осередок b 0 вважається виходом і дає вихідне значення (k i ). Крайня ліва комірка, b m-1 отримує своє значення відповідно до значення інформації функції зворотного зв'язку. Позначаємо вихід функції з інформацією зворотного зв'язку b m. Функція інформації зворотного зв'язку визначає, які значення мають осередки, щоб обчислити b m.

Регістр зсуву інформації зворотного зв'язку може бути лінійним або нелінійним.Лінійний регістр зсуву із зворотним зв'язком (LFSR)

Лінійний регістр зсуву зі зворотним зв'язком працює з двійковими цифрами, тому множення і додавання знаходяться в полі GF(2) , так що значення C i є або 1 або 0 , але C 0 має бути 1 щоб отримати інформацію зворотного зв'язку на виході. Операція додавання – це операція ВИКЛЮЧНЕ АБО. Іншими словами,

Приклад 7.18

Побудуємо лінійний регістр зсуву зі зворотним зв'язком з 5-ма осередками, в яких .

Рішення

Якщо i = 0, b i не відіграє ролі у обчисленні b m , то це означає, що b i не пов'язаний з функцією інформації зворотного зв'язку. Якщо c i = 1, b i включається до обчислення b m. У цьому прикладі c 1 і c 3 - нулі, це означає, що ми маємо тільки три підключення. Малюнок 7.24 показує схему лінійного регістру зсуву із зворотним зв'язком.

Мал. 7.24.

Приклад 7.19

Побудуємо лінійний регістр зсуву зі зворотним зв'язком з 4-ма осередками, в яких . Покажіть значення регістру після 20 операцій (зрушень), якщо вихідне значення - (0001) 2 .

Рішення

Малюнок 7.25 показує схему та використання лінійного регістру зсуву зі зворотним зв'язком для шифрування.

Мал. 7.25.

Таблиця 7.6. показує значення потоку ключів. Для кожного переходу перше значення b 4 обчислюється, а потім кожен біт зсувається на одну комірку праворуч.

Таблиця 7.6.

поточне значення	b 4	b 3	b 2	b 1	b 0	k i
Початкове значення	1	0	0	0	1
1	0	1	0	0	0	1
2	0	0	1	0	0	0
3	1	0	0	1	0	0
4	1	1	0	0	1	0
5	0	1	1	0	0	1
6	1	0	1	1	0	0
7	0	1	0	1	1	0
8	1	0	1	0	1	1
9	1	1	0	1	0	1
10	1	1	1	0	1	0
11	1	1	1	1	0	1
12	0	1	1	1	1	0
13	0	0	1	1	1	1
14	0	0	0	1	1	1
15	1	0	0	0	1	1
16	0	1	0	0	0	1
17	0	0	1	0	0	0
18	1	0	0	1	0	0
19	1	1	0	0	1	0
20	1	1	1	0	0	1

Зауважимо, що потік ключів – 1000100110101111 1001…… . Він виглядає, на перший погляд, як випадкова послідовність, але, якщо переглянути велику кількість транзакцій (зрушень), ми можемо побачити, що послідовності періодичні. Це повторення по 15 біт показано нижче.

Ключ потоку генерує за допомогою лінійного регістру зсуву із зворотним зв'язком псевдовипадкову послідовність, у якій повторюються послідовності завдовжки N . Потік періодичний. Він залежить від схеми генератора та початкової інформації та може бути не понад 2 m – 1 . Кожна схема породжує m-бітові послідовності від містять усі нулі до містять усі одиниці. Однак якщо початкова послідовність складається тільки з нулів, результат марний - вихідний текст був би потоком з одних нулів. Тому така початкова послідовність виключена.

Міністерство освіти та науки

РОСІЙСЬКИЙ ДЕРЖАВНИЙ СОЦІАЛЬНИЙ УНІВЕРСИТЕТ

ФАКУЛЬТЕТ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

КАФЕДРА ЗАХИСТУ ІНФОРМАЦІЇ

Криптографічні методи та засоби забезпечення інформаційної безпеки

Курсова робота

«Р егістри зсуву з лінійним зворотним зв'язком як генератори псевдовипадкових чисел»

Виконав:

студент 3-го курсу

група КЗВД-Д-3

Ларіонов І.П.

Перевірила:

доц. Баранова О.К.

Москва 2011
ЗМІСТ

Вступ ……………………………..…………………………………….3

Теоретичні основироботи…………………………………………4
1. Загальні відомостіпро регістри зсуву із зворотним зв'язком……...…..4
  1. Про потокових шифрах з урахуванням РгСсЛОС………………….………10
  2. Про лінійну складність генерованої псевдовипадкової послідовності РгСсЛОС………………………………….……12
  3. Про кореляційну незалежність генерованої послідовності псевдовипадкових чисел РгСсЛОС………..….13
  4. Про інші способи розтину генерованої послідовності псевдовипадкових чисел РгСсЛОС…………………………………..14
Програмна реалізація РгСсЛОС як генератора псевдовипадкової послідовності….…………………………….15
1. Узагальнена схема алгоритму…………………………………...15
2. Опис програмних модулів та інтерфейсу.……………….16
3. Інструкція користувача………………………………………...20

Висновок ………………………………………………………………22

Список літератури………………………………………………….....23

Додаток А ….………………………………………………………..24

ВСТУП

Метою даної є розробка програмного докладання, що реалізує роботу генератора псевдовипадкових чисел на регістрах зсуву зі зворотним зв'язком. Розробка цього додаткуз графічним інтерфейсом здійснюється мовою C++ для ОС Windows.

З розвитком криптографії у ХХ столітті перед криптографами постало завдання створення шифрувальних пристроїв та машин, які могли б швидко та надійно зашифровувати та розшифровувати повідомлення. Цій вимогі відповідали вже відкриті на той час симетричні системи шифрування, проте їх слабким місцем була сильна залежність від ключа та його секретність. Найбільш зручним класом шифрів, які можна було використовувати для цієї мети, це шифри гамування. Виникла задача генерації гами, яку не можна було б виявити під час дешифрування повідомлення. Теоретично це було можливо, якщо щоразу гама була випадковою та змінювалась у часі. Однак при використанні абсолютно випадкової гами, що змінюється, було б важко забезпечити достовірне шифрування-дешифрування повідомлення. Криптографи зайнялися вирішенням цього завдання, метою якого було знаходження алгоритму реалізує генерацію випадкової гами за певним правилом, така послідовність повинна містити в собі нулі та одиниці на «нібито» випадкових позиціях, причому число одиниць та нулів має бути приблизно однаково. Така випадкова послідовність була названапсевдовипадковою,оскільки вона генерувалася за певним правилом, а не випадковим чином.

Рішення було знайдено. Вивчення властивостей регістрів зсуву дозволило встановити, що регістри зсуву із зворотним зв'язком здатні генерувати досить стійкі до дешифрування псевдовипадкові послідовності, зумовлені їхньою внутрішньою будовою.

1.Теоретичні основи роботи

1.1.Загальні відомості про регістри зсуву з лінійним зворотним зв'язком

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

Регістр зсуву із зворотним зв'язком (далі РгСсОС) складається з двох частин: регістру зсуву та функції зворотного зв'язку.Регістр зсуву є послідовністю бітів. Кількість бітів визначаєтьсядовжиною зсувного регіструякщо довжина дорівнює n бітам, то регістр називаєтьсяn-бітовим зсувним регістром. Щоразу, коли потрібно витягти біт, всі біти зсувного регістру зрушуються вправо на 1 позицію. Новий крайній лівий біт є функцією решти бітів регістра. На виході зсувного регістру виявляється один, зазвичай молодший біт.Періодом зсувного регіструназивається довжина одержуваної послідовності на початок її повторення.

Малюнок Регістр зсуву із зворотним зв'язком

Регістри зсуву дуже швидко знайшли застосування потокових шифрах, оскільки вони легко реалізовувалися з допомогою цифрової апаратури. У 1965 році Ернст Селмер (Ernst Selmer), головний криптограф норвезького уряду, розробив теорію послідовності регістрів зсуву. Соломон Голомб (Solomon Golomb), математик NSA, написав книгу, що викладає деякі свої результати та результати Селмера. Найпростішим видом регістру зсуву із зворотним зв'язком єрегістр зсуву з лінійним зворотним зв'язком ( linear feedback shift register , далі LFSR або РгСсЛОС) . Зворотний зв'язок таких регістрів є просто XOR (складання по модулю два) деяких бітів регістру, перелік цих бітів називається відвідною послідовністю (tap sequence). Іноді такий регістр називається конфігурацією Фіббоначі. Через простоту послідовності зворотний зв'язок для аналізу РгСсЛОС можна використовувати досить розвинену математичну теорію. Проаналізувавши отримані вихідні послідовності, можна переконатися, що ці послідовності досить випадкові, щоб бути безпечними. РгСсЛОС частіше за інших зсувних регістрів використовуються в криптографії.

Малюнок РгСсЛОС Фіббоначі

У загальному випадку n -бітовий РгСсЛОС може бути в одному з N = 2 n -1 внутрішніх станів. Це означає, що теоретично такий регістр може генерувати псевдовипадкову послідовність з періодом Т=2 n -1 біт. (Кількість внутрішніх станів і період дорівнюють N = T max =2 n -1, тому що заповнення РгСсЛОС нулями, призведе до того, що зсувний регістр видаватиме нескінченну послідовність нулів, що абсолютно марно). Тільки за певних відвідних послідовностей РгСсЛОС циклічно пройде через усі 2 n -1 внутрішніх станів, такі РгСсЛОС єРгСсЛОС з максимальним періодом. Результат, що вийшов, називаєтьсяМ-послідовністю.

приклад . На малюнку нижче показаний 4-бітовий РгСсЛОС з відведенням від першого та четвертого бітів. Якщо його проініціалізувати значенням 1111, то до повторення регістр прийматиме такі внутрішні стани:

Номер такту зсуву (внутрішнього стану)	Стан регістрів	Вихідний біт
Номер такту зсуву (внутрішнього стану)		Вихідний біт
Ініціальне значення














15 (повернення до ініціального стану)
16 (повтор станів)

Вихідною послідовністю буде рядок молодших бітів: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 з періодом Т=15, загальна кількість можливих внутрішніх станів (крім нульового), N = 24 -1 = 16-1 = 15 = T max , отже, вихідна послідовність M -Послідовність.

Для того щоб конкретний РгСсЛОС мав максимальний період, багаточлен, утворений з відвідної послідовності та константи 1, повинен бути примітивним за модулем 2. Багаточлен представляється у вигляді суми ступенів, наприклад, багаточлен ступеня n видається так:

a n x n +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 +…+a 1 x+a 0 де а i =(0, 1) для i = 1 ... n, a x i вказує розряд .

Ступінь многочлена є довжиною зсувного регістру. Примітивний багаточлен ступеня n – це неприведений багаточлен, який є дільником x 2n−1 +1, але не є дільником x d +1 для всіх d, які є дільниками 2 n -1. Відповідну математичну теорію можна знайти у .

У загальному випадку не існує простого способугенерувати примітивні багаточлени даного ступеня за модулем 2. Найпростіше вибирати многочлен випадковим чином і перевіряти, чи він примітивним. Це нелегко і чимось схоже на перевірку, чи не є простим випадково обране число - але багато математичних пакетів програм можуть вирішувати таке завдання.

Деякі, але, звичайно ж, не всі багаточлени різних ступенів, примітивні за модулем 2, наведені далі. Наприклад, запис

(32, 7, 5, 3, 2, 1, 0) означає, що наступний многочлен примітивний за модулем 2: x 32+x7+x5+x3+x2+x+1.

Це можна легко узагальнити для РГСЛОС з максимальним періодом. Першим числом є довжина РГСЛОС. Останнє число завжди дорівнює 0 і його можна опустити. Усі числа, за винятком 0, задають відвідну послідовність, що відраховується від лівого краю регістру зсуву. Тобто члени багаточлена з меншим ступенем відповідають позиціям ближче до правого краю регістру.

Продовжуючи приклад, запис (32, 7, 5, 3, 2, 1, 0) означає, що для взятого 32-бітового зсувного регістра новий біт новий біт генерується за допомогою XOR тридцять другого, сьомого, п'ятого, третього, другого та першого бітів , що виходить РгСсЛОС буде мати максимальну довжину, циклічно проходячи до повторення через 2 32 -1 значень.

Рисунок 4 32-бітовий РгСсЛОС з максимальною довжиною

Розглянемо програмний кодРгСсЛОС, у якого відвідна послідовність характеризується многочлен (32, 7, 5, 3, 2, 1, 0). На мові C виглядає так:

int LFSR () (

static unsigned long ShiftRegister = 1;

/* Все , крім 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1);

return ShiftRegister & 0 x 00000001;)

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

Слід звернути увагу, що у всіх елементів таблиці непарне число коефіцієнтів. Така довга таблиця наведена для подальшої роботи з РгСсЛОС, так як РгСсЛОС часто використовуються для криптографії з потоковими шифрами та в генераторах псевдовипадкових чисел. У нашому випадку можна використовувати багаточлени зі старшим ступенем не більше семи.

Якщо p(x) примітивний, то примітивний і x n p(1/x), тому кожен елемент таблиці насправді визначає два примітивні багаточлени. Наприклад, якщо (a, b, 0) примітивний, то примітивний і (a, a-b, 0). Якщо примітивний (a, b, c, d, 0), то примітивний (a, a-d, a-c, a-b, 0). Математично:

якщо примітивний x a +x b +1, то примітивний і x a +x a-b +1,

якщо примітивний x a + x b + x c + x d +1, то примітивний і x a + x a-d + x a-c + x a-b +1. Найшвидше програмно реалізуються примітивні тричлени, так як для генерації нового біта потрібно виконувати XOR тільки двох бітів регістру зсуву (нульовий член не враховується, тобто х 0 =1, див. приклад вище). Справді, все многочлени зворотний зв'язок, наведені у таблиці, є розрідженими, тобто, вони трохи коефіцієнтів. Розрідженість завжди є джерелом слабкості, якої іноді достатньо для розкриття алгоритму. Для криптографічних алгоритмів краще використовувати щільні примітивні багаточлени, ті, у яких багато коефіцієнтів. Застосовуючи щільні багаточлени, особливо як частину ключа, можна використовувати значно більш короткі РГСсЛОС.

Генерувати щільні примітивні багаточлени за модулем 2 нелегко. У випадку для генерації примітивних многочленов ступеня k потрібно знати розкладання на множники числа 2 k -1.

Самі по собі РГСЛОС є хорошими генераторамипсевдовипадкових послідовностей, але вони мають деякі небажані невипадкові (детерміновані) властивості. Послідовні біти лінійні, що робить їх непотрібними для шифрування. Для РгСсЛОС довжини n внутрішній стан є попередніми n вихідними бітами генератора. Навіть якщо схема зворотного зв'язку зберігається в секреті, вона може бути визначена по 2n вихідним бітам генератора за допомогою ефективного алгоритму Berlekamp-Massey .

Крім того, великі випадкові числа, що генеруються з використанням бітів цієї послідовності, що йдуть поспіль, сильно кореловані і для деяких типів додатків зовсім не є випадковими. Незважаючи на це РгСсЛОС часто використовуються для створення алгоритмів шифрування як складових частин систем та алгоритмів шифрування.

1.2.Про потокові шифри на базі РгСсЛОС

Основний підхід під час проектування генератора потоку ключів з урахуванням РгСсЛОС простий. Спочатку береться один або кілька РгСсЛОС, зазвичай з різними довжинами та різними многочленами зворотного зв'язку. (Якщо довжини взаємно прості, проте багаточлени зворотний зв'язок примітивні, то у утвореного генератора буде максимальна довжина.) Ключ є початковим станом регістрів РгСсЛОС. Щоразу, коли необхідний новий біт, посуньте на біт регістри РгСсЛОС (це іноді називають тактуванням (clocking)). Біт виходу є функцією, бажано нелінійною, деяких бітів регістрів РгСсЛОС. Ця функція називається комбінуючою функцією, а генератор загалом - комбінаційним генератором. (Якщо біт виходу є функцією єдиного РгСсЛОС, то генератор називається фільтруючим генератором.) Більшість теорії подібного роду пристроїв розроблена Селмером (Selmer) і Нілом Цирлером (Neal Zierler). Можна запровадити низку ускладнень. У деяких генераторах різних РгСсЛОС використовується різна тактова частота, іноді частота одного генератора залежить від виходу іншого. Все це електронні версії ідей шифрувальних машин, що з'явилися до Другої світової війни, які називаються генераторами з керуванням тактовою частотою ( clock - controlled generators ). Управління тактовою частотою може бути з прямим зв'язком, коли вихід одного РгСсЛОС управляє тактовою частотою іншого РгСсЛОС, або зі зворотним зв'язком, коли вихід одного РгСсЛОС управляє його власною тактовою частотою. Хоча всі ці генератори чутливі, принаймні теоретично, до розтину вкладенням та ймовірною кореляцією, багато з них безпечні досі.

Ян Касселлс (Ian Cassells), який раніше очолював кафедру чистої математики в Кембриджі і працював криптоаналітиком у Блетчлі Парк (Bletchly Park), сказав, що «криптографія – це суміш математики та плутанини, і без плутанини математика може бути використана проти вас». Він мав на увазі, що в потокових шифрах для забезпечення максимальної довжинита інших властивостей необхідні певні математичні структури, такі як РгСсЛОС, але щоб завадити комусь отримати зміст регістру і розкрити алгоритм, необхідно внести деякий складний нелінійний безлад. Ця порада справедлива і для блокових алгоритмів.

Більшість реальних потокових шифрів засновані на РГСЛОС. Навіть у перші дні електроніки збудувати їх було нескладно. Зсувний регістр не є нічого більшого, ніж масив бітів, а послідовність зворотного зв'язку - набір вентилів XOR. Навіть при використанні НВІС потоковий шифр на базі РгСсЛОС забезпечує неабияку безпеку за допомогою декількох логічних вентилів. Проблема РгСсЛОС у тому, що й програмна реалізація дуже неефективна. Вам доводиться уникати розріджених багаточленів зворотного зв'язку - вони полегшують кореляційні розтину, а щільні багаточлени зворотного зв'язку неефективні.

Ця галузь криптографії швидко розвивається і перебуває під пильним державним контролем із боку NSA . Більшість розробок засекречені - безліч військових систем шифрування, що використовуються сьогодні, засновані на РгСсЛОС. Справді, більшість комп'ютерів Cray (Cray 1, Cray X-MP, Cray Y-MP) є дуже цікава інструкція, зазвичай називається як "лічильник сукупності" (population count). Вона підраховує кількість одиниць у регістрі і може бути використана як для ефективного обчислення відстані Хеммінга між двома двійковими словами та для реалізації векторизованої версії РгСсЛОС. Ця інструкція вважається канонічною інструкцією NSA, яка обов'язково фігурує майже у всіх контрактах щодо комп'ютерів.

З іншого боку було зламана велика кількість генераторів, що здавалися складними, на базі зсувних регістрів. І, звичайно, число таких генераторів, зламаних військовими криптоаналітичними установами, такими як NSA, ще більше.

1.3.Про лінійну складність генерованої послідовності псевдовипадкових чисел РгСсЛОС

Аналізувати потокові шифри часто простіше ніж блокові. Наприклад, важливим параметром, що використовується для аналізу генераторів на базі РгСсЛОС є лінійна складність (linear complexity), або лінійний інтервал. Вона визначається як довжина найкоротшого РгСсЛОС, який може імітувати вихід генератора. Будь-яка послідовність, генерована кінцевим автоматом над кінцевим полем, має кінцеву лінійну складність. Лінійна складність важлива, тому що за допомогою простого алгоритмуЯк називається алгоритмом Berlekamp-Massey, можна визначити цей РгСсЛОС, перевіривши лише 2n біти потоку ключів . Відтворюючи потрібний РГСсЛОС, ви зламуєте потоковий шифр.

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

1.4.Про кореляційну незалежність генерованої послідовності псевдовипадкових чисел РгСсЛОС

Криптографи намагаються отримати високу лінійну складність, нелінійно поєднуючи результати деяких вихідних послідовностей. При цьому небезпека полягає в тому, що одна або кілька внутрішніх вихідних послідовностей - часто просто виходи окремих РгСсЛОС - можуть бути пов'язані загальним ключовим потоком і розкриті за допомогою лінійної алгебри. Часто таке розтин називають кореляційним розкриттям або розкриттям розділяй-і-пануй. Томас Сігенталер (Thomas Siegenthaler) показав, що можна точно визначити кореляційну незалежність, і що є компроміс між кореляційною незалежністю та лінійною складністю.

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

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

1.5.Про інші способи розтину генерованої послідовності псевдовипадкових чисел РгСсЛОС

Існують інші способи розтину генераторів потоків ключів. Тест на лінійну коректність (linear consistency) намагається знайти деяке підмножина ключа шифрування за допомогою матричної техніки. Існує і розтин коректності "зустрічею посередині" (meet-in-the-middle consistency attack). Алгоритм лінійного синдрому (linear syndrome algorithm) заснований на можливості записати фрагмент вихідної послідовності у вигляді лінійного рівняння. Існує розкриття найкращим афінним наближенням (best afflne approximation attack) і розкриття виведеною пропозицією (derived sequence attack). До потокових шифрів можна застосувати також методи диференціального та лінійного криптоаналізу.

2. Опис програмної реалізації РгСсЛОС як генератора псевдовипадкової послідовності

2.1.Узагальнена схема алгоритму

2.2.Опис програмних модулів та інтерфейсу

Нижче малюнку 3 представлено вікно програми.

Інтерфейс програми

У меню є такі функції:

Файл->Зберегти звіт

Ця функція здійснює створення файлу звіту, куди записується ініціальний стан РгСсЛОС, відвідна послідовність, період отриманої псевдовипадкової послідовності біт, сама послідовність та таблиця станів. Якщо файл був успішно збережений, то видається повідомлення про успішне збереження (рисунок 4). Розширення файлу звіту, що рекомендується *. txt.

Малюнок

Файл-> Вихід

Ця функція забезпечує закриття програми.

Задати відвідну послідовність

Ця функція формує відвідну послідовність, зчитуючи значення клітин, які користувач відзначив галочкою на екранній формі. Після цього вона повідомляє користувача про створення відвідної послідовності (рисунок 5). Відвідна послідовність визначає від яких тригерів регістру зсуву будуть йти зворотні зв'язки XOR для формування біта усунення. За замовчуванням зворотний зв'язок від першого тригера завжди стоїть, за відсутності інших зв'язків, буде здійснюватися зрушення вліво з перестановкою молодшого біта на позицію старшого.

Малюнок

Встановити ініціальне значення

Ця функція зчитує введене користувачем ініціальне значення регістра з вікна Edit 1 і здійснює перевірку введеного значення згідно з заданими умовами: введений рядок непустий (рисунок 6), введений рядок має довжину рівну восьми (8біт=1байт, малюнок 7), введений рядок містить тільки нулі та/або одиниці (рисунок 8), введений рядок ненульовий (Малюнок 9). В іншому випадку видаються повідомлення про помилку, користувач повинен виправити їх і знову натиснути на кнопку. У разі успішної перевірки ініціальне значення буде записано до таблиці станів у рядку «Ініціальне» та видано повідомлення (рисунок 10).

Малюнок

Здійснити зсув регістру

Ця функція емулює роботу регістра зсуву. Послідовно виробляючи 256 зрушень, кожен зсув формує вихідний біт псевдовипадкової послідовності та новий стан регістра. Як тільки стан регістру дорівнює ініціальному, обчислюється період і виводить у поле Memo 1 отриману псевдовипадкову послідовність.

Допомога-> Про програму

Ця функція виводить на екран короткий описпрограми та інструкцію (рисунок 11).

Малюнок

Допомога-> Про автора

Ця функція відображає інформацію про автора програми (малюнок 12).

Малюнок

2.3.Інструкція користувача

Спочатку встановіть ініціальний стан регістру. Воно має містити вісім двійкових символів. В іншому випадку буде видано повідомлення про помилку і Вам доведеться виправити введене значення. Натисніть пункт меню "Встановити ініціальне значення".
Потім позначте прапорцями в клітинах зворотні зв'язки регістра (відвідна послідовність). Натисніть пункт меню "Задати відвідну послідовність".
Далі натисніть пункт меню "Зсув регістру". Обов'язково перед тим переконайтеся, що ви виконали пункти 1 і 2, інакше буде програмна помилка.
Отримавши результати, ви можете їх зберегти натиснувши пункт меню «Файл->Зберегти звіт». Обов'язково перед цим переконайтеся, що ви виконали пункти 1-3, інакше буде програмна помилка.
Для отримання довідки натисніть пункти меню «Файл->Про програму», «Файл->Про автора».
Щоб переглянути роботу регістру при інших значеннях відвідної послідовності та ініціального стану регістра, повторіть послідовно дії в пунктах 1-3, ввівши інші параметри.

ВИСНОВОК

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

На сьогоднішній момент дані регістри не використовуються як самостійні генератори псевдовипадкових чисел, а входять до складу складніших пристроїв. Однак саме вони відкрили нові напрями в математиці (пошук примітивних багаточленів у кінцевих полях, математичні способи злому генераторів псевдовипадкових чисел). Без знання принципів роботи генераторів на РГСсЛОС не можна зрозуміти роботу складніших пристроїв. Завдяки своїй простій апаратній реалізації вони набули широкого поширення в техніці. Дослідження РгСсОС призвело до виникнення нових шифрів - блокових і потокових - заснованих на цих типах регістрів (шифр ковзної перестановки, DES і т.п.; ЕЦП, хеш-функції).

Загалом дослідження в цій галузі серйозно підштовхнули розвиток криптографії та криптоаналітики, ЕОМ та пристроїв, а також дозволили реалізувати й низку інших корисних функцій(наприклад, коригувальні циклові коди).

СПИСОК ЛІТЕРАТУРИ

Шнайєр Брюс. Прикладна криптографія. Протоколи, алгоритми, вихідні тексти мовою Сі. М.: Тріумф, 2002
Бабаш А.В. Криптографічні та теоретико-автоматні аспекти сучасного захисту інформації. Том 1 М.: Вид. центр ЄАОІ, 2009. 414 с.
О.С. Селмер. Монографія: «Лінійна рекурсія у кінцевому полі». Університет Бергена, Норвегія, 1966р.
Н.Зієрлер та Дж. Бріллхарт. "Про примітивні тричлени за модулем 2", журнал Інформація та Контроль, видання 13 №6 грудень 1968, стор 541-544.
К.Х. Мейєр та У.Л.Тучман. "Псевдовипадкові коди можуть бути зламані," журнал Електронік Дизайн, №. 23, листопад 1972 року.
Дж.Л.Масей. "Узагальнення регістрів зсуву та дешифрування коду Бозе-Чоудхурі-Хоквінгема", IEEE Transactions on Information Theory, v. IT -15, n . 1, січень 1969, стор 122-127.
С.У. Голомбі. Послідовності регістрів зсуву, Сан-Франциско, Голден-Дей, 1967 (перевидано Аігеан Парк Прес, 1982).

Додаток А

Таблиця деяких примітивних багаточленів за модулем 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Введення ініціального стану (ІВ)

роверка на правильність введення

Видача повідомлення про помилку

Встановлення відвідної послідовності

Запис ІВ у таблицю станів

Запис i -го стану регістру та вихідного біта в таблицю станів

ІС==Поточний стан

Збереження результатів

Висновок псевдовипадкової послідовності

Вихід

Запуск

Так

Ні

У регістрі зсуву з лінійним зворотним зв'язком виділяють дві частини (модуля): власне регістру зсуву і схеми (або підпрограми) обчислюють значення біта, що всувається. Регістр складається з функціональних осередків (або бітів машинного слова або кількох слів), у кожному з яких зберігається поточний стан одного біта. Кількість осередків називають довжиною регістра. Біти (комірки) зазвичай нумеруються числами , кожна з яких здатна зберігати біт, причому в комірку відбувається всування обчисленого біта, а з комірки витягується черговий згенерований біт, що висувається. Обчислення біта, що всувається, зазвичай проводиться до зсуву регістра, і тільки після зсуву значення обчисленого біта поміщається в комірку .

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

Для РСЛОС функція зворотний зв'язок є лінійної булевої функцією від станів всіх чи деяких бітів регістру. Наприклад, сума за модулем два або її логічна інверсія є лінійною булевою функцією (операція 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 = 1; S = ((((S>>31)^(S>>30)^(S>>29)^(S>>27)^(S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1);

return S&1; [)] Програмні реалізації РСЛОС генераторів досить повільні і швидше працюють, якщо вони написані на асемблері, а не мовою Сі. Одним із рішень є використання паралельно 16-ти РСЛОС (або 32, залежно від довжини слова в архітектурі конкретного комп'ютера). У такій схемі використовується масив слів, розмір якого дорівнює довжині РСЛОС, а кожен біт слова масиву відноситься до свого РСЛОС. За умови, що використовуються однакові номери відвідних послідовностей, це може дати помітний виграш у продуктивності.

потрібен приклад коду

(Див.: bitslice).

Конфігурація Галуа

Конфігурація Галуа регістру зсуву з лінійним зворотним зв'язком

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

Int LFSR (void) (static unsigned long Q = 1; Q = (Q>> 1) ^ (Q&1?0x80000057:0); return Q&1;)
Виграш полягає в тому, що всі XOR виконуються за одну операцію.
можна довести, що наведена перша конфігурація Фібоначчі і наведена конфігурація Галуа дають однакові послідовності (довжиною 2 32 −1), але зміщені по фазі одна від іншої

Приклади генераторів

Генератори «стоп-пішов»

Черговий генератор «стоп-пішов»

Цей генератор використовує виведення одного РСЛОС для управління тактовою частотою іншого РСЛОС. Тактовий вихід РСЛОС-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. Причому краще використовувати більше коротких РСЛОС ніж менше довгих РСЛОС.

Пороговий генератор

Цей генератор намагається обійти проблеми безпеки, характерні попередніх генераторів з допомогою змінного числа регістрів зсуву. Теоретично при застосуванні більшого числазсувних регістрів складність шифру зростає, що було зроблено у цьому генераторі.

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

Для випадку трьох регістрів зсуву генератор можна уявити як:

Цей генератор схожий на генератор Геффа за винятком того, що пороговий генератор має більшу лінійну складність. Його лінійна складність дорівнює:

де , , - Довжини першого, другого і третього регістрів зсуву.

Його недоліком і те, кожен вихідний біт дає деяку інформацію про стан зсувного регістру. А точніше 0,189 біта. Тому даний генератор може не встояти перед кореляційним розтином.

Інші види

Самопроріджувальні

Самопроріджувальні називаються генератори, які керують власною частотою. Було запропоновано два типи таких генераторів. Перший складається з регістру зсуву зі зворотним лінійним зв'язком і деякою схемою, яка тактує цей регістр, залежно від того, якими виходять вихідні значення регістра зсуву. Якщо вихід РСЛОС дорівнює одиниці, то регістр тактується d разів. Якщо вихід дорівнює нулю, то регістр тактується разів. Другий має практично ту ж конструкцію, але дещо модифіковану: у схемі тактування на вхід, як перевірку на 0 або 1, надходить не сам вихідний сигнал, а XOR певних бітів регістру зсуву з лінійним зворотним зв'язком. На жаль, цей вид генератора не є безпечним.

Багатошвидкісний генератор із внутрішнім твором

Цей генератор використовує два регістри зсуву з лінійним зворотним зв'язком з різними тактовими частотами: РСЛОС-1 і РСЛОС-2. Тактова частота РСЛОС-2 у d разів більша ніж РСЛОС-1. Окремі біти цих регістрів поєднуються операцією AND. Потім із виходами операції AND виконується операція XOR. З цього блоку XOR знімається вихідна послідовність. Знову ж таки і цей генератор не бездоганний (Він не вистояв перед розкриттям лінійної узгодженості. Якщо - довжина РСЛОС-1,- довжина РСЛОС-2, а d - відношення тактових частот, то внутрішній стан генератора може бути отримано за вихідною довжиною послідовності), але він має високу лінійну складність і має чудові статистичні характеристики.

Визначення

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

Для РСЛОС функція зворотного зв'язку є сумою за модулем 2 (xor) деяких бітів регістра, званих відведеннями.

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

Регістр зсуву з лінійним зворотним зв'язком

Таким чином, як функція зворотного зв'язку береться логічна операція XOR (що виключає АБО), тобто:

Властивості

Властивості послідовності, що видається РСЛОС, тісно пов'язані з властивостями асоційованого багаточленанад полем. Його ненульові коефіцієнти називаються відведеннями, Як і відповідні осередки регістру, що поставляють значення аргументів функції зворотного зв'язку.

Періодичність

Так як існує різних ненульових станів регістра, то період послідовності, що генерується РСЛОС при будь-якому початковому ненульовому стані, не перевищує . У цьому період залежить від асоційованого многочлена:

Властивості примітивних багаточленів

Лінійна складність

Визначення

Лінійною складністюнескінченної двійкової послідовності називається число, яке визначається наступним чином:

Лінійною складністюКінцевою двійковою послідовністю називається число , яке дорівнює довжині найкоротшого РСЛОС, який генерує послідовність, що має як перші члени .

Властивості лінійної складності

Нехай і – двійкові послідовності. Тоді:

Кореляційна незалежність

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

Примітка

приклад

Номер кроку	Стан	Генерований біт
0		-
1		1
2		0
3		0
4		1
5		1
6		1
7		0

Алгоритми генерації примітивних багаточленів

Готові таблиці

Int LFSR (void) (static unsigned long S = 1; S = ((((S>>31)^(S>>30)^(S>>29)^(S>>27)^(S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1);

потрібен приклад коду

(Див.: bitslice).

Конфігурація Галуа

Конфігурація Галуа регістру зсуву з лінійним зворотним зв'язком

Примітки:

можна довести, що наведена перша конфігурація Фібоначчі та наведена конфігурація Галуа дають однакові послідовності (довжиною 2³²-1), але зміщені по фазі одна від іншої
цикл із фіксованого числа викликів функції LFSR у конфігурації Галуа виконується приблизно вдвічі швидше, ніж у конфігурації Фібоначчі (компілятор MS VS 2010 на Intel Core i5)
можна довести, що наведена перша конфігурація Фібоначчі і наведена конфігурація Галуа дають однакові послідовності (довжиною 2 32 −1), але зміщені по фазі одна від іншої

Приклади генераторів на РСЛОС

Генератори «стоп-пішов»

Черговий генератор "стоп-пішов"

Каскад Голлманна

Каскад Голлманна є посиленою версією генератора «стоп-пішов». Він складається з послідовності РСЛОС, тактування кожного з яких керується попереднім РСЛОС. Якщо виходом РСЛОС-1 на момент часу t є 1, то тактується РСЛОС-2. Якщо виходом РСЛОС-2 у час t є 1, то тактується РСЛОС-2, тощо. Вихід останнього РСЛОС є виходом генератора. Якщо довжина всіх РСЛОС однакова і дорівнює n, то лінійна складність системи з k РСЛОС дорівнює

Ця ідея просто і може бути використана для генерації послідовностей з величезними періодами, великими лінійними складнощами та добрими статистичними властивостями. Але, на жаль, вони чутливі до розтину, що зветься «замиканням» (lock-in). Для більшої стійкості рекомендується використовувати k не менше 15. Причому краще використовувати більше коротких РСЛОС ніж менше довгих РСЛОС.

Пороговий генератор

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

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

Для випадку трьох регістрів зсуву генератор можна уявити як:

Де , , - Довжини першого, другого і третього регістрів зсуву.

Його недоліком є те, що кожен вихідний біт дає деяку інформацію та стан зсувного регістру. А точніше 0,189 біта. Тому даний генератор може не встояти перед кореляційним розтином.

Інші види генераторів

Опишемо їх коротко

Реєстр зсуву із зворотним зв'язком

Властивості примітивних багаточленів

Властивості

Лінійна складність

Кореляційна незалежність

приклад

Алгоритми генерації примітивних багаточленів

Готові таблиці

потрібен приклад коду

Приклади генераторів

Генератори «стоп-пішов»

Каскад Голлманна

Пороговий генератор

Інші види

Самопроріджувальні

Багатошвидкісний генератор із внутрішнім твором

Визначення

Властивості

Періодичність

Властивості примітивних багаточленів

Лінійна складність

Кореляційна незалежність

приклад

Алгоритми генерації примітивних багаточленів

Готові таблиці

потрібен приклад коду

Приклади генераторів на РСЛОС

Генератори «стоп-пішов»

Каскад Голлманна

Пороговий генератор

Інші види генераторів

Самопроріджуючі генератори