Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
46
Добавлен:
19.02.2016
Размер:
596.48 Кб
Скачать

Лекція 3 лінійні рекуренти над gf(2)

3.1 Основні властивості лінійних рекурент над gf(2)

У потокових шифрах генератори гами, у більшості випадків, складаються з типових вузлів, основаних на комбінаціях так званих регістрів зсуву і функціях ускладнення.

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

Регістр зсуву зі зворотним зв’язком складається з двох частин: регістра зсуву і функції зворотного зв'язку довільної природи.

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

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

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

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

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

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

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

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

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

Ми пререконаємося далі, що задана рекурентна послідовність може бути породжені регістрами різної довжини та з іншими точками зворотного зв’язку.

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

Безпосередньо для генерації гами РЗЛЗЗ не підходять. На практиці застосовуються комбінації т.зв. залежних РЗЛЗЗ, що взаємно впливають на формування своїх послідовних заповнень.

Послідовність, що генерує РЗЛЗЗ, можна розглядати як послідовну зміну станів регистра: ,. При цьому ці стани перетинаються по елементах, що дозволяє записати їх компактно:.

З іншого боку, можна вважати, що послідовність вже існує і розглядати стани як значення «вікна» - відрізку послідовності зелементів, який просувається вправо на один елемент за крок.

В останньому випадку ми можемо розглядати відрізки довільної довжини.

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

Запишемо матрицю , для якої елементи останнього стовбчиказ номерамидорівнюють одиниці, а решта – нулі.

, ,.

Матриця зворотна і наступний стан регістра має вигляд .

Звідки і .

Зокрема, якщо , то , де рекуренти додаються поелементно.

Від’ємні значення відповідають розгортці рекуренти зправа наліво, тобто коли виходячи зобчислюється елемент.

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

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

Покажемо, що для нашої рекуренти існують інші рекурентні співвідношення.

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

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

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

Якщо - характеристичний многочлен мінімального степеня, то многочлени виду називаються покриваючими многочленами рекурентної послідовності з мінімальним многочленом.

Відповідні рекурентні та перевірочні співвідношення також називаються покриваючими або похідними.

Многочлени і тільки вони задають покриваючі рекурентні співвідношення.

Нехай тепер дано дві рекурентні послідовності з відомими рекурентними співвідношеннями (мінімальними многочленами ,) і початковими станами,.

Який початковий стан та яке рекурентне співвідношення відповідає сумі цих рекурент?

Многочлен НСК є покриваючим мінімального степеня одночасно для кожної з рекурент, таким чином, рекурентне співвідношення для суми рекурент задають його коефіціенти, а довжина (розмірність) дорівнює.

Якщо ми продовжимо іза відповідними рекурентними законами добітів, то отримаємо послідовностіі, з яких отримаємо.

Соседние файлы в папке Конспекти_лекцій