Програмно-апаратні засоби генерації псевдовипадкових послідовностей для підвищення ефективності захисту інформації в ЕОМ та мережах

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

”КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

ПРОГРАМНО-АПАРАТНІ ЗАСОБИ ГЕНЕРАЦІЇ ПСЕВДОВИПАД- КОВИХ ПОСЛІДОВНОСТЕЙ ДЛЯ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЗАХИСТУ ІНФОРМАЦІЇ В МЕРЕЖАХ

Спеціальність 05.13.13 - Обчислювальні машини, системи та мережі

Зохре Карім Заде

Київ 2007

Дисертацією є рукопис.

Робота виконана в Національному технічному університеті України ”Київський політехнічний інститут” на кафедрі обчислювальної техніки.

Науковий керівник - кандидат технічних наук

Марковський Олександр Петрович,

НТУУ ”КПІ”, доцент кафедри обчислювальної техніки

Офіційні опоненти: доктор технічних наук, професор

Романкевич Олексій Михайлович,

НТУУ ”КПІ”, професор кафедри спеціалізованих обчислювальних систем

кандидат технічних наук,

Алішов Надір Ісмаіл-огли,

Інститут кібернетики ім.В.М.Глушкова НАН України, провідний науковий співробітник.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

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

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

Предмет дослідження - способи підвищення функціональної ефективності використання псевдовипадкових двійкових послідовностей для захисту інформації в комп'ютерних системах, а також методи проектування апаратно-програмних засобів генерації послідовностей, що мають покращені характеристики нелінійності.

Основні задачі дослідження у відповідності до поставленої мети полягають у наступному:

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

2. Огляд та аналіз з позицій виявлених критеріїв існуючих програмно-апаратних засобів генерації псевдовипадкових двійкових послідовностей для систем захисту інформації. Виявлення можливостей підвищення ефективності використання псевдовипадкових послідовностей та шляхів вдосконалення програмно-апаратних засобів їх генерації.

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

4. Дослідження способу одержання нелінійних булевих функцій зворотного зв'язку з заданими характеристиками складності і нелінійності шляхом направленого об'єднання кодових кілець. Розробка на цій основі методу проектування n-розрядних зсувних регістрів з нелінійною функцією зворотного зв'язку для формування псевдовипадкових двійкових послідовностей з періодом повторення 2ⁿ та високими характеристиками складності і нелінійності. Створення програмних засобів автоматизації проектування програмно-апаратних засобів генерації псевдовипадкових двійкових послідовностей.

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

6. Комбінаторний аналіз можливостей одержання всіх нелінійних булевих функцій зворотного зв'язку n-розрядного зсувного регістру, які забезпечують формування псевдовипадкових двійкових послідовностей з періодом 2ⁿ. Розробка на цій основі комбінаторного способу одержання нелінійних булевих функцій, який дозволяє формувати всі можливі двійкові послідовності з періодом 2ⁿ з використанням n-розрядного зсувного регістру.

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

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

Наукова новизна одержаних результатів полягає в наступному:

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

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

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

- Розроблено комбінаторний метод одержання нелінійних булевих функцій зворотного зв'язку n-розрядних зсувних регістрів з періодом повторення 2ⁿ, який дозволяє одержувати всі нелінійні булеві функцій зворотного зв'язку вказаного класу.

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

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

Особистий внесок здобувача полягає в теоретичному обґрунтуванні одержаних результатів, експериментальній їх перевірці та дослідженні, а також в створенні програмних продуктів для практичного використання одержаних результатів. У роботах, що написані в співавторстві, автору належать: [1] - комбінаторний аналіз кодових кілець і розробка на його основі методу проектування зсувних регістрів з нелінійною функцією зворотного зв'язку, синтез якої виконується шляхом направленого об'єднання кодових кілець; [2] - розробка методу синтезу нелінійних булевих функцій зворотного зв'язку, реалізація якого має обчислювальну складність O(n²), значно меншу в порівнянні з відомими методами побудови функцій зворотного зв'язку для зсувних n-розрядних регістрів; [3] - розробка методу синтезу генератора нелінійних булевих функцій, що відповідають критерію лавинного ефекту для підвищення ефективності двокаскадної схеми формування псевдовипадкових послідовностей); [4] - дослідження властивостей нелінійних булевих функцій, що використовуються в засобах формування псевдовипадкових двійкових послідовностей, метод синтезу систем функцій, використання яких дозволяє підвищити ефективність захисту інформації; [6] - дослідження впливу нелінійності функції зворотного зв'язку схем формування псевдовипадкових послідовностей на ефективність їх використання для захисту інформації.

