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

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

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

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

Лекція № 3

План лекції:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

…

Функція зворотного зв’язку

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

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

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

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

…

Функція зворотного зв’язку –

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

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

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Аналіз фінансових інвестицій та їх ефективності.	\|	Лінійна рекурентна послідовність, що генерується РЗЛЗЗ

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.