Генерация ключей RSA

1. Для начала берутся случайные простые числа p и q
2. Далее находится модуль n по формуле n = p ∙ q (шифруемое сообщение не может быть больше либо равным n, поэтому не следует брать маленькие значения p и q)
3. Вычисляется значение функции Эйлера по формуле φ(n) = (p-1)∙(q-1)
4. Находится простое целое число — открытая экспонента e, которое больше 1, меньше φ и взаимно простое с φ
5. И ещё одно простое число — закрытая экспонента d, которая удовлетворяет условию (d ∙ е) % φ = 1
6. Получается 2 пары чисел:

• {e, n} — открытый ключ

• {d, n} — закрытый ключ

Открытым ключом можно зашифровать сообщение, а после этого расшифровать закрытым

p = 3; q = 7

n = 3 ∙ 7 = 21

φ = (3 - 1) ∙ (7 - 1) = 2 ∙ 6 =12

e=5; 1 < 5 < 12

d=17; (17 ∙ 5) % 12 = 1

{5; 21} — открытый ключ

{17; 21} — закрытый ключ

Сообщение шифруется по формуле E = M^e % n, и оно может быть расшифровано по формуле M = E^d % n

M = 19

E = 19^5 % 21 = 10

M = 10^17 % 21 = 19