Апробація результатів дисертації. Основні результати дисертації доповідались та обговорювались на:

1. ХХVII Міжнародній науково-технічній конференції ”Проблеми електроніки”, 17-19 квітня 2007 р., м. Київ.

2. VIIІ Міжнародній науково-практичній конференції ”Современные информационные и электронные технологии”, 22-26 травня 2007 р., м..Одеса.

3. VIII Міжнародній науково-технічній конференції студентів, аспірантів та молодих вчених ”Системний аналіз та інформаційні технології”, 13-16 вересня 2006 р., м. Київ.

4. VI Міжнародній науково-практичній конференції ”Проблеми впровадження інформаційних технологій в економіці”, 31травня-1 червня 2007.-м.Ірпінь.

Публікації Основні результати роботи викладені в 6 публікаціях, з них 4 статті в провідних фахових виданнях.

Структура та об'єм роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків та додатків. Загальний обсяг роботи складає 148 сторінки, робота містить 12 малюнків, 7 таблиць та список використаної літератури на 96 найменувань, 2 додатки.

ОСНОВНИЙ ЗМІСТ

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

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

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

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

Переважна більшість засобів генерації псевдовипадкових двійкових послідовностей для систем захисту інформації побудована з використанням зсувних регістрів з лінійною функцією зворотного зв'язку (Linear feedback shift register - LFSR), які забезпечують просту та ефективну апаратну реалізацію, а також цикл повторення 2ⁿ-1 (n- розрядність зсувного регістру) за умови відповідності функції зворотного зв'язку простому поліному на полях Галуа. При цьому кількість N_L(n) простих поліномів на полях Галуа, а відповідно і функцій зворотного зв'язку, визначається формулою:

,

де (2ⁿ-1)- число Ейлера - кількість позитивних цілих чисел, включаючи 1, менших за 2ⁿ-1 і таких, що не мають загального подільника з 2ⁿ-1.

Самі по собі генератори на зсувних регістрах з лінійною функцією зворотного зв'язку не забезпечують умови складності екстраполяції, оскільки їх функціонування описується лінійними функціями. Тобто, маючи 2•n бітів послідовності можна, шляхом розв'язання системи з 2•n лінійних булевих рівнянь, однозначно визначити початковий n-розрядний код на зсувному регістрі та лінійну функцію зворотного зв'язку.

Виходячи з цього, реальні генератори псевдовипадкових послідовностей, які орієнтовані на використання в системах захисту інформації, мають більш складну структуру, обов'язковим елементом яких є нелінійні булеві перетворювачі. Найбільшого поширення в системах захисту інформації здобула двокаскадна схема генератора, що представлена на рис.1. Перший каскад схеми утворюють h LFSR, розрядність яких збільшується на одиницю, а другий -нелінійний перетворювач, що реалізує нелінійну булеву функцію від h змінних. Характеристики послідовності, що генерується такою схемою залежать від нелінійності та диференційних параметрів функції. Недоліком схеми є складність, відносно низький темп генерації, потреба в спеціальних засобах синтезу функції.

Значно більша ефективність генерації псевдовипадкових послідовностей може бути досягнута при використанні для цього зсувного n-розрядного регістра з нелінійною функцією зворотного зв'язку (Nonlinear feedback shift register -NFSR), яка забезпечує максимальний період повторення - 2ⁿ (рис.2).

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

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

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

Поточний стан n розрядів зсувного регістру характеризується двійковим вектором X_w , якому може бути співставлено двійкове число w:

Через X_w позначимо двійковий вектор, який утворюється n-1 молодшими розрядами X_w : .

При зсуві регістру його молодшому розряду присвоюється значення функції зворотного зв'язку f(x₁,x₂,…,x_n):

Необхідна умова генерації двійкової послідовності з максимальним циклом повторення - 2ⁿ має наступний вигляд:

(1)

Якщо функція f(x₁,x₂,…,x_n) зворотного зв'язку задовольняє умові (1), то кожному коду v на зсувному регістрі передує лише один код w.

З урахуванням (1) функцію f(x₁,x₂,…,x_n) зворотного зв'язку можна представити у такому вигляді:

Кільцем R називається множина кодів, які послідовно формуються на зсувному регістрі з функцією зворотного зв'язку f(x₁,x₂,…,x_n)=x_n. Кожний з 2ⁿ можливих n-розрядних кодів входить до одного з кілець.

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

Задачею такого дослідження є визначення залежності кількості кодових кілець від кількості одиниць, що містять їх коди. Через довжину кодового кільця позначимо кількість кодів, що його утворюють. Нехай _n-множина t_n подільників n: . Тоді будуть існувати: кодові кільця, що включають l_n кодів, кільця, що включають n кодів, а також два кільця, що включають один код (складається з нулів або одиниць).

Дійсно, нехай число n ділиться на d. Тоді існують n-розрядні коди, які утворюються як конкатенація n/d ідентичних d-розрядних фрагментів. Цілком очевидно, що після d циклічних зсувів буде мати місце повторення початкового коду. Кількість таких кодів визначається кількістю можливих d-розрядних фрагментів 2^d. Таким чином, для того, щоб визначити кількість NС(n) двійкових кодів, що входять до кілець довжиною n, необхідно від загальної кількості 2ⁿ можливих n-розрядних кодів відняти число кодів, які при циклічному зсуві утворюють кільця, довжина яких менша за n. В свою чергу, кільце довжиною d може включати в собі цикли меншої довжини t<d, за умови, що t є подільником d. З урахуванням цього, кількість NС(n) двійкових кодів, що входять до кілець довжиною n визначається наступною рекурентною формулою:

,

де (n,d)=1, якщо d є подільником n, в противному випадку (n,d)=0, а NC(2)=2.

Відповідно, кількість NR(n) кілець довжиною n, що утворюються при циклічному зсуві n-розрядного коду визначається рекурентним виразом:

,

причому NR(2)=1.

Загальна кількість NS(n) кодових кілець різної довжини, що можуть бути утворені шляхом циклічного зсуву n-розрядного коду визначається формулою:

В таблиці 1 наведені значення комбінаторних характеристик кілець, які обчислені за одержаними формулами для деяких значень n.

Таблиця 1.

Комбінаторні характеристики кодових кілець

Розрядність коду (n)	Кількість NR(n) кілець довжиною n	Кількість NC(n) кодів, що входять до n-кодових кілець.	Загальна кількість NS(n) кілець
3	2	6	4
4	3	12	6
5	6	30	8
6	9	54	14
7	18	126	20
8	30	240	36
9	56	504	60
10	99	990	108
11	186	2046	188
12	335	4020	352

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

Кількість NR(n,k), які складаються з n кодів, кожен з яких містить точно k одиниць, може бути обчислена як частка від ділення кількості кодів NC(n,k), що входять до таких кілець, на n. Числове значення NC(n,k), в свою чергу, визначається різницею числа всіх можливих n-розрядних кодів, що містять в точності k одиниць і числа кодів, які входять в кільця довжиною d (d - подільник n), та складаються з n/d повторюємих d-розрядних фрагментів, кожен з яких має в точності kd/n одиниць. З урахуванням цього, значення NR(n,k) визначається наступною рекурентною формулою:

(2)

причому NR(2,1)=1.

Загальна кількість NS(n,k) кілець, коди яких містять в точності k одиниць, визначається як сума кількості всіх циклів довжиною меншою або рівною n:

Очевидно, що:

В третьому розділі роботи досліджуються методи проектування апаратно-програмних засобів генерації псевдовипадкових двійкових послідовностей на базі зсувного регістру з нелінійною функцією зворотного зв'язку. Для таких генераторів основною проблемою проектування є синтез нелінійної булевої функції зворотного зв'язку, яка забезпечує максимальний період повторення коду- 2ⁿ на n-розрядному зсувному регістрі.

Частковим кільцем GR ,будемо називати підмножину кодів кільця R, старший розряд яких дорівнює одиниці: . Через позначимо множину всіх часткових кілець, коди якіх містять в точності u одиниць, де NR(n,k) - кількість кілець, які містять в точності k одиниць для зсувного регістру розрядністю n.

Пропонується метод синтезу нелінійної булевої функції зворотного зв'язку, яка забезпечує період 2ⁿ для зсувного регістру. В основі методу лежить процедура, що складається з наступної послідовності дій:

1. Для всіх k{1,…,n} формуються множини Q_k .

2. На всіх 2^n-1 наборах значень n-1 двійкових змінних x₁,x₂,…,x_n-1 встановлюється нульове значення функції (x₁,,x_n-1).

