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

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

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

( Іран )

УДК 004.056.5

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

ЗАХИСТУ ІНФОРМАЦІЇ В ЕОМ ТА МЕРЕЖАХ

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

АВТОРЕФЕРАТ

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

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

Київ 2007

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

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

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

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

НТУУ ”КПІ”, доцент кафедри

обчислювальної техніки

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

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

НТУУ ”КПІ”, професор кафедри

спеціалізованих обчислювальних систем

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

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

Інститут кібернетики ім.В.М.Глушкова НАН

України, провідний науковий співробітник.

Захист відбудеться 22 жовтня 2007 р. о 16-00 годині на засіданні спеціалізованої ради Д 26.002.02 у НТУУ ”КПІ” (м. Київ, проспект Перемоги 37, корп.18,ауд.306)

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

Відзиви на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати на адресу: 03056, м. Київ, проспект Перемоги 37, вченому секретарю НТУУ ”КПІ”.

Автореферат розісланий 21 вересня 2007 р.

Вчений секретар

спеціалізованої вченої ради Д 26.002.02 Орлова М.М.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особистий внесок здобувача полягає в теоретичному обґрунтуванні одержаних результатів, експериментальній їх перевірці та дослідженні, а також в створенні програмних продуктів для практичного використання одержаних результатів. У роботах, що написані в співавторстві, автору належать: [1] – комбінаторний аналіз кодових кілець і розробка на його основі методу проектування зсувних регістрів з нелінійною функцією зворотного зв’язку, синтез якої виконується шляхом направленого об’єднання кодових кілець; [2] – розробка методу синтезу нелінійних булевих функцій зворотного зв’язку, реалізація якого має обчислювальну складність O(n2), значно меншу в порівнянні з відомими методами побудови функцій зворотного зв’язку для зсувних 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), які забезпечують просту та ефективну апаратну реалізацію, а також цикл повторення 2n-1 (n- розрядність зсувного регістру) за умови відповідності функції зворотного зв’язку простому поліному на полях Галуа. При цьому кількість NL(n) простих поліномів на полях Галуа, а відповідно і функцій зворотного зв’язку, визначається формулою:

,

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

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

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

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

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

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

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

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

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

При зсуві регістру його молодшому розряду присвоюється значення функції зворотного зв’язку f(x1,x2,…,xn):

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

(1)

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

З урахуванням (1) функцію f(x1,x2,…,xn) зворотного зв’язку можна представити у такому вигляді:

Кільцем R називається множина кодів, які послідовно формуються на зсувному регістрі з функцією зворотного зв’язку f(x1,x2,…,xn)=xn. Кожний з 2n можливих n-розрядних кодів входить до одного з кілець.

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

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

Дійсно, нехай число n ділиться на d. Тоді існують n-розрядні коди, які утворюються як конкатенація n/d ідентичних d-розрядних фрагментів. Цілком очевидно, що після d циклічних зсувів буде мати місце повторення початкового коду. Кількість таких кодів визначається кількістю можливих d-розрядних фрагментів 2d. Таким чином, для того, щоб визначити кількість NС(n) двійкових кодів, що входять до кілець довжиною n, необхідно від загальної кількості 2n можливих 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 | 44 | 3 | 12 | 65 | 6 | 30 | 86 | 9 | 54 | 14 | 7 | 18 | 126 | 20 | 8 | 30 | 240 | 36 | 9 | 56 | 504 | 60 | 10 | 99 | 990 | 108 | 11186 | 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:

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

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

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

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

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

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

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

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

5. З часткового кільця вибирається набір . На наборі Xw встановлюється одиничне значення функції (x1,…,xn-1): (Xw)=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, тобто існує лише одне часткове кільце , що включає єдиний набір Xw={10000}. Відповідно Xw={0000} і (0000)=1.

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

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

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

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

Таблиця істинності отриманої функції (х1,х2,х3,х4) наведена в таблиці 2.

Таблиця 2.

Значення (х1,х2,х3,х4)

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,х2,х3,х4) = 1 х1 х3 х1х3 х3х4 х2х3х4 х1х2х3х4.

Покажемо, що запропонована базова процедура методу є конструкт-ив-ною. Операція уста-новки в одиницю значення функції (х1,х2,…,хn-1) може бути співставлень з об’єднанням кільця, що містить код Xi={x1,x2,…,xn-1,xn=1} та кільця, що включає код Xj={x1,x2,…,xn-1,xn=0}, де i{1,…,NR(n,k)}, j{1,…,NR(n,k-1)}. В силу того, що метод передбачає вибір одного коду Х з усіх кілець, кожне кільце виявляється пов’язаним мінімум з одним із кілець, коди яких містять на одиницю меншу кількість одиниць. Таким чином, всі кільця виявляються пов’язаними в одне кільце, яке містить всі 2n n–розрядні коді, що забезпечує макси-мальний пе-ріод повторення коду на зсувному регістрі.

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

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

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

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

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

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

,

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

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

, (3)

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

. (4)

Набір Y не може співвідноситися до мінімального числа в кільці, якщо він містить хоча б одну послідовність з і бітів, що закінчується j–тим бітом коду Y виду: , таку, що Wi(Sj)<Wi(S0), де S0 – послідовність і старших розрядів набору Y: . Зокрема, набору Y не відповідає мінімальне число в кільці, якщо послідовності Sj та S0 відрізняються лише молодшим бітом: для послідовності Sj він дорівнює нулю, а для S0 – одиниці. Фактично кожний з термів tij являє собою логічний вираз (4), що дорівнює одиниці, якщо виконується умова:

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

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

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

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

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

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

(5)

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

, (6)

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

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

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

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

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

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

1. Множина ={x1,x2,…,xn+h} n+h змінних, на яких визначена функція g(x1,x2,…,xn+h) розділяється на п’ять непересічних підмножин: 1, Q1, , 2, Q2: 1 Q1 2 Q2 =, причому 1, , 2 і ( Q1 Q2) h, де -кількість елементів множини.

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

,

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

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

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

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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