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

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

Національна академія наук України

Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова

УДК 004.056

Спеціальність 05.13.21 - „Системи захисту інформації”

Автореферат

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

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

Абу Усбах Олексій Нідалійович

Київ - 2004



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

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

Науковий керівник - член-кореспондент Національної академії наук України, доктор технічних наук, професор Самофалов Костянтин Григорович, НТУУ ”КПІ”, радник ректора

Офіційні опоненти: доктор технічних наук, старший науковий співробітник Мохор Володимир Володимирович, Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, зав. відділом

кандидат технічних наук, доцент, Гузій Микола Миколайович, Національний авіаційний університет, доцент

Провідна установа -Інститут проблем реєстрації інформації НАН України, відділ цифрових моделюючих систем

Захист відбудеться “ 10” червня 2004 р. о 1400 годині на засіданні спеціалізованої вченої ради Д 26.185.01 Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України за адресою: 03164, м. Київ, вул. Генерала Наумова, 15.

З дисертацією можна ознайомитися в бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України за адресою: 03164, м. Київ, вул. Генерала Наумова, 15.

Автореферат розісланий “ 04 ” травня 2004 р.

Вчений секретар спеціалізованої вченої ради Д 26.185.01 кандидат технічних наук Семагіна Е.П.

Загальна характеристика роботи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Міжнародній науково-практичній конференції “Комп'ютери. Програми. Інтернет. 2003. ”, 21-23 квітня 2003 р., м. Київ.

IV-й Міжнародній науково-практичній конференції “Современные информационные и электронные технологии”, 19-23 травня 2003 р., м. Одеса

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

Робота відзначена дипломом “За участь та високий рівень представленої роботи на IV Міжнародній науково-практичній конференції “Системний аналіз та інформаційні технології”

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

Структура і об'єм роботи. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків і додатку. Загальний обсяг роботи складає 173 сторінки, робота містить 13 малюнків, 3 таблиці, список використаної літератури з 106 найменувань та додаток.

Основний зміст

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

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

Булева функція f(x1,…,xn) від n змінних, визначена на 2n можливих наборах їх значень, задовольняє критерію максимуму повної ентропії, або є балансною, якщо ймовірність прийняття функцією нульового значення (Q) дорівнює ймовірності прийняття одиничного значення (P) - цей критерій може бути визначений через W(f) - Хеммінгову вагу функції (кількість наборів значень аргументів функції f на яких вона приймає одиничне значення):

Булева функція f(x1,…,xn) від n змінних задовольняє критерію максимуму диференційної ентропії, або критерію чіткого лавинного ефекту (Strict Avalanche Criterion - SAC), якщо зміна будь-якого з n аргументів призводить до зміни значення функції з ймовірністю 0,5:

Нелінійність Nf булевої функції f(x1,…,xn) від n змінних характеризує достовірність лінійної апроксимації такої функції і визначається мінімальною Хеммінговою вагою W суми за модулем 2 функції f(x1,…,xn) та лінійної функції:

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

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

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

якості функцій, що складають перетворення (балансність, чіткий лавинний ефект, максимальна нелінійність);

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

можливість побудови бієктивних перетворень;

можливість ефективної процедурної реалізації одержаних перетворень.

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

У другому розділі досліджуються властивості булевих функцій, що містять кон'юнктивну суперпозицію k елементів лінійного базису pi(Xi), i=1..k:

(1)

де pi(Xi) - лінійна функція, визначена на множині аргументів Xi; l(X) - лінійна функція визначена на множині аргументів X.

Доведено, що функції виду (1) задовольняють критерію максимуму повної ентропії за умови ортогональності системи

При цьому нелінійність функцій виду (1) складає

Функція (1) задовольняє критерію чіткого лавинного ефекту при k=2 та за умови ортогональності вищенаведеної системи.

Проведені дослідження дозволили виділити серед функцій виду (1) замкнений відносно лінійних операцій клас булевих функцій та довести притаманні йому властивості балансності, відповідності критерію чіткого лавинного ефекту та нелінійність, яка дорівнює Nf= 2n-2:

(2)

Визначена загальна кількість M функцій інваріантного до лінійних перетворень класу (2) складає:



Функції виду (2) задовольняють критерію чіткого лавинного ефекту порядку r = min(q, (n-q)) - 1. Тобто будь-яка функція отримана з (2) шляхом фіксації r змінних буде задовольняти критерію чіткого лавинного ефекту. З цієї точки зору найбільш важливим є випадок r = n/2 - 1 (при q=n/2). Кількість таких функцій M':

