Головна → Налаштування Windows Регістр зсуву з лінійним зворотним зв'язком с. Зсувні регістри зі зворотним зв'язком

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

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

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

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

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

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

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

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

Виконав:

студент 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 представляється так:

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

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

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

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

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

Вихід

Запуск

Так

Ні

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

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

Реєстр зсуву з лінійним зворотним зв'язком(РСЛОС, анг. 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), коли

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

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

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

Рисунок 2. РгСсЛОС Фіббоначі

У випадку 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=2 4 -1=16-1= 15 = T max, отже, вихідна послідовність - M-послідовність.

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

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. Найпростіше вибирати багаточлен випадковим чином і перевіряти, чи він не є примітивним. Це нелегко і чимось схоже на перевірку, чи не є простим випадково обране число - але багато математичних пакетів програм уміють вирішувати таке завдання.

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

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

static unsigned long ShiftRegister = 1;

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

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

| (ShiftRegister >> 1);

return ShiftRegister & 0x00000001;)

Якщо зсувний регістр довший за комп'ютерне слово, код ускладнюється, але не набагато. У додатку 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, див. Приклад вище). Справді, все многочлени зворотний зв'язок, наведені у таблиці, є розрідженими, тобто, вони трохи коефіцієнтів. Розрідженість завжди є джерелом слабкості, якої іноді достатньо для розкриття алгоритму. Для криптографічних алгоритмів краще використовувати щільні примітивні багаточлени, ті, у яких багато коефіцієнтів. Застосовуючи щільні багаточлени, особливо як частина ключа, можна використовувати значно більш короткі РгСсЛОС.

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

- "Tetromino tennis"). Він створив і вирішив незліченну кількість математичних головоломок та каламбурів. 20 років тому я дізнався, що він був дуже близький до відкриття мого улюбленого правила 30 для клітинних автоматів ще в 1959 році, коли я тільки народився.

Як я зустрів Сола Голомба

Багато вчених і математиків, з якими я знайомий, я дізнався завдяки моїм професійним зв'язкам. Але тільки не Сола Голомба. Йшов 1981 рік, і я, 21-річний фізик (що став трохи відомим у ЗМІ тому, що був наймолодшим одержувачем премії МакАртура на першій церемонії нагородження) займався дослідженнями у . У двері мого кабінету постукали, і невдовзі його поріг переступила молода жінка. Вже це було незвичайно, тому що в ті часи, де займалися теоретичною фізикою високих енергій, жінок було безнадійно мало. Хоча я й прожив у Каліфорнії кілька років, проте не залишав меж університету, а тому виявився погано підготовлений до сплеску південнокаліфорнійської енергії, яка вдерлася до мене до кабінету. Жінка представилася Астрід і сказала, що відвідувала Оксфорд і знала когось, з ким я був у дитячому садку. Вона пояснила, що їй було доручено зібрати відомості про цікавих людей у районі Пасадени. Думаю, вона вважала мене важким випадком, але наполягала на розмові. І одного разу, коли я намагався розповісти щось про те, чим займаюся, вона сказала: " Ви повинні зустрітися з моїм батьком. Він уже літня людина, але його розум, як і раніше, гострий, як бритва. І так сталося, що Астрід Голомб, старша дочка Сола Голомба, познайомила мене з ним.

Сім'я Голомб жила в будинку, розташованому в горах поблизу Пасадени. У них було дві дочки: Астрід - трохи старший за мене, честолюбна голлівудська дівчина, і Беатріс - приблизно мого віку та наукового складу розуму. Сестри Голомб часто влаштовували вечірки – як правило, у себе вдома. Теми були різні: це і вечірка в саду та крокет із фламінго та їжаками (" переможцем стане той, чий костюм найбільше відповідатиме заявленій темі"), або вечірка в стилі Стоунхендж з інструкціями, написаними рунами. На цих вечірках перетиналися молоді і не дуже люди, у тому числі - різні місцеві світила. І на них, трохи осторонь, була присутня завжди маленька людина з великою бородою, трохи схожа на ельфа і що носив завжди темне пальто, - сам Соломон Голомб.

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

