Page 16 - 4395

для всіх М < n;
е d
 відносна легкість обчислення М і С для всіх

значень М < n;
 неможливість визначити d, знаючи е і n.
Вказані співвідношення показують, що правильне

дешифрування можливо лише за умови e*d = 1 mod n.
Можна показати [6], що ця умова виконується, якщо e і d є
взаємно обернені за модулем Ф(n), тобто

e*d = 1 mod Ф(n),

де Ф(n) - функція Ейлера, тобто число позитивних чисел, менших n і

взаємно простих з n. Якщо p - просте, то Ф(р) = p - 1. Якщо p і q -
прості, то Ф(p·q) = (p - 1)·(q - 1). Відмітимо, що відповідно до правил
модульної арифметики, це вірно тільки в тому випадку, якщо d

(і отже, е) є взаємно простимі з Ф(n). Тому
gcd (Ф(n), d) = 1,

де gcd() - (від англ. greatest common divisor) функція визначення
найбільшого спільного дільнику двох чисел.
Сумуємо алгоритм RSA.

Створення ключів:
Вибрати прості р и q.

Обчислити n = p · q.
Вибрати e за умов gcd (Φ(n), e) = 1; 1 < e < Φ(n).

-1
Обчислити d за умови d= e mod Φ(n).
Відкритий ключ: KU = {e, n}.

Закритий ключ: KR = {d, n}.
Шифрування:

Явний текст: М < n.
е
Криптограма: С = М (mod n).

Дешифрування:
Криптограма: С .

d
Явний текст: М = С (mod n).
Кінець алгоритму RSA.

Розглянемо конкретний приклад.
Задаємо два простих числа: р = 7, q = 17.
Обчислюємо: n = p · q = 7 · 17 = 119.

16