3. Встановлюється k = 1

4. Встановлюється j = 1

5. З часткового кільця вибирається набір . На наборі X_w встановлюється одиничне значення функції (x₁,…,x_n-1): (X_w)=1.

6. j = j+1. Якщо j RN(n,k), то повернення на п.5.

7. k = k+1. Якщо k n, то повернення на п.4.

Наприклад, потрібно синтезувати нелінійну булеву функцію зворотного зв'язку для 5-розрядного зсувного регістру (n=5).

Множини часткових кілець формуються у вигляді:

,

,,

, ,

При k=1 згідно (2) RN(5,1)=1, тобто існує лише одне часткове кільце , що включає єдиний набір X_w={10000}. Відповідно X_w={0000} і (0000)=1.

При k=2 згідно (2) існує два часткових кільця: . При j=1 з - довільно вибирається набір X_w={10010}; X_w={0010} і (0010)=1. При j=2 з - довільно вибирається набір X_w={11000}: X_w={1000} и та (1000)=1.

При k=3 існує два часткових кільця: . З , що містить три набори, довільно вибирається набір X_w={11010}: X_w={1010} та (1010)=1. З множини довільно вибирається набір X_w={11100}: X_w={1100} і (1100)=1.

При k=4 існує лише одне часткове кільце , яке включає 4 набори. Довільним чином з них вибирається, наприклад, набір X_w={11101}. Відповідно, X_w={1101} та (1101)=1.

При k=5 існує лише одне часткове кільце : X_w={11111} і (1111)=1.

Таблиця істинності отриманої функції (х₁,х₂,х₃,х₄) наведена в таблиці 2.

Таблиця 2.

Значення (х₁,х₂,х₃,х₄)

X	(X)	X	(X)	X	(X)	X	(X)
0 0 0 0	1	0 1 0 0	0	1 0 0 0	1	1 1 0 0	1
0 0 0 1	0	0 1 0 1	0	1 0 0 1	0	1 1 0 1	0
0 0 1 0	1	0 1 1 0	0	1 0 1 0	1	1 1 1 0	1
0 0 1 1	0	0 1 1 1	0	1 0 1 1	0	1 1 1 1	1

В АНФ (х₁,х₂,х₃,х₄) = 1 х₁ х₃ х₁х₃ х₃х₄ х₂х₃х₄ х₁х₂х₃х₄.

Покажемо, що запропонована базова процедура методу є конструктивною. Операція установки в одиницю значення функції (х₁,х₂,…,х_n-1) може бути співставлень з об'єднанням кільця, що містить код X_i={x₁,x₂,…,x_n-1,x_n=1} та кільця, що включає код X_j={x₁,x₂,…,x_n-1,x_n=0}, де i{1,…,NR(n,k)}, j{1,…,NR(n,k-1)}. В силу того, що метод передбачає вибір одного коду Х з усіх кілець, кожне кільце виявляється пов'язаним мінімум з одним із кілець, коди яких містять на одиницю меншу кількість одиниць. Таким чином, всі кільця виявляються пов'язаними в одне кільце, яке містить всі 2ⁿ n-розрядні коді, що забезпечує максимальний період повторення коду на зсувному регістрі.

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

Суттєвою вадою розробленого методу синтезу нелінійних функцій зворотного зв'язку для NFSR є значні затрати обчислювальних ресурсів на його реалізацію. Це не дозволяє використовувати його для проектування NFSR великої розрядності, зокрема при n=72, що передбачено рядом стандартів систем бездротової передачі цифрової інформації. Значна обчислювальна складність є характерною і для відомих методів проектування NFSR.

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

Позначимо через ? множину всіх NS(n) кілець: . Відповідно, множина ={min(R₁),min(R₂),…,min(R_NS(n))} є множиною кодів, яким співставляються мінімальні числа в кільцях.

Для того щоб період повторення NFSR становив 2ⁿ, значення функції (Х) на кодах, що складають множину , має дорівнюватися одиниці.

Пропонується формувати функцію зворотного зв'язку у вигляді:

,

де - вектор, що утворюється зсувом коду Х на один розряд вправо з заповненням молодшого розряду одиницею, а (Y)- булева функція, що приймає нульове значення, якщо Y відповідає мінімальному коду кільця, та одиничне значення на всіх інших наборах.

Покажемо, що функція (Y) може бути сформована у вигляді диз'юнкції всіх термів t_ij, i,j{1,…,n-1}:

