Лекція № 3

Тема: Лінійні рекурентні послідовності над полем

План лекції:

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

2. Лінійна рекурентна послідовність, що генерується РЗЛЗЗ.

3. Запис станів двійкового регістру через супроводжуючу матрицю.

4. Вираз елементів рекуренти через початковий стан.

5. Анулюючі та мінімальні многочлени послідовностей над полем

6. Існування тричленних похідних співвідношень.

7. Знаходження покриваючого співвідношення для лінійної рекуренти методом Гаусса

8. Теорема про лінійну складність комбінуючого генератора.

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

Потоковий шифр — це симетричний шифр, в якому кожен символ відкритого тексту перетворюється в символ шифрованого тексту в залежності не лише від використовуваного ключа, але і від його розташування в потоці відкритого тексту.

Потокові шифри є різновидом шифрів гамування і перетворюють відкритий текст в шифрований послідовно по 1 біту. Потоковий шифр перетворює елемент відкритого тексту залежно від значення гамми (тобто ключа) на кожному такті шифрування.

У криптографічній літературі під потоковим шифром дуже часто розуміють так званий двійковий адитивний потоковий шифр, що є шифром гамування за модулем два з псевдовипадковою гаммою.

Для такого шифру ключовий потік можна записати за допомогою нулів і одиниць і безпосередньо використовувати для гамування відкритого тексту.

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

.

На приймальній стороні шифрований текст додається за модулем 2 з ідентичною ключовою послідовністю для отримання вихідного тексту:

.

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

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

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

Початковий стан регістра називається його початковим заповненням. Вміст комірки називається розрядом (з відповідним номером).

Під час роботи вміст комірок регістру змінюється.

В результаті одного такту роботи регістра генерується один біт. Новий біт обчислюється як функція від бітів, які вибираються з комірок регістра з наперед визначеними номерами. Вказані комірки називаються комірками зворотного зв'язку, а функція – функцією зворотного зв'язку. Номери комірок зворотного зв'язку називаються точками знімання зворотного зв'язку. Значення функції зворотного зв'язку записується в найлівішу комірку регістра, зсуваючи всі інші його біти на одну позицію вправо. Виходом регістра зсуву на даному такті є біт, знятий з фіксованої (звичайно з крайньої правої) комірки.

Мал. 1. Загальний вид регістра зсуву із

зворотним зв’язком довжини , що виробляє гаму

Регістр зсуву генерує рекурентну послідовність виду .

Найбільш простим і найбільш розповсюдженим вузлом є регістр зсуву з лінійним зворотним зв’язком (РЗЛЗЗ, англ. LFSR), що генерує рекурентну послідовність, для якої функція є лінійною формою над полем. Зворотний зв'язок являє собоюXOR деяких бітів регістру.

Мал. 2. Загальний вид регістра зсуву з лінійним

зворотним зв’язком довжини , що виробляє гаму

Далі будемо розглядати тільки двійкові регістр зсуву з лінійним зворотним зв’язком.