Показано, що функція (2) може бути представлена у наступному вигляді:

Має місце наступна система m булевих функцій виділеного класу:

f1(X) = p1(X) (1 Ф(X)) l1(X);(3)

f2(X) = p2(X) (1 Ф(X)) l2(X);

fm(X) = pm(X) (1 Ф(X)) lm(X).

Наведена система є ортогональною у відповідності до властивостей класу (балансність, інваріантність до лінійних перетворень). Для досягнення більших значень нелінійності ніж Nf = 2n-2 системи (3) запропоновано виконувати суперпозицію k систем (3), визначених на різних множинах аргументів. При цьому результат суперпозиції матиме вигляд:



f1'(X) = p1,1(X) (1 Ф1(X)) ... p1,k(X) (1 Фk(X)) l1(X);

f2'(X) = p2,1(X) (1 Ф1(X)) ... p2,k(X) (1 Фk(X)) l2(X);

fm'(X) = pm,1(X) (1 Ф1(X)) ... pm,k(X) (1 Фk(X)) lm(X).

Теоретично обґрунтовані вимоги до лінійних складових вищенаведеної системи ( i=1…m, j=1…k : {pi,j(X) , li(X)} ), які забезпечують її ортогональність. Нелінійність функцій такої системи наближається до максимально можливої для даного числа аргументів і складає:

(4)

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

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

Формалізований метод одержання нелінійної булевої функції f(x1,x2,…,xn) від n змінних, що задовольняє критерію чітко лавинного ефекту:

Задається k множин Mi змінних xj j=1..n, які у об'єднанні дають повну множину n аргументів:



Формується ортогональна лінійна система з 2k+1 (при k<n/2) або 2k (при k=n/2) булевих функцій:

функції f1(X), … , fk(X) - лінійні булеві функції визначені на множинах аргументів M1,…,Mk відповідно;

функції fk+1(X), … , f2k(X) - є сумою за модулем 2 одиничної константи з усіма змінними відповідних множин M1,…,Mk;

функція f2k+1(X) - лінійна булева функція визначена на повній множині n змінних.

Формується результуюча функція:

F(X) = f1(X) fk+1(X) … fk(X) f2k(X) f2k+1(X).

Запропонований метод формує лінійну комбінацію k булевих функцій виділеного класу, визначених на різних множинах змінних. Таким чином, нелінійність результуючої функції визначається згідно (4). При k<n/2 результуюча функція є нелінійною балансною функцією, що задовольняє критерію чіткого лавинного ефекту, а при k=n/2 - є функцією з максимальною нелінійністю, аналогом функцій Майорана.

Для формування ортогональних систем m булевих функцій виділеного класу (3) пропонується наступний метод:

1. Задати ортогональний лінійний базис з m функцій {G}m={gi(X)},i=1..m :

2. Задати ортогональний лінійний базис з m функцій {H}m={hi(X)},i=1..m :



3. Сформувати результуючу систему {Z}m={zi(X)},i=1..m :

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

1. Задається k множин Mi змінних xj j=1..n, які у об'єднанні дають повну множину n аргументів:

2. Задається m ортогональних базисів {G}2k+1,i (i = 1…m) з 2k+1 функцій:

функції g1i(X), … ,gki(X) - лінійні булеві функції визначені на множинах аргументів M1,…,Mk відповідно;

функції gk+1i(X), … ,g2ki(X) - є сумою за модулем 2 одиничної константи з усіма змінними відповідних множин M1,…,Mk;

функція g2k+1i(X) - лінійна булева функція визначена на повній множині n змінних;

виконуються умови:

3. Формується результуюча система:

Проведений порівняльний аналіз показав, що характеристики перетворень, побудованих каскадним методом, еквівалентні аналогам методу Сіберрі-Жанга-Женга. Але, на відміну від методу Сіберрі, запропонований не має технологічних обмежень розрядності синтезованих перетворень, зумовлених використанням матричних перетворень експоненціальної розмірності. Нелінійність перетворень побудованих каскадним методом поступається аналогам методів Нюберг і Куросави-Сато. Відносне значення різниці нелінійності:

Така різниця є незначною для великих значень n.

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