, (3)

причому самі терми t_ij визначаються за наступним виразом:

. (4)

Набір Y не може співвідноситися до мінімального числа в кільці, якщо він містить хоча б одну послідовність з і бітів, що закінчується j-тим бітом коду Y виду: , таку, що W_i(S_j)<W_i(S₀), де S₀ - послідовність і старших розрядів набору Y: . Зокрема, набору Y не відповідає мінімальне число в кільці, якщо послідовності S_j та S₀ відрізняються лише молодшим бітом: для послідовності S_j він дорівнює нулю, а для S₀ - одиниці. Фактично кожний з термів t_ij являє собою логічний вираз (4), що дорівнює одиниці, якщо виконується умова:

Таким чином, доведено, що функція (Y), сформована у вигляді (3,4), приймає нульове значення лише на кодах, що відповідають мінімальному числу кодового кільця.

Метод синтезу функції (Y) полягає в тому, що в ДНФ визначаються всі (n-1)² терми t_ij, а ДНФ функції (Y) формується як диз'юнкція визначених ДНФ термів. Одержана в результаті ДНФ функції (Y) може бути прямо використана для синтезу відповідної електронної схеми. Зокрема, при реалізації схеми NFSR на матрицях FPGA введення одержаної ДНФ функції (Y) може реалізований засобами VHDL.

Обчислювальна складність формування функції (Y) в ДНФ є еквівалентною складності самої функції.

Для обчислення значення одного терму t_ij згідно з (4) необхідно виконати і операцій порівняння та і-1 логічних операцій AND для об'єднання результатів порівнянь; тобто всього 2(і-1) операцій. Загальна кількість операцій для обчислення всіх термів t_ij складає:

Ще (n-2)² логічних операцій OR потрібно виконати для диз'юнктивного об'єднання (3) значень термів. Таким чином, для формування в ДНФ функції (Y) потрібно виконати операцій, Це означає, що обчислювальна складність реалізації процесу синтезу складає O(n³).

Цілком очевидним є те, що обчислення термів t_ij за формулою (4) є надлишковими, оскільки при попарному порівнянні компонентів послідовностей S₀ та S_j довжиною i > 2 операції порівняння для перших і-2 пар уже виконувалися при обчисленні терму t_(i-1)j. Виходячи з цього, більш ефективним є обчислення терму t_ij за формулою:

(5)

Значення q_ij обчислюється за рекурентною формулою:

, (6)

причому для і=2 q_ij =1.

Кількість операцій для обчислення термів t_ij за формулами (5,6) складає . Це значить, що обчислювальна складність реалізації синтезу ДНФ функції зворотного зв'язку складає O(n²).

При формуванні функції (Y) за запропонованим методом потрібно зберігати в пам'яті значення всіх термів t_ij для всіх i{1…n-1} та j{1…n-1}. Таким чином, затрати пам'яті для реалізації запропонованого методу синтезу функцій зворотного зв'язку також пропорційні n².

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

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

Сутність методу синтеза функції-генератора g(x₁,x₂,…,x_n+h) функцій від n змінних, переналагоджуваного по значенням h керуючих бітів, полягає в виконанні наступної послідовності дій:

1. Множина ={x₁,x₂,…,x_n+h} n+h змінних, на яких визначена функція g(x₁,x₂,…,x_n+h) розділяється на п'ять непересічних підмножин: ₁, Q_1, , _2, Q₂: ₁ Q_{1 2} Q₂ =, причому ₁, , ₂ і ( Q₁ Q₂) h, де -кількість елементів множини.

2. Формуються три булеві функції B₀, B₁ та B₂ наступним чином:

,

де U(Q₁Q₂), S(Q₂), R(Q₁) - булеві функції, визначені на змінних відповідних множин. Ці функції вибираються довільним чином.

3. Результат - нелінійна булева функція g(x₁,…,x_n+h), що задовольняє лавинному критерію формується у вигляді:

Доведено, що при будь-яких значеннях управляючих змінних функція g трансформується в функцію f(x₁,…,x_n) з нелінійністю N(f) =2^n-1-2^n/2. Високе значення нелінійності зумовлює неефективність використання для екстраполяції послідовності лінійні відтворюючі моделі. Показано, що функція f(x₁,…,x_n) відповідає критерію лавинного ефекту, що зумовлює неефективність використання для екстраполяції диференційних моделей. Таки чином, запропоноване вдосконалення двокаскадної схеми генератора двійкових послідовностей забезпечує за рахунок поліпшення характеристик останніх, підвищення ефективності їх використання для захисту інформації.

