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
   20   21   22   23   24   25   26   27   28   29   30