Метод модулярного множення в системі залишкових класів

Размещено на http://www.allbest.ru/

Метод модулярного множення в системі залишкових класів

Касянчук Михайло Миколайович,

Тимошенко Лідія Миколаївна,

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

Єрьоменко Анастасія Іванівна, магістрант кафедри кібербезпеки та програмного забезпечення ОНПУ, м. Одеса, Україна

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

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

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

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

MODULAR MULTIPLICATION METHOD IN THE RESIDUAL CLASS SYSTEM

Kasianchuk Mykhailo,

Cand. Sci. (Phys-Math.), Associate Professor of the Department of Cybersecurity of West Ukrainian National University, Ternopil, Ukraine,

Tymoshenko Lidiia,

Cand. Sci. (Economics), Associate Professor of the Department of Cybersecurity and Software of Odessa National Polytechnic University, Odesa, Ukraine,

Ieriomenko Anastasiia,

Graduate student of the Department of Cybersecurity and Software of Odessa National Polytechnic University, Odesa, Ukraine

Today the idea of developing algorithms for paralleling large number processing processes in asymmetric cryptographic information protection systems is becoming more and more relevant. Such paralleling does not allow using a binary number system through its serial structure. Therefore, it is important to use the residual class system as a non-positional number system. In spite of certain disadvantages, it can be successfully used for paralleling addition, multiplication, and multibit number building processes. Searching for the reverse number in arithmetic operations using the Chinese residual theorem is quite a difficult task. To avoid these problems, it is suggested to use the perfect and modified perfect form of the residual class system. However, the implementation of the modular multiplication method in the residual class system and its modified perfect form has not been investigated bor today.

In this paper, we experimentally investigated time costs of software implementation of multiplication in a three-module residual class system and its modified perfect form. In the course of the study several cases for numbers of different discharges and with different module systems were considered: modules that differ little and modules that differ significantly. Graphs of dependence of average time of execution of the operation of multiplication on the digit numbers for different cases are constructed. Average computation time when using a modified perfect form of the system of residual classes is reduced by about 2.5-3 times compared with the case of using the same systems of modules of an ordinary integer form in the system of residual classes. To avoid accidental impacts on the computer, all calculations were repeated a hundred times.

It is shown that the use of a modified perfect form makes it possible to reduce the time of calculating arithmetic operations by eliminating the operation of searching for the reverse element by module and multiplication by it when converted to the decimal system of calculation. Graphical dependencies of time characteristics are given, confirming the advantages of using the modified perfect form of the residual classes system.

Keywords: residual class system, modified perfect form of residual class system, modular multiplication, multi-digit numbers.

модулярне множення залишковий клас

При опрацюванні великих чисел в асиметричних криптографічних системах захисту інформації для підвищення швидкодії процесів шифрування та криптоаналізу [1], при кодуванні інформації [2], обробці зображень необхідно багато ресурсів та значень відповідних чисел через розподіл завдань у процесі виконання арифметичних операцій [3]. Таке розпаралелення не дозволяє використовувати двійкову систему числення через її послідовну структуру. Тому є актуальним варіант використання системи залишкових класів (СЗК) [4] як непозиційної системи числення. Незважаючи на певні недоліки, вона може успішно використовуватись при розпаралеленні процесів додавання, множення, піднесення до степені багаторозрядних чисел.

Теоретичні засади системи залишкових класів. Досконала та модифікована форми СЗК. Основою СЗК є теорія чисел [5]. Будь-яке ціле десяткове число N може бути представлено у СЗК у вигляді набору (b1, b2, ..., bn) найменших додатних залишків від ділення цього числа на фіксовані натуральні попарно взаємні прості числа (модулі) р1, р2, ... , рп (b=N modp.), де n - кількість модулів. При цьому повинна виконуватись нерівність 0<N<P-1, де Р= П Pi - число, яке визначає умову переповнення розрядності розрахунків. Результати виконання арифметичних операцій додавання, множення, піднесення до степені з використанням китайської теореми про залишки подаються у десятковій системі числення так:

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

Тому для уникнення цих проблем запропоновано використати досконалу форму (ДФ) СЗК [7] за умови Mi modpt = 1. Тоді рівність (1) спрощується так:

Однак у такому разі значення _р1=2, р2=3, ..., р швидко збільшуються, що неприйнятне за необхідності використання модулів приблизно однакової розряд- ності.

У роботі [8] запропонована модифікована досконала форма (МДФ) СЗК, де Mj mod pi = ±1, що також дозволяє уникнути виконання операції пошуку оберненого елементу. Обчислення виконують за формулою:

де m.=±1.

У [9] визначено теоретичні засади побудови трьохмодульної МДФ СЗК. Проте на сьогодні не досліджено, як саме виконується модулярне множення у СЗК та МДФ СЗК. Ця задача вирішується в запропонованому дослідженні.

