Page 25 - 4395
P. 25
Оперування з великими десятковими числами (порядку 100-200
знаків) вимагає спеціальних алгоритмів піднесення до степеня. В [1,
додаток 2] наведено чотири групи таких алгоритмів. З них найбільш
поширеними є базові методи піднесення до степеня, в яких основа і
показник степеня є довільними. У додатку А наведені два варіанти
бінарного базового методу, коли показник степеня представляється
двійковим числом. Ці два бінарні алгоритми розрізняються способом
читання двійкового показника степеня при обчисленні: алгоритм
зліва направо LR_bin_exp та алгоритм справа наліво RL_bin_exp.
Перший з них характеризується простотою, тоді як другий дозволяє
дещо підвищити швидкодію за рахунок можливості паралельних
обчислень. Оскільки типова курсова робота не оперує з великими
числами, рішуче значення отримує простота. Тому функція
INVOLUTION використовує алгоритм LR_bin_exp.
Текст програми INVOLUTION є простим (див. В.3). Спочатку
показник степеня перетворюється у двійковий рядок за
допомогою функції 10 DEC2BIN і визначається його довжина
11 LENGTH, а потім застосовується алгоритм LR_bin_exp (рядки
14-20). Слід зауважити, що для правильного читання показника
степеня зліва направо простіше за все передбачити цикл не
низхідним, як у додатку А, а висхідним, що і зроблено.
Головний модуль програми MAIN_RSA (див. В.4) спочатку
звільняє пам’ять середовища від роботи попередніх програм
командою 5 CLEAR ALL і очищає командне вікно командою 6 СLС.
Вибір варіанта завдання, як вже вказувалось, здійснюється шляхом
присвоєння рядковій змінній ALTERNATIVE значення ‘Crypt’ або
‘Signature’ (рядок 13). У кінці файлу вказується порядок виклику
інших модулів (рядки 14-16).
3.2 Синтезування ключів
Відповідно до пункту 2.2.1 процедура визначення ключів
(див. В.5) починається з обчислення модуля n = p*q (рядок 6) і
обчислення функції Ейлера Е = (p-1)*(q-1) — рядок 7. При p = 23 і
q = 31 отримаємо n = 713, E = 660.
Ключ е обирається випадково і так, щоб е < Е і, крім того, е і Е
повинні бути взаємно простими, тобто мати одиничним найбільший
спільний дільник gcd(e,E) = 1. У 2.2.2 описана загальна процедура
25