ВИСНОВКИ

В дисертаційній роботі, відповідно до поставленої мети, виконано теоретичне обґрунтування і одержано нове вирішення наукової задачі: підвищення ефективності захисту інформації в комп'ютерних системах та мережах з використанням псевдовипадкових двійкових послідовностей за рахунок поліпшення їх характеристик шляхом вдосконалення програмно-апаратних засобів їх генерації.

Основні наукові і практичні результати полягають у наступному:

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

2. Модифіковано метод проектування n-розрядних зсувних регістрів з нелінійною функцією зворотного зв'язку для формування псевдовипадкових двійкових послідовностей з періодом повторення 2ⁿ. Відмінністю методу є застосування для одержання функції направленого об'єднання кодових кілець виходячи з заданих характеристик її складності і нелінійності, що забезпечує високу ефективність використання двійкових послідовностей, які сформовані такими схемами, для захисту інформації.

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

4. Запропоновано комбінаторний метод формування нелінійних булевих функцій зворотного зв'язку n-розрядного зсувного регістру, які забезпечують формування псевдовипадкових двійкових послідовностей з періодом 2ⁿ. Відмінністю методу є те, що він дозволяє одержувати всі нелінійні булеві функцій зворотного зв'язку вказаного класу, що, з одного боку відкриває можливості оптимізації засобів генерації послідовностей, а з другого - утруднює підбір функцій зворотного зв'язку при спробах порушення захисту інформації.

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Самофалов К.Г., Марковский А.П., Зохре Карим Заде Сейфоллах. Метод синтеза нелинейной функции обратной связи для сдвигового регистра с максимальным периодом повторения // Проблеми інформатизації та управління. Збірник наукових праць: К.,НАУ.- 2006.- Випуск 2(17).- С.105-111. (Автором виконано комбінаторний аналіз кодових кілець і розроблено на його основі метод проектування зсувних регістрів з нелінійною функцією зворотного зв'язку, синтез якої виконується шляхом направленого об'єднання кодових кілець).

2. Марковський О.П., Зохре Карім Заде Сейфолах, Гурін В.Є. Ефективний метод побудови нелінійних генераторів для телекомунікаційних систем //Электроника и связь. Тематический выпуск ”Проблемы электроники” ч.3. - ПЦ ”Аверс” - 2007.- С.87-89. (Автору належить розробка методу синтезу нелінійних булевих функцій зворотного зв'язку, реалізація якого має обчислювальну складність O(n²), значно меншу в порівнянні з відомими методами побудови функцій зворотного зв'язку для зсувних n-розрядних регістрів).

3. Орлова М.Н., Аль-Хавальди Али, Зохре Карим Заде. Метод синтеза управляемых генераторов балансных SAC-функций // Вісник Національного технічного університету України ”KПI” Інформатика, управління та обчислювальна техніка. К.: „ВЕК+”.- 2004. - № 41.- С.155-164. (Автором запропоновано метод синтезу генератора нелінійних булевих функцій, що відповідають критерію лавинного ефекту для підвищення ефективності двокаскадної схеми формування псевдо випадкових послідовностей)

4. Марковский А.П., Зохре Карим Заде Сейфоллах, Троян О.С. Метод синтеза ортогональных систем булевых SAC-функций // Вісник Національного технічного університету України ”KПI”. Інформатика, управління та обчислювальна техніка. К.: „ВЕК+”.- 2005 - № 43.- С.21-31. (Автором досліджено властивості нелінійних булевих функцій, що використовуються в засобах формування псевдовипадкових двійкових послідовностей, запропоновано метод синтезу систем функцій, використання яких дозволяє підвищити ефективність захисту інформації).

5. Зохре Карим Заде Сейфоллах. К проблеме оценки качества случайных и псевдослучайных двоичных последовательностей.// Матеріали VII Міжнародної науково-технічної конференції ”Системний аналіз та інформаційні технології” ( 13-16 вересня 2006 р., м.Київ). К.: НТУУ ”КПІ”.-2006.-С.171-174. (Автором виконано аналіз ефективності використання псевдовипадкових послідовностей в системах захисту інформації, обґрунтовано використання комбінаторного підходу для одержання всіх функцій зворотного зв'язку, що забезпечують максимальний період повторення коду на зсувному регістрі).

