Алгоритм RSA

В настоящее время одним из наиболее популярных криптоалгоритмов с открытым ключом является криптоалгоритм RSA.

В 1978 году трое ученых (Ривест, Шамир и Адлеман) разработали систему шифрования с открытыми ключами RSA (Rivest, Shamir, Adleman), полностью отвечающую всем принципам Диффи—Хеллмана. Этот метод состоит в следующем.

1. Случайно выбираются два очень больших простых числа p и q.

2. Вычисляются два произведения n = р * q и m = (р - 1) * (q - 1).

3. Выбирается случайное целое число Е, не имеющее общих сомножителей с m.

4. Находится D такое, что DE = 1 по модулю m.

5. Исходный текст Х разбивается на блоки таким образом, чтобы 0<Х<n.

6. Для шифрования сообщения необходимо вычислить С = X^E по модулю n.

7. Для дешифрирования вычисляется X = С^D по модулю n.

Таким образом, чтобы зашифровать сообщение, необходимо знать пару чисел (Е, n), а чтобы расшифровать — пару чисел (D, n). Первая пара — это открытый ключ, а вторая — закрытый.

Зная открытый ключ (E, n), можно вычислить значение закрытого ключа D. Необходимым промежуточным действием в этом преобразовании является нахождение чисел р и q, для чего нужно разложить на простые множители очень большое число n, а на это требуется очень много времени. Именно с огромной вычислительной сложностью разложения большого числа на простые множители связана высокая криптостойкость алгоритма RSA. В некоторых публикациях приводятся следующие оценки: для того чтобы найти разложение 200-значного числа, понадобится 4 миллиарда лет работы компьютера с быстродействием миллион операций в секунду. Однако следует учесть, что в настоящее время активно ведутся работы по совершенствованию методов разложения больших чисел, поэтому в алгоритме RSA стараются применять числа длиной более 200 десятичных разрядов. Программная реализация криптоалгоритмов типа RSA значительно сложнее и менее производительна, чем реализации классических криптоалгоритмов типа DES. Вследствие сложности реализации операций модульной арифметики криптоалгоритм RSA обычно используют только для шифрования небольших объемов информации, например для рассылки классических секретных ключей или в алгоритмах цифровой подписи, а основную часть пересылаемой информации шифруют с помощью симметричных алгоритмов. В табл. 24.1 приведены некоторые сравнительные характеристики классического криптоалгоритма DES и криптоалгоритма RSA

Таблица 24.1. Сравнительные характеристики алгоритмов шифрования