Анотація до роботи:

Рамзі Анвар Саліба Сунна. Високопродуктивна реалізація протоколів захисту інформації на базі операцій модулярної арифметики. – Рукопис.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публікації автора:

1. Рамзи Анвар Салиба Сунна. Алгоритм модулярного умножения методом Монтгомери при фиксированном модуле // Вісник НТУУ “КПІ” Інформатика, управління та обчислювальна техніка. К., ТОО „ВЕК+”.- 2005.- №43.- C.42-53. (Дисертантом запропоновано розробка модифікації алгоритму модулярного множення з використанням редукції Монтгомері для сталого модуля, обчислювальна складність якого близька до теоретичного мінімуму і вдвоє менша в порівнянні з класичним алгоритмом Монтгомері ).

2. Самофалов К.Г., Рамзи Анвар Салиба Сунна, Романовский А.Е. Алгоритм ускоренного модулярного умножения чисел большой разрядности при фиксированном модуле // Проблеми інформатизації та управління. Збірник наукових праць. -К.,НАУ. - 2005.-Випуск 3(14).- C.121-128. (Дисертантом запропоновано новий алгоритм модулярного множення, що відрізняється від класичного табличним способом виконання модулярної редукції та забезпечує суттєве зниження обчислювальної складності за рахунок використання результатів передобчислень для малорозрядних мікропроцесорів, вбудованих мікроконтролерів та смарт-карт ).

3. Самофалов К.Г., Рамзи Анвар Салиба Сунна, Левчун Д.Ю. Ускоренная реализация модулярного экспоненцирования на малоразрядных микропроцессорах и встроенных микроконтроллерах // Проблеми інформатизації та управління. Збірник наукових праць: Випуск 4(15).-К.,НАУ, 2005.- C.144-153. (Дисертантом запропоновано метод прискореної обчислювальної реалізації модулярного експоненціювання на малорозрядних мікропроцесорах, мікроконтролерах та смарт-картах, який забезпечує вшестеро більшу продуктивність реалізації модулярного експоненціювання над числами великої розрядності в порівнянні з методом Монтгомері).

4. Рамзи Анвар Салиба Сунна, Чебанюк Е.В. Метод получения балансных булевых функций, соответствующих критерию строго лавинного эффекта // Вісник НТУУ “КПІ” Інформатика, управління та обчислювальна техніка. К., ТОО „ВЕК+”.- 2003. - №41.- C.133-140. (Дисертантом запропоновано підхід до використання функцій, що відповідають критерію лавинного ефекту для контролю помилок при виконання операцій модулярного множення над числами великої розрядності).

5. Стефанская В.А., Рамзи Анвар Салиба Сунна. Об одном методе ускоренного умножения на полях Галуа // Тези 6-ї міжнародної конференції ”Системний аналіз та інформаційні технології”. Київ, ННК ”ІПСА” -2005.- С.138. (Дисертантом запропоновано структури апаратних засобів для високопродуктивної реалізації операцій модулярного множення з використанням табличної пам’яті передобчислень).