6. Марковский А.П., Зохре Карим Заде Сейфоллах, Яцишина О.О. Оценка сложности двоичных последовательностей с использованием нелинейных моделей // Труды 8-й международной научно-технической конференции ”Современные информационные и электронные технологии” (21-25 травня 2007 р., м. Одеса). Одеса: ОНТУ.-2007. - С.194. (Автором досліджено вплив нелінійності функції зворотного зв'язку схем формування псевдовипадкових послідовностей на ефективність їх використання для захисту інформації).

АНОТАЦІЇ

Зохре Карім Заде. Програмно-апаратні засоби генерації псевдо випадкових послідовностей для підвищення ефективності захисту інформації в ЕОМ та мережах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 - Обчислювальні машини, системи та мережі. - Національний технічний університет України ”Київський політехнічний інститут”, Київ, 2007.

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

Основна увага приділена розробці методів проектування зсувних регістрів з нелінійною функцією зворотного зв'язку, яка забезпечує період повторення 2ⁿ для n-розрядного регістру. Проведено теоретичне дослідження властивостей таких функцій. Базовою концепцією методу побудови нелінійних функцій зворотного зв'язку, що забезпечують період повторення 2ⁿ для n-розрядного зсувного регістру є направлене об'єднання кодових кілець - множин n-розрядних кодів, які утворюються при циклічному зсуві.

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

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

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

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

Зохре Карим Заде. Программно-аппаратные средства генерации псевдослучайных последовательностей для повышения эффективности защиты информации в ЭВМ и сетях. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - Вычислительные машины, системы и сети.- Национальный технический университет Украины ”Киевский политехнический институт”, Киев, 2007.

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

Исследованы факторы, влияющие на эффективность применения псевдослучайных двоичных последовательностей для защиты информации в компьютерных системах и сетях. Доказано, что наибольшее значение имеет невозможность экстраполяции последовательности при попытках нарушения защиты данных. Возможность экстраполяции двоичной последовательности определяется нелинейными преобразованиями, выполняемыми в процессе ее формирования.

Основное внимание в диссертации уделено разработке методов проектирования сдвиговых регистров с нелинейной булевой функцией обратной связи, которая обеспечивает период повторения 2ⁿ для n-разрядного регистра. Такие схемы выгодно отличаются от широко используемых сдвиговых регистров с линейной функцией обратной связи тем, что экстраполяция фрагмента последовательности не может быть сведена к решению систем линейных уравнений. Использование сдвиговых регистров с нелинейных функций обратной связи позволяет обойтись без многокаскадных схем генерации псевдослучайных последовательностей и, тем самым, упростить аппаратную реализацию.

В работе выполнено теоретическое исследование свойств таких функций, на основе которого предложены новые эффективные методы проектирования генераторов этого класса. Базовой концепцией получения нелинейных булевых функций обратной связи, обеспечивающих период 2ⁿ повторения кода для n-разрядного сдвигового регистра, является направленное объединение кодовых колец - множеств n-разрядных кодов, образованных циклическим сдвигом. В диссертации произведен комбинаторный анализ кодовых колец, в результате которого получены аналитические оценки, использованные для синтеза функций обратной связи.

Разработан метод синтеза нелинейной обратной связи, обеспечивающей максимальный период повторения кода сдвигового регистра, на основе направленного объединения колец исходя из заданных требований к сложности и нелинейности функции. Разработанный метод иллюстрируется примером построения нелинейной функции обратной связи для сдвигового регистра. Выполнен анализ числа функций указанного класса, которые могут быть синтезированы предложенным методом. Доказано, что метод позволяет получать на порядок больше таких функций по сравнению с известными методами.

Разработана модификация предложенного метода, которая использует для представления функции обратной связи в процессе ее синтеза алгебраическую форму. За счет этого, а также за счет уменьшения количества синтезируемых функций существенно уменьшить вычислительную сложность процесса синтеза. Проведенные теоретические исследования показали, что, в отличие от известных методов, вычислительная сложность которых O(2ⁿ), предлагаемая модификация требует для своей реализации существенно меньших ресурсов: ее вычислительная сложность - O(n²). Это позволяет синтезировать нелинейные функции обратной связи для сдвиговых регистров большой разрядности, используемых в системах беспроводной передачи цифровых данных. Построенные предложенным методом генераторы обеспечивают высокий темп генерации последовательности и эффективную аппаратную реализацию.