КРИПТОГРАФІЧНИЙ СИСТЕМА 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.

 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >