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

Date: 2015-10-07; view: 672.

ЛЕКЦІЯ 3 ЛІНІЙНІ РЕКУРЕНТИ НАД GF(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

, , .

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

Звідки і .

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

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

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

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