Указание к работе. Алгоритм RSA был разработан в 1977 году Роном Ривестом, Ади Шамиром и Леном Адлеманом и опубликованный в 1978 году

Алгоритм RSA был разработан в 1977 году Роном Ривестом, Ади Шамиром и Леном Адлеманом и опубликованный в 1978 году. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом.

Алгоритм RSA состоит из трех этапов:

I. Вычисление ключей

Важным моментом в этом криптоалгоритме является создание пары ключей: открытого и закрытого. Для алгоритма RSA этап создания ключей состоит из следующих операций:

1. Выбираются два простых РАЗЛИЧНЫХ числа p и q. Вычисляется их произведение n=p*q, называемое модулем.
2. Вычисляется функция Эйлера Ф(n)=(p - 1)*(q - 1).
3. Выбирается произвольное число e (e <n), такое, что 1< e <Ф(n) и не имеет общих делителей кроме 1 (взаимно простое) с числом (p - 1)*(q - 1).
4. Вычисляется d методом Евклида таким образом, что (e*d - 1) делится на (p - 1)*(q - 1).
5. Два числа (е, n) - публикуются как открытый ключ.
6. Число d хранится в секрете - закрытый ключ есть пара (d, n), который позволит читать все послания, зашифрованные с помощью пары чисел (е, n).

II. Шифрование

Шифрование с помощью этих чисел производится так:

• Отправитель разбивает свое сообщение на блоки . Значение , поэтому длина блока в битах не больше k=[log₂(n)] бит, где квадратные скобки обозначают, взятие целой части от дробного числа.

Например, если n=21, то максимальная длина блока k=[log₂(21)]=[4.39…]=4 бита.

• Подобный блок может быть интерпретирован как число из диапазона (0;2^k-1). Для каждого такого числа m_i вычисляется выражение (c_i – зашифрованное сообщение): .

Необходимо добавлять нулевые биты слева в двоичное представление блока до размера k=[log₂(n)] бит.

III. Расшифрование

Чтобы получить открытый текст надо каждый блок расшифровать отдельно:

Пример:

Выбрать два простых числа: р = 7, q = 17.
Вычислить n = p·q = 7 · 17 = 119.
Вычислить Ф(n) = (p - 1)·(q - 1) = 96.
Выбрать е так, чтобы е было взаимнопростым с Ф(n) = 96 и меньше, чем Ф(n): е = 5.
Определить d так, чтобы d·e ≡ 1 mod 96 и d < 96.
d = 77, так как 77 · 5 = 385 = 4 · 96 + 1.
Результирующие ключи открытый {5, 119} и закрытый ключ {77, 119}.
Например, требуется зашифровать сообщение М = 19.
19⁵ = 66 (mod 119); С = 66.
Для расшифрования вычисляется 66⁷⁷ (mod 119) = 19.