Криптосистема RSA была разработана в 1977 году и получила название в честь своих создателей: Рона Райвеста (Rivest), Ади Шамира (Shamir) и Леонарда Адлемана (Adleman). Они воспользовались тем фактом, что нахождение больших простых чисел осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. В 1993 г. метод RSA был обнародован и принят в качестве стандарта (PKCS # 1: RSA Encryption Standard).
- Выбираются два больших простых целых числа p и q приблизительно одинакового размера.
- Вычисляется модуль системы n = pq и φ(n) = (p-1)(q-1) – функция Эйлера.
- Выбирается достаточно большое число d, удовлетворяющее условию 1 < d < φ(n), и взаимно простое с φ(n), то есть НОД( d, (p-1)(q-1) ) = 1 (см. раздел 2).
- Используя расширенный алгоритм Евклида, вычисляется большое целое число e, отвечающее условию (ed) mod φ(n) = 1, 1 < e < φ(n). Метод Евклида находит множество пар (e, y), каждая из которых является решением уравнения: e · d + ( p - 1)(q - 1) · y = 1 в целых числах.
- Входное сообщение разбивается на блоки mi, их размер определяется целым k, соответствующим неравенству 10k 1 < n < 10k.
- Вычисляется значение ci = mie mod n.
- Значение ci, которое является зашифрованным блоком сообщения, посылается по открытым каналам передачи данных.
- Расшифрование заключается в вычислении значения mi = cid mod n.
Таким образом, секретным ключом является пара чисел (n,d), а открытым – пара чисел (n,e), но можно взять и наоборот.
Для работы программы нужно ввести три больших целых числа p, q и d. Можно, например, сгенерировать их на сайте https://bigprimes.org/
