Київський університет імені тараса Шевченка

Салем Шеріф Ель-фард

УДК 519.1

Порівняльний аналіз методів модулярної

редукції

01.05.01. - теоретичні основи інформатики та кібернетики

Автореферат

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

кандидата фізико-математичних наук

Київ - 1999

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

Робота виконана на кафедрі математичної інформатики Київського університету імені Тараса Шевченка

Науковий керівник: доктор фізико математичних наук,

професор Анісімов Анатолій

Васильович (Київський університет

імені Тараса Шевченка, професор)

Офіційні опоненти: 1.доктор фізико-математичних наук,

професор Асельдеров Зайнутдін

Макашаріпович( Інститут проблем

математичних машин та

систем НАНУ, головний науковий

співробітник)

2.кандидат фізико-математичних наук,

доцент Проценко Володимир

Семенович (Український Експортно-

імпортний банк, начальник відділу)

Провідна установа: Інститут кібернетики імені

В.М.Глушкова НАН України, відділ

моделювання інформаційно-

функціональних систем, м.Київ.

Захист відбудеться "24" червня 1999 р. на засіданні спеціалізованої вченої ради Д 26.001.09 Київського університету імені Тараса Шевченка, м.Київ, пр.Академіка Глушкова 6, корп. 2, ф-т кібернетики, ауд. 40 о 14 годині. (Тел./факс 252-58-83, E-mail: rada@cyb.univ.kiev.ua).

З дисертацією можна ознайомитись у Науковій бібліотеці Київського університету імені Тараса Шевченка, м.Київ, вул.Володимирська, 58.

Автореферат розісланий "20" травня 1999 р.

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

спеціалізованої вченої ради В.П.Шевченко

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

Актуальність теми. Сучасний період розвитку суспільства відзначається інтенсивним рухом у напрямку глобальної інформатизації всіх сфер діяльності людини. Комп'ютерні мережі охоплюють майже всі системи керування економікою та технологічними процесами. У такому інформаційному просторі на перший план висуваються задачі інтегральної безпеки інформації. Тому, в наш час, велика увага приділяється розвитку методів захисту інформації у комп'ютерних та комунікаційних системах несанкційованого доступу. Традиційні методи, базовані на таємності всіх параметрів систем захисту інформації не можуть бути ефективно застосовані у таких глобальних масштабах. Тому зараз акцент в проблематиці захисту інформації зосередився на системах з відкритими ключами. Такі системи дозволяють користувачам самим будувати надійні системи захисту даних без спеціальних організаційних заходів. Системи з відкритими ключами базуються не на принципах таємності всіх ключів, а на принципі неможливості перехоплювачу виконати дуже великий обсяг обчислювальних робіт. Такі системи вперше почали розроблятися з другої половини 70-х років. Це відомі системи логарифмічного обміну Діффі і Хеллмана, RSA - системи Рівеста, Шаміра і Адельмана, схема цифрового підпису ЕльГамаля та інші.

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

Основним недоліком систем захисту, базуючих на відкритих ключах, є їх велика відносна повільність обробки даних, яка є гальмом у багатьох системах обробки та передачі інформації. Це пов'язано з наступними чинниками. По-перше, системи з відкритими ключами застосовують модулярну арифметику надвеликих чисел. Рекомендована в наш час довжина таких чисел повинна бути 1024 біт або 2058 біт, що значно перевищує розмір стандартних машинних слів. Зменшення довжини оброблюючих чисел підвищує ризик розкриття системи захисту сучасними комп'ютерними методами. Розмір чисел, які використовуються в системах з відкритими ключами, постійно збільшується пропорційно розвитку новітніх технологій. Так, наприклад, рекомендована довжина чисел в стандартах RSA підписах за останні 3 роки зросла вдвічі. По-друге, експоненційно нарощується навантаження на вузли сучасних комп'ютерних мереж, тому швидкість систем захисту даних повинна бути адекватна швидкодії передаючих каналів або перевищувати їх. Ось чому саме розробці загальних алгоритмів обчислення модулярної редукції приділяється постійна увага. Відомо декілька методів модулярної редукції. Основні з них: метод Монтгомері, метод Баррета, класичний метод. Останнім часом пропонуються інші альтернативні методи, наприклад, метод Флойда - Кнута та метод, запропонований А.В.Анісімовим. Кількість існуючих методів, іх важливість щодо застосування в системах інформаційного захисту потребують проведення ретельного порівняльного аналізу. Також, в зв'язку з розширенням можливостей дистрибутивної обробки інформації, значний інтерес викликає розробка нових паралельних алгоритмів.

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

