Лінійний регістр зсуву приклад. Регістри зсуву із зворотним зв'язком. Приклади генераторів на Рослос

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

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

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

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

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

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

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

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

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

Не дивно, що він цього не зміг зробити. Вже 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-ї річниці їхнього весілля.

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

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

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

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

Для РСЛОС функція зворотний зв'язок є лінійної булевої функцією від станів всіх чи деяких бітів регістру. Наприклад, сума за модулем два або її логічна інверсія є лінійною булевою функцією (операція 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), але зміщені по фазі одна від іншої
цикл із фіксованого числа викликів функції LFSR у конфігурації Галуа виконується приблизно вдвічі швидше, ніж у конфігурації Фібоначчі (компілятор MS VS 2010 Intel Core i5)
Зверніть увагу, що в конфігурації Галуа порядок біт у слові, що визначає зворотний зв'язок, зворотний у порівнянні з конфігурацією Фібоначчі

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

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

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

Цей генератор використовує виведення одного РСЛОС для управління тактовою частотою іншого РСЛОС. Тактовий вихід РСЛОС-2 управляється виходом РСЛОС-1, так що РСЛОС-2 може змінювати свій стан у момент часу t, тільки якщо вихід РСДОС-1 в момент часу t-1 дорівнював одиниці. Але ця схема не встояла перед кореляційним розтином.

Тому було запропоновано покращений генератор, заснований на цій самій ідеї. Його називають генератор «стоп-пішов», що чергується. У ньому використовуються три РСЛОС різної довжини. РСЛОС-2 тактується, коли вихід РСЛОС-1 дорівнює одиниці, а РСЛОС-3, коли вихід РСЛОС-1 дорівнює нулю. Виходом генератора є сума за модулем 2 РСЛОС-2 та РСЛОС-3. Даний генератор має великий період і велику лінійну складність. Його автори показали також спосіб кореляційного розтину РСЛОС-1 але це не сильно послаблює генератор.

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

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

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

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

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

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

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

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

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

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

Інші види

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

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

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

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

При цьому ті біти, які є змінними функціями зворотного зв'язку, прийнято називати відведеннями.

Протягом кожного такту часу виконуються такі операції:

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

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

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

Властивості

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

Лінійна складність бінарної послідовності - одна з найважливіших характеристик роботи РСЛОС. Введемо такі позначення:

Визначення

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

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

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

приклад

Номер кроку	Стан	Генерований біт
0		-
1		1
2		1
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); return S&1; )

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

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

Int LFSR (void) (static unsigned long Q = 1; Q = (Q>> 1) ^ (Q&1?0x80000057:0); return Q&1;)

Виграш полягає в тому, що всі XOR виконуються за одну операцію.

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

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

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

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

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

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

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

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

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

Інші види

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

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

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

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

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

Рис 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

Важливим параметром генератора на базі РСЛОС є лінійна складність. Вона визначається як довжина nнайкоротшого РСЛОС, який може імітувати вихід генератора. Лінійна складність важлива, оскільки за допомогою простого алгоритму Берленкемп-Мессіможна відтворити такий РСЛОС, перевіривши всього 2 nбітів гами. З визначенням необхідного РСЛОС потоковий шифр практично зламується.

Крім РСЛОС застосовуються і регістри зсуву з нелінійним зворотним зв'язком, зворотним зв'язком по переносу та ін.

Ряд генераторів розроблений на основі теоретико-числового підходу (генератори Блюма-Мікалі, RSA, BBS, стискаючі, адитивні генератори та ін.).

Математичне забезпечення синтезу потокових криптографічних алгоритмів розроблено повніше і докладніше порівняно з блочними криптоалгоритмами. Тим не менш, для створення потокових шифрів часто використовують блокові криптоалгоритми в режимах OFB або CFB.