Шаблоны фраз для автореферата
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
”КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”
Рамзі Анвар Саліба Сунна
(Йорданія)
УДК 004.4 (043.2)
ВИСОКОПРОДУКТИВНА РЕАЛІЗАЦІЯ ПРОТОКОЛІВ ЗАХИСТУ
ІНФОРМАЦІЇ НА БАЗІ ОПЕРАЦІЙ МОДУЛЯРНОЇ АРИФМЕТИКИ
Спеціальність 05.13.13 – Обчислювальні машини, системи та мережі
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Київ 2006
Дисертацією є рукопис.
Робота виконана в Національному технічному університеті України ”Київський політехнічний інститут” на кафедрі обчислювальної техніки.
Науковий керівник – член –кореспондент Національної Академії Наук
України, доктор технічних наук, професор
Самофалов Костянтин Григорович,
НТУУ ”КПІ”, радник ректора
Офіційні опоненти: доктор технічних наук, професор
Печурін Микола Капітонович,
Національний авіаційний університет, професор
кафедри обчислювальних машин, систем та мереж
кандидат технічних наук,
Алішов Надір Ісмаіл-огли,
Інститут кібернетики ім.В.М.Глушкова НАН
України, провідний науковий співробітник.
Провідна установа: Інститут проблем моделювання в енергетиці
ім. Г.Є.Пухова НАН України, відділ
спеціальних засобів моделювання
Захист відбудеться 16 жовтня 2006 р. о 14-30 годині на засіданні спеціалізованої ради Д 26.002.02 у НТУУ ”КПІ” (м. Київ, проспект Перемоги 37, корп.18,ауд.306)
Відзиви на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати на адресу: 03056, м. Київ, проспект Перемоги 37, вченому секретарю НТУУ ”КПІ”.
З дисертацією можна ознайомитися в бібліотеці Національного технічного університету України ”Київський політехнічний інститут”.
Автореферат розісланий 14 вересня 2006 р.
Вчений секретар
спеціалізованої вченої ради Д 26.002.02 Орлова М.М.
кандидат технічних наук, доцент
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Однією з домінуючих тенденцій сучасного етапу розвитку інформаційних технологій є інформаційна інтеграція на основі комп’ютерних мереж. Забезпечуючи якісно більш високий рівень розв’язання прикладних задач, інформаційна інтеграція розширюється на всі рівні комп’ютерної обробки інформації, включаючи вбудовані мікропроцесори та мікроконтролери, які на теперішній час складають більше половини термінальних пристроїв комп’ютерних мереж.
Важливою передумовою ефективної взаємодії обчислювальних терміналь-них пристроїв в комп’ютерних мережах є забезпечення високої продуктивності при реалізації ними існуючих мережових протоколів. Найбільш критичними з точки зору обчислювальної реалізації протоколів мережового обміну є операції модулярної арифметики, що виконуються над числами великої розрядності, яка значно перевищує розрядність процесорів. Такі обчислення передбачуються існуючими протоколами захисту інформації в мережах.
Для широкого класу протоколів, що використовують технологію відкритих ключів рівень захищеності прямо пов’язаний з розряд-ністю чисел, якими вони оперують. На теперішній час, для досягнення прийнят-ного для більшості застосувань рівня захищеності, необхідна довжина чисел становить 1024-2048 розрядів з перспективою її зростання в найближчі роки до 4096.
Зростання розрядності чисел, з якими оперують існуючі протоколи захисту інформації в мережах призводить до сповільнення їх реалізації на комп’ютерах загального призначення. З особливою гостротою ця проблема стоїть для малорозрядних вбудованих мікропроцесорів та мікроконтролерів.
З іншого боку, стала тенденція росту пропускної здатності каналів передачі даних комп’ютерних мереж вимагає адекватного зростання швидкості реалізації протоколів захисту інформації як на комп’ютерах загального призначення, так і на малорозрядних мікроконтролерах.
Наведені фактори визначають розробку нових підходів до прискорення програмної реалізації операцій модулярної арифметики при їх застосування в протоколах захисту інформації, як важливу та актуальну проблему, від вирішення якої значною мірою залежить ефективність локальних та глобальних комп’ютерних мереж.
Зв’язок роботи з науковими програми, планами, темами. Дисер-таційне дослід-ження проводилось в рамках держбюджетної теми ”Розробка цифрових систем обробки даних з високошвидкісними комутаторами” (номер держреєстрації 0102U000222).
Мета і завдання дослідження.
Метою роботи є підвищення продуктивності обчислення операцій модулярної арифметики над числами великої розрядності при реалізації протоколів захисту інформації в комп’ютерних мережах за рахунок розробки методів та алгоритмів, які враховують специфічні особливості виконання указано класу операцій в системах захисту інформації.
Об’єктом досліджень є обчислювальні процедури реалізації мультиплікативних операцій модулярної арифметики над числами великої розрядності при їх застосуванні в протоколах захисту інформації.
Предметом досліджень є способи, алгоритми та засоби підвищення продуктивності обчислення операцій модулярної арифметики при їх використані для реалізації протоколів захисту інформації в комп’ютерних мережах.
Основні задачі дослідження у відповідності до поставленої мети полягають у наступному:
1. Огляд протоколів та алгоритмів захисту інформації в комп’ютерних мережах, аналіз особливостей їх практичного використання, обґрунтування вимог до обчислювальних процедур їх реалізації.
2. Огляд алгоритмів модулярного множення та експоненціювання. аналіз можливостей підвищення продуктивності їх реалізації. Визначення напрямків досліджень виходячи з особливостей використання мультиплікативних операцій модулярної арифметики в протоколах захисту інформації.
3. Дослідження можливостей реалізації модулярної редукції при постійному модулі в рамках класичного алгоритму модулярного множення та розробка на цій основі алгоритму, який використовує передобчислення, що дозволяє зменшити обчислювальну складність модулярного множення.
4. Аналіз обчислювальних процедур алгоритму Монтгомері і розробка на цій основі модифікації модулярного множення Монтгомері для сталого модуля, обчислювальна складність якого зменшена за рахунок використання результатів передобчислень, що залежать від модуля.
5. Розробка алгоритму прискореного піднесення до квадрату з використанням модулярної редукції Монтгомері.
6. Розробка модифікації алгоритму модулярного множення Монтгомері при сталих співмножнику та модулі, який має меншу складність за рахунок використання результатів передобчислень.
7. Розробка методу прискореної обчислювальної реалізації модулярного експоненціювання при сталому модулі з використанням редукції Монтгомері.
Методи дослідження базуються на теорії імовірностей та математичної статистики, теорії булевих функцій та комбінаторики, теорії організації обчислювальних процесів, а також на використанні методів моделювання.
Наукова новизна одержаних результатів полягає в наступному:
- Розроблено новий алгоритм модулярного множення, що відрізняється від класичного табличним способом виконання модулярної редукції при сталому модулі і забезпечує суттєве зменшення обчислювальної складності за рахунок використання результатів передобчислень.
- Запропонована модифікація алгоритму модулярного множення Монтгомері для сталого модуля, обчислювальна складність якого близька до теоретичного мінімуму і вдвоє менша в порівнянні з алгоритмом Монтгомері.
- Розроблено метод прискореної обчислювальної реалізації модулярного експоненціювання з використанням редукції Монтгомері на основі запропонованих алгоритмів модулярного піднесення до квадрату і множення на сталий співмножник для малорозрядних мікропроцесорів, мікроконтролерів та смарт-карт, який забезпечує вшестеро більшу продуктивність в порівнянні з алгоритмом модулярного експоненцію-вання Монтгомері.
Практичне значення одержаних результатів результатів роботи визначається створенням на основі теоретично розроблених методів приско-рення обчислен-ня операцій модулярного множення та модулярного екпоненціювання відповідних програмних засобів, які реалізують ці методи. Найбільш практично вагомою є запропо-нований метод швидкої реалізації модулярного експо-неціювання, який базується на комплексному використанні запропо-нованих алгоритмів модулярного піднесення до квадрату та модулярного множення на постійне число і забезпечує шестрикартне зростання продуктивності реалізації протоколів обміну ключами, автентифікації віддалений користувачів та цифрового підпису абонентів комп’ютерних мереж.
Практичне використання запропонованих підходів до організації прискореного обчислення мультиплі-кативних операцій модулярної арифметики при їх застосуванні в мережових протоколах захисту інформації дозволяє суттєво підвищити продуктивність їх реалізації і, відповідно, ефективність викорис-тання в комп’ютерних мережах.
Особистий внесок здобувача полягає в теоретичному обґрунтуванні одержаних результатів, експериментальній їх перевірці та дослідженні, а також в створенні програмних продуктів для практичного використання одержаних результатів. У роботах, що написані в співавторстві, автору належать: [2] – розробка нового алгоритму модулярного множення, що відрізняється від класичного табличним способом виконання модулярної редукції та забезпечує суттєве зниження обчислювальної складності за рахунок використання результатів передобчислень для малорозрядних мікропроцесорів, вбудованих мікро-контро-лерів та смарт-карт, [3] – розробка методу прискореної обчислю-вальної реалізації модуляр-ного експоненціювання на малорозрядних мікропро-цесорах, мікроконтро-лерах та смарт-картах, який забезпечує вшестеро більшу продуктивність реалізації модулярного експоненціювання над числами великої розрядності в порівнянні з методом Монтгомері, [4] – розробка підходу до контролю помилок при виконання операцій модулярного множення над числами великої розрядності з використанням булевих перетворень спеціальних класів, [5] – розробка структур апаратних засобів для високопро-дуктив-ної реалізації операцій модулярного множення з використанням табличної пам’яті передобчислень.
Апробація результатів дисертації. Основні результати дисертації доповідались та обговорювались на:
1. V-й Міжнародній науково-практичній конференції Современные информа-цион-ные и электронные технологии., 17-21 травня 2004 р. м. Одеса.
2. VІ-й Міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених. Системний аналіз та інформаційні технології, 1-3 липня 2005 м.Київ.
Публікації Основні результати роботи викладені в 5 публікаціях, з них 4 статті - в провідних фахових виданнях.
Структура та об’єм роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків та додатків. Загальний обсяг роботи складає 143 сторінки, робота містить 8 малюнків, 10 таблиць та список використаної літератури на 95 найменувань, 2 додатки.
ОСНОВНИЙ ЗМІСТ
У вступі обґрунтована актуальність проблеми підвищення продуктивності реалізації протоколів, пов’язаних з захистом інформації в комп’ютерних мережах, в основі яких лежать мультиплікативні операції модулярної ариф-метики, що виконуються над числами, розрядність яких суттєво перевищує розрядність процесора. Особливо ця проблема актуальна для малорозрядних термінальних пристроїв комп’ютерних мереж. Сформульована мета роботи, основ-ні задачі досліджень, наведені головні нові наукові результати, одержаних в ході досліджень та їх практичне значення для сучасного етапу розвитку мережових технологій, одержаних результатів.
У першому розділі дисертації виконано аналіз протоколів захисту інформації в комп’ютерних мережах.
Основним алгоритмом, що лежить в основі значної частини протоколів захисту інформації є алгоритм шифрування RSA. Процес шифрування блоку Х повідомлення виконується у вигляді , а процес відновлення реалізується у відповідності з виразом: .
Широко використовується в протоколах захисту інформації алгоритм Ель-Гамаля. При шифруванні блоку Х повідомлення випадково вибирається ціле k і обчислюються , де g,M - частини ключа. Розшифру-ван-ня виконується у відповідності з виразом: .
В основі протоколів автентифікації користувачів мережі та перевірки автентичності повідомлень лежить стандартизований алгоритм цифрового підпису DSS. Автентифікація виконується за наступною схемою: користувач формує при заданих p,q,r, що є відкритою частиною ключа параметрах:
Числа r та s відсилаються системі, яка виконує обчислення:
Повідомлення М вважається автентичним, якщо виконується .
Проведений аналіз практичного використання протоколів захисту інформації в комп’ютерних мережах показав, що переважна їх більшість має за основу криптографічних властивостей важкорозв’язувані теорії чисел.
Відповідно, обчислювальної основою криптографічних механізмів, на яких базуються мережові протоколи захисту інформації є мультиплікативні операції модулярної арифметики над числами, розрядність яких становить 1024-4096. Основними обчислювальними опера-ціями вказаних протоколів є модулярне множення та модулярне експонен-ціювання.
Аналіз практичного використання протоколів, основаних на крипто-графічних алгоритмах несиметричного шифрування типу RSA, El-Gamal, алго-рит-му цифрового підпису –DSS показує, що їх ключі змінюються відносно рідко, оскільки їх відкрита частина ідентифікує абонентів комп’ютерної мережі. Відповідно, модуль М, що є частиною відкритого ключа, можна вважати постійним і зменшити, за рахунок цього, обчислювальну складність мульти-плікативних операцій модулярної арифметики.
Вважаючи на важливість ефективної реалізації протоколів захисту інформації, що базуються на операціях модулярної арифметики, до теперіш-нього часу запропоновано ряд алгоритмів, найбільш відомими з яких є класичний та Монтгомері.
При обробці чисел великої розрядності n на k-розрядному процесорі, число А представляється за основою b, де b – кількість k -розрядних чисел: b = 2k : А={as-1,…,a1,a0}, 0 aj < b, j{0,…,n-1}: . Базовою операцією модулярної арифметики в протоколах за-хис-ту інформації є модулярне множення: R=AB mod M, причому 2n-1 M< 2n, A<M, B<M. Кожне з чисел A, B і M скла-даються з s=n/k слів: , де aj, bj, mj – k-розрядні слова, j{0,…,s-1}.
Модулярне множення складається з обчислення добутку АВ та модулярної редукції – віднаходження залишку АВ по модулю М: AB mod M. Всі алгоритми модулярного множення відрізняються способом виконання модуляр-ної редукції.
В нотації мови С++ класичний алгоритм модулярного множення без деталізації способу реалізації процедури модуляр-ної редукції Reduce(X) може бути представлений у такому вигляді:
1. R = 0;
2. for ( i=0; i <= s-1; i ++)
{
2.1. Y = 0;
2.2. for ( j = 0; j <s; j ++ ) Y += (ai * bj ) << ( j *k);
2.3. R+= Reduce(Y) ;
2.4. if ( i < s -1 )
{
2.4.1. B <<= k ;
2.4.2. Reduce (B) ;
}
}
3. Reduce( R) ;
В класичному алгоритмі модулярна редукції виконується з вико-ристанням операції цілочисельного ділення 2k-розрядного діленого на k–розрядний подільник з одержанням части та залишку. З огляду на те, що операція ділення n–розрядних чисел на k–розрядному процесорі (n>>k) виконується доволі неефективно, реалізація редукції в класичному алгоритмі потребує (s+2.5) операцій процесорного множення і s операцій процесорного ділення.
Щоб уникнути операції ділення багаторозрядних чисел при реалізації модулярної редукції запропоновано ряд алгоритмів, найбільш відомими з яких є алгоритми Баретта та Монгомері.
Найбільш афективно модулярна редукція реалізується в алгоритмі Монтгомері: шляхом переходу від редукції за модулем М до редукції за числом, що є степенем 2.
Застосування модулярного множення за Монтгомері вимагає додаткових операцій, що виконуються до і після власне множення. На прак-тиці моду-ляр-не множення з використанням алгоритму Монтгомері доцільне лише я якості базової операції модулярного експоненціювання. При обчисленні XY mod M, множення виконується тисячі разів, проте додаткові операції виконуються лише до та після модулярного експоненціювання і, відповідно не мають суттєвого впливу на обчислювальну складність модулярного експоненцію-вання.
Вихідними даними для модулярного множення по Монтгомері являються: модуль M, співмножники А і В, а також попередньо обчислена модулярна інверсія M = - M-1 mod 2k. В процесі виконання алгоритму ітераційно формується n-розрядний код результату R=ABU mod M, де U – модулярна інверсія числа 2n за модулем M, тобто U = (2n)-1 mod M. Сам алгоритм Монтгомері можна представити з використанням нотацій С++ в наступному вигляді:
1. R = 0.
2. for ( j=0; j <= s-1; j++)
{
2.1. pj = (r0 + aj b0)M mod 2k;
2.2. R= ( R + ajB + pjM)/2k;
}
3. if ( R M) R = R – M.
Щоб отримати правильний результат XY mod M потрібно виконати додаткові обчислення над R : помножити одержаний результат на 2n mod M.
Проведений аналіз алгоритму Монтгомері показав, що його обчислювальна складність модулярного множення, що виконується за цим алгоритмом, без урахування додаткових перетворень близька до теорети-чного мі-ні-муму. Аналіз чисельних публікацій, присвячений розвитку ідей алгоритму Монтгомері значною мірою підтверджують цю оцінку.
Характеристики обчислювальної складності алгоритмів модулярного множення наведені в таблиці 1.
Таблиця 1. Кількість операцій процесорного множення та ділення, потрібних для обчислення AB mod M в різних алгоритмах модулярного множення.
Алгоритм | Кількість операцій множення для об-
числення АВ |
Кількість операцій множення для об- чис-лення залишку | Кількість опе-ра-цій ділення Класичний | s2 | s2 +2.5s | s | Баретта | s2 | s2 + 4s | 0 | Монтгомери | s2 | s2 + s | 0 |
Аналіз наведених даних свідчить про те, що при постійному модулі можуть бути ефективно модифіковані класичний алгоритм модулярного множення та алгоритм Монтгомері.
В другому розділі роботи пропонуються алгоритми модулярного множення з фіксованим модулем і зменшеною обчислювальною складністю. Один з них має за основу класичну схему модулярного множення, а другий являє собою модифікацію алгоритму Монтгомері.
В класичному алгоритмі процедура модулярної редукції Reduce(X) виконується над частковим добутком ajB та зсунутим на k розрядів ліворуч кодом множеного B. В обох випадках, довжина числа Х, над яким реалізується редукція не перевищує (s+1) k-розрядних слів або (s+1)k=(n+k) двійкових розрядів х0, х1, х2,…,хn+k-1:
Число Х може бути представлено у вигляді суми двох компонент: (n-1)-розрядного числа X, яке співпадає з n-1 молодшими розрядами Х і (n+k)-розрядного числа X, яке складається з (k+1) старших розрядів, співпадаючих з однойменними розрядами Х і n-1 молодших розрядів, що дорівнюють нулю:
Згідно з властивістю конгруентності для модулярної редукції, залишок X mod M може бути представлений у вигляді модулярної редукції суми залишків X та X:
В силу того, що старший, (n-1)-вий розряд модуля М дорівнює одиниці, а Х являє собою (n-1)-розрядне число, то X<M і, відповідно, Xmod M = X. Число X має тільки k+1 значущих розрядів (інші n-1 молодших роз-рядів X дорівнюють нулю). Таким чином, X і відповідно X mod M може приймати тільки 2k+1 різних значень. Всі можливі n-розрядні значення X mod M для відповідних значень X можуть бути попередньо обчислені та збережені в пам’яті у вигляді таблиці. Якщо позначити через Z двійковий код, що складається з (k+1) старших значущих розрядів X : а через T(Z) – n-розрядний код табличного значення T(Z) = X mod M, то процедура модулярної редукції Reduce(X) реалізується у відповідності з наступним виразом:
Обчислювальна складність реалізації модулярної редукції при цьому визначається щонайбільше двома операціями типу додавання над (n+k)–роз-ряд-ними числами: першої для обчислення T(Z)+X і другої для виконання віднімання (T(Z)+X)-M, якщо T(Z)+XM. Оскільки 0T(Z)+X<2M, для обчислення залишку (T(Z)+X) mod M потрібно не більше одного віднімання n-розрядних чисел. Виходячи з цього, час реалізації процедури модулярної редукції не перевищить 2(s+1)ta, при середньому значенні 1.5sta. Об’єм пам’яті, потрібний для зберігання попередньо обчислених всіх можливих значень T(Z) складає 2k+1n бітів або 2k+1s k-розрядних слів.
Запропонований підхід є особливо ефективним при реалізації моду-лярного множення на малорозрядних мікропроцесорах, мікро-контролерах та смарт-картах. В цьому випадку, об’єм пам’яті для зберігання резуль-та-тів передобчислень при постійному модулі виявляється доволі прийнятним з точку зору реалізації для більшості використань. Наприклад, для реалізації прискореного модулярного множення 1024-розрядних чисел на 8-розрядному мікроконтролері об’єм пам’яті становить всього 29128=216 байт (64 Кбайтів).
При реалізації запропонованого методу прискорення модулярного множення на процесорах розрядністю 16 и більше, об’єм потребуємої пам’яті суттєво зростає, що знижує ефективність застосування передобчислень.
Для зменшення об’єму табличної пам’яті результатів передобчислень T(Z) пропонується організувати її у вигляді декількох секцій.
Сутність пропонуємої організації таблиць передобчислень полягає в тому, що значення X розділяється на q складових: що мають розрядності відповідно n+r1, n+r1+r2, …, n+r1+…+rq, причому r1+r2+…+rq=k+1. Кожна i–та складова Xi (i=1,…,q) включає ri старших значущих розрядів, що співпадають з розрядами числа X ( h=0 для i=1 і h=r1+…+ri-1 для i>1), а інші молодші розряди дорівнюють нулю:
Тоді, в відповідності з властивістю конгруентності для модулярної редукції залишок X mod M може бути представлено у вигляді:
Для обчислення кожного із значень Xi mod M пропонується використати результати передобчислень, які виконуються для всіх мо-жливих кодів Xi. Оскільки кількість значущих (ненульових) розрядів в коді Xi дорівнює ri , то число різних значень Xi становить , а об’єм пам’яті для зберігання всіх можливих значень Xi mod M відповідно становить бітів. Якщо позначити через Zi двійковий ri–розрядний код, що містить тільки ri старших значущих розрядів Xi, то:
Якщо позначити через Ti(Zi) – n-розрядний код табличного значення Ti(Zi) = Xi mod M, то процедура модулярної редукції реалізується у відповідності з наступним виразом:
Загальний об’єм табличної пам’яті для зберігання T1(Z1),T2(Z2),…,Tq(Zq) становить бітів.
Використання багатосекційних таблиць передобчислень дозволяє суттєво зменшити об’єм пам’яті для їх зберігання. Наприклад, за умов наведеного вище прикладу реалізації прискореного множення 1024-разрядних чисел на 8-розрядному мікроконтролері при двосекцій пам’яті (q=2, r1 =5, r2=4), об’єм потрібної для зберігання таблиць пам’яті становитиме всього 1024(25+24)= 101048 біт або 6144 байт, що в 10.67 раз менше в порівнянні з односекційною організацією табличної пам’яті.
З іншого боку, використання багатосекційної організації таб-лич-ної памяті має наслідком збільшення часу виконання модуляр-ної редукції. Загальна кількість операцій процесорного додавання становить (q+1.5)(s+1).
Важливим аспектом аналізу ефективності запропонованого алгоритму модулярного множення є оцінка часових затрат на програмну реаліза-цію на k–розрядному процесорі и порівняння її з найефективнішим на сьогоднішній день алгоритмом Монтгомері.
Розроблений алгоритм прискореного модулярного множення на основі класичного, з використанням передобчислень включає s циклів. Кожний j-тий (j=0,…,s-1) з цих циклів реалізує обчислення ajB, віднаходження залишку R = ajB mod M, зсув В на k розрядів з наступною модулярною редукцією для віднаходження нового значення В: B=B2k mod M. Таким чином, процедура модулярної редукції на кожному циклі виконується двічі і потребує в сумі 3(s+1) операцій процесорного додавання. В свою чергу, обчислення часткового добутку ajB складається з s операцій процесорного множення ajbe, де індекс e послідовно приймає значення від 0 до s-1, і, в середньому, 3-х операцій процесорного додавання для добавлення 2k-розряд-ного результату множення ajbe к частковій сумі. Таким чином, програм-на реалізація модулярного множення за запропонованим алгоритмом на k-розрядному процесорі потребує s2 операцій процесорного множення та 3s2 + 7.5s+1.5 операцій процесорного додавання. При цьому, реалізація власне множення АВ потребує s2 операцій множення та 3s операцій процесорного додавання, а модульна редукція - 3s(s+1)+1.5(s+1) операцій типу додавання. Відповідно, значення середнього часу Т1 програмної реалізації модулярного множення при використанні однієї таблиці передобчислень визначається наступним виразом:
де tm - час виконання процесорного множення, ta -час операції процесорного додавання, w = tm/ta.
В порівнянні з алгоритмом Монтгомері, розроблений алгоритм забезпечує підвищити продуктивність програмної реалізації модулярного множення в d разів:
Для найбільш розповсюджених на практиці розрядностей (від 1024 до 2048) чисел, що використовуються при виконанні модулярного множення при реалізації протоколів захисту інформації та невеликої розрядності процесору (k=8), величина s є достатньо великою, так, що s2>>s, і коефіцієнт d прискорення може бути, з достатньою для порівняльної оцінки точністю, представлено у вигляді:
Результати проведених експериментальних досліджень показали, що використання запропонованого алгоритму модулярного множення дозволяє підвищити продуктивність програмної реалізації на 8-розрядному контролері в порівнянні з алгоритмом Монтгомері приблизно в 1.8 раз. При цьому складність програми за запропонованим алгоритмом приблизно в двоє менша в порівнянні з програмою, що реалізує алгоритм Монтгомері.
При використанні q-секційної организації таблиць передобчислень час Tq програмної реалізації модулярного множення за запропонованим алгоритмом збільшується в порівнянні з Т1 і визначається наступним виразом:
Коефіцієнт dq прискорення реалізації операції модулярного множення в порівнянні з алгоритмом Монтгомері визначається наступним чином:
Для приблизної оцінки числового значення коефіцієнта dq при великих значеннях s, для яких s2>>s, можна враховувати тільки відношення складових часу, що мають множник s2:
Проведений аналіз показав, що запропонований алгоритм модулярного множення доцільно використовувати в протоколах захисту інформації при виконанні одиночних операцій модулярного множення, що входять до складу алгоритмів Ель-Гамаля та DSS.
Другий, з запропонований алгоритмів прискореного модулярного множен-ня при фіксованому значенні модуля являє собою модифікацію алгоритму Монтгомері.
Аналіз операцій, що складають алгоритм Монтгомері показує, що в основному циклі має місце дублювання операції множення ajb0: воно виконується в п.2.1. та повторюється п.2.2 в процесі множення k–розряд-ного коду aj на n-розрядний код B={bs-1,…,b1,b0}. Це дублювання може бути виключено наступним чином. Розділимо код суми r0 + aj b0 на дві k-розрядні складові: gj = (r0 + aj b0) mod 2k и dj = (r0 + aj b0 - gj)/2k так, що pj = dj2k + gj. З урахуванням цього, pj = (dj2k + gj)M mod 2k = gjM mod 2k . Відповідно: pjM = gjМM - tM2k, де t – ціле число. В силу того, що , очевидно, що МM = c2k – 1, де c- ціле. Тоді pjM = gjc2k – gj - tM2k = hj2k –gj , причому hj = gjc - tM. З урахуванням цих перетворень, обчислення п.2.2. базо-вого алгоритму Монтгомери можуть бути представлені таким чином:
R являє собою (n-k)-розрядний код, який може бути отриманий зсувом R на k розрядів праворуч: R= {rs-1,…,r2,r1}=R/2k , (n-k)-розрядный код В отри-муєть-ся зсувом множеного В праворуч на k розрядів: B ={bs-1,…,b2,b1} = =R/2k. Складова ajB являє собою добуток k–розряд-но-го слова множника aj - на код В={bs-1,…,b2,b1}:
При фіксованому модулі М значення h на кожному циклі алгоритма залежить тільки від gj= (r0+ajb0) mod 2k, тобто h може бути представлене у вигляді:
Таким чином, значення h можуть бути попередньо обчислені для всіх 2k можливих g і збережені у вигляді таблиці T(g).
З урахуванням введених перетворень пропонується модифікований алгоритм модулярного множення на основі редукції Монтгомері:
Передобчислення: M=-M-1 mod 2k, T(g) =((gM mod 2k)M)/2k для всіх g{0,1,…,2k-1}.
1. R = 0.
2. for ( j=0; j <= s-1; j++)
{
2.1. vj = r0 + aj b0 ; gj =vj mod 2k; dj = vj/2k;
2.2. R= R/2k + ajB/2k + T(gj) + dj ;
}
3. if ( RM) R = R – M.
Об’єм V1 пам’яті таблиці передобчислень становить 2k(s-1) k-розрядних слів і може бути зменшений шляхом фрагментації таблиці.
Обчислювальна складність модулярного множення за запропонованим алгоритмом без урахування передобчислень визначається s2 операціями процесорного множення і s(2s+3) операціями додавання:
Теоретично, обчислювальна складність модулярного множення АВ mod M не може бути меншою за складність обчислення AB, яка визначається s2 операціями множення і 2s2 операціями додавання. Таким чином, обчислю-вальна складність запропонованого алгоритму модулярного множення, якщо враховувати тільки операції множення, співпадає з теоретичним мінімумом.
В порівнянні з базовим алгоритмом Монтгомери обчислювальна склад-ність запропонованого алгоритму є меншою в раз:
Така ефективність запропонованого алгоритму практично може бути досягнута лише процесорів розрядності 8 або 16, коли обєм пам’яті таблиць передобчислень не великий.
В третьому розділі роботи розробляються ефективні алгоритми реалізації основної операції обчислювальної операції протоколів захисту інформації – модулярного експоненціювання.
Процес модулярного експоненціювання, тобто обчислення ХЕ mod M зводиться до послідовного виконання log2E=n циклів, в кожному з яких виконується операція піднесення до квадрату одержаного на попередньому циклі результату, а також, в залежності від значення поточного біту степені виконується операція множення. Виходячи з того, в якому порядку аналізуються розряди ступеню Е можна розглядати два типа алгоритмів експоненціювання. На практиці, більшого розповсюдження набули алгоритми, в яких розряди ступеню Е аналізуються починаючи зі старших: це дозволяє в якості співмножника мати постійне число. Алгоритм модулярного експоненціювання цього типу з використанням нотацій С++ наведено нижче:
1. A = 1.
2. for ( j=n; j >=0; j -- )
{
2.2. A = AA mod M ;
2.3. if ( ej == 1) A = AX mod M ;
3. Результат: ХЕ mod M.
Проведений аналіз показав, що продуктивність модулярного експонен-ціювання може бути підвищена шляхом розробки нових алгоритмів виконання модулярного піднесення до квадрату та модулярного множення на постійний множник – базових операцій модулярного експоненціювання.
Запропоновано алгоритм модулярного піднесення до квадрату, який в нотаціях мови С++ може бути представлений наступним чином:
1. R = x0x0; d = x0;
2. for ( j=1; j<=s-1; j++)
{
2.1. p = r0M mod 2k
2.2. R=(R+ pM) >> k;
2.3. X = X>>k;
2.4. t = (2dX)<<(k(j-1))
2.5. z = (x0x0)<<(kj)
2.6. R = R + t + z; d = x0
}
3. p = r0M mod 2k
4. R=(R + pM) >> k;
5. if ( R >= M) R = R – M
Результатом роботи алгоритму є R = Х2U-1 mod M.
Загальна кількість NM операцій процесорного множення, що використо-вується для реалізації запропонованого алгоритму становить:
В порівнянні з базовим алгоритмом модулярного множення Монтгомері, запропонований алгоритм дозволяє за рахунок виключення надлишкових операцій, прискорити модулярне піднесення до квадрату в 1.3 рази.
Ще однією, потенційною можливістю прискорення модулярного експонен-ціювання є використання передобчислень при модулярному множенні на постійний множник.
Модифікований алгоритм множення на постійне число на основе рекурсії Монтгомері - Mont(A,B), може бути представлений у вигляді:
1. R = 0.
2. for ( j=0; j <= s-1; j++)
{
2.1. pj = (r0 + Т1(aj))M mod 2k;
2.2. R= ( R + T1(aj) + T2(pj))>>k;
}
3. if ( RM) R = R – M,
В циклі запропонованого алгоритму використовується одна операція процесорного множення і 2s+1 операцій процесорного додавання. Відповідно, при реалізації цього алгоритму модулярного множення потрібно s2 операцій процесорного множення і 2s2+s/2 операцій додавання, в той час, як алгоритм Монтгомері потребує 2s2+s операцій процесорного множення та 4s2 + 4s операцій процесорного додавання.
При постійному модулі М і використанні передобчислень сумарна кількість операцій процесорного множення, необхідних для модулярного піднесення до квадрату становить ns2/2 + n/2. Середня кількість операцій про-це-сор-ного множення, необхідних для множення на постійне число в процесі модулярного експоненціювання становить, в середньому, sn/2. Таким чином, загальна кількість операцій процесорного множення, необхідних для реалізації модулярного експоненціювання становить:
Порівняльний аналіз кількості необхідних операцій процесорного множення при звичайному модулярному експоненціювання Монтгомері і з використанням запропонованих алгоритмів показує що для k=8 і 16 число процесорних операцій множення зменшується практично в шість раз, при цьому об’єм пам’яті для таблиць результатів передобчислень становить 2k+2(n+1) біт.
В четвертому розділі розроблюються програмні засоби реалізації запропонованих в другому та третьому розділах алгоритмів прискореного модулярного множення та модулярного експоненціювання.
ВИСНОВКИ
В дисертаційній роботі виконано теоретичне обґрунтування і одержано нове вирішення наукової задачі підвищення продуктивності реалізації протоколів захисту інформації в комп’ютерних мережах, обчислювальною основою яких є мультиплікативні операції модулярної арифметики.
Основні наукові і практичні результати полягають у наступному:
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. (Дисертантом запропоновано структури апаратних засобів для високопро-дуктив-ної реалізації операцій модулярного множення з використанням табличної пам’яті передобчислень).
АНОТАЦІЇ
Рамзі Анвар Саліба Сунна. Високопродуктивна реалізація протоколів захисту інформації на базі операцій модулярної арифметики. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 – Обчислювальні машини, системи та мережі. – Національний технічний університет України ”Київський політехнічний інститут”, Київ, 2006.
Дисертація присвячена проблемі підвищення продуктивності реалізації протоколів захисту інформації в комп’ютерних мережах, в основі яких лежить модулярна арифметика.
Підхід, що пропонується для вирішення цієї проблеми, має за основу те, що при практичному застосуванні систем захисту інформації з відкритим ключем таких як RSA та DSS, останній міняється достатньо рідко. Відповідно, рідко міняється і модуль. Це дозволяє прискорити реалізацію модулярних операцій за рахунок використання передобчислень, що залежать тільки від модуля.
Представлені нові алгоритми модулярного множення, що використо-вують передобчислення при фіксованому модулі. Один з них має за основу класичну схему модулярного множення, а другий являє собою модифікацію алгоритму Монтгомері. Показано, що продуктивність розроблених алгоритмів приблизно вдвоє вища в порівнянні з алгоритмом Монтгомері при прийнятних об’ємах потребуємої пам’яті.
Запропоновано нові алгоритми для модулярного піднесення до квадрату та множення, що мають за основу рекурсію Монтгомері. Завдяки виключенню надлишкових операцій та використанню передобчислень, обчислювальна складність запропонованих алгоритмів є суттєво меншою в порівнянні з алго-ритмом множення Монтгомері. Показано, що при реалізації запропоно-ваних алгоритмів на мікропроцесорах малої розрядності, вбудованих мікро-контро-лерах та старт-картах, час обчислення модулярного експоненціювання в шість раз менший в порівнянні з алгоритмом модулярного експоненціювання Монтгомері.
Ключові слова: комп’ютерна арифметика, модулярне множення, модулярне експо-ненціювання, передобчислення, протоколи захисту інформації в мережах.
Рамзи Анвар Салиба Сунна. Высокопроизводительная реализация про-то-ко--лов защиты информации на базе операций модулярной арифметики. - Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - Вычислительные машины, системы и сети.- Национальный технический университет Украины ”Киевский политехничес-кий институт”, Киев, 2006.
Диссертация посвящена проблеме повышения производительности реали-зации сетевых протоколов защиты информации, основанных на мультипли-кативных операциях модуль-ной арифметике.
Предлагаемый подход к решению указанной проблемы основан на том, что при практическом использовании систем защиты информации с открытым ключом, последний меняется достаточно редко. Соответственно, редко меняется и модуль. Это позволяет ускорить реализацию модулярных операций путем использования предвычислений, зависящих только от модуля.
Представлены новые алгоритмы модулярного умножения, использую-щие предвычисления при фиксированном модуле. Один из них основан на классической схеме модулярного умножения, а второй является модификацией алгоритма Монтгомери. Показано, что производительность разработанных алгоритмов примерно вдвое выше по сравнению с алгоритмом Монтгомери при приемлемом объеме требуемой памяти.
Для повышения производительности наиболее трудоемкой операции модулярного экспоненцирования при постоянном модуле предложены новые алгоритмы вычислительной реализации составляющий экспоненцирования - модулярного возведения в квадрат и умножения на фиксированное число, основанные на рекурсии Монтгомери. Благодаря исключению избыточных операций и использованию предвычислений, зависящих от модуля вычисли-тель-ная сложность предложенных алгоритмов существенно ниже по сравнению с алгоритмом умножения Монтгомери. Показано, что при реализации предложенных алго-рит-мов на малоразрядных микропроцессорах, встроенных микроконтрол-лерах или смарт-картах, время вычисления модулярного экспо-нен-цирования в шесть раз меньше по сравнению с алгоритмом модулярного экспонен-цирования Монтгомери.
Ключевые слова: компьютерная арифметика, модулярное умножение, модулярное экспо-нен-цирование, предвычисления, протоколы защиты инфор-мации в сетях.
Ramzi Anwar Saliba Sunna. High-efficiency implementation of the data protection protocols based on modular arithmetic operations. - Manuscript.
Thesis for a Ph.D. degree by specialty 05.13.13 – Computers, systems and networks. National Technical University of Ukraine “Kiev Polytechnic Institute”, Kiev, 2006.
Thesis is dedicated to a problem of implemenproductivity of network data protections protocols based on modular arithmetic increasing.
The proposed approach to solving of this problem is base on of assumption that in practice the keys of the most public-keys data
