елік цих бітів називається відвідної послідовністю.
Рисунок 2.5 - Регістр Фібоначчі
бітовий LFSR може знаходитися в одному з внутрішніх станів. Це означає, що теоретично такий регістр може генерувати псевдослучайную послідовність з періодом бітів. Тільки за певних відвідних послідовностях LFSR циклічно пройде через усі внутрішніх станів. Такі LFSR є LFSR з максимальним періодом. Для того, щоб LFSR мав максимальний період, многочлен, утворений від відвідної послідовності і константи 1, повинен бути примітивний за модулем 2. Ступінь многочлена є довжиною зсувного регістру. Примітивний многочлен ступеня - це непріводімий многочлен, який є дільником, але не є дільником для всіх, які є дільниками.
У загальному випадку не існує простого способу генерувати примітивні многочлени даній ступеня за модулем 2. Найпростіше вибирати многочлен випадковим чином і перевіряти, чи не є він примітивним.
Приклади деяких примітивних поліномів наведені в таблиці 2.1.
Таблиця 2.1 - Примітивні поліноми
Довжина пери одаМногочлен22-1 (2, 1, 0) 23-1 (3, 1, 0) 24-1 (4, 1, 0) 25-1 (5, 2, 0) 26-1 (6, 1, 0) 27-1 (7, 1, 0) 28-1 (8, 6, 5, 1, 0) 211-1 (11, 2, 0) 212-1 (12, 7, 4, 3, 0) 213-1 (13, 4, 3, 1, 0) 214-1 (14,12, 11, 1, 0) 216-1 (16, 5, 3,2, 0) 218-1 (18, 7, 0) 220-1 (20,3,0) 221-1 (21,2,0) 222-1 (22,1,0) 223-1 (23,5,0) 224-1 (24, 4, 3, 1, 0) 225-1 (25,3,0) 227-1 (27,8,7,1,0) 230-1 (30,16,15,1, 0) 231-1 (31,3,0) 232-1 (32, 7, 6, 2, 0)
Наприклад, запис (14, 12, 11, 1, 0) означає, що наступний многочлен примітивний за модулем 2:.
Першим числом є довжина LFSR. Останнє число завжди дорівнює 0, і його можна опустити. Всі числа, за винятком 0, задають відвідну послідовність, відлічувану від лівого краю регістра. Продовжуючи приклад, запис (14, 12, 11, 1, 0) означає, що для взятого 32-бітового регістра зсуву новий біт генерується за допомогою XOR чотирнадцятого, дванадцятого, одинадцятого і першого бітів, то результуюча послідовність буде мати максимальний період - вона пройде через значень до того, як почне повторюватися.
Кожен елемент таблиці 2.1 визначає два примітивних полінома, оскільки якщо примітивний, то примітивний і Наприклад, якщо примітивний, то примітивний і, або якщо примітивний, то примітивний і. Математично, якщо примітивний
, (2.6)
, (2.7)
, (2.8)
, (2.9)
Слід зазначити, що всі поліноми зворотного зв'язку, наведені в таблиці 2.1, є Проріджена, тобто мають лише кілька ненульових коефіцієнтів. Зрідженому - це завжди джерело слабкості, що полегшує розтин такого алгоритму генерації. Для криптографічних алгоритмів краще використовувати щільні примітивні многочлени. Генерувати щільні примітивні многочлени по модулю 2 нелегко. У загальному випадку для генерації примітивних многочленів ступеня потрібно знати розкладання на множники числа.
2.4.2 Регістри Галуа
Схему зворотного зв'язку LFSR можна модифікувати. Добутий генератор не буде криптографічно більш надійним, але він все ще буде володіти максимальним періодом, і його легше реалізувати програмно.
Замість використання для генерації нового крайнього лівого біта бітів відвідної послідовності...