Одним з перспективних напрямків підвищення ефективності обчислення є запропонований Біхамом ”бітовий зріз” (bit-slice) - паралелізм на бітовому рівні, оснований на уніфікації операцій при одночасному обчисленні перетворення для групи блоків даних. Недоліком ”бітового зрізу” є те, що одночасна обробка групи блоків даних накладає обмеження на режими роботи засобів захисту, не дозволяючи застосовувати об'єднання по вихідним даним.

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

Для системи (3) має місце матричний еквівалент - матриця А розмірності mЧn, в якій кожен рядок - векторне представлення pi(X). Тоді обчислення системи (3) може бути записане у матричній формі:

де А-матриця системи, L - матриця лінійних частин X - вектор аргументів.

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

ПОЧАТОК

КРОК 0Vl = 0, Vr = 0, i = 1;

КРОК 1Якщо xi = 0, то перейти на КРОК 3;

КРОК 2Vl = Vl A[i], Vr = Vr not(A[i]);

КРОК 3i = i + 1;

КРОК 4Якщо i ? n, то перейти на КРОК 1;

КРОК 5Y = Vl Vr L;

КІНЕЦЬ.

Для більшості систем процес обчислення можна прискорити за рахунок використання таблиць замість послідовності бітових операцій. Розмір таблиць варіюється в залежності від доступного об'єму надоперативної пам'яті. Нижче наведено формулу заповнення k таблиць Ti розмірності mЧn біт (mk = n):

Запропонований таблично-паралельний спосіб обчислення реалізовано у наступному алгоритмі:

ПОЧАТОК

КРОК 0Y = L, i = 1;

КРОК 1Якщо W(X) - непарне, то перейти на КІНЕЦЬ;

КРОК 2Q = (X ((i-1)m)) Mask;

КРОК 3Y = Y Ti[Q];

КРОК 4i = i + 1;

КРОК 5Якщо i ? k, то перейти на КРОК 2;

КІНЕЦЬ.

Робота алгоритму ілюструється на поданому нижче мал. 1.

булевий захист інформація програмний



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

Для обчислення булевих функціональних перетворень, сформованих за рахунок циклічного зсуву (відповідний алгоритм наведено у третьому розділі) немає необхідності у використанні k таблиць, оскільки всі таблиці пов'язані наступним співвідношенням:



Висновки

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

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

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

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

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

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

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

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

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



Список опублікованих праць за темою дисертації

1. Абу Усбах А.Н. Таблично-параллельная организация вычислений систем булевых функций специальных классов.// Вісник Національного технічного університету України “КПІ”. Інформатика, управління та обчислювальна техніка. - Київ: ВЕК+.- 2002.- №38.- С.81-92. (Дисертантом запропоновано таблично-паралельний спосіб обчислення булевих функціональних перетворень для блокових засобів захисту інформації).

2. Марковский А.П., Бардис Николас, Абу Усбах А.Н., Кищенко А.В. Анализ защищенности криптографических алгоритмов с использованием булевых функций.// Вісник Національного технічного університету України “КПІ”. Інформатика, управління та обчислювальна техніка. - Київ: ВЕК+. - 1998. - №31. - С.24-34. (Дисертантом запропоновано результати аналізу використання булевих функціональних перетворень в засобах захисту інформації).

3. Марковский А.П., Абу Усбах А.Н., Аль-Омар Салех. Получение систем ортогональных булевых SAC-функций для систем защиты информации. // Вісник Національного технічного університету України “КПІ”. Інформатика, управління та обчислювальна техніка. - Київ: ВЕК+. - 2001. -№36. - С.94-108. (Дисертантом запропоновано методи синтезу булевих функцій спеціального класу та побудови на їх основі функціональних перетворень для блокових засобів захисту інформації).

4. Самофалов К.Г., Абу Усбах А.Н., Стефанская В.А. Организация вычислений нелинейных систем взаимно ортогональных булевых функций специальных классов.// Вісник Національного технічного університету України “КПІ”. Інформатика, управління та обчислювальна техніка. - Київ: ВЕК+. - 2002. - №37. - С.3-14. (Дисертантом запропоновані підходи до організації процесів обчислення булевих функцій та функціональних перетворень для засобів захисту інформації).

