Информатика и выч. техника \ Основы теории защиты информации

Джерела ключів та вимоги до них, страница 2

· великий розмір ансамблю послідовностей, формованих на одній алгоритмічній основі;

· оптимальність кореляційних функцій в ансамблі;

· збалансованість структури;

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

ЛРР являє собою регістр зсуву зі зворотними зв'язками, об'єднаними за модулем 2. Його структурна схема представлена на рис. 1.

Рисунок 3.1

Чергове значення, яке формуються на виході ЛРР, обчислюється за формулою

де - операція обчислення суми за модулем 2,

- стан j - комірки ЛРР

- коефіцієнт зворотного зв’язку.

При цьому для двійкового ЛРР .

Кожному лінійному рекурентному регістру довжиною n розрядів можна зіставити поліном зворотних зв'язків h(x) із двійковими коефіцієнтами виду

причому обов'язково .

Якщо поліном h(x) – незвідний, то довжина послідовності, яка генерується ЛРР, максимальна і дорівнює

Необхідно враховувати, що в чистому виді лінійні рекурентні послідовності не використовуються через низьку структурну скритність формованих ними послідовностей. Для підвищення структурної скритності використовують:

· комбінування декількох ЛРР;

· нелінійні функції в зворотному зв'язку регістра;

· нелінійну логіку і фільтрацію вмісту регістра.

Приклади незвідних поліномів (триномів)

x²⁰ + x³ + 1	x⁴¹ + x²⁰ + 1
x²⁰ + x⁵ + 1	x⁴¹ + x³ + 1
x³¹ + x³ + 1	x⁵² + x⁷ + 1
x³¹ + x¹³ + 1	x⁵² + x²¹ + 1
Перевірити що поліном незвідний x³ + x¹ + 1	X⁵ + x⁴ + 1 Перевірити що поліном незвідний

Поліном є примітивним, якщо він не зводиться, ділить поліном

(10.7)

і не ділить всі поліноми , де є дільники , де n – степінь полінома .

Властивості ЛРП

1. Максимальна серія із n однакових символів „1” та максимальна серія із n-1 нулів.

2. Всі числа від 1 до з’являються у деякій послідовності один раз(елементи поля на періоді з’являються один раз).

Лінійно-рекурентний регістр забезпечує формування послідовності з наперед відомим періодом . Якщо n= 257 , то .

Твердження 1. Для розкриття закону формування лінійно-рекурентної послідовності необхідно і достатньо перехопити 2n поряд розміщених вірних бітів. Структурну скритність можна обчисли як:

(10.8)

Лінійно-рекурентний регістр має низьку структурну скритність, але забезпечує необхідний гарантований період повторення .

2.9.1 Приклади розв’язку задач

Задача 1.

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

Розв’язок задачі.

Оскільки числа та 127 є прості числа Ейлера і періоди повторень та є також прості числа, то період повторення L послідовності, що формується згідно з ЛРР1 примітивний поліном) та ЛРР2 примітивний поліном)

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

Рисунок 2.22 - Схема формування двійкової послідовності з періодом L

Задача 2.

Визначте закон формування гами скремблювання, якщо відомі відрізки послідовності

Покладемо спочатку, що ці послідовності сформовані лінійним рекурентним регістром m-го порядку з поліномом (для А₁) і, що перехоплено 2m символів. Значить для А₁ m=5.