Зв’язок роботи з науковими програмами, планами, темами. Робота виконана відповідно до плану наукових досліджень кафедри математичної інформатики Київського університету імені Тараса Шевченка:

·

· тема Міністерства у справах науки і технології "Створення та вивчення програмно-алгоритмічних засобів для вирішення класів задач, пов'язаних з обробкою даних надвеликої розмірності" - договір № 97506 (договір ФЧ/246-97 )

· тема Національного Агенства по Інформатиці при Президентові України "Розробка алгоритмічних методів та програмно-технічних засобів інтелектуалізації інформаційних технологій на базі мереж та розподілених обчислювальних комплексів" (1996 - 1997 рр., договір № 29/2 - 96)

Мета роботи. Метою дисертаційної роботи є:

·

· розробити нові загальні алгоритми для задач модулярної редукції;

· довести математично коректність найбільш швидкого алгоритму модулярної редукції - метода Монтгомері;

· розробити та дослідити новий паралельний алгоритм модулярного експоненціювання надвеликих чисел;

· провести комп’ютерні експерименти щодо порівняльного аналізу методів модулярної редукції.

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

Наукова новизна роботи. Наукова новизна роботи полягає в тому, що:

·

· В роботі вперше проведено математичне обгрунтування метода Мотгомері;

· Запропоновано новий паралельний алгоритм обчислення операції модулярного експоненціювання xd mod m. Цей алгоритм узагальнює паралельний бінарний алгоритм Чіоу;

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

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

Матеріали дисертаційної роботи використовувалися при читанні спецкурсу "Захист інформації" на факультеті кібернетики Київського університету імені Тараса Шевченка.

Особистий внесок автора. Всі результати автора сформульовані у дисертації як нові та отримані ним особисто. Робіт у співавторстві здобувач не має.

Апробація роботи. Основні результати обговорювались на семінарах кафедри математичної інформатики факультету кібернетики Київського університету імені тараса Шевченка та семінарах відділу інтелектуалізації інформаційних технологій Міжнародного науково - учбового центру інформаційних технологій і систем НАНУ.

Публікації. За темою дисертації опубліковано 5 статей.

Структура та об'єм роботи. Дисертація складається зі вступу, чотирьох глав, висновків, списку літератури та додатку. Загальний об'єм роботи складає 104 сторінки, список літератури нараховує 44 найменування.

ЗМІСТ РОБОТИ.

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

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

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

Основу таких систем складають так звані односторонні функції та односторонні функції з пасткою (trap - door). Функція y = f(x) називається односторонньою, якщо ії значення y можна обчислити за реальний час, але обернене значення x маючи y обчислити дуже важко. Прикладами односторонніх числових функцій є добуток двох великих множників y = x* u або модулярне експоненціювання y = xu mod m для великих чисел. Пряме обчислення таких функцій досить просте, але обернені задачі - розкласти задане велике число на множники; обчислення кореня - знайти x, маючи y, u та m, де y = xu mod m; задача дискретних алгоритмів - знайти u, маючи y, x та m , де y = xu mod m, у наш час комп'ютерно не можуть бути обчисленими при великих числах y, x та m. Сучасні рекомендації систем захисту дають числа довжиною 1024 або 2058 біт.

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

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

В розділі 1.4. обгрунтовується необхідність прискорення основних функцій в системах з відкритими ключами з практичної точки зору. Так, наприклад, більшість серверів, які проводять кодування інформації по RSA-методу за стандартами протоколів SET та SSL для комерційних та банківських операцій, витрачають до 90% свого часу на такі перетворення.

В главі 2 розглядається відома схема з відкритими ключами.

В розділі 2.1. описується перша схема генерування закритого ключа, яка використовує протоколи обміну через відкритий канал зв'язку. Це схема Діффі та Хеллмана, запропонована у 1976 році.

Розділ 2.2. дає опис відомої RSA-схеми захисту з ключами загального доступу. Ця схема запропонована трьома авторами - Рівестом, Шаміром і Адельманом - ще у 1978 році.

У розділі 2.3. дається оригінальний опис відомої схеми ЕльГамаля, яка є узагальненням системи обмінів Діффі та Хеллмана.

Мета другої глави - на конкретних прикладах пояснити важливість швидкого обчислення операції модулярної редукції x mod m для побудови сучасних систем захисту інформації.

Глави 3 і 4 - це ядро самої дисертації. В главі 3 досліджуються існуючі методи модулярної редукції. Великі числа записуються за основою системи b, де b - розмір машинного слова .

Нехай модуль m має вигляд

m = , 0 < mk-1 < b i 0 mi < b, для i = 0,1,..., k -2,

а аргумент x

x = , 0 < xk-1 < b і 0 xi < b, для i = 0,1,..., l -2,

У розділі 3.1. ми розглядаємо чотири з п'яти загальних методів модулярної редукції: класичний метод, метод Баррета, метод Кнута - Флойда та метод А.В.Анісімова.

Класичний алгоритм є узагальненням звичайного ділення у стовпчик. Цей метод дає непогані показники і дуже часто використовується на практиці.

Algorithm 1. класичний алгоритм (mk-1 ).

if ( x > mbl-k ) then x = x - mbl-k;

for ( i = l - 1; i > k - 1; i --) do {

if ( xi = = mk-1 ) then

q = b -1;

else

q = (xib + xi-1) div mk-1;

while (q (mk-1b + mk-2 ) > xib2 + xi-1b + xi-2 ) do

q = q -1;

x = x - qmbi-k;

if ( x < 0 ) then

x = x + mbi-k;

}

Метод Баррета базується на ідеї наближеного обчислення x div m таким способом, що тільки зручні операції виконуються у процесі обчислення. Нехай R = b2k. Тоді x/m =( x /b2k-t)( b2k/m ) / bt і q = x/m = ( x /b2k-t)( b2k/m ) / bt .

Для обчислення q використовується наближення = (( x div b2k-t ) ) div bt , де = b2k div m .

Як показав Баррет, якщо k < t < 2k, то похибка між q i не буде перевищувати 2.

Наближене обчислення x mod m виконується по формулі

= (x mod bk+1 - (m) mod bk+1) mod bk+1.

Метод Флойда - Кнута дуже цікавий, тому що він не використовує множення та ділення. Флойд і Кнут розглядали регістрову машину, яка має тільки 6 типів операцій: введення x, присвоєння x y, додавання x y, порівняння x y та виведення x. Використовуючи ідею швидкого обчислення виразів, які мають вигляд yFk , де Fk - k-те число Фібоначчі, та можливість зображення довільного цілого числа у вигляді суми чисел Фібоначчі, Флойд і Кнут запропонували швидкий алгоритм обчислення x mod m на адитивній машині за час O(log x/y).

А.В.Анісімов запропонував обчислювати модулярну редукцію x mod m за допомогою базового співвідношення R = qm + r, де R > u. Тоді обчислення x mod m виконується по схемі

read(x);

while (x > m) do {

if x > m then x = x - m

}

print x

Число t швидко обчислюється.

Метод Монтгомері найбільш відомий і є традиційним для практичних застосувань. Цей метод подається окремо у розділі 3.2. Монтгомері використовує базове співвідношення

R R-1-mm = 1,

0< R-1 < m, 0< m'< R, m' = -m-1 mod R.

Монтгомері винайшов спосіб, як швидко обчислювати xR-1 mod m.

int function REDC (int x)

t = (x mod R) m 'mod R;

g =(x+tm )/R;

if (g > m) return (g-m) ;

else return (g ).

Фактор R-1 дещо ускладнює пряме обчислення x mod m, але Монтгомері винайшов цікавий прийом, як швидко обчислити число t у вище наведеній схемі.

В оригінальній роботі Монтгомері дається тільки алгоритм, а сам вигляд числа t залишається невизначеним. Пошукачу вдалося дати математичне обгрунтування метода Монтгомері та визначити явний вигляд числа t, яке може бути інколи корисним для швидких обчислень.

У розділі 3.4. проводиться теоретичний та експериментальний аналіз наведених п'яти методів. Теоретичні оцінки на числах довжини 2k при k-значному модулі такі: класичний - k(k + 2.5), метод Баррета - k(k + 4), метод Монтгомері - k(k + 1), метод Флойда - Кнута - O(k2) і метод Анісімова - O(k2). Вибір довжини 2k має особливе значення. Це довжина добутку двох чисел довжини k, які є залишками по модулю.

Глава 4 присвячена виконанню основної важкої операції систем з відкритими ключами - модулярному експоненціюванню xy mod m.

У параграфі 4.1. згадується відомий послідовний бінарний метод обчислення xd mod m. Також наводяться табличні дані обчислення xy mod m з використанням вище наведених п'яти методів модулярної редукції.

Новий паралельний алгоритм обчислення xy mod m запропоновано у наступному розділі 4.2. Цей алгоритм узагальнює бінарний паралельний алгоритм, запропонований Чіоу у 1995 році. Узагальнення полягає у виборі довільного базиса b замість 2. Це дає алгоритм з більшим збалансованим завантаженням при виконанні на двох процесорах.

