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

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

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

УДК 681.3.06

Спеціальність 05.13.05 - Комп'ютерні системи та компоненти

Автореферат

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

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

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

Бевз Олександр Миколайович

Вінниця - 2008



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

Робота виконана у Вінницькому національному технічному університеті, Міністерство освіти і науки України.

Науковий керівник - доктор технічних наук, професор Квєтний Роман Наумович, Вінницький національний технічний університет, завідувач кафедри автоматики та інформаційно- вимірювальної техніки

Офіційні опоненти: доктор технічних наук, професор Лужецький Володимир Андрійович, Вінницький національний технічний університет, завідувач кафедри захисту інформації

кандидат технічних наук, доцент Горпенюк Андрій Ярославович, Національний університет “Львівська політехніка”, доцент кафедри захисту інформації

Захист відбудеться “3” жовтня 2008 р. о 9-30 годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому національному технічному університеті за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95, ГУК, ауд. 210.

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

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

Вчений секретар спеціалізованої вченої ради С.М. Захарченко



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

Актуальність теми

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

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

Багато додатків вимагають створення комп`ютерних мереж з інформаційним захистом при застосуванні відкритих ліній зв`язку. Ці обчислювальні системи відомі як Віртуальні Приватні Мережі (Virtual Private Networks - VPNs). VPN вимагають шифрування на швидкості, що перевищує швидкість асинхронного режиму передавання - більше за 1 Гбіт/с. Тому існує нагальна потреба розробляти методи, засоби та алгоритми шифрування з високою криптологічною стійкістю, які працюють в комп`ютерних системах та мережах та мають швидкість роботи понад 1 Гбіт/c.

Зв`язок роботи з науковими програмами, планами, темами

Робота виконувалася у відповідності до програми про технічний захист інформації в Україні, що затверджена постановою Кабінету Міністрів України від 9 вересня 1994 р. N 632. Результати досліджень, що представлені в дисертації виконувались в рамках науково-дослідної роботи по договору з Вінницькою обласною дирекцією АППБ "Аваль” від 1.02.2006 р. № 41/30 “Розробка та впровадження програмного забезпечення для передавання інформації каналами зв`язку колективного користування з використанням мережних технологій” ( № державного реєстру 0106U006438). Основний зміст роботи складають наукові дослідження, що були проведені на кафедрі автоматики та інформаційно-вимірювальної техніки Вінницького національного технічного університету в 2002-2007 роках.

Мета і завдання дослідження

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

Завдання дослідження:

1. Аналіз існуючих криптографічних підходів до захисту інформації в комп`ютерних системах та мережах.

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

3. Розробка методу формування блочних шифрів, який ефективно протидіє криптоаналізу.

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

5. Розробка методу формування перемішування з криптографічно стійкими S-боксами.

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

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

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

9. Експериментальні дослідження та впровадження результатів роботи в практику розробки та застосування комп`ютерних систем та мереж.

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

Предмет дослідження - методи шифрування для захисту інформації в комп`ютерних системах та мережах.

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

Наукова новизна одержаних результатів.

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

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

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

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

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

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

Практичне значення одержаних результатів.

Практичне значення отриманих результатів полягає в тому, що:

- розроблено методику захисту інформації на основі реалізації блочного шифру в комп`ютерних системах та мережах;

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

- розроблено алгоритм реалізації процедури формування S-боксу;

- розроблено алгоритм табличної реалізації процедури формування S-боксу;

- розроблено алгоритм табличної реалізації формування підстановочно-перестановочної мережі;

- результати проведених досліджень впроваджено в інтелектуальні програмні засоби корпоративної комп`ютерної мережі Вінницької обласної дирекції АППБ "Аваль” в рамках договору про творчу співдружність від 1.02.2006 р. № 41/30 “Розробка та впровадження програмного забезпечення для передавання інформації каналами зв`язку колективного користування з використанням мережних технологій”, № державного реєстру 0106U006438, в автоматизовану систему підключення абонентів ІВП "ІННОВІНН", а також у навчальний процесс у Вінницькому національному технічному університеті на кафедрі автоматики та інформаційно-вимірювальної техніки при підготовці студентів зі спеціальності 7.091401 "Системи управління та автоматики".

Особистий внесок здобувача

