Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
27
тернопільський національний економічний університет
Кінах Ярослав Ігорович
УДК 658.012.011.56:681.3.06
Методи паралельних обчислень та обґрунтування рівня криптографічного захисту інформації
в комп’ютерних мережах
05.13.13 –обчислювальні машини, системи та мережі
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Тернопіль - 2007
Дисертацією є рукопис.
Робота виконана у Тернопільському національному економічному університеті Міністерства освіти і науки України
Карпінський Микола Петрович,
Тернопільський національний економічний університет,
завідувач кафедри безпеки
інформаційних технологій.
Офіційні опоненти: доктор технічних наук, професор
Петров Олександр Степанович,
завідувач кафедри комп'ютерних систем і мереж,
Східноукраїнського національного університету
імені Володимира Даля;
доктор технічних наук, професор
Петришин Любомир Богданович,
завідувач кафедри інформатики, Прикарпатського національного університету ім. Василя Стефаника.
Захист дисертації відбудеться ’’’’жовтня 2007р. о 14 годині на засіданні спеціалізованої вченої ради К 58.082.02 Тернопільського національного економічного університету за адресою: 46009, м. Тернопіль, вул. Львівська 11, тел. (0352) 53-39-82.
З дисертацією можна ознайомитись у бібліотеці Тернопільського національного економічного університету за адресою: 46009, м. Тернопіль, вул. Львівська 11.
Автореферат розісланий "18 ’’вересня 2007 р.
Вчений секретар
спеціалізованої вченої ради Яцків В.В.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Сучасні комп’ютерні мережі є швидкісними та забезпечують високу продуктивність роботи під час обробки і збереження інформації. Проте вони потребують надійного захисту, оскільки із зростанням швидкодії мережі скорочується час виконання паралельної реалізації криптоаналітичних алгоритмів, це дає можливість несанкціонованого доступу в комп’ютерних мережах.
Визначний вклад у розвиток комп’ютерних мереж та криптоаналізу внесли: Горбенко І.Д., Долгов В.І. удосконалили мережні методи криптоаналізу, Широчин В.П., Тарасенко В.П. запропонували оригінальні методи криптографічного захисту інформації, Кожем’яко В.П., Жуков І.А., Воєводін В.В. розвинули теорію паралельної обробки інформації. Мельникова О.А., Качко О.Г., дослідили сучасні асиметричні методи захисту інформації у комп’ютерних мережах, Задірака В.К. розробив методи та удосконалив засоби захисту інформації, A. Лєнстра дослідив мережні засоби криптоаналізу, Дж. Джонсон запропонував оригінальний синтез різних типів алгоритмів шифрування в комп’ютерних алгоритмах. В. Глушков, М. Вигодський, Дж. Хопкрофт, М. Глибовець, Р. Стівенс розвинули теорію комп’ютерних алгоритмів, удосконалили методи паралельних обчислень. Проте дослідження в цьому напрямі не втрачають своєї актуальності оскільки розв’язок задачі визначення стійкості криптосистем ресурсами мереж з різними технічними характеристиками, дозволяє захистити комп’ютерні мережі від несанкціонованого доступу.
Слід зазначити роботу мереж на основі використання АТМ технології. Найбільш перспективними є ІР та MPLS технології. Незалежно від лідерства, обидві технології будуть співіснувати протягом низки років. Для швидкого проведення криптоаналізу в Україні потрібно якомога активніше формувати мультисервісну пакетну магістральну мережу загального користування, а також мультисервісні пакетні мережі доступу. Безпосередня консолідація мережі має бути ефективною там, де переважна частина мережі є цифровою. Цифрові станції типу EWSD, 5ESS, 1000E-10 мають високу масштабованість і дозволяють за потреби збільшити свою потужність для під’єднання нових абонентів. Окрім того, фірми-виробники розробили варіанти доповнення своєї продукції обладнанням NGN (інформаційними та сигнальними шлюзами, їх контролерами та ін.), тому модернізація, що відбувається зараз в Україні, сприяє переходу до мереж типу NGN.
Актуальною науково –технічною задачею є обґрунтування та дослідження рівня криптографічного захисту інформації в комп’ютерних мережах. При цьому особливої значимості набуває задача ефективного захисту від можливої атаки криптоаналітиків на основі паралельних комп’ютерних алгоритмів.
Зв’язок роботи з науковими програмами, планами, темами. Напрямок виконаних досліджень та дисертаційних розробок безпосередньо пов’язаний з науково –дослідницьким напрямком кафедри “Безпека інформаційних технологій” Тернопільського національного економічного університету. Результати, отримані в дисертаційній роботі, використано при виконанні держбюджетної науково-дослідної роботи на тему "Багатоканальні процесорні ядра реалізації симетричних блокових алгоритмів шифрування" (номер державної реєстрації 0101U002363), що виконувалась у Тернопільській академії народного господарства та у спільній україно –італійській науково –дослідній роботі на тему “Розробка web –базованої вимірювальної системи з розподіленим інтелектом” (номер державної реєстрації 0104U006975), що виконувалась у 2006 р. в Тернопільському державному економічному університеті.
Мета і задачі дослідження. Метою досліджень є підвищення захисту комп’ютерних мереж на основі обґрунтування рівня криптографічного захисту та удосконалення методів паралельних обчислень у комп’ютерних мережах шляхом скорочення часу криптоаналізу на основі розподілених обчислень.
Дана робота являє собою комплексний теоретичний аналіз і створення нової сучасної мережевої обчислювальної технології та обґрунтування рівня стійкості криптографічних систем, криптоаналіз котрих базується на розв'язанні задач факторизації, дискретного логарифмування та підвищенні ефективності розв'язання задач в області чисельних методів, пов'язаних з великим обсягом обчислень. Розробка паралельних алгоритмів криптоаналізу є одним з перспективних аспектів створення надійних алгоритмів шифрування інформації у комп’ютерних мережах.
Для досягнення поставленої мети необхідно ефективно розв‘язати наступні взаємопов‘язані задачі:
) аналіз, вибір та раціоналізація методів дослідження комп’ютерних мереж для обґрунтування рівня стійкості асиметричних систем шифрування;
) подальший розвиток алгоритму оцінки рівня стійкості асиметричних систем шифрування на основі використання алгоритму загального решета числового поля (ЗРЧП);
) дослідження та подальший розвиток методів факторизації чисел багатократної точності, створення засобів їх практичної реалізації;
) створення високопродуктивної обчислювальної структури для паралельної реалізації алгоритму ЗРЧП;
) формування правил оптимізуючих перетворень для паралельної мережної реалізації алгоритму ЗРЧП;
) дослідження у комп’ютерних мережах отриманої оцінки стійкості асиметричних алгоритмів.
7) формулювання рекомендацій для підвищення рівня криптографічного захисту комп’ютерних мереж.
Об'єкт дослідження –комп’ютерні мережі для криптоаналізу асиметричних систем шифрування інформації на основі використання алгоритму ЗРЧП.
Предмет дослідження –визначення складності виконання паралельного мережного криптоаналітичного алгоритму, що дозволить оцінити рівень стійкості асиметричних систем шифрування інформації RSA та Ель-Гамала.
Методи дослідження. Для проведення поставлених в даній роботі досліджень, використовуються результати з таких областей знань: комп’ютерні системи та мережі та теорія інформації для обґрунтування рівня захисту мереж; для дослідження та аналізу криптографічних перетворень - теорія чисел та алгебра Евкліда; при досліджені методів криптоаналізу та організації розподілених обчислень - лінійна алгебра, теорія складності та теорія Галуа.
Наукова новизна отриманих результатів. Під час досліджень отримано такі результати:
- отримала подальший розвиток мережна криптоаналітична система обґрунтування стійкості асиметричних систем шифрування на основі використання методу ЗРЧП, що дозволяє оцінити швидкість виконання криптоаналізу асиметричних систем шифрування;
- досліджено удосконалений метод криптоаналізу на основі організації високопродуктивної мережевої обчислювальної структури, орієнтованої на сучасну інтегральну технологію для суперрідких матриць, які представлені системами алгебраїчних рівнянь або конгруенцій великої розмірності шляхом визначення адекватних можливостей ресурсів мережі для конкретної криптоаналітичної підзадачі, це дозволяє, на відміну від існуючих методів, оцінити верхні границі можливостей мережного криптоаналізу, який може бути реалізований без використання суперкомп'ютерів для матричних операцій алгоритму ЗРЧП;
- вперше виведено правила оптимізації для блокових методів розпаралелювання операцій алгоритму ЗРЧП, за допомогою котрих можна виключити непродуктивні перетворення при декомпозиції алгоритму ЗРЧП, що значно підвищує швидкодію криптоалгоритму;
- удосконалено математичну модель паралельної роботи розподіленої обчислювальної системи шляхом доповнення її додатковим технічним параметром, що дозволяє підвищити точність оцінки прискорення паралельного виконання алгоритму;
Практичне значення одержаних результатів. Отримані результати дисертаційних досліджень, реалізовані на ВАТ Тернопільський радіозавод "Оріон". За результатами проведених досліджень впроваджено метод розрахунку стійкості асиметричних криптосистем у локальній мережі радіозаводу, що дозволяє розв'язувати задачу знаходження закритого ключа за відкритим у комп’ютерних мережах, а також оцінювати якість ключового матеріалу асиметричних систем шифрування. Запропоноване розподілене програмне забезпечення зменшує час виконання алгоритму ЗРЧП. Розроблено програмне забезпечення, яке дозволяє виконувати алгоритм ЗРЧП паралельно на N комп'ютерах.
Теоретичні та експериментальні результати досліджень впроваджено у навчальний процес кафедри безпеки інформаційних технологій Тернопільського національного економічного університету з дисциплін “Захист інформації в комп’ютерних системах” і “Комп’ютерна криптографія”. Результати впроваджень підтверджуються відповідними актами.
Особистий внесок здобувача. Дисертаційна робота є результатом самостійної роботи автора. У працях, опублікованих у співавторстві, здобувачу особисто належать: в роботі [1] висвітлена актуальність удосконалення методів захисту інформації в комп'ютерних системах і мережах. Запропоновано алгоритми керування ключами, що дозволяє забезпечити нормовані рівні технічного захисту інформації в комп'ютерних мережах. В роботі [2] проведено криптоаналіз із використанням методу ЗРЧП, що дозволяє одночасно визначити таємний ключ системи шифрування RSA. В роботі [3] проведено порівняльний аналіз методів квадратичного решета та ЗРЧП. В роботі [4] проілюстровано і проаналізовано впровадження запропонованої ідеї паралельної обробки розріджених матриць великої розмірності, що виникають в процесі виконання алгоритму ЗРЧП. В роботах [5, 6] проаналізовано застосування та переваги алгоритму RSA у сучасних комп’ютерних мережах. В [7, 8] визначено обчислювальну складність криптоаналізу асиметричних алгоритмів. У роботі [10] удосконалено розпаралелення матричних операцій. В [11] пропонується використання оптоволоконної техніки для скорочення часу виконання етапу просіювання алгоритму ЗРЧП у комп’ютерних мережах. В одноосібній статті [12] досліджено ресурси сучасних комп’ютерних мереж для обґрунтування стійкості асиметричних криптоалгоритмів.
Апробація результатів дисертації. Результати досліджень, що включено до дисертації оприлюднено:
1) на міжгалузевому міжрегіональному семінарі "Технічні засоби захисту інформації", Харків, березень 2000р.;
) на міжгалузевому міжрегіональному семінарі "Технічні засоби захисту інформації", Львів, березень 2000р.;
) на другій науково-технічній конференції "Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні", Київ, квітень 2000р.;
) на міжнародній науково-практичній конференції "Проблеми впровадження інформаційних технологій в економіці та бізнесі", Ірпінь, травень 2000р.;
) на науково-технічній конференції "Прогресивні матеріали, технології та обладнання в машино- і приладобудуванні", Тернопіль, травень 2000р.
) на міжнародній науково-практичній конференції “IDAACS'2003”, Львів, вересень 2003р.
) на науковому семінарі „Проблеми інформатики та керування”, Київ, березень, 2005р.
) на другій міжнародній науково –технічній конференції “Світлотехніка й електроніка: історія, проблеми, перспективи”, Тернопіль, травень 2005р.
) на науковій конференції професорсько-викладацького складу “Економічні, правові, інформаційні та гуманітарні проблеми розвитку України в пост стабілізаційний період”, Тернопіль, квітень 2006р.
) на науковій конференції професорсько-викладацького складу “Економічні, правові, інформаційні та гуманітарні проблеми розвитку України в пост стабілізаційний період”, Тернопіль, квітень 2007р.
Публікації. Результати, отримані за час досліджень, опубліковані в дванадцяти наукових роботах, з них 8 статей в наукових фахових виданнях, чотири з яких є одноосібними, 4 тези доповідей на конференціях.
Структура дослідження. Дисертація складається з вступу, переліку умовних скорочень, чотирьох розділів, висновків, переліку використаних джерел та додатків. Основний зміст викладений на 137 сторінках тексту, 45 рисунків, 5 таблиць, бібліографія з 102 найменувань та додатків загальним обсягом 24 сторінки.
У вступі обґрунтовується вибір теми та її актуальність, визначаються об’єкт та предмет дослідження, мета та завдання роботи, методи дослідження, вказано теоретичне та практичне значення здобутих результатів.
У першому розділі подано критичний огляд літератури за темою, вибір напрямків досліджень. Висвітлено взаємозв’язок алгоритму RSA з безпекою комп'ютерних мереж. Зроблено аналіз швидкодії та перепускної здатності сучасних комп’ютерних мереж. Стійкість розглядуваних систем шифрування RSA і Ель-Гамала оцінюється на основі використання перспективного методу ЗРЧП, що розпаралелюється на блоки і кожен блок реалізується на окремому комп'ютері. Аналіз показав, що найбільш перспективним і динамічним напрямком збільшення швидкості розв'язання прикладних задач є широке впровадження принципу паралелизму в роботу обчислювальної системи. Зроблено постановку задачі дослідження та вибір перспективних методів криптоаналізу у комп’ютерних мережах. Задачі факторизації алгоритму RSA від RSA-768 до RSA-2048 залишаються не розв’язаними. Оскільки деякі методи факторизації можна розпаралелити, зокрема метод решета числового поля, то розповсюдження персональних комп'ютерів веде до дискредитації системи шифрування RSA. Збільшення довжини ключа компенсує будь-які удосконалення алгоритмів факторизації. Відкритим залишається питання верхньої межі асимптотичної оцінки часу роботи алгоритмів факторизації у мережі.
У другому розділі, використовуючи метод ЗРЧП, удосконалено паралельний метод розрахунку надійності системи шифрування RSA. Удосконалення полягає у оптимізації етапу вибору поліному алгоритму ЗРЧП, скороченні часу просіювання розрідженої матриці, зменшенні кількості групових операцій алгоритму ЗРЧП, скорочені матричних операцій. Показано, що удосконалення апаратних засобів комп’ютерних мереж підвищує рівень стійкості згаданих вище систем шифрування інформації.
Дослідження методу загального решета числового поля показали, що для модуля криптографічного перетворення довжиною менше 60-ти десяткових знаків доцільно використовувати поліном третього степеня:
. (1)
Коли довжина числа більша 60- ти і менша 180-ти десяткових знаків, то степінь полінома (1), за якого кількість групових операцій найменша, дорівнює п'яти.
Доведено, що при виборі цілого числа і, такого, що та виконується рівність , коефіцієнти полінома f(x) знаходяться в межах .
Запропоновано використовувати критерій Ензейштейна для формування незвідного поліному (1) над кільцем цілих чисел. Проведено чисельні експерименти на ЕОМ з алгоритмом формування поліномів, що дозволило визначити оптимальний поліном f(x).
На діаграмі (рис. 1) представлені дані про кількість відсіяних векторів за допомогою удосконаленого та класичного алгоритмів формування поліному. У першому випадку з матриці H, порядок якої 10, відсіяно приблизно однакову кількість векторів обома методами відповідно. Аналогічна ситуація для другого та третього випадків, де розмірності матриць 10 та 10. Найбільший ефект спостерігається у п’ятому випадку, коли сформований поліном (1) за допомогою критерію Ензейштейна відсіює значно більшу кількість векторів.
Рис. 1. Порівняння поліномів за кількістю відсіяних векторів
Отже дослідження показали, що на практиці доцільно скористатися критерієм Ензейштейна, оскільки зменшено кількість операцій алгоритму ЗРЧП на 6%.
На етапі просіювання алгоритму ЗРЧП, використовуючи низку тверджень з теорії Галуа, досліджено властивості відображення алгоритму ЗРЧП. Показано, що відображення можна представити групою підстановок. Оскільки етап просіювання криптоалгоритму є трудомістким, то для його реалізації доцільно використовувати електронно–оптичні прилади, які працюють зі швидкістю обмеженою тільки доступними електронно–оптичними компонентами. Змоделюємо роботу такого приладу:
, (2)
де Z –функція, сформована за допомогою методу вагових коефіцієнтів та є безрозмірною величиною, що показує у скільки разів зменшується час виконання удосконаленого алгоритму, порівняно з його традиційною реалізацією;
N –кількість робочих станцій;
k- кількість підзадач.
Деяка частина сигналів відсіюється та формує на приймачі просіяну матрицю. Система рідкокристалічних клапанів складається з окремих комірок, у яких розміщено рідкий кристал. Залежно від його стану промінь змінюється, таким чином виконується операція просіювання. Графічне представлення результату експерименту, згідно моделі (2), розміщено на рис. 2:
Рис. 2. Процес просіювання алгоритму ЗРЧП
З графіка видно, що за наведеної реалізації алгоритму час його виконання значно зменшується при довільній кількості процесорів, та підзадач. За такої реалізації цього етапу час його виконання зменшується у 7 разів.
Запропоновано алгоритм формування оптимального ідеалу виду , де - корінь многочлена ; a, b –цілі числа. Суть його полягає у формуванні матриці W, кожний рядок котрої –множина всеможливих розв’язків конгруенції і кожен елемент матриці є квадратичним лишком за модулем р, для конкретної норми р ідеалу виду . Відокремлюючи множник елемента ідеалу, котрий є квадратичним лишком за модулем р, зменшено кількість групових операцій алгоритму ЗРЧП на 8%. При цьому стартова точка решета змінюється і збільшується кількість "відсіяних" векторів по базі .
Складність даного етапу оцінюють виразом
exp(5n+134n+35n+17n+25n+27), (3)
де n –довжина асиметричного ключа.
Після удосконалення він набуде виду:
exp(5n-33n-23n-45n-5n+27). (4)
Порівняємо удосконалений алгоритм (ряд 2) з відомим (ряд 1) рис. 3 на основі моделей (3) та (4).
Рис. 3. Зменшення кількості групових операцій алгоритму ЗРЧП
З графіка видно, що на основі використання вищезгаданої теореми можна відокремлювати множник від елементів ідеалу, завдяки чому зменшиться кількість групових операцій алгоритму ЗРЧП на 5% (рис 3, ряд 2). Очевидно, що стартова точка решета зміниться і збільшиться кількість "відсіяних" векторів по базі . Отже, аналізуючи всі корені многочлена, можна зменшити кількість групових операцій алгоритму ЗРЧП за рахунок формування оптимального ідеалу.
Дослідження показали, що обробку матриці Н можна проводити без використання суперкомп’ютерів, це дозволяє проводити всі етапи криптоаналізу на персональних комп’ютерах, які під’єднані до мережі, тобто нарощувати потужність системи не за рахунок підвищення продуктивності окремої ЕОМ, а завдяки використанню масово розповсюджених комп’ютерів.
Під час дослідження роботи мережного криптоалгоритму використаємо математичну модель (5), сформовану під час реальних експериментів та екстрапольовану на масове розповсюдження обчислювальної техніки:
; ;
; ; (5)
,
де t, t –час бар’єрної синхронізації;
S S S- функції прискорення криптоалгоритму.
Результати експериментів показали, що під час виконання одного завдання час бар’єрної синхронізації дещо нижчий (крива 1), порівняно з тим випадком (крива 2), коли на одній робочій станції виконуються принаймні два процеси (рис 5).
На рис. 6 проілюстровано роботу паралельної системи, згідно моделі (5) крива 1. Крива 2 відображає роботу системи, що використовує правила оптимізації. Найефективнішу роботу можна спостерігати у третьому випадку (крива 3), коли використано правила оптимізації та ефект кешування одночасно.
Рис. 5. Час бар’єрної синхронізації Рис. 6. Прискорення алгоритму ЗРЧП
Таким чином, запропоновані удосконалення дозволяють скоротити час виконання алгоритму ЗРЧП загалом на 12%.
Досліджено міжпроцесорну взаємодію паралельної реалізації алгоритму ЗРЧП. Для усунення завад, таких, як перевантаження процесорів або комунікації мережі змоделюємо операцію декілька разів і виберемо середнє значення з отриманих даних. Нехай кількість типових алгоритмічних структур (ТАС) має порядок 10. Для дослідження цього процесу скористаємось відомою математичною моделлю:
, (6)
де PSi –імовірність під’єднання;
S –інтенсивність мережного трафіку;
TRi –час під’єднання до мережі;
TS –час латентності.
Тоді згідно з методикою визначення часу, наведеною у I розділі дисертації, отримані дані представимо у вигляді графіка залежності часу міжпроцесорної взаємодії від N, використовуючи модель (6), (рис 7).
Отже експеримент показав, що міжпроцесорна взаємодія значно впливає на час роботи криптоаналітичного алгоритму, тому необхідно її враховувати під час оцінки стійкості системи шифрування RSA, доповнити математичну модель параметром, що враховує міжпроцесорну взаємодію, оскільки ігнорування цього процесу призведе до неправильних результатів досліджень в цілому.
Алгоритм ЗРЧП розбито на типові алгоритмічні структури, виконано їх декомпозицію. Дослідження показали, що на структурі під назвою “розділяй і володій”, котра здійснює декомпозицію вихідної задачі на підзадачі, знаходяться розв’язки підзадач. Наступна комбінація часткових розв’язків системи лінійних алгебраїчних рівнянь (СЛАР) оптимально розв’язується методом Гауса.
В цілій низці випадків роботи алгоритму ЗРЧП ефективнішою є схема обчислень і відповідна їй структура, в основу котрої покладене дублювання послідовних обчислень, оскільки економиться час на виконання обміну інформацією. В цій структурі відсутні витрати на декомпозицію та збір даних, відповідні проектори є тотожними функціями, а послідовна функція співпадає з паралельною.
Точність отриманого розв’язку за такої організації обчислень на рівні крупномодульного розпаралелювання блоків не відрізняється від точності послідовних алгоритмів даного методу.
Для визначення оптимальної типової алгоритмічної структури (ТАС) доцільно порівняти їх обчислювальну складність. Для цього скористаємось відповідними математичними моделями:
O(N) = N-23N+N-17;
O(N) = N ln(N); (7)
O(N) = N ln(N).
Схематичне представлення чисельних експериментів дозволить порівняти складність виконання криптоалгоритму на різних структурах, на основі моделі (7), рис. 8.
Рис. 8. Складність виконання криптоалгоритму на різних структурах
Дослідження показали, що коли кількість процесорів N не перевищує 1378 штук, то найефективнішою є структура типу “застосувати до всіх” (крива 1). Для 1378 < N < 3173 доцільно скористатися редукцією (крива 2), при 1378<N оптимальної роботи можна досягти на структурі типу “розділяй та володій”, оскільки складність її реалізацій в останньому випадку є найменшою (крива 3).
Сформульовано правила оптимізації розпаралелення матричних операцій методу ЗРЧП:
COMP(TAS(matrix)[dZ(Hi)], TAS(gather)[ Hi]) → COMP(TAS(matrix), TAS(gather) [ Hi← id]),
COMP(TAS(matrix)[Hi], TAS(gather)[Wi]) → COMP(TAS(matrix)[ Hi ← id], TAS(gather) [Wi← id]),
де COMP - композиція типових алгоритмічних структур (ТАС) TAS та TAS;
matrix - функція, що виконує декомпозицію суперрідкої матриці Н;
gather - функція, що здійснює збір фрагментів структури, розташовуючи їх послідовно в процесі–колекторі;
Hi - нуль-підматриця суперрідкої матриці H;
Wi - нуль-підматриця зв’язку;
[s ← r] - підстановка виразу r замість всіх входжень виразу s;
id - нейтральна функція відносно декомпозиції.
Суть правил полягає у виключенні дублюючих декомпозицій та взаємообернених функцій.
Для дослідження ефективності використання правил оптимізації скористаємось математичною моделлю, сформованою за допомогою методу вагових коефіцієнтів. Вона показує кількість операцій, що буде спрощено:
. (8)
Графічне представлення результатів дослідження, згідно моделі (8), показано на рис 9.
Рис. 9. Ефективність використання правил оптимізації
Отже, значне підвищення ефективності спостерігається при роботі з великою кількісттю робочих станцій N та підзадач k, тому при зростанні кількості процесорів та підзадач значно підвищується ефективність правил оптимізації. Для N = 1 спостерігається збільшення ефективності, що відповідає послідовному виконанню криптоаналітичного алгоритму, котрий розбитий на k підзадач. Вертикальна область в площині (N, E) відповідає роботі високопродуктивного комп’ютера.
Запропоновано повну систему правил оптимізації, що дозволяє уникнути зайвих операцій передавання даних та усунути обчислення взаємо обернених функцій.
У третьому розділі на основі концепції розвитку Укртелекому запропоновано тришарову архітектуру паралельного криптоаналізу, а в ній реалізацію методу сумісного паралельного використання базових ресурсів комп’ютерних мереж. Це дозволить залучити до криптоаналізу максимальну кількість, в тому числі віддалених станцій, а також суттєво скоротити час та значно знизити вартість криптоаналізу по відношенню до розв’язку еквівалентних задач на суперкомп’ютерах.
Розроблено критерій ефективності роботи криптоаналітичної мережі:
, (9)
де ti –час роботи окремого ресурсу мережі;
ri –продуктивність окремого ресурсу мережі;
A та B нормовані значення критерію, що визначається експериментально для кожної конкретної мережі.
Під час нарощування продуктивності і малому часі роботи не спостерігається висока ефективність. Аналогічна ситуація має місце для великого значення часу та для малої продуктивності. Даний експеримент дозволив визначити оптимальні значення параметрівt та r.
Представимо результати експерименту у графічному вигляді, згідно (9).
Рис. 10. Оцінка ефективності роботи криптоаналітичної мережі
Дослідження функціоналу F(ti,ri) показали, що робота мережі є найефективнішою, для сумарної продуктивності рівній 746324, а сумарний час роботи ресурсів t= дорівнює 3721 мкс, що відповідає локальному максимуму поверхні (рис 10). Для більш детального дослідження руху точки Fopt розглянуто проекцію функціоналу F в координатах (F,G) (рис. 11), де параметр G = ti∙ri. Порівняно, згідно з цим параметром, ефективність використання суперкомп’ютерів та обчислювальних машин мережі, що працюють паралельно, при їх оптимальних параметрах, за допомогою наведеного критерію. Згідно супровідної документації високопродуктивної техніки, характерною ознакою роботи суперкомп’ютера є повільне зростання ефективності при збільшенні параметру G для задачі криптоаналізу асиметричних алгоритмів шифрування інформації.
Рис. 11. Порівняльний аналіз високопродуктивної техніки та ресурсів мережі
З рис. 11 випливає, що при зростанні кількості робочих станцій ефективність F зростає і досягає максимуму для G = 273. Лінія 1 характеризує потенційні можливості векторно–конвеєрних комп’ютерів типу CREY T90: їх доцільно використовувати для практичного криптоаналізу при G < 110, оскільки значення їхньої ефективності є більшою ніж для випадку мережі (крива 4). КолиG < 159, то спостерігається висока продуктивність масово–паралельних машин типу Intel Paragon, CRAY T3D/T3E (лінія 2). Найефективнішу роботу можна спостерігати при використанні паралельних комп’ютерів зі спільною пам’яттю для G < 237 або G >3 17 (лінія 3). На проміжку 237 <G <317 доцільно скористатися запропонованим мережним криптоаналітичним алгоритмом для визначення асиметричного ключа. Тут крива 4 досягає свого максимуму в точці max. Під час подальшого зростання параметру G ефективність роботи спадає тому, що значна кількість мережних ресурсів задіяна для організації обчислень.
Для того щоб визначити, наскільки ефективно використовуються обчислювальні ресурси, доцільно провести експерименти з ТАС. Суть дослідження полягає у одночасному виконанні цих експериментів на робочих станціях. Результатом буде час виконання ТАС на окремій робочій станції та ефективність каналів зв’язку, процесорів. На рис. 5 представлені графічно результати цього експерименту згідно з математичною моделлю:
;
(10)
,
де trs - час обробки інформації;
P - продуктивність роботи паралельного алгоритму.
Рис. 12 Залежність часу та продуктивності від кількості робочих станцій N
Для N, що дорівнює 500 і більше, значно зростає час обробки інформації, а продуктивність роботи паралельного алгоритму досягає максимуму і не збільшується під час подальшого збільшення числа N.
Дослідження показали, що згідно з даними аналізатора мережі типу Distributed Observer, передача даних по каналах зв’язку займає 8% від часу розв’язку поставленої задачі, час роботи серверів –%, а робочих станцій –%. Отже, подальше нарощення потужності обчислювальної системи доцільно виконувати за рахунок збільшення використання ресурсів робочих станцій.
У четвертому розділі проведено детальний аналіз розробленої обчислювальної системи. Досліджено ресурси системи, які необхідні для реалізації алгоритму ЗРЧП.
Дослідження показали, що за допомогою оптоелектронних засобів, котрі використовують рідкокристалічний клапан доцільно виконувати трудомістку операцію просіювання, що дозволяє значно швидше змінювати значення комірок решета. Система рідкокристалічних клапанів складається з окремих комірок, у яких розміщено рідкий кристал. Залежно від його стану промінь змінюється, таким чином виконується операція просіювання. Згідно з принципом суперпозиції променів в одному приладі може працювати три джерела і три приймачі одночасно, завдяки чому значно економляться обчислювальні ресурси.
Для ілюстрації цього процесу скористаємось відомою моделлю:
(11)
де V –швидкодія решета;
M –кількість комірок решета;
- час виконання підзадачі.
Графічне представлення роботи оптоелектронного решета представлено на рис. 13, згідно моделі (11).
Такі засоби криптоаналізу відрізняються від відомих перспективнішими часовими характеристиками.
Навести час роботи обчислювальної системи практично неможливо, оскільки загальний час роботи залежить від кількості доступних в мережі комп’ютерів та їх характеристик. Для ключа довжиною 1024 біт необхідно виконати арифметичних операцій у 52 мільйони більше, а також збільшити обсяг доступної пам’яті у 7200 разів в порівнянні з найбільш вживаним ключем довжиною 512 біт.
Під час обробки суперрідкої матриці методом Гауса використано блочний алгоритм розпаралелення. За допомогою чисельних експериментів визначено оптимальну кількість підматриць, що обробляються окремо методом Гауса, використовуючи таку математичну модель:
;
(12)
,
де k=;
;
;
;
;
;
- коефіцієнт зв'язку підсистем СЛАР;
ci - ширина i-го блокового рядка та i-го блокового стовпця;
S - прискорення алгоритму розпаралелення матричних операцій;
Ns –кількість підсистем СЛАР;
S;
- середнє арифметичне значення суперкроків обчислень.
Графічне представлення чисельних експериментів, згідно моделі (12) подано на рис. 14 та рис. 15.
Рис.14 Графік функції ефективності . Рис. 15 Графік функції прискорення S.
Збільшення кількості підсистем суперрідкої СЛАР за умови Ns>Nопт (Nопт –оптимальна кількість підсистем) не підвищує ефективність розв'язування, оскільки основна кількість операцій виконується при розв'язанні підсистеми зв'язку. Аналіз показав, що мінімальний недосяжний ключ для даної реалізації алгоритму ЗРЧП має довжину 1524 біти.
Тому в мережі доцільно використовувати ключі не менші, ніж 2048 біт. Доцільно також синтезувати асиметричні та симетричні алгоритми з плаваючими ключами, що мають короткий життєвий цикл.
ВИСНОВКИ
СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
АНОТАЦІЯ
Кінах Я. І. Методи паралельних обчислень та обґрунтування рівня криптографічного захисту інформації в комп’ютерних мережах. –Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 –обчислювальні машини, системи та мережі. –Тернопільський національний економічний університет, Тернопіль, 2007.
Дисертація присвячена визначенню рівня стійкості асиметричних криптоалгоритмів в комп’ютерних мережах на основі використання алгоритму ЗРЧП, що забезпечить конфіденційність та автентичність інформації. Дано рекомендації щодо вибору поліному алгоритму ЗРЧП для чисел багатократної точності різної довжини. В роботі алгоритм ЗРЧП розбито на типові алгоритмічні структури, виконано їх декомпозицію, сформульовано правила оптимізації для декомпозиції. Запропоновано засоби на основі використання розроблених правил оптимізації для обробки матриці, які суттєво зменшують час виконання цих операцій, а також час виконання алгоритму ЗРЧП, а їх реалізація підтверджує теоретичні розрахунки та адекватність запропонованих моделей. Розроблений принцип побудови оптоволоконного засобу криптоаналізу відрізняється від відомих перспективнішими часовими характеристиками, це дозволяє на практиці значно скоротити час етапу просіювання. Побудовано обчислювальну систему, що дозволяє реалізувати алгоритм ЗРЧП паралельно. Удосконалено математичну модель оцінки ефективності та прискорення виконання паралельного алгоритму. Це дозволяє скоротити час виконання криптоаналітичного алгоритму та точніше визначити рівень стійкості алгоритмів RSA та Ель - Гамала, а на практиці користуватися безпечними ключами.
Ключові слова: комп’ютерна мережа, криптоаналіз, шифрування, дешифрування, факторизація, алгоритм загального решета числового поля, RSA алгоритм.
АННОТАЦИЯ
Кинах Я.И. Методы параллельных вычислений и обоснование уровня криптографической защиты информации в компьютерных сетях. - Рукопись.
Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.13 –вычислительные машины, системы и сети, Тернопольский национальный экономический университет, Тернополь, 2007.
Диссертация посвящена определению уровня стойкости асимметричных криптоалгоритмов на основании использования алгоритма общего решета числового поля (ОРЧП), что обеспечит конфиденциальность и автентичнось информации в компьютерных сетях. Проанализировано современное состояние эффективности информационной безопасности компьютерных сетей. Выполнен анализ основных методов криптоанализа современных асимметричных алгоритмов шифрования информации. Сделан теоретический анализ информационной безопасности компьютерных сетей. Наведены основные направления развития вычислительной техники высокой производительности. Описаны перспективные методы факторизации чисел многократной точности.
В работе криптографическую атаку проведено на модуль криптографического преобразования асимметричных криптоалгоритмов. Дано рекомендации выбора полинома алгоритма ОРЧП для чисел многократной точности разной длины. Проведены эксперименты с всевозможными коэффициентами полинома, что дало возможность определить оптимальный полином.
Сокращено время этапа просеивания алгоритма ОРЧП. Предложено описывать преобразование просеивания с помощью подстановок, при реализации криптоалгоритма на оптико - электронной компьютерной системе, что сократит время просеивания в 7 раз.
Сокращено количество групповых операций алгоритма ОРЧП, что позволяет сократить сложность криптоаналитического алгоритма.
В работе алгоритм ОРЧП разбито на типичные алгоритмические структуры, исполнено их декомпозицию, сформулировано правила оптимизации для декомпозиции. Проведено программирование криптоаналитического алгоритма с массивным параллелизмом. Построено вычислительную систему, которая реализует алгоритм ОРЧП параллельно. Наведён способ организации распределённых вычислений. Проведён расчёт стойкости систем шифрования RSA и Ель-Гамала. Усовершенствовано математическую модель оценки эффективности и ускорения выполнения параллельного алгоритма. Исследовано эффективность организации параллельных вычислений при решении задач большой размерности. Это позволит сократить время исполнения криптоаналитического алгоритма и точнее определить уровень стойкости алгоритмов RSA и Эль –Гамала, а на практике пользоваться безопасными ключами.
Ключевые слова: компьютерная сеть, криптоанализ, шифрование, дешифрование, факторизация, алгоритм общего решета числового поля, RSA алгоритм.
ABSTRACT
Kinakh Y.I. Methods of parallel calculations and ground of level of cryptographic defence of information are in computer networks. –Manuscript.
The work for competition for a candidate degree of technical sciences by specialty 05.13.13 –Computers, systems and networks. Ternopil National Economical University, Ternopil, 2007.
This dissertation deals with the RSA encryption algorithm. Its safety is analyzed using the number field sieve method. The algorithm work results allow to define a define a secret key in a simple way.
The means of information protection within calculation system are analyzed in the dissertation the algorithms of protection lock construction and confidential information organization are described.
Work deals with the definition of the safety level of the cryptoalgorithm RSA and El-Gamala based on the usage of the algorithm Number Field Sieve (NFS) which provides confidentional and authentic information in computer networks. It suggests the choice polynom of the algorithm NFS for big numbers. In the work the algorithm NFS is divided into algorithmic structures. Their decomposition is done and the optimization rulers of decomposition are formulated. The calculated system is offered which allows the algorithm NFS to be applied parallel. It shortens the full filament time of the algorithm in order to define the level of the reliability of the algorithm RSA, El-Gamala and use the safe keys in practice.
Key words: computer networks, RSA algorithm, encryption, number field sieve, factorization.