ться XOR кожного біта відвідної послідовності з виходом генератора і заміна його результатом цієї дії, потім результат генератора стає новим крайнім лівим бітом. Іноді цю модифікацію називають конфігурацією Галуа.
. 2.3 Лінійна складність
Аналізувати потокові шифри часто простіше, ніж блокові. Наприклад, важливим параметром, використовуваним для аналізу генераторів на базі LFSR, є лінійна складність (linear complexity), або лінійний інтервал. Вона визначається як довжина n самого короткого LFSR, який може імітувати вихід генератора. Будь-яка послідовність, генерована кінцевим автоматом над кінцевим полем, має кінцеву лінійну складність. Лінійна складність важлива, тому що за допомогою простого алгоритму, званого алгоритмом Berlekamp-Massey, можна визначити цей LFSR, перевіривши тільки 2n бітів потоку ключів. Відтворюючи потрібний LFSR, ви Зламуй потоковий шифр.
Ця ідея можна розширити з полів на кільця і ??на випадки, коли вихідна послідовність розглядається як числа в полі непарній характеристики. Подальше розширення призводить до введення поняття профілю лінійної складності, який визначає лінійну складність послідовності по мірі її подовження. Інший алгоритм обчислення лінійної складності простий тільки в дуже специфічних умовах. Узагальнення поняття лінійної складності виконано в. Існує також поняття сферичної і квадратичної складності.
У будь-якому випадку пам'ятайте, що висока лінійна складність не обов'язково гарантує безпеку генератора, але низька лінійна складність вказує на недостатню безпеку генератора.
. 2.4 Кореляційна незалежність
криптографії намагаються отримати високу лінійну складність, нелінійно об'єднуючи результати деяких вихідних послідовностей. При цьому небезпека полягає в тому, що одна або декілька внутрішніх вихідних послідовностей - часто просто виходи окремих LFSR - можуть бути пов'язані спільним ключовим потоком і розкриті за допомогою лінійної алгебри. Часто таке розтин називають кореляційним розкриттям або розкриттям розділяй-і-володарюй. Томас Сігенталер (Thomas Siegenthaler) показав, що можна точно визначити кореляційну незалежність , і що існує компроміс між кореляційної незалежністю і лінійної складністю.
Основною ідеєю кореляційного розтину є виявлення деякої кореляції між виходом генератора і виходом однієї з його складових частин. Тоді, спостерігаючи вихідну послідовність, можна отримати інформацію про це проміжному виході. Використовуючи цю інформацію та інші кореляції, можна збирати дані про інших проміжних виходах до тих пір, поки генератор НЕ буде зламаний.
Проти багатьох генераторів потоків ключів на базі LFSR успішно використовувалися кореляційні розтину і їх варіації, такі як швидкі кореляційні розтину, що пропонують компроміс між обчислювальною складністю та ефективністю.
. 2.5 Потокові шифри на базі LFSR
Основний підхід при проектуванні генератора потоку ключів на базі LFSR простий. Спочатку береться один або кілька LFSR, зазвичай з різними довжинами і різними многочленами зворотного зв'язку. (Якщо довжини взаємно прості, а всі многочлени зворотного зв'язку примітивні, то у утвореного генератора буде максимальна довжина.) Ключ є початковим станом регістрів LFSR. Кожен раз, коли необхідний новий біт, посуньте на біт регістри LFSR (це іноді називають тактуванням (clocking)). Біт виходу являє собою функцію, бажано нелінійну, деяких бітів регістрів LFSR. Ця функція називається комбинирующей функцією, а генератор в цілому - комбінаційним генератором. (Якщо біт виходу є функцією єдиного LFSR, то генератор називається фільтруючим генератором.) Велика частина теорії подібного роду пристроїв розроблена Селмер (Selmer) і Нілом Цірлером (Neal Zierler).
Можна ввести ряд ускладнень. У деяких генераторах для різних LFSR використовується різна тактова частота, іноді частота одного генератора залежить від виходу іншого. Все це електронні версії ідей шифрувальних машин, що з'явилися до Другої світової війни, які називаються генераторами з управлінням тактовою частотою (clock-controlled genelators). Управління тактовою частотою може бути з прямим зв'язком, коли вихід одного LFSR управляє тактовою частотою іншого LFSR, або зі зворотним зв'язком, коли вихід одного LFSR управляє його власної тактовою частотою.
Хоча всі ці генератори чутливі, принаймні теоретично, до розтинам вкладенням і вірогідною кореляцією, багато з них безпечні досі. Додаткову теорію зсувних регістрів з керованою тактовою частотою можна знайти в.
Ян Касселлс (Ian Cassells), який раніше очолював кафедру чистої математики в Кембриджі і працював криптоаналітиків в Bletchly Park, сказав, щ...