Основні теоретичні, розрахункові та експериментальні результати з формулюванням відповідних висновків отримані автором самостійно. У роботі [1], опублікованій в співавторстві, здобувачем запропоновано метод формування збалансованої бульової функції семи аргументів з високою нелінійністю; в роботі [2] - розроблено метод формування нелінійного фільтр-генератора; в роботі [3,12] - визначено особливості реалізації операцій в полі Галуа GF (2n); в роботі [4,11] - визначено криптографічні властивості нелінійного фільтр-генератора; в роботі [7] - визначено криптографічні властивості блочних шифрів.

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

- VII міжнародному молодіжному форумі ”Радиоэлектроника и молодежь в ХХI веке”, Харків, 2003 р.;

- VII міжнародній конференції ”Контроль і управління в складних системах” (КУСС-2003), Вінниця, 2003 р.;

- IV міжнародній конференції ”ІНТЕРНЕТ - ОСВІТА - НАУКА - 2004” (ІОН-2004), Вінниця, 2004 р.;

- VIIІ міжнародній конференції ”Контроль і управління в складних системах” (КУСС-2005), Вінниця, 2005 р.;

- щорічних науково-технічних конференціях професорсько-викладацького складу Вінницького національного технічного університету, Вінниця, 2003-2007 р.;

- міжнародному науковому семінарі Вінницького національного технічного університету та університету ”Хайфський техніон ” (Ізраїль), Вінниця, 2007 р.

Публікації. Результати дослідження були опубліковані в 12 наукових працях, з яких 6 - у фахових наукових виданнях за переліком ВАК, 1 стаття у збірнику матеріалів міжнародних конференцій, 5 тез доповідей на конференціях.

Структура і обсяг дисертації

Дисертація складається з вступу, чотирьох розділів, списку використаних джерел та додатків. Загальний обсяг дисертації складає 181 сторінка, з яких основний зміст викладений на 129 сторінках друкованого тексту, містить 32 ілюстрації та 25 таблиць. Список використаних джерел складається з 126 найменувань. Додатки містять окремі лістинги та акти впровадження результатів роботи і викладені на 38 сторінках.

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

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

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

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

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

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

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

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

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

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

Критичним фактором протидії лінійному та диференційному криптоаналізу є високе значення лінійної та відповідно диференційної ймовірності бульового відображення. Лінійна ймовірність раунду t визначається лінійною ймовірністю кроку підстановки відносно векторів vit і wit

M

LPt(vt, vt+1)= ? LPSi(vit , wi t) , (1)

i=1

де М - кількість S-боксів в раунді;

LPS - лінійна ймовірність S-боксу;

vt, - вхідний відносний вектор раунду t;

vt+1 - вихідний відносний вектор раунду t.

Аналогічно диференційна ймовірність (Дvt Дvt+1) раунду t залежить від диференційної ймовірності кроку підстановки (Дvit , Дwit) і визначається виразом:

M

DPt(Дvt, Дvt+1)= ? DPSi(Дvit , Д wi t) , (2)

i=1

де DPS - диференційна ймовірність S-боксу.

Як видно з виразів 1 та 2 лінійна та диференційні ймовірності залежать від тих з S-боксів, які приймають участь у формуванні лінійної та диференційної характеристики. Ці S-бокси мають назву активні.

Для збільшення кількості активних S-боксів пропонується використання гніздової підстановочно-перестановочної мережі з типом перетворення на нижньому рівні на основі коду з максимальною відстанню (2 1 2) в полі GF (28) та типом перетворення на верхньому рівні на основі коду (32 16 17) в полі GF (2128) рис.1.

Рис.1. Запропонована гніздова підстановочно-перестановочна мережа

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

На рис.2 наведені значення коефіцієнтів ефективності захисту інформації для гніздових підстановочно-перестановочних мереж з різними типами кодів з максимальною відстанню та різними розмірами S-боксів. Крива 1 демонструє коефіцієнт ефективності мереж з розміром S-боксу вісім біт. Крива 2 - для мереж з розміром 4 біт. Точка 1 на кривій 1 відповідає мережі на нижньому рівні якої код з максимальною відстанню (2 1 2), на верхньому - код з максимальною відстанню (32 16 17); точка 2 відповідає мережі на нижньому рівні якої код з максимальною відстанню (4 2 3), на верхньому - код з максимальною відстанню (16 8 9); точка 3 відповідає мережі на нижньому рівні якої код з максимальною відстанню (8 4 5), на верхньому - код з максимальною відстанню (8 4 5); точка 4 відповідає мережі на нижньому рівні якої код з максимальною відстанню (16 8 9), на верхньому - код з максимальною відстанню (4 2 3); точка 5 відповідає мережі на нижньому рівні якої код з максимальною відстанню (32 16 17), на верхньому - код з максимальною відстанню (2 1 2).

