• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

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

Лекція № 3

План лекції:

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

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

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

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

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

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

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

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

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

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

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

.

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. В. Друга теорема про розклад.
2. Друга теорема Вейєрштрасса
3. Зварювального генератора.
4. Інтегральна теорема Лапласа
5. Локальна теорема Лапласа
6. Магнітний потік. Теорема Гауса для магнітного поля
7. Момент інерції. Теорема Гюйгенса-Штейнера
8. Напряженность поля. Теорема Гаусса
9. Незалежні події. Теорема множення для незалежних подій
10. Опукле програмування. Необхідні та достатні умови існування сідлової точки. Теорема Куна-Такера.
11. Основна теорема арифметики цілих невід’ємних чисел.
12. ОСНОВНІ ВІДОМОСТІ ПРО ЛІНІЙНУ ПЕРСПЕКТИВУ

Переглядів: 941