зі зворотним зв'язком є ??лінійний зсувний регістр зі зворотним зв'язком (linear feedback shift register, або LFSR) (малюнок 1.2.2). Зворотній зв'язок являє собою просто XOR деяких бітів регістра, перелік цих бітів називається відвідної послідовністю (tap sequence). Іноді такий регістр називається конфігурацією Фіббоначі. Через простоту послідовності зворотного зв'язку для аналізу LFSR можна використовувати досить розвинену математичну теорію. Криптографи люблять аналізувати послідовності, переконуючи себе, що ці послідовності досить випадкові, щоб бути безпечними. LFSR частіше інших зсувних регістрів використовуються в криптографії.
Рис. 1.2.2. Зсувний регістр з лінійною зворотним зв'язком
На Рис. 1.2.3 показаний 4-бітовий LFSR з відведенням від першого і четвертого бітів. Якщо його проініціалізувати значенням 1111, то до повторення регістр буде приймати наступні внутрішні стани:
1. 1 січня
1. 1 січня
0 1 січня
1 0 1
0 1 0
1 0 1
1 1 0
0 1 січня
0 0 1
1 0 0
0 1 0
0 0 1
0 0 0
1 0 0
1 1 0
Рис. 1.2.3. 4-бітовий LFSR
Вихідний послідовністю буде рядок молодших значущих бітів:
1 1 1 0 1 0 1 1 0 0 1 0 0 0 ....
бітовий LFSR може перебувати в одному з 2n - 1 внутрішніх станів. Це означає, що теоретично такий регістр може генерувати псевдовипадкову послідовність з періодом 2n - 1 бітів. (Число внутрішніх станів і період рівні 2n - 1, тому що заповнення LFSR нулями, призведе до того, що зсувний регістр видаватиме нескінченну послідовність нулів, що абсолютно марно.) Тільки за певних відвідних послідовностях LFSR циклічно пройде через усі 2n - 1 внутрішніх станів , такі LFSR є LFSR з максимальним періодом. Одержаний результат називається М-послідовністю.
Для того, щоб конкретний LFSR мав максимальний період, многочлен, утворений з відвідної послідовності і константи 1, повинен бути примітивним по модулю 2. Ступінь многочлена є довжиною зсувного регістру. Примітивний багаточлен ступеня n - це непріводімий многочлен, який є дільником, але не є дільником xd + 1 для всіх d, що є дільниками 2n - 1.
У загальному випадку не існує простого способу генерувати примітивні многочлени даній ступеня по модулю 2. Найпростіше вибирати многочлен випадковим чином і перевіряти, чи не є він примітивним. Це нелегко - і чимось схоже на перевірку, чи не є простим випадково вибране число - але багато математичні пакети програм вміють вирішувати таке завдання.
Деякі, але, звичайно ж, не все, многочлени різних ступенів, примітивні по модулю 2. Наприклад, запис (32, 7, 5, 3, 2, 1, 0) означає, що наступний многочлен примітивний по модулю 2:
+ x7 + x5 + x3 + x2 + x + 1
Це можна легко узагальнити для LFSR з максимальним періодом. Першим числом є довжина LFSR. Останнє число завжди дорівнює 0, і його можна опустити. Всі числа, за винятком 0, задають відвідну послідовність, відлічувану від лівого краю зсувного регістру. Тобто, члени многочлена з меншим ступенем відповідають позиціям ближче до правого краю регістра.
Продовжуючи приклад, запис (32, 7, 5, 3, 2, 1, 0) означає, що для взятого 32-бітового зсувного регістру новий біт новий біт генерується за допомогою XOR тридцять другий, сьомого, п'ятого, третього, другого і першого бітів получающийся LFSR матиме максимальну довжину, циклічно проходячи до повторення через 232-1 значень.
. 2.2 Програмная реалізація LFSR
Програмні реалізації LFSR повільні і швидше працюють, якщо вони написані на асемблері, а не на C. Одним з рішень є використання паралельно 16 LFSR (або 32, залежно від довжини слова вашого комп'ютера). У цій схемі використовується масив слів, розмір якого дорівнює довжині LFSR, а кожен біт слова масиву ставиться до свого LFSR. За умови, що використовуються однакові многочлени зворотного зв'язку, це може дати помітний виграш продуктивності. Взагалі, кращим способом оновлювати зсувні регістри є множення поточного стану на підходящі двійкові матриці.
Схему зворотного зв'язку LFSR можна модифікувати. Добутий генератор НЕ БУДЕ криптографічно більш надійним, але він все ще буде володіти максимальним періодом, і його легше реалізувати програмно. Замість використання для генерації нового крайнього лівого біта бітів відвідної послідовності виконує...