5. Марковский А.П., Виноградов Ю.Н., Абу Усбах А.Н. Некоторые свойства булевых функций и их использование для построения алгоритмов защиты информации. Моделювання та інформаційні технології.// Збірник праць. - Київ: ІПМЕ НАН України. - 2002. - Вип.12. - С.79-84. (Дисертантом запропоновано замкнений відносно лінійних операцій клас булевих функцій та теоретичне обґрунтування властивостей функцій такого класу).

6. Марковский А.П., Абу Усбах А.Н., Иваненко Я.П. К вопросу об определении нелинейности булевых функций специальных классов.// Вісник Національного технічного університету України “КПІ”. Інформатика, управління та обчислювальна техніка. - Київ: ВЕК+. - 2002. - №37. - С.14-25. (Дисертантом запропоновано результати аналізу відомих методів побудови булевих функціональних перетворень для блокових засобів захисту інформації).

7. Абу Усбах А.Н. Булевы функции специальных классов для систем защиты информации.// Тези IV Міжнародної науково-практичної конференції ”Системний аналіз та інформаційні технології.” . - м. Київ. 2002. - С. 85-86. (Дисертантом запропоновано замкнений відносно лінійних операцій клас булевих функцій для побудови перетворень в засобах захисту інформації).

8. Абу Усбах А.Н. Построение генераторов булевых функций для систем статистического моделирования.// Тези Міжнародної науково-практичної конференції ” Комп'ютери. Програми. Інтернет. 2003.”. - м. Київ. 2003. - С. 76-77. (Дисертантом запропоновано каскадний метод побудови булевих функціональних перетворень).

9. Абу Усбах А.Н. Синтез и организация вычисления булевых функций.// Труды IV Международной научно практической конференции ”Современные информационные и электронные технологии.” . - м. Одеса. 2003. - С. 84-85. (Дисертантом запропоновано метод синтезу та спосіб обчислення булевих функцій спеціального класу в засобах захисту інформації).

10. Абу Усбах А.Н. Повышение эффективности систем моделирования за счет использования булевых функциональных преобразований специальных классов.// Тези V Міжнародної науково-практичної конференції ”Системний аналіз та інформаційні технології”. - м. Київ. 2002.- С.131-132. (Дисертантом запропоновано спосіб організації обчислення булевих функціональних перетворень).



Анотації

Абу Усбах Олексій Нідалійович. Методи синтезу та спосіб обчислення булевих функцій спеціального класу для засобів захисту інформації. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.21 - Системи захисту інформації. - Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, Київ, 2004.

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

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

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

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

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



Абу Усбах Алексей Нидальевич. Методы синтеза и способ организации вычисления булевых функций специального класса для средств защиты информации. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.21.- Системы защиты информации.- Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины, Киев, 2004.

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

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

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

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

Предложен новый таблично-параллельный способ вычисления булевых функциональных преобразований, основанных на функциях выделенного класса. Способ использует унификацию и совместное выполнение битовых операций - так называемый “битовый срез” Бихама. В отличие от битового среза, предложенный способ использует внутриблоковую унификацию операций, а не межблоковую, что снимает ограничения режимов работы средств защиты информации характерные для подхода предложенного Бихамом. Способ имеет линейную вычислительную сложность и позволяет повысить эффективность средств защиты данных путем использования преобразований большой разрядности.

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



Oleksiy N Abu Usbakh. Synthesis and calculation methods of special class Boolean functions for data security means. - Manuscript.

Thesis for a Ph.D. degree in speciality 05.13.21. - Data security systems. Pukhov's Institute of Modelling Problems in Power Engineering, National Academy of Sciences of Ukraine. Kiev. 2004.

Thesis is dedicated to a problem of research the ways to increase the data security means efficiency by using Boolean function transformations based on special class functions.

New class of Boolean functions is suggested. Being balanced and nonlinear the class functions satisfy strict avalanche criterion. The class properties are invariant for any class functions linear combination. Class functions can be effectively calculated by means of bit operation unification with concurrent execution.

New synthesis method of balanced nonlinear SAC-functions is given. Cascade construction method of the Boolean function transformations is proposed as well. Unlike other methods this one allows varying transformations' nonlinearity with its computation complexity. Also the Cascade method can be used for large block transformations construction.

New calculation method for Boolean function of suggested class is proposed. The method has linear computational complexity that allows increasing efficiency of data security means by large block transformation utilization.

Key words: Boolean functions, Boolean function transformations, strict avalanche criterion, nonlinearity, block algorithms, data security.

Размещено на Allbest.ru