Експериментальне дослідження програмної реалізації методу модулярного множення в системі залишкових класів та її модифікованій досконалій формі. У цій роботі для дослідження множення в СЗК та МДФ СЗК використано Python - мову програмування, яка дозволяє запускати програмний засіб на різних операційних системах, але водночас не змінює свого змісту та можливості зчитати його. До того ж, Python є лаконічним, що дозволяє написати програму меншу за розміром порівняно з іншими мовами програмування. А широка бібліотека, яка встановлюється автоматично з Python, дає можливість використовувати його для проведення наукових досліджень. Приклад введення вхідних параметрів зображено на рисунку 1.

Рис. 1 Вікно з введеними вхідними параметрами програми

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

Рис. 2. Приклад збереженого файлу

На рисунку 3 зображені часові характеристики виконання операції множення N=p4q у трьохмодульній СЗК при фіксованому множнику _р=в5536 з двома різними системами модулів (пертий випадок - модулі мало відрізняються один від одного:_р1=1625= 3655362 ,/>2=1626, _р3=1627 - пунктирні лінії; другий випадок - модулі значно відрізняються: _р1=163, _р2=1627, _р3=16381 - суцільні лінії). Другий множник q змінювався від значення 67 до p із кроком 1311. Останній визначав кількість отриманих розрахунків, яка дорівнює 50. Добуток модулів обох систем перевищує 232.

Рис. 3. Часові характеристики виконання операції множення у СЗК

Можна побачити із рисунка 3, що графік 1 має осцилюючий характер. Середній час виконання операції множення (графік 2) дорівнює 0,009259 мс. У другому випадку, крім початкових значень q, час виконання множення (графік 3) не має істотних коливань. Середній час (лінія 4) складає 0,006066 мс, що у 1,53 рази менше, ніж у попередньому випадку. Тому для підвищення швидкості виконання обчислення в СЗК попарно взаємні прості модулі необхідно вибирати так, щоб вони відрізнялись одне від одного якомога менше.

Для дослідження МДФ СЗК система модулів зі значною різницею між ними (p1=65l, p2=691, p3=11246) обиралася за формулою, отриманою у [8]:

При побудові трьохмодульної МДФ СЗК за формулою (4) неможливо обрати систему модулів однакової розрядності. Найменша різниця між модулями буде за умови:

З огляду на це, обрано такі модулі: _р1=1025, ^2=2049, ^,=2051. Добуток модулів в обох випадках перевищує 232 .

Вхідні параметри обрані ті ж самі, що й для звичайної СЗК. Розрахунки проводилися згідно з виразом для МДФ СЗК, який випливає з (3):

де b. - залишки.

Отримані результати зображені на рисунку 4. Суцільна лінія показує час виконання множення (крива 1) і середній час виконання множення (лінія 2) для п'ятдесяти значень p при p1=651, p2=691, p3=11246, пунктирна (графіки 3, 4) - відповідно, для _р1=1025, _р2=2049, _р3=2051.

Рис. 4. Часові характеристики виконання операції множення у МДФ СЗК

Можна побачити, що в попередньому та останньому випадках при малих значеннях q амплітуда коливань велика, а при збільшенні q вона зменшується, за винятком невеликого відрізку у другій половині діапазону змін значення q. Середній час для системи модулів _p1=65l, p2=691, p3=11246 складає 0,002293 мс (лінія 2), а для _р1=1025, р2=2049, р3=2051 - 0,002169 мс (лінія 4), що у 1,057 рази менше, ніж у попередньому випадку.

Порівняння рисунків 3 та 4 засвідчує істотне підвищення швидкодії за рахунок використання МДФ СЗК.

Наступні експериментальні дослідження проводились для чисел, розрядність n яких змінювалася від 16 до 24 біт. Розглянуто чотири випадки побудови системи модулів:

1) модулі СЗК значно відрізняються один від одного;

2) модулями є три послідовних числа, перше та третє із яких непарні:

3) модулі обчислюються за формулами р2= Р1+1, Р3= р1(р1+1) - 1;

4) модулі обчислюються за формулами р2= 2р1-1, р3= 2р1+1.

У всіх випадках добуток модулів є мінімальним, але таким, що перевищує 22n. У третьому та четвертому випадках утворюється система модулів МДФ СЗК. Перший множник у добутку N=p4q був фіксованим: p=2n-1, що відповідає максимальній заданій розрядності. Другий множник q змінювався від початкового

Таким чином, отримано тисячу різних значень числа q і, відповідно, час виконання тисячі множень N=p * q при фіксованому p і змінному q. Далі для кожної розрядності визначено середній час виконання операції. Для того, щоб виключити випадкові впливи на роботу комп'ютера, усі розрахунки повторювалися 100 разів. Використані набори модулів та середній час розрахунків для чисел різних розрядностей подано в таблиці 1.

Таблиця 1

Набори модулів та середній час розрахунків для чисел різних розрядностей