Спеціальний алгоритм, який дає високий ступінь паралельної обробки, дано у параграфі 4.3. Цей алгоритм використовує зручні обчислювальні характеристики чисел Фібоначчі. Так обчислення потребує k модулярних множень. Для побудови алгоритму використовуються лінійні форми Фібоначчі, введені А.В.Анісімовим.

Лінійна форма Фібоначчі рангу t - це вираз типу xFt-1 + yF t , де x, y 0. А.В.Анісімовим доведено, що довільне ціле число u може бути зображено у вигляді лінійної форми Фібоначчі максимального рангу y = aFt-1 + bF t.

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

y = aFt-1 + bF t,

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

Більш того, глибина бінарного дерева Фібоначчі буде O(log log y) (Теорема 4.2.). Тобто, глибина бінарного дерева дуже невелика в порівнянні із значенням числа.

У висновках обговорюються отримані результати.

У додатку наведено тексти програм, написаних на мові С, які реалізують проаналізовані п'ять методів.

ВИСНОВКИ

1.

2.

3.

4.

5.

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

Основні положення дисертації надруковані в наступних працях:

1.

2.

3.

4.

5.

Салем Шеріф Ель-фард. Порівняльний аналіз методів модулярної редукції. Рукопис.

Дисертація на здобуття ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики - Київський університет імені Тараса Шевченка.

Робота присвячена вивченню складності операції модулярної редукції x mod m для великих чисел. Досліджено п'ять методів: класичний метод, метод Баррета, метод Кнута - Флойда, метод Монтгомері та метод А.В.Анісімова. На основі теоретичних досліджень та машинних експериментів зроблено порівняльний аналіз усіх наведених у роботі методів. Досліджено паралельні варіанти обчислення модулярної експоненти.

Ключові слова: арифметика довгих чисел, модулярна редукція, часова складність, алгоритми, паралельні алгоритми.

Салем Шериф Ель-фард. Сравнительный анализ методов модулярной редукции. Рукопись.

Диссертация на соискание степени кандидата физико-математических наук по специальности 01.05.01 - торетические основы информатики и кибернетики - Киевський университет имени Тараса Шевченко.

Работа посвящена изучению сложности операции модулярной редукции x mod m для больших чисел. Проанализировано пять методов: классический метод, метод Баррета, метод Кнута - Флойда и метод А.В.Анисимова. На основании теоретических исследований и машинных экспериментов выполнен сравнительный анализ всех пяти методов. Рассмотрены паралельные варианты вычисления модулярной экспоненты.

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

Salem Sherif Elfard Comparative Analysis of Modular Reductions Methods. - Manuscript.

Thesis for the degree of Candidate of Science (Ph.D) in Physics and Mathematics, on speciality 01.05.01 Theoretical base of informatics and cybernetics.- Kyiv Taras Shevchenko University, Kyiv ,1999.

The thesis is devoted to the study of modular reduction function x mod m for large numbers. This operation is basic for public-key cryptosystems and determines their speed of processing. The research is aimed to comprehensively analyze modular reduction methods from the viewpoint of computation complexity. The general aim of the research is as follows: to create new effective algorithms for solving modular reduction problems for large numbers; to do comparative analysis of known modular reduction methods with the purpose to choose the fastest and most suitable for use in public-key cryptography; to prove theoretically correctness of some concrete modular reduction methods; to create new parallel algorithms for modular exponention of large numbers; to fulfill computer experiments for comparison of modular reduction methods.

Five methods of modular reduction have been analyzed. They are: classical method, Barret 's method, Montgomery's method, method suggested by Floyd and Knuth on addition machines and Anisimov's method .

The novelty of obtained results is as follows:

·

· new parallel algorithm for computing exponential modular function xd mod m in any arithmetical radix is proposed. This algorithm generalizes the algorithm by Chiou;

· new recursive – and - parallel algorithm for computing modular exponentiation based on linear Fibonacci forms is suggested;

· time estimates by computer experiments for considered modular reduction algorithms are obtained.

A theoretical and practical comparison has been made of five algorithms for the reduction of large numbers. They are: classical method, Barrett,s method, iterative Anisimov’s method, Floyd-Knuth method and Montgomery method. It has been shown that in a good portable implementation the three algorithms, Barret’s, Montgomery’s and classical, are quite close to each other in performance. The classical algorithm is the best choice of a single modular reductions. Modular exponentiation based on Barrett’s algorithm is superior to the others for small arguments. For small numbers iterative Anisimov’ s method is as classicall but easier for programming.

For general modular exponentiations the exponentiation based on Montgomery’s algorithm has the best performance. Method based on the linear Fibonacci forms is very perspective for parallel implementations.

Key words: arithmetic of large numbers, modular reduction, time complexity, algorithms, parallel algorithms.