Рис.2. Значення коефіцієнтів ефективності для SPN-мереж з розміром S-боксів 8х8 (крива 1) та 4х4.(крива 2)

Точка 1 на кривій 2 відповідає мережі на нижньому рівні якої код з максимальною відстанню (2 1 2), на верхньому - код з максимальною відстанню (64 32 33); точка 2 відповідає мережі на нижньому рівні якої код з максимальною відстанню (4 2 3), на верхньому - код з максимальною відстанню (32 16 17); точка 3 відповідає мережі на нижньому рівні якої код з максимальною відстанню (8 4 5), на верхньому - код з максимальною відстанню (16 8 9); точка 4 відповідає мережі на нижньому рівні якої код з максимальною відстанню (16 8 9), на верхньому - код з максимальною відстанню (8 4 5); точка 5 відповідає мережі на нижньому рівні якої код з максимальною відстанню (32 16 17), на верхньому - код з максимальною відстанню (4 2 3); точка 6 відповідає мережі на нижньому рівні якої код з максимальною відстанню (64 32 33), на верхньому - код з максимальною відстанню (2 1 2).

Таким чином, метод лінійного перетворення для формування ефективного шифрування в комп`ютерних системах має складатися з таких кроків:

а) використання КМВ - перетворення (2, 1, 2) в полі GF (28) для перетворення вихідного байту S-боксу на низькому рівні;

б) використання КМВ - перетворення (32, 16, 17) в полі GF (2128) для перетворення сукупності вихідних значень КМВ - перетворення (2, 1, 2) в полі GF (28) на високому рівні.

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

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

Клас бульових функцій, які мають назву бент-функції задовольняють всім наведеним вище вимогам окрім збалансованості. В другому розділі дисертації було визначено, що розмір S-боксу має дорівнювати 8х8. Для задоволення цих вимоги, а також враховуючи те, що розмір полуслова комп`ютерної системи дорівнює байт, для створення методу формування криптографічно стійкого S-боксу необхідно створити бульову функцію, що має вісім аргументів та задовольняє вимозі збалансованості. [1, 6] Створення цієї функції виконано в два етапи: на першому етапі створено семикоординатну функцію, а на другому - восьмикоординатну.

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

Теорема.3.1 Якщо z(x2...xn) - будь-яка бент-функція, то функція f(x1..xn)=x1 z(x2...xn), задовольняє критерію розповсюдження по відношенню до всіх векторів довжини n за винятком вектору =(10..0), збалансована, і має нелінійність N=2n-1-2(1/2)n-1.

Так створена семикоординатна функція має вигляд:

f(x1 x2 x3 x4 x5 x6 x7)= x1 z(x1x2 x1x3 x1x4 x1x5 x1x6 x1.x7)= x1 (x1x2)(x1x3) (x1x4)(x1x5) (x1x6)(x1x7) (3)

(x1x3)(x1x5)(x1x7).

Для створення восьмикоординатної функції за допомогою операції додавання з`єднаємо семикоординатну функцію f(x) з однокординатною функцією h(x) = x.

Теорема 3.2. Якщо функція f(x) = x1 (x1x2)(x1x3) (x1x4)(x1x5) (x1x6)(x1x7)(x1x3)(x1x5)(x1x7), а функція h(x) = x, то функція g(x) = f(x)+h(x) збалансована, має ступінь нелінійності - 112, критерій розповсюдження - 7.

Так восьмикоординатна бульова функція наступна: 

f(x) = x0 x1 (x1x2)(x1x3) (x1x4)(x1x5) (4)

(x1x6)(x1x7) (x1x3)(x1x5)(x1x7).

Для ефективної реалізації S-боксу на основі визначеної функції пропонується реалізацію S-боксу виконати наступним чином:

Y = Х0 Х1 (Х1 Х2)(Х1 Х3) (Х1 Х4) (Х1 Х5) (Х1 (5)

Х6) (Х1 Х7) (Х1Х3)(Х1Х5)(Х1Х7),

де Х0 - вхідний байт S - бокса;

Х 1 - байт Х0 циклічно зсунутий на 1 біт вліво;

Х2 - байт Х0 циклічно зсунутий на 2 біта вліво;

Х3 - байт Х0 циклічно зсунутий на 3 біта вліво;

Х 4 - байт Х0 циклічно зсунутий на 4 біта вліво;

Х5 - байт Х0 циклічно зсунутий на 5 біт вліво;

Х 6 - байт Х0 циклічно зсунутий на 6 біт вліво;

Х 7 - байт Х0 циклічно зсунутий на 7 біт вліво.

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

Проведені дослідження продемонстрували, що середня кількість пар відкритих текст-шифротекст для зламу S-боксу диференційним криптаналізом на основі запропонованої бульової функції дорівнює 1116 байт, що в 1, 12 рази вище за стійкість S-боксу шифру AES.

Середня кількість відкритих текстів для зламу S-боксу лінійним криптаналізом на основі функції 4 дорівнює 1448 байт, що вище за стійкість S-боксу шифру AES в 1, 15 рази.

Подальші комп`ютерні дослідження показали, що стійкість шістнадцяти раундів шифру на основі методу, що розроблено в розділі 2, та S-боксу на основі функції 4 вище за стійкість шістнадцяти раундів шифру AES в 1,8 рази.

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

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

В четвертому розділі проведена розробка алгоритмів та програмних засобів для реалізації запропонованих методів шифрування, виконані експериментальні дослідження по визначенню необхідного об`єму пам`яті та швидкості роботи існуючих алгоритмів шифрування та запропонованого, описане впровадження програми шифрування в автоматизовану систему підключення абонентів ІВП ІННОВІНН та інтелектуальні програмні засоби корпоративної комп`ютерної мережі Вінницької обласної дирекції АППБ "Аваль”.

Програмні модулі розроблені з використанням мови програмування С++. Реалізація алгоритмів здійснювалося на комп`ютері з такою конфігурацією: операційна система - Windows XP, процессор - Itel Pentium IV 2.4 ГГц; оперативна пам`ять - DDR 400, 512 Mb.

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

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

Програмні модулі розроблені з використанням мови програмування С++.

В відповідності сучасним вимогам методи шифрування мають оперувати з блоками даних розміром 128 біт. Тому на вхід програми шифрування поступають дані такого розміру.

На наступному кроці дані заповнюють одновимірний масив, елементами якого є байти (16 байтів) в порядку A0 …A15. Після цього дані перетворюються згідно алгоритму шифрування наведеного на рис. 3. Зашифровані дані мають також формат одномірного массиву, елементами якого є 16 байтів

Рис. 3. Граф-схема алгоритму шифрування

Після заповнення масиву над байтом A[j] на першому кроці здійснюється лінійне перетворення низького рівня LT1. Це лінійне перетворення здійснюється кодом з максимальною відстанню (2, 1, 2) в полі GF (28).

На другому кроці виконується перетворення байту S-боксом, що визначений функцією 4. На третьому кроці здійснюється лінійне перетворення високого рівня LT2. Це лінійне перетворення здійснюється кодом з максимальною відстанню (32, 16, 17) в полі GF (2128). На четвертому кроці до отриманого байту за модулем два додається ключ шифрування. Для обробки всіх байтів масиву такі перетворення необхідно повторити 16 раз.

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

Сучасні мережі при проектуванні не планувалися як захищені мережі, тому їхні проблеми відносно конфіденційності (проблеми протоколів TCP-IP) наступні:

- можливість перехоплення даних і фальсифікація адресів комп`ютерних систем в мережі (основна частина трафіка Internet - відкриті дані - E-mail, паролі та файли можуть бути перехоплені доступними програмами);

- ряд засобів TCP-IP не були спроектовані як захищені і можуть бути зміненими.

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

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

а) визначення інформації, яка буде передаватися каналами зв`язку;

б) генерування ключа шифрування розробленим методом потокового шифрування;

в) передавання ключа шифрування закритим каналом зв`язку;

г) шифрування інформації розробленим методом блочного шифрування;

д) передавання інформації відкритим каналом зв`язку;

е) розшифрування прийнятої інформації.

Експериментальні дослдження по визначенню обчислювальних характеристик розроблених алгоритмів шифрування в комп`ютерних системах були проведені для порівняння обчислювальних характеристик запропонованих методів з обчислювальними характеристиками існуючих методів шифрування.

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

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

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

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

Проведені експериментальні дослідження продемонстрували, що програмна реалізація розроблених методів шифрування вимагає розмір пам`яті в 1,05 - 1,17 разів менше, а швидкодія в 1,05-1,44 разів вища ніж у найпоширеніших алгоритмів шифрування.



ВИСНОВКИ ПО РОБОТІ

Основні результати досліджень є такими:

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

2. Розроблено метод формування лінійного перетворення на основі гніздової SPN-мережі з типом лінійного перетворення низького рівня КМВ-кодом типу (2, 1, 2) та лінійного перетворення високого рівня КМВ-кодом типу (32, 16, 17), який на відміну від існуючих має більшу кількість активних S-боксів та менший час реалізації в комп`ютерних системах, що дозволить підвищити ефективність шифрування.

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

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

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

Нелінійність функції дорівнює - 112, критерій розповсюдження дорівнює 7, що дає змогу знизити результативність криптоаналізу

5. Розроблено метод формування нелінійного перетворення (S-бокс) на основі восьмикоординатної високонелінійної булевої функцію, яка на відміну від існуючих має високі криптографічні властивості: стійкість запропонованого S-боксу вище за стійкість стандарту шифрування AES відносно лінійного криптаналізу в 1,15 рази, відносно диференційного в 1,12 рази.

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

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

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

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

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

11. Результати проведених досліджень впроваджено в AKБ „Аваль”, ІВП „ІННОВІНН” при проектуванні засобів та пристроїв передавання інформації, а також у навчальний процес у Вінницькому національному технічному університеті на кафедрі автоматики та інформаційно-вимірювальної техніки.



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

1. Бевз О. Протистояння диференційному і лінійному криптаналізу збалансованими булевими функціями / Олександр Бевз, Роман Квєтний // Наукові праці Донецького Національного Технічного Університету. Серія: Обчислювальна техніка та автоматизація. - 2003 - Випуск 64. - C. 150-155.

2. Бевз О.М. Кореляційні властивості фільтр-генератора з суттєво нелінійною булевою функцією / Р.Н. Квєтний, О.М. Бевз, О.О. Юдін // Вісник Черкаського державного технологічного університету. - 2004 - №2. - С.107-111.

3. Бевз О. Паралелізована хеш - функція з двома ключами / Олександр Бевз, Володимир Папінов // Вісник Вінницького політехнічного інституту. - 2003. - № 6. - С.322 - 325.

4. Бевз О. Використання булевих високонелінійних функцій для створення поточного шифру / Олександр Бевз, Володимир Папінов // Інформаційні технології та комп`ютерна інженерія. - 2005. -- № 3. - С.263-267.

5. Бевз О.М. Криптографічні властивості підстановочно-перестановочних мереж / О.М. Бевз // Наукові праці Донецького національного технічного університету. Серія: ”Обчислювальна техніка та автоматизація”. - 2006. - Випуск 107.- С.12-16.

6. Бевз О.М. Кореляційні та диференційні властивості S-боксів на основі високонелінійних функцій / О.М. Бевз // Інформаційні технології та комп`ютерна інженерія. - 2006. -№ 1(5). - С.154-158.

7. Бевз А. Способ передачи информации с защитой и быстрым декодированием / Александр Бевз , Олег Юдин // Proceeding of the Forth International Conference Internet - Education - Science (IES-2004). -28 вересня -2 жовтня 2004. - Vol. 2. - UNIVERSUM-VINNYTSA. - P.744-745.

8. Бевз О. М. Використання кубічних перетворень в шифрах для захисту інформації / О.М. Бевз .// Радиоэлектроника и молодежь в ХХІ веке: VII Международный молодежный форум, 2003: тези доповіді. - Харьков. -22 - 24 квітня 2003. - 136 с.

9. Бевз О.М. Схема Фейстеля модифікована керованими операціями / О.М. Бевз // Контроль і управління в складних системах (КУСС-2003): VII міжнародна конференція, 2003.: тези доповіді. - Вінниця. -8-11 жовтня 2003. - С. 345