Ось що відбувається через деякий час:

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

Якщо регістр зсуву має розмір n,то у нього є 2 nможливих станів (відповідають усім можливим послідовностям 0 та 1 при довжині n). Оскільки правила для регістру зсуву детерміновані, будь-яке дане положення завжди має прийти до іншого такого ж положення. А це означає, що максимально можливе число кроків, яке регістр зсуву може пройти, перш ніж кроки почнуть повторюватися, n(насправді 2 n- 1, так як становище з усіма 0 не може еволюціонувати у щось ще).

У наведеному вище прикладі, регістр зсуву має розмір 7 і повториться через 2 7 - 1 = 127 кроків. Але які регістри зсуву - з якими розташуваннями відгалужень будуть виробляти послідовності максимальної довжини? Це питання Соломон Голомб почав досліджувати влітку 1954 року. І його відповідь була простою і елегантною.

Регістр зсуву наведений вище має відгалуження в положеннях 7, 6 і 1. Сол представив це алгебраїчно, використовуючи багаточлен х 7 + х 6 + 1. Він показав тоді, що послідовність, що генерується, буде максимальною довжиною, якщо цей многочлен " ненаводимо по модулю 2"; тому він не може бути факторизований, що робить його аналогом простого числа серед багаточленів; а наявність деяких інших властивостей робить його "примітивним багаточленом". На сьогоднішній день це легко перевірити за допомогою системи Mathematica та мови Wolfram Language:

Тоді, 1954 року, Сол повинен був робити все це вручну; він склав досить довгу таблицю примітивних багаточленів, що відповідають регістрам зсуву, які видавали послідовності максимальної довжини:

Передісторія регістрів зсуву

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

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

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

Ще у 2001 році, коли я працював над історичними нотатками для моєї книги Новий вид наукиМи з Солом довго говорили по телефону про зсуви регістру. Сол сказав мені, що коли він починав, він нічого не знав про криптографічну роботу з регістрів зсуву. Він сказав, що співробітники лабораторії Белла, лабораторії Лінкольна та Лабораторії реактивного руху почали працювати над регістрами зсуву приблизно в той же час, що він; проте йому вдалося просунутися трохи далі, що він і наголосив у своєму звіті від 1955 року.

Протягом наступних років Сол поступово дізнавався про різних попередників своїх робіт із літератури, присвяченої чистій математиці. Вже в 1202 Фібоначчі говорив про те, що тепер називають числами Фібоначчі і які генеруються рекурентним співвідношенням (яке може розглядатися як аналог регістру зсуву з лінійним зворотним зв'язком, що працює з довільними цілими числами, а не з нулями і одиницями). Існують також невеликі роботи початку 1900-х за циклічністю 0 і 1, проте першим великомасштабним дослідженням стала робота Ойстена Оре з Університету Осло. У Оре був студент на ім'я Маршалл Холл, який консультував попередника Агентства національної безпеки наприкінці 1940-х років. - мабуть, на тему регістрів зсуву. Однак усе, що він робив, було засекречено, і тому він домовився із Солом, щоб той опублікував історію регістрів зсуву з лінійним зворотним зв'язком; Сол присвятив свою книгу Маршаллу Холлу.

Навіщо потрібні послідовності, генеровані регістрами зсуву?

Я багато разів помічав, що системи, які визначаються простими правилами, зрештою мають багато варіантів додатків; регістри зсуву також дотримуються цієї закономірності. І сучасне обладнання, і програмне забезпечення напхане регістрами зсуву: у звичайному мобільному телефоні, ймовірно, їх десяток або два, реалізованих, як правило, на апаратному рівні, а іноді - і в програмне забезпечення(Коли я пишу тут «регістр зсуву», я маю на увазі регістр зсуву з лінійним зворотним зв'язком - LFSR).

У більшості випадків використовуються ті регістри зсуву, які дають послідовності максимальної довжини (інакше відомі як " М-послідовностіПричини, за якими вони використовуються, як правило, пов'язані з деякими їх властивостями, які виявив Сол. Вони завжди містять однакову кількість 0 і 1 (хоча насправді завжди є рівно одна додаткова 1). Згодом Сол показав, що їм також властиво однакову кількість послідовностей 00, 01, 10 і 11 - і для великих блоків теж. балансуЦе саме собою вже дуже корисно, - наприклад, якщо тестувати всі можливі комбінації бітів як вхідні дані.

Однак Сол виявив ще одну, навіть більш важливу властивість. Замініть кожен 0 у послідовності на 1, потім помножте кожен елемент у зсунутій версії послідовності на відповідний елемент оригіналу. Сол показав, що при складанні ці елементи завжди дорівнюватимуть нулю (крім випадків, коли ніякого зсуву немає взагалі). Тобто послідовність не має жодної кореляції зі зрушеними версіями самої себе.

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

Саме ця структура, властива регістрам зсуву з лінійним зворотним зв'язком, робить їх непридатними для серйозної криптографії. Але вони чудово підходять для базової «перестановки елементів» та дешевої криптографії та активно використовуються для цих цілей. Часто стоїть завдання просто "відбілити" сигнал (як у "білому шумі"). Іноді потрібно передавати дані з довгими послідовностями 0. Але електроніка в такому разі може заплутатися, якщо "мовчання" буде надто довгим. Можна уникнути цієї проблеми через скремблінг вихідних даних шляхом об'єднання його з послідовністю, що генерується регістром зсуву. Саме це було зроблено з Wi-Fi, Bluetooth, USB, цифровим TV, інтернетом і т.д.

Побічний ефект скремблінгу регістру зсуву - більш складне декодування, що використовується іноді для підвищення безпеки (у технології DVD для кодування даних використовується комбінація регістрів зсуву з довжиною 16 і 24 біти; багато GSM телефонів використовують комбінацію з трьох регістрів зсуву для кодування всіх сигналів).

Сол створив математичну основу для цього, а також перезнайомив один з одним ряд ключових фігур. Ще в 1959 році він познайомився з Ірвіном Джейкобсом, який нещодавно отримав докторський ступінь у Массачусетському технологічному інституті. Також він був знайомий з Енді Вітербі, який працював у Лабораторії реактивного руху. Сол познайомив їх, і в 1968 вони заснували компанію під назвою Linkabit, що працювала над системами кодування (в основному для військових цілей).

У 1985 році Джейкобс і Вітербі заснували ще одну компанію під назвою Qualcomm. Спочатку справи у них йшли не дуже добре, але до початку 1990-х років, коли вони почали виробляти компоненти для розгортання CDMA в стільникових телефонах, компанія почала стрімко зростати.

Ну і де ці регістри?

Дивно, що більшість людей ніколи не чули про регістри зсуву і при цьому взаємодіють з ними щоразу, коли користуються сучасними системамизв'язку, обчислювальною технікою і т. д. Тут нескладно заплутатися, враховуючи, що за різними назвами та абревіатурами виявляються ті ж послідовності регістрів зсуву з лінійним зворотним зв'язком (PN, псевдошум, M-, FSR, LFSR послідовності, MLS, SRS, PRBS, і т.д.).

Якщо розглядати мобільні телефони, то використання в них послідовностей, що генеруються регістрами зсуву, змінювалося протягом багатьох років, то збільшуючись, то зменшуючись. мережі засновані на TDMA, так що для кодування своїх даних не використовують послідовності, що генеруються регістрами зсуву, однак часто використовують CRC (циклічний надлишковий код) для перевірки блоків даних. мережі - найбільші користувачі CDMA, отже послідовності, генеровані регістрами зсуву, задіяні передачі кожного біта. мережі зазвичай використовують поєднання часу та частоти слотів, що не включають послідовності регістрів зсуву, хоча CRC ще використовуються: наприклад, щоб взаємодіяти з цілісними даними, коли частотні вікна перекривають один одного. має більш складну структуру - з безліччю антен, що динамічно адаптуються для використання оптимального часу та частоти слотів. Однак половина їх каналів, як правило, виділяється для «пілот-сигналів», що використовуються для виведення локального радіосередовища; в їх основі також лежать послідовності, що генеруються регістрами зсуву.

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

Регістри зсуву настільки всюдисущі, що практично неможливо оцінити, скільки біт ними генерується. Існує приблизно 10 мільярдів комп'ютерів, трохи менше – телефонів, і величезна кількість пристроїв у вбудованому IoT («інтернетом речей»). Майже кожен автомобіль у світі (а їх більше мільярда!) - близько 10 вбудованих мікропроцесорів.

На якій частоті працюють регістри зсуву? У системах зв'язку є базова несуча частота в герцовому діапазоні, а також швидкість передачі елементів сигналу, яка говорить про те, як швидко здійснюється множинний доступ (мова йде про CDMA) в діапазоні МГц. З іншого боку, в шинах усередині комп'ютерів усі дані передаються за допомогою регістрів зсуву найкращою швидкістюпередачі у герцовому діапазоні.

Існує щонайменше 10 мільярдів ліній зв'язку, що працюють принаймні 1/10 мільярда секунд (близько 3-х років), які використовують щонайменше 1 мільярд бітів зі зсувних регістрів кожну секунду, що означає, що на сьогоднішній день алгоритм Сола був використаний принаймні октиліон разів.

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

Проте є «алгоритмічні ідеї», які залишаються незрозумілими всім, крім дизайнерів мікропроцесорів. Коли Беббідж робив свою різницеву машину (див. статтю на Хабре "Розплутуючи історію Ади Лавлейс (першого програміста в історії)"), переноси стали великою перешкодою у виконанні арифметичних операцій (насправді, про регістр зсуву з лінійним зворотним зв'язком можна думати як про системі, яка робить щось подібне до арифметичних обчислень, але не здійснює перенесення). Існують «дерева поширення сигналу перенесення», що оптимізують перенесення. Є також маленькі хитрощі (на кшталт "алгоритму Бута", "дерев Уоллеса" і т. д.), які зменшують кількість бітових операцій, необхідних для створення "нутрощів" арифметики. Але, на відміну від регістрів зсуву з лінійним зворотним зв'язком, єдиної алгоритмічної ідеї, яка використовувалася б практично будь-де, просто не існує; тому я думаю, що максимально довгі послідовності, що генеруються регістрами зсуву з лінійним зворотним зв'язком, все-таки перемагають серед найбільш використовуваних послідовностей.

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

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

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

Це вкладений патерн; і ця картина дуже схожа на ту, яку можна отримати у випадку, якщо клітинний автомат візьме клітину та сусідню з нею і складе їх за модулем 2 (XOR). Ось що відбувається з клітинним автоматом, якщо він має свої клітини так, що вони знаходяться в колі того ж розміру, що і регістр зсуву вище:

Спочатку клітинні автомати і патерни зсувного регістру виявляються такими самими. Якщо подивитися на ці картинки, менш дивно, що математика регістрів зсуву повинна мати відношення до клітинних автоматів. І з огляду на повторюваність вкладених патернів стає ясно, чому повинна існувати елегантна математична теорія регістрів зсуву.

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

Наскільки ж широка відповідність між регістрами зсуву і клітинними автоматами? Для клітинних автоматів правила генерації нових значень осередків можуть бути будь-якими. У регістрах зсуву з лінійним зворотним зв'язком вони завжди повинні бути засновані на додаванні за модулем 2 (або XOR). Це те, що означає «лінійна» частина «регістру зсуву з лінійним зворотним зв'язком». Також можливе використання будь-якого правила для поєднання значень для регістрів зсуву з нелінійним зворотним зв'язком (NFSR).

І справді: коли Сол розробив свою теорію для регістрів зсуву з лінійним зворотним зв'язком, він почав з нелінійного випадку. Коли він прибув у JPL у 1956 році, він отримав лабораторію, укомплектовану стійками для маленьких електронних модулів. Сол розповідав, що модулі (кожен із яких був розміром з сигаретну пачку) були побудовані для проекту Bell Labs для виконання певної логічної операції (AND, OR, NOT, ...). Модулі можуть бути використані разом для реалізації будь-яких бажаних регістрів зсуву з нелінійним зворотним зв'язком, забезпечуючи близько мільйона біт на секунду (Сол сказав мені, що хтось намагався зробити те саме за допомогою універсального комп'ютера, і те, що зайняло 1 секунду при використанні апаратних модулів, зажадало 6 тижнів роботи на універсальному комп'ютері).

Коли Сол став вивчати регістри зсуву з лінійним зворотним зв'язком, першим його серйозним відкриттям стали періоди їхнього повторення. І у випадку з нелінійними він більшу частину своїх зусиль направив на спроби зрозуміти те саме. Він зібрав усі види експериментальних даних. Він розповів мені, що він перевіряв навіть послідовності довжиною 245, що зажадало рік. Він зробив резюме як на малюнку нижче (зверніть увагу на візуалізацію послідовностей, показаних на лінії осцилограми). Але йому так і не вдалося вигадати якоїсь загальної теорії, яка була у нього для регістрів зсуву з лінійним зворотним зв'язком.

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

І тільки пізніше стало ясно, наскільки складною може бути поведінка навіть дуже простих програм. Мій улюблений приклад - правило 30 для клітинного автомата, в якому значення сусідніх осередків поєднуються за допомогою функції, яка може бути представлена у вигляді р + q + r + q*r mod 2(або р XOR ( q OR r)). Неймовірно, але Сол розглядав регістри зсуву з нелінійним зворотним зв'язком, засновані на аналогічних функціях: р + г + s + q*r + q*s + r*s mod 2. Ось тут, нижче, - ілюстрації того, як функція Сола (яку можна розглядати як "правило 29070"), правило 30 та кілька інших подібних правил виглядають у регістрі зсуву:

А тут вони, не обмежені регістром фіксованого розміру, схожі на клітинні автомати:

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

Сол ставив собі питання про те, чи можуть регістри зсуву з нелінійним зворотним зв'язком бути джерелами хаотичності. З того, що сьогодні відомо про клітинні автомати, ясно, що можуть. Наприклад, для створення хаотичності системи Mathematica ми протягом 25 років використовували правило 30 клітинних автоматів (хоча недавно ми відмовилися від нього на користь більш ефективного правила, яке ми знайшли, вивчивши трильйони можливостей).

Про шифрування Сол говорив трохи; хоча я гадаю, що він недовго працював на уряд. Він сказав мені, що хоча в 1959 році він і виявив " багатовимірні кореляційні атаки на нелінійні послідовності", в той же час він" ретельно уникав тверджень, що програма була для криптоаналізу". Справа в тому, що правило 30 для клітинних автоматів (і, можливо, також регістри зсуву з нелінійним зворотним зв'язком) можуть бути хорошими криптосистемами - хоча через те, що вони ніби еквівалентні регістрам зсуву з лінійним зворотним зв'язком (а це не так), вони ніколи не використовувалися настільки, наскільки можна.

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

Поліоміно

Почувши прізвище Голомб ", багато хто згадає про регістри зсуву. Проте більшість згадає про поліоміно. Сол не винаходив поліоміно, хоч і вигадав цю назву. Він зробив систематичним те, що раніше з'являлося лише в окремих головоломках.

Головне питання, у відповіді на яке Сол був зацікавлений, це як набори поліоміно можуть бути організовані, покривши деяку область. Іноді це досить очевидно, а іноді досить складно. Свою першу статтю про поліоміно Сол опублікував у 1954 році, проте справді популярним зробив поліоміно Мартін Гарднер у 1957 році (він вів колонку про математичні ігри в журналі Scientific American). Як пояснив Сол у передмові до своєї книги від 1964 року, в результаті він отримав постійний потік кореспондентів з усього світу та з усіх верств суспільства: голів ради директорів провідних університетів, мешканців невідомих монастирів, ув'язнених із відомих в'язниць.".

Ігрові компанії також звернули увагу на нові головоломки, і протягом кількох місяців з'явилися заголовки на кшталт нові сенсаційні головоломки", а за ними послідували десятиліття інших головоломок та ігор на основі поліоміно (ні, зловісний лисий хлопець не схожий на Сола):

Сол друкував статті про поліоміно ще 50 років після першої публікації. У 1961 році він представив варіанти розподілу на дрібні частини "rep-tiles", за допомогою яких можна створювати фрактальні ("Infin-tile") візерунки. Але майже все, що Сол робив з поліоміно, включало рішення конкретних проблем.

Мене мало цікавить специфіка поліоміно; мене цікавлять пов'язані з ними феномени більш загального характеру. Здається, що вирішити, чи можна за допомогою кількох простих форм "замостити" всю площину, легко. Але у випадку з поліоміно (а також з усіма іграми та головоломками, заснованими на них) стає ясно, що все не так просто. І справді - у 1960-ті роки було доведено, що це завдання теоретично нерозв'язне.

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

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

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

Відомо, що складні та ретельно розроблені набори поліміно фактично підтримують універсальні обчислення. Але що щодо простого набору? Чи він досить простий для того, щоб випадково натрапити на нього? Якщо подивитися на всі ті системи, які я вивчав, то найпростіший набір справді виявляється простим. Проте знайти його складно.

Значно простіша завдання полягає у знаходженні поліоміно, які успішно заповнюють площини, хоч і лише неперіодично. Роджер Пенроуз в 1994 знайшов відповідний приклад. У моїй книзі Новий вид наукия навів трохи простіший приклад з 3 поліоміно:

Решта історії

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

Регістри зсуву та поліоміно – об'ємні теми (вони навіть виведені в окремі категорії в AMS класифікації). В останні десятиліття вони обидві отримали новий виток розвитку, коли на їхній основі стали проводити комп'ютерні експерименти; Сол також брав у них активну участь. Проте багато питань залишаються без відповідей. І якщо для регістрів зсуву з лінійним зворотним зв'язком можна знайти великі матриці Адамара, то навіть зараз про регістри зсуву з нелінійним зворотним зв'язком мало що відомо, не кажучи вже про всі неперіодичні та інші екзотичні поліоміно.

Сол завжди цікавився головоломками - як математичними, так і зі словами. Деякий час він вів колонку головоломок для Los Angeles Times, і протягом 32 років писав гамбіти ГоломбаУ журнал для випускників Джона Хопкінса. Він брав участь у тестуванні MegaIQ і виграв поїздку в Білий дім, коли він сам і його начальник увійшли до п'ятірки найкращих у країні.

Він вкладав величезні зусилля у свою роботу в університеті: не лише навчав студентів та керував аспірантами та сходив по адміністративних сходах (президент університетської ради, віце-проректор з досліджень та ін.), а й висловлював свою думку про управління університетом загалом (наприклад, написав статтю, під назвою «Консалтинг на факультеті: прибрати чи залишити?» ; Відповідь: ні, це добре для університету!). В університеті Південної Каліфорнії він займався хедхантингом, і за час своєї роботи він допоміг університету піднятися з невідомості на вершину рейтингу освітніх програм.

А потім був консалтінг. Сол був скрупульозним і не розкривав те, що робив для урядових організацій. Наприкінці 60-х рр., розчарований тим, що всі, крім нього взялися за продаж ігор на основі поліоміно, Сол заснував компанію, яку назвав Recreational Technology, Inc. Справи йшли не дуже добре, проте Сол познайомився з Елвіном Берлекемпом - професором з Берклі, який захоплювався теоріями кодування та головоломками. Згодом вони заснували компанію Cyclotomics (на честь циклотомічних багаточленів виду x n- 1), яка в результаті була продана компанії Kodak за круглу суму (Берлекемп створив також алгоритмічну торгову систему, яку він потім продав Джиму Сімонсу і яка стала відправною точкою для Renaissance Technologies - одного з найбільших на сьогоднішній день хедж-фондів).

Більше 10000 патентів так чи інакше пов'язані з роботами Сола, а ось сам Сол отримав лише один патентна криптосистеми на основі квазігруп - і я думаю, що він мало що зробив для комерціалізації своєї роботи.

Протягом багатьох років Сол працював із Техніоном – ізраїльським технологічним інститутом. Він говорив про себе як про " нерелігійному ортодоксальному євреї", але при цьому іноді вів для новачків семінари з книги Буття, а також працював над розшифровкою частин сувоїв Мертвого моря (Кумранських рукописів).

Сол та його дружина багато подорожували, проте «центром миру» для Сола безумовно були його офіс у Лос-Анджелесі в Університеті Південної Каліфорнії, та будинок, у якому він та його дружина жили протягом майже 60-ти років. Він завжди був оточений друзями та студентами. І він мав сім'ю. Його дочка Астрід зіграла роль студентки в п'єсі про Річарда Фейнмана (вона позувала йому), і в романі мого друга як один з персонажів. Беатріс присвятила свою кар'єру застосуванню математичного рівня точності до різних видів медичних показань та діагностики (хвороби, пов'язані з війною в Перській затоці, ефекти статинів, напади гикавки тощо). Я навіть зробив свій невеликий внесок у життя Беатріс, познайомивши її з людиною, яка стала потім її чоловіком - з Террі Сейновськи, одним із засновників сучасної обчислювальної нейронауки.

Здавалося, що Сол залучений до багатьох подій, навіть якщо він не надто говорив про деталі. Іноді мені хотілося поговорити з ним про науку та математику, але йому цікавіше було розповідати історії (часто дуже цікаві) як про окремих осіб, так і про організації (" Чи можете ви повірити, що [1985 року], після багаторічної відсутності на конференціях, Клод Шеннон просто з'явився без попередження в барі на щорічній конференції з теорії інформації?"; "ви знаєте, скільки вони мали заплатити главі Каліфорнійського технологічного інституту, щоб змусити його поїхати до Саудівської Аравії?", і т.д.).

Озираючись назад, я розумію, що хотів би зацікавити Сола у вирішенні деяких математичних питань, піднятих у моїй роботі. Думаю, що я так і не зрозумів, як він любив вирішувати проблеми, запропоновані іншими людьми. Незважаючи на значний внесок у розвиток інфраструктури обчислювального світу, сам Сол ніколи всерйоз не використав комп'ютери. Він дуже пишався тим, що може легко проводити обчислення в умі. До 70-ти років він не користувався електронною поштою і ніколи не користувався комп'ютером удома, хоча ось мобільний телефону нього був (звичайний електронної поштивід нього майже не надходило. Я згадав якось, що близько року тому я вивчав історію Ади Лавлейс; він відповів: " Історія Ади Лавлейс як програміста Беббіджа настільки поширена, що всі, здається, приймають її як факт, проте я ніколи не бачив джерел з цього питання.").

Дочки Сола кілька років тому організували вечірку з приводу його 80-річчя та створили такі цікаві запрошення:

У Сола були певні проблеми зі здоров'ям, хоча, здавалося, це не дуже позначається на його ритмі життя. Здоров'я його дружини погіршувалося, і останні кілька тижнів досить різко. У п'ятницю Сол, як завжди, пішов до свого кабінету, а в суботу вночі помер уві сні. Його дружина Бо пережила його всього на два тижні і померла лише за два дні до 60-ї річниці їхнього весілля.

Хоча Сол і пішов, його робота живе в октильйонах біт у цифровому світі.

Прощавай, Сол. І від усіх нас – дякую.

Це цікаво: