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

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

Акрам Ареф Найеф Мустафа

(Йорданія)

УДК 681.3

РОЗРОБКА ЗАСОБІВ ЕФЕКТИВНОГО ВИБОРУ ТА

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

В КОМП'ЮТЕРНИХ СИСТЕМАХ

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

АВТОРЕФЕРАТ

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

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

Київ 2003

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

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

Науковий керівник – член –кореспондент Національної Академії Наук,

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

Самофалов Костянтин Григорович,

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

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

бітник Мохор Володимир Володимирович,

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

ім. Г.Є.Пухова НАН України, зав.відділом

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

Корченко Олександр Григорович, Національний

авіаційний університет, докторант.

Провідна установа: Інститут проблем реєстрації інформації НАН

України, відділ цифрових моделюючих систем

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

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

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

Автореферат розісланий 12 лютого 2003 р.

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

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

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

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

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

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

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

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

Мета і задачі дослідження. Метою роботи є :

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

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

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

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

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

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

2. Теоретичне обґрунтування і дослідження моделі забезпечення криптостійкості хеш-алгоритмів та розробка на її основі методів та засобів паралельного обчислення хеш-сигнатур без зменшення рівня їх захищеності.

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

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

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

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

7. Розробка архітектури апаратних засобів реалізації симетричних алгоритмів захисту інформації на FPGA –структурах.

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

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

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

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

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

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

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

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

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

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

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

Структура та об'єм роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків та додатку. Робота містить 159 сторінок друкованого тексту, 17 малюнків, 10 таблиць і список використаної літератури на 95 найменувань.

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

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

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

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

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

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

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

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

Практично всі сучасні хеш-алгоритми, зокрема, такі як SHA-1, MD-5, RIPEMD-160 та ГОСТ Р.34.11-94 структурному плані близькі між собою: всі вони реалізують блочно-послідовну організацію обробки повідомлень. При цьому повідомлення М поділяється на блоки M1,M2,…,Mn фіксованої довжини d і над кожним j-тим блоком Мj, j=1,…,n виконується хеш-перетворення H(s,Mj) результатом якого є t-бітова часткова хеш-сигнатура hj , де s – ініціюючий код. Відповідно, повна хеш-сигнатура HS(M) інформаційного повідомлення М визначається як сума за модулем два всіх часткових хеш-сигнатур:

( 1 )

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

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

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

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

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

Ця функція зберігає властивості максимуму повної та умовної ентропії, але сама по собі не забезпечує вимог щодо унеможливлення блокових маніпуляцій. Її застосування можливе лише за умови модифікації процедури одержання часткових хеш-сигнатур. Така модифікація повинна виконуватися таким чином, щоб при перестановці j-го блоку Mj змінювався б відповідний йому код часткової хеш-сигнатури hj=H(Mj). Це може бути реалізовано в наступних формах:

- зміною коду інформаційного блоку на вході хеш-перетворювача - тобто подачу на його вхід замість коду Mj модифікованого коду Mmj=j(Mj,mj) де mj –модифікуючий код для j-го блоку;

- використанням в якості ініціюючого коду s при обробці j-того блоку модифікуючого коду mj ;

- перетворенням часткових хеш-сигнатур після їх одержання hmj=f(hj,mj) ;

Найпростішою формою організації незалежного обчислювання часткових хеш-сигнатур є модифікація вхідного блока Mmj=j(Mj,mj) безпосередньо перед обчисленням його часткової хеш-сигнатури hj=H(Mmj)=H(j(Mj,mj)). При цьому слід мати на увазі, що з одного боку функціональне перетворення j(Mj,mj) має забезпечувати зміну одного розряду Mmj при зміні будь-якого одного розряду Mj, а з іншого боку самі перетворення j(Mj,mj) мають виключати віднаходиження M'j № Mj : j(M'j,mj)= j(Mj,mj). Це може бути забезпечено, якщо функція j(Mj,mj) є або однозначною, або незворотною. Оскільки реалізація не зворотних функцій потребує значних обчислювальних ресурсів, то більш перспективним є використання в якості функцій j(Mj,mj) модифікації інформаційних блоків однозначних функцій. Для таких функцій виконується умова L(Mmj)=L(Mj)+L(mj), де L(Mj)- довжина інформаційного блока, L(mj)-довжина модифікуючого кода а L(Mmj)-довжина вхідного коду хеш-перетворення. Найпростішою функцією, яка задовольняє викладеним умовам являється конкатенація інформаційного блоку та його порядкового номеру в повідомленні (mj=j) : .

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

Модифікація кодів часткових хеш-сигнатур hj кожного j–го з n блоків Mj інформаційного повідомлення після їх формування в результаті хеш-перетворення hj=H(Mj) реалізується модифікуючою функцією hmj=f(hj,mj). Якщо J={h1,h2,…,hn} – множина n немодифікованих часткових хеш-сигнатур інформаційного повідомлення, то для виключення можливості віднаходження колізуючого повідомлення перестановкою блоків необхідно, щоб для функції модифікації виконувалась умова:

(2)

Функція f(hj,mj) повинна також зберігати статистичні властивості хеш-сигнатур: при зміні будь-якого з розрядів немодифікованої хеш-сигнатури hj має змінюватись така ж кількість розрядів модифікованої хеш-сигнатури hmj при будь якому значенні модифікуючого коду mj :

(3)

де HW(X)- вага Хемінга двоїчного коду Х (кількості одиниць в коді Х), а a- довільний вектор, довжина якого співпадає з hj. Останньому з наведених вимог задовольняють функції перестановки бітів. Процедура перестановки бітів має бути простою та ефективною в реалізації, а також задовольняти умовам (2).

В якості функції перестановки, що задовольняє наведеним вимогам і може бути практично використана для модифікації часткових хеш-сигнатур пропонується функція Р(Х,r) фрагментового циклічного зсуву. Операція фрагментового циклічного зсуву q-розрядного коду Х передбачає поділення його на m k-розрядних фрагментів Х=D1||D2||…||Dm, m=q/k. В свою чергу, кожний фрагмент Dj, j=1,…,m містить k двоїчних розрядів Dj=dj1,dj2,…,djk, dО{0,1}. Кожному j-тому з фрагментів Dj коду Х ставиться у відповідність одноіменний розряд m –розрядного коду U={u1,u2,…,um}, ujО{0,1}. Операція r-разових бітових перестановок коду Х - P(X,r) полягає в послідовній реалізації зсувів фрагментів Х, причому в кожній t –тій операції зсуву (t=1,…,r) приймають участь лише ті фрагменти, для яких відповідні розряди вектору U(t)= (t-1) mod (2m-1)+1 дорівнюють одиниці. Таким чином, базовою операцією перетворення Р(Х,r) є логічний зсув ліворуч на одну позицію k–розрядного фрагменту Dj для якого виконується умова uj=1 з заповненням розряду що звільнюється переносом cj в j –тий фрагмент: Dj<<cj. Визначивши через Q множину номерів фрагментів, які зсуваються: Q=Иj:uj=1, процедуру бітової перестановки на t–тому кроці можна формально представити у вигляді:

(4)

При виборі в якості функції f(hj,mj) модифікації часткових хеш-сигнатур розглянутої вище функції фрагментових зсувів - P(hj,mj) важливо забезпечити високу швидкодію реалізації модифікації. Вважаючи на те, що запропонованій функції фрагментарного зсуву притаманна властивість P(hЕt,y)=P(h,y)ЕP(t,y), то модифікацію всіх раніше сформованих часткових сигнатур можна реалізувати одночасно. Зокрема, при використанні в якості модіфікуючого коду для j-тої часткової хеш-сигнатури різниці n-j, тобто при mj=n-j, процес модифікації на кожному кроці всіх раніше обчислених часткових хеш-сигнатур може виконуватися одночасно.

При цьому код повної хеш-сигнатури формується рекурсивно в відповідності з наступним виразом: .При практичному використанні запропонованого перетворення для 160-розрядної хеш-сигнатури SHA-1 можуть бути розглянуті варіанти її поділення на 5 32-розрядних фрагментів, 10 16-розрядних фрагментів та 20 байтових фрагментів. Періоди повторення перестановок при фрагментарному циклічному зсуві для поділення 160-розрядної хеш-сигнатури на 5, 10 та 20 фрагментів становлять відповідно 231Ч120=3720, 21023Ч60=61380 і 21048575Ч495”5Ч108. Таким чином, при розділенні на 10 и 20 фрагментів виконання умови (2) забезпечується при довжині повідомлення відповідно 3.74 Мбайт та 31.68 Гбайт.

Іншим шляхом для унеможливлення віднахождення колізій з використанням блокових маніпуляцій при незалежному обчисленні часткових хеш-сигнатур є використання асиметричних функцій y(h1,h2,…,hn) для формування повної хеш-сигнатури по кодам часткових хеш-сигнатур:.

Умова асиметричності полягає в тому, що для будь-якої пари часткових хеш-сигнатур hk№ht, t,kО{1,…,n} виконується нерівність y(h1,…,hk-1,hk,hk+1, ,…,ht-1,ht,ht+1,…,hn) № y(h1,…,hk-1, ht, hk+1,…, ht-1, hk,ht+1,…,hn), тобто функція y міняє своє значення при зміні порядку слідування компонент, на яких вона визначена. Крім того, функція y має зберігати диференційні властивості повної хеш-сигнатури: при інвертуванні будь-якої підмножини розрядів однієї хеш-сигнатури за умови що інші залишаються сталими, має, в середньому, змінюватися відповідна кількість розрядів повної хеш-сигнатури.

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

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

Стандартами ISO передбачено ряд тестів для оцінювання рівня захищеності даних алгоритмами різних класів. Практична реалізація цих тестів потребує значних обчислювальних ресурсів і тому актуальною є задача розробки ефективних в обчислювальному плані процедур їх реалізації. Зокрема найбільш ресурсоємким для класу потокових алгоритмів є передбачений стандартами ISO тест на визначення складності відтворюючої моделі фрагменту псевдовипадкової двійкової послідовності S ={s1,s2,...,sn}, sjО{0,1}, j=1,...,n, причому довжина n визначається кількістю бітів послідовності, яка потенціально, виходячи з конкретних умов практичного застосування може виявитися у розпорядженні сторони, що виконує криптоаналіз. Для оцінки складності послідовності S найчастіше використовується складність лінійної моделі L(S)– тобто розрядність зсувного регістру з лінійною булевою функцією зворотного зв'язку, який здатний відтворити послідовність S. При цьому послідовність вважається повністю випадковою, якщо L(S)”n/2. Класичний алгоритм Berlekamp-Massey одержання оцінки лінійної складності потребує для реалізації значних ресурсів ЕОМ, пропорційних n2.

В роботі пропонується для оцінки складності послідовності S нелінійну відтворюючу модель – зсувний регістр з нелінійною функцією зворотного зв'язку, який здатен відтворювати задану послідовність S і, відповідно, складність M(S) послідовності визначається через його мінімальну розрядність. Теоретично доведено, що математичне очікування верхньої границі складності M(S) такої моделі для повністю випадкових послідовностей визначається формулою:

(5)

Показано, що середньоквадратичне відхилення нелінійної оцінки складності не перевищує 0.5Чlog2n. Таким чином, на відміну від лінійних моделей стохастичних двійкових послідовностей, складність яких пропорційна n, нелінійна оцінка складності пропорційна log2n, що вимагає суттєво менших ресурсів при реалізації запропонованих моделей на ЕОМ.

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

В формалізованому вигляді алгоритм передбачає представлення кожної h–тої вершини vh дерева G у вигляді трьох компонент : vh={ th, p0h, p1h }, де th – номер біту з послідовності S, пов'язаний з вершиною vh, якщо ця вершина є кінцевою, p0h- номер наступної вершини дерева, перехід на яку виконується за нульовим значенням поточного біту послідовності S, відповідно p1h – номер вершини, перехід до якої відбувається з вершини vh за одиничним значенням поточного біту послідовності S. Якщо p0h = p1h = 0, то вершина є кінцевою, або термінальною. Сам алгоритм зводиться до наступної послідовності дій:

1. Визначити компоненти першої вершини v1, яка є коренем дерева G наступним чином: p01=2, p11=0, якщо s0 =0, інакше p01=2, p11=0.

2. Визначити компоненти вершин v1 v2 дерева G наступним чином: t1=0, t2 =1, p02 = p12 =0; визначити поточну кількість w вершин дерева : w=2, номер j вершини, з якого починається поточний фрагмент послідовності: j=1, установити поточне значення m складності : m=1.

3. Визначити зміщення k в поточному фрагменті послідовності: k=0 та номер q поточної вершини дерева наступним чином: q=1.

4. Якщо для z=Sj+k виконується pzq=0, то перейти на п.6.

5. Визначити поточною вершину q=pzq, якщо k=m-1 та Sj+k+1?Stq , то q=0. Перейти на п.7.

6. Додати вершину до дерева G: w=w+1, визначивши її компоненти наступним чином: p0w = p1w = 0, tw = j+k+1, з'єднати створену вершину w з поточною q: pzq=w, я якості поточної вершини розглядати новостворену вершину: q=w.

7. Перейти до наступного біту послідовності: k=k+1.

8. Якщо k<m, то перейти на п.4.

9. Якщо q=0, то перейти на п.11.

10. Установити j = j+1, перейти на п.12

11. Збільшити значення поточної складності: m=m+1, j=0.

12. Якщо j<n-m, то перейти на п.3, інакше кінець.

Алгоритм складається з послідовного аналізу n-М(S) фрагментів послідовності S, причому кількість операцій при аналізі кожного з них пропорца числу ярусів дерева, тобто log2n. Таким чином, затрати часу на побудову нелінійної моделі пропорційні nЧlog2n, що суттєво менше в порівнянні з алгоритмом Berlekamp-Massey, реалізація якого потребує затрат часу пропорційного n2.

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

Аналіз обчислювальних процедур найпоширеніших блокових алгоритмів DES, Rijndael, RC-6 та ГОСТ 28147-89 показав, що таблична реалізація булевих функціональних перетворень є неефективною при реалізації на FPGA-структурах, які мають порівняно невеликий об'єм внутрішньої пам'яті, притому що матриця логічних елементів використовуються не більше як на 20-30%. Виходячи з цього досліджено можливість реалізації нелінійних перетворень алгоритмів симетричної криптографії шляхом рекурсивного обчислення відповідних булевих функцій. Розроблено програмні засоби проектування рекурсивних логічних схем, за допомогою яких одержано відповідні схеми реалізації нелінійних перетворень для найпоширеніших алгоритмів цього класу. Аналіз одержаних результаті показав, що використання рекурсивних логічних схем з одного боку помітно підвищує ефективність використання вмонтованих схем FPGA-структур, з іншого, дозволяє розпаралелити реалізацію нелінійних перетворень. Експериментальні дослідження показали, що при реалізації DES на FPGA-матриці типу FLEX 10KE200 з використанням табличних перетворювачів швидкість криптограмфічної обробки становить 110 Мбіт/с., а при використанні паралельно-рекурсивного обчислення на тій же матриці – 880 Мбіт/с.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ

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

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

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

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

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

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

1. Корочкин А.В., Мустафа Акрам. Параллельные вычисления: АДА и JAVA // Вісник Національного технічного університету України ”KПI”. Інформатика, управління та обчислювальна техніка, – Київ: ВЕК+ – 1999. – № 32.– С. 137-145. ( Дисертантом проаналізовані можливості реалізації паралельних обчислень в системах захисту інформації).

2. Марковский А.П., Мустафа Акрам Ареф Найеф, А.В. Бойко. Об одном подходе к определению сложности случайных и псевдослучайных двоичных последовательностей // Вісник Національного технічного університету України ”KПI”. Інформатика, управління та обчислювальна техніка, – Київ: ВЕК+ –2002.–№ 37.– С.120-129. ( Дисертантом запропоновано метод оцінювання рівня захищеності даних потоковими алгоритмами з використанням нелінійних відтворюючих моделей та алгоритм побудови таких моделей).

3. Мустафа Акрам Ареф Найеф. Статистическая оценка нелинейности и лавинного эффекта булевых функций // Вісник Національного технічного університету України ”KПI”. Інформатика, управління та обчислювальна техніка, – Київ: ВЕК+. – 2002 – № 38.– С. 106-113.(Дисертантом запропоновано експрес-метод визначення нелінійності булевих функцій та методику його використання для оцінювання стійкості алгоритмів захисту інформації до лінійного криптоаналізу).

4. Самофалов К.Г., Марковський О.П., Мустафа Акрам Ареф Найеф. Організація паралельного обчислення хеш-сигнатур для систем забезпечення цілісності інформації в комп'ютерних мережах // Наукові вісті НТУУ ”KПI”.- № 4.- 2002.- С.31-38. (Дисертантом запропоновано методи паралельного обчислення хеш-сигнатур без зменшення рівня їх захищеності).

5. Мустафа Акрам Ареф Найеф. Комплексное определение сложности двоичных случайных и псевдослучайных двоичных последовательностей. Системний аналіз та інформаційні технології. // Тези доповідей учасників IV Міжнародної науково-практичної конференції студентів, аспірантів та молодих вчених. - 2002.- Київ.- С.105. ( Дисертантом запропоновано метод комплексної оцінки криптостійкості потокових алгоритмів захисту інформації шляхом побудови нелінійної відтворюючої моделі ).

6. Марковський О.П., Мустафа Акрам Ареф Найеф. Нелінійні моделі стохастичних двійкових потоків в імітаційних системах проектування. // Тези доповідей на Міжнародній науково-технічній конференції “Проблеми математичного моделювання сучасних технологій”.- 2002. - м. Хмельницький. - С.78-79. (Дисертантом запропоновано алгоритм побудови нелінійних відтворюючих моделей стохастичних двійкових послідовностей).

АНОТАЦІЇ

Акрам Ареф Найеф Мустафа. Розробка засобів ефективного вибору та реалізації алгоритмів захисту інформації в комп'ютерних системах. – Рукопис.

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

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

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

Akram Aref Nayef Mustafa. Development of data protection algorithms effective selection and realization in computer systems aids.- Manuscript.

Thesis for a Ph.D. degree by specialty 05.13.13.–Computers, systems and networks. National Technical University of Ukraine “KPI”, Kiev, 2003.

Thesis is dedicated to a problems of research the ways for increase of efficiency of complex testing and realization of algorithms for data protection in computer systems and networks. Modification of hash-algorithms are suggested which make it possible to arrange independent parallel calculation of particular hash-signatures with maintaining the irreversibility level. For increasing of stream cipher testing efficiency a nonlinear reproduction models using for estimate of complexity has been proposed. A algorithm is developed for building of nonlinear reproduction model and determining of nonlinear complexity of binary sequences of length n. Time for is proportional of nЧlog2n.

Key words: parallel calculation, hardware implementation of data protection algorithm, Boolean functions, hash-algorithms, estimation of security level.

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

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

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

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

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

Предложена нелинейная воспроизводящая модель в виде сдвигового регистра с нелинейной обратной связью для оценивания уровня защищенности данных потоковыми алгоритмами. Теоретически получены математические параметры и критерии предложенной модели и на этой основе разработана методика ее использования для оценки сложности двоичных псевдослучайных последовательностей, используемых в потоковых алгоритмах. Предложен алгоритм построения нелинейной модели для определения сложности двоичной последовательности длиной n, реализация которого требует времени, пропорционального nЧlog2n, что значительно меньше в сравнении с алгоритмом Berlekamp-Massey, время реализации пропорционально n2.

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

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