10. Бевз О.М. Кореляційні та диференційні властивості S-боксів на основі високонелінійних функцій / О.М. Бевз // Контроль і управління в складних системах (КУСС-2005): VIIІ міжнародна конференція, 2005.: тези доповіді. - Вінниця. - 24-27 жовтня 2005. - С. 101.

11. Бевз О. Використання булевих високонелінійних функцій для створення поточного шифру / Олександр Бевз, Володимир Папінов // Контроль і управління в складних системах (КУСС-2005): VIIІ міжнародна конференція, 2005.: тези доповіді. - Вінниця. - 24-27 жовтня 2005. - С. 105.

12. Бевз О. Паралелізована хеш - функція з двома ключами / Олександр Бевз, Володимир Папінов // Контроль і управління в складних системах (КУСС-2003): VII міжнародна конференція, 2003.: тези доповіді. - Вінниця. - 8-11 жовтня 2003. - С. 84



АНОТАЦІЯ

Бевз Олександр Миколайович. Методи шифрування на основі високонелінійних бульових функцій та кодів з максимальною відстанню. - Рукопис.

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

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

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

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

Ключові слова: криптографічна стійкість, криптоаналіз, відстань Хеммінга, підстановочно-перестановочна мережа, S-бокс.



АННОТАЦИЯ

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - Винницкий национальный технический университет, Винница - 2008.

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

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

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

Так линейные булевые преобразования используются для изменения избыточности открытого текста путем распространения избыточности по всему тексту.

Нелинейные булевые преобразования используются для удаления связи между шифротекстом и текстом путем устранения избыточности и статистических закономерностей.

Основными методами формирования линейных булевых преобразований являются применение сети Фейстеля, обобщенной или расширенной сети Фейстеля, несбалансированной сети Фейстеля и подстановочно-перестановочных сетей.

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

Методами формирования нелинейных булевых преобразований есть табличные подстановки и блоки подстановки (S-боксы), созданные на основе алгебраических функций. Недостатком табличных подстановок является необходимость размещения таблиц подстановки в оперативной памяти компьютера. Недостатком S-боксов есть алгебраическая простота и криптографическая слабость функций, которые в них применяются.

Для устранения недостатков линейного преобразования разработан метод формирования двухуровневого линейного преобразования на основе кода с максимальным расстоянием (2 1 2) в поле GF (28) на низком уровне и кода с максимальным расстоянием (32 16 17) в поле GF (2128) на высоком уровне. Как показали дальнейшие исследования, данное преобразования обладает наибольшей криптографической стойкостью и наивысшим коэффициентом эффективности реализации в компьютерных системах.

Для устранения недостатков нелинейного преобразования разработан метод формирования блока подстановки - S-бокс на основе высоконелинейной сбалансированной булевой функции от восьми аргументов. Эта функция является конкатенацией бент-функции от шести аргументов и аффинной функции от двух аргументов.

Как показали исследования, S-бокс на основе этой функции имеет криптографическую стойкость на 12-15% выше ,чем у S-бокса шифра AES, который является стандартом шифрования. Дальнейшие исследования продемонстрировали, что шестнадцать раундов шифра на основе разработанных методов имеют криптографическую стойкость на 80% выше, чем у шифра AES.

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

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

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

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

Экспериментальные исследования показали, что программная реализация разработанных методов шифрования требует размер памяти на 5-17% меньше, а обеспечивает быстродействие на 5 - 44% выше, чем у наиболее распространенных алгоритмов шифрования.

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



ABSTRACT

Bevz Оlexander Мikolayevich. Cipher methods based on high nonlinear boolean functions and the maximal distance codes. - А manuscript.

Thesis for a candidate degree of technical sciences by speciality 05.13.05 - Computer systems and components. - Vinnytsia National Technical University, Vinnytsia - 2008.

The dissertation is devoted to development of cipher methods for the protection of computer systems and networks information.

On the basis of the carried out analysis of the existing cipher methods are development the cipher methods used the highly nonlinear Boolean functions and the maximal distance codes. These methods differ from other existed the greater speed of the ciphering and the cryptology security. The algorithms and software are developed too.

Experimental researches validified results.

Key words: cryptographic security, cryptanalyst, Hamming distance, substitution-permutation networks, S-box.

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

...