Алгоритм RSA: Методичні вказівки до виконання і оформлення практичної роботи № 5

ПРАКТИЧНА РОБОТА №5

ПО ДИСЦИПЛІНІ КРИПТОЛОГІЯ

“АЛГОРИТМ RSA”

Зміст

Теоретична частина.. 5

Приклад розв’язання задачі11

Вимоги до виконання і оформлення практичної  роботи.. 14

Варіанти завдань. 17

Контрольні питання.. 20

Список літератури.. 21

 1. Теоретична частина

Алгоритм RSA запропонували у 1978 р. три автори: Р. Райвест (Rivest),  А. Шамир (Shamir) і А. Адлеман (Adleman). Алгоритм одержав свою назву за першими буквами прізвищ його авторів. Алгоритм RSA став першим повноцінним алгоритмом з відкритим ключем, що може працювати як у режимі шифрування даних, так і в режимі електронного цифрового підпису.

Надійність алгоритму ґрунтується на складності факторизації великих чисел і складності обчислення дискретних логарифмів.

У криптосистемі RSA відкритий ключ К_A, секретний ключ К_B, повідомлення М і криптограма С належать безлічі цілих чисел

,                                              (1)

де N – модуль:

.                                      (2)

Р і Q – випадкові великі прості числа.

Для забезпечення максимальної безпеки вибирають Р и Q однокової довжини та зберігають у таємниці.

Множина Z_N з операціями додавання й множення за модулем N утворює арифметику за модулем N.

Відкритий ключ К_A вибирають випадковим чином так, щоб виконувалися умови:

                             ,                                                    (3)

,                                         (4)

де   – функція Ейлера, що  показує  кількість позитивних цілих чисел в інтервалі від 1 до N, які взаємно прості з N:

.

Умова (4) означає, що відкритий ключ К_A і функція Ейлера  повинні бути взаємно простими. Далі, використовуючи розширений алгоритм Евкліда, обчислюють секретний ключ K _B із порівняння:

                                (5)

або

       .

Це можна здійснити, завдяки тому що одержувач В знає пару простих чисел (P,Q) і може легко знайти . Зауважимо, що K_B і N повинні бути взаємно простими.

Відкритий ключ К_A використовують для зашифрування даних, а секретний ключ K_B – для розшифрування. Перетворення шифрування визначає криптограму Cчерез пару (відкритий ключ К_A, повідомлення М) відповідно до такої формули:

.               (6)

Обернення функції , тобто визначення значення М за відомим значенням С, К _A та N, практично нездійсненне при N > 2⁵¹². Проте зворотну задачу, тобто задачу розшифрування криптограми C, можна розв’язати, використовуючи пари (секретний ключ K _B, криптограма C) за такою формулою:

.                         (7)

Процес розшифрування можна записати так:

.                                      (8)

Підставляючи в (8) значення (6) і (7), одержуємо:

,

або

.                                    (9)

Величина відіграє важливу роль у теоремі Ейлера, яка стверджує: якщо , то

,

або в  більш загальній формі

.                        (10)

Зіставляючи вирази (9) і (10), одержуємо

або, що теж саме, .

Саме тому для обчислення секретного ключа K_B використовують співвідношення (5). Таким чином, якщо криптограму

піднести до степеню K_B, то в результаті відновлюється вихідний відкритий текст М, тому що

Таким чином, одержувач В, що створює криптосистему, захищає два параметри: секретний ключ K_B і пару чисел (P,Q), добуток яких дає значення модуля N. З іншого боку, одержувач В відкриває значення модуля N і відкритий ключ К_А . Супротивнику відомі лише значення К _А та N. Якби він зміг розкласти число N на множники Р и Q, то він довідався б "потайний хід" - трійку чисел { Р,Q, К _A }, обчисливши значення функції Ейлера

і визначивши значення секретного ключа K _B. Проте, як було вказано вище, розкладання дуже великого N на множники обчіслювально неможливі (за умови, що довжини обраних Р и Q становлять не менш 100 десяткових знаків).

Розглянемо алгоритм шифрування й розшифрування в криптосистемі RSA. Припустимо, що користувач А хоче передати користувачеві В повідомлення в зашифрованому вигляді, використовуючи криптосистему RSA. У такому випадку користувач А виступає в ролі відправника повідомлення, а користувач В - у ролі одержувача. Як відзначалося вище, криптосистему RSA повинен сформувати одержувач повідомлення, тобто користувач В. Розглянемо послідовність дій користувача В и користувача А:

1. Користувач В вибирає два довільних великих простих числа Р и Q;

2. Користувач В обчислює значення модуля N

;

3. Користувач В обчислює функцію Ейлера (8)

;

4. Користувач В вибирає випадковим чином значення відкритого ключа К_A з урахуванням виконання умов:

, ;

5. Користувач В обчислює значення секретного ключа К_B, використовуючи розширений алгоритм Евкліда при розв’язку порівняння

;

6. Користувач В пересилає користувачеві А пару чисел
(N, К_A) по незахищеному каналу.