КРИПТОГРАФІЧНИЙ СИСТЕМА RSA
Алгоритм RSA був запропонований в 1977 році і став першим повноцінним алгоритмом асиметричного шифрування і елекгронной цифрового підпису. Алгоритм названий за першими літерами прізвищ авторів - Рональд Райвсст (Ronald Rivest), Аді Шамір (Adi Shamir) і
Леонард Адлеман (Leonard Adleman). Стійкість алгоритму ґрунтується на обчислювальної складності задачі факторизації (розкладання на множники) великих чисел і завдання дискретного логарифмування.
Криптосистема заснована на теоремі Ейлера, в якій мовиться, що для будь-яких взаємно простих чисел М і п (М <п) виконується співвідношення:
де <р (п ) - функція Ейлера. Ця функція дорівнює кількості натуральних чисел, менших п , які взаємно прості з п. За визначенням, <р {) = I. Також доведено, що для будь-яких двох натуральних взаємно простих чисел а і b виконується рівність (р (а? Ь) = (р (а)? р (Ь).
Алгоритм будується наступним чином. Нехай М - блок повідомлення, Про <М <п. Він шифрується відповідно до формули:
В цьому випадку е - відкритий ключ одержувача. Тоді відповідний йому секретний ключ d повинен бути таким, що
Як уже зазначалося, теорема Ейлера стверджує, що М , pin) = 1 (mod п) або, що те ж саме, М до ^ (п) +] = м (mod п ), де до - натуральний множник. Зіставивши цей вислів з виразом (2.18) отримуємо, що їй d повинні бути пов'язані співвідношенням:
Тепер припустимо, що п-pq, де р і q - прості числа, причому р Ф q. Негрудно показати, що для проегого числа р Ф 1 функція Ейлера буде дорівнює <р (р) = р-. Тоді, враховуючи, що р і q - прості і не рівні один одному (а значить, вони і взаємно прості), буде справедливо рівність:
Розглянемо тепер алгоритм RSA «по кроках». Першим етапом є генерація ключів.
- 1) Вибираються два великих простих числа р і q, р ф с /.
- 2) Обчислюється модуль п: п = p q. Зверніть увагу, що для криптосистеми RSA модуль п є частиною відкритого ключа та повинен змінюватися при зміні ключової пари.
- 3) Випадковим чином вибирається число d, таке, що
- 4) Обчислюється значення е таке, що:
- 1
е? d = 1 mod (( р -1 ) (q - 1))
Доведено, що для випадку, коли Нодді, (р -) (q -)) = 1, таке е існує і єдино.
В результаті виконання даних обчислень маємо відкритий ключ, представлений парою чисел ( «, е) і секретний ключ d.
Шифрування проводиться таким чином.
Відправнику відомий відкритий ключ одержувача - (/ ?, М < п. Криптограма обчислюється за формулою:
Криптограма З передається одержувачу. Власник секретного ключа d може розшифрувати повідомлення за формулою (2.22).
Розглянемо тепер схему побудови електронного цифрового підпису. Повідомлення М підписується з використанням секретного ключа d (але для генерації підпису використовується вже ключова пара відправника):
Відправник передає одержувачу підписане повідомлення, т. Е. Пару значень (M, S). Перевірка ЕЦП по відкритому ключу (п, е) проводиться гак:
Збіг значень МиМ 'є доказом того, що повідомлення отримано від власника відповідного секретного ключа і не було змінено в процесі передачі.
Як видно, самі перетворення відносно прості. Основну складність при реалізації алгоритму RSA представляє етап генерації ключів. Зокрема, прості числа р і q вибираються такими, що:
- - одне з них повинно бути менше іншого на кілька порядків;
- - (р- 1 ) і (q- 1 ) повинні мати якомога менший НСД;
- - хоча б одне з чисел (pl), (ql) повинно мати в розкладанні великий простий множник (наприклад, (р- 1 ) = 2г, де t - просте).
Точне визначення, чи є велике число простим чи ні, у багатьох випадках є обчислювально складним завданням. Тому, як правило, використовуються «псевдопростие» тести, які дозволяють з досить великою ймовірністю відкинути числа не є простими. Один з таких тестів заснований на малій теоремі Ферма, в якій мовиться, що якщо р - просте число і 1 <х <р, то х р ~ 1 = 1 mod р. Перевіривши «кандидата» в прості числа з декількома х, вибираними в відповідності зі спеціальними вимогами, можна з великою ймовірністю з'ясувати, чи є ої простим.
Знаходження найбільшого загального дільника і визначення значення е на кроці 4 алгоритму генерації ключів проводиться відповідно до алгоритму Евкліда і узагальненим алгоритмом Евкліда [7,9,121.
