Алгоритм RSA

Алгоритм RSA предложили в 1978 г. три автора: Роналдьд Райвест (Ronald Rivest), Ади Шамир (Adi Shamir) и Леонард Адльман (Leonard Adlman). Алгоритма получил свое название по первым буквам фамилий их авторов. Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

Надежность алгоритма основывается на трудности факторизации большихз чисел и трудности вычисления дискретных логарифмов.

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

1. Выбираются два больших простых числа р и q (простым называется число, делящееся на единицу и на само себя).

2. Вычисляется n, равное (p ´ q).

3. Выбирается произвольное число e (e < n), такое, что наибольший общий делитель НОД (e, (p-1) ´ (q-1)) = 1, т. е. должно быть взаимно простым с числом

(p-1) ´ (q-1).

4. Методом Евклида решается в целых числах уравнение e ´ d + (p-1) ´ (q-1) ´ y = 1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d, y), каждая из которых является решением уравнения в целых числах.

5. Пара чисел (e, n) – публикуется как открытый ключ. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать исе послания, зашифрованные с помощью пары ключей (e, n).

Второй этап – собственно шифрование с помощью открытого ключа.

1. Отправитель разбивает свое сообщение на блоки, равные k = [log₂ (n)], где квадратные обозначают взятие целой части от дробного числа. Подобный блок может быть интерпретирован как число из диапазона (0: 2^k – 1).

2. Для каждого такого числа (назовем его m_i) вычисляется выражение c_i = ((m_i)^e) mod n. Блоки c_i и есть зашифрованное сообщение. Их можно без опасения передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа является трудноразрешимой математической задачей.

Третий этап – дешифрование послания с помощью секретного ключа. Частный случай теоремы Эйлера утверждает, что если число n может быть представлено в виде произведения двух простых чисел p и q, то для любого х имеет место равенство:

(х^{(р-1) ´ (q-1)}) mod n = 1.

Для дешифрования RSA – сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y): ((х^{(-y) ´ (р-1) ´ (q-1)}) mod n = 1^(-y) = x. После умножения обеих частей равенства на х получим

(х^{(-y) ´ (р-1) ´ (q-1)}) mod n = 1 ´ = х.

Далее вернемся к созданию открытого и закрытого ключей. Величина d была подобрана с помощью алгоритма Евклида так, что e ´d + (p-1) ´ (q-1) ´ y = 1, т. е.

e ´ d = 1 + (-y) ´ (p-1) ´ (q-1). Следовательно, в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e ´ d). Получаем

(x^{(e ´ d)}) mod n = (x ^{(-y) ´ (р-1) ´ (q-1)+1}) mod = m_i

Общий вид криптосистемы RSA приведен на рис. 3.1.

Рассмотрим работу схемы RSA на примерах шифрования небольших чисел. Небольшие числа используются для простоты (на практике применяются числа, которые намного больше).

Пример 1. Пусть р = 5, а q = 11, тогда значение n = 55. В качестве открытого ключа е выберем число 7, таким образом, весь открытый ключ имеет вид (е=7, n=55).

Вычислим закрытый ключ d: уравнение e ´ d + (p-1) ´ (q-1) ´ y = 1 приобретает вид

7 ´ d + 40 ´ y = 1 и имеет в целых числах решение d = 23, y = - 4. Таким образом, закрытым ключом являются числа (23, 55).

Пусть произвольный отправитель хочет передать абоненту комбинацию бит 100111₂, ее числовой эквивалент 39₁₀. Возводим 39 в степень открытого ключа е = 7 по модулю n = 55: (39⁷ mod 55) = 19. Число 39 является шифрограммой и передается по каналу связи. Получатель по приходу сообщения возводит его в степень d = 23: (19²³ mod 55) = 39. Исходное значение восстановлено.

Пример 2. Зашифруем сообщение “САВ”.

1. Выберем p=3 и q=11.

2. Определим n=3*11=33.

3. Найдем n=(p-1)(q-1)=20. Выберем в качестве d, число взаимно простое с 20, например, d = 3. Взаимно простые числа делятся только на 1 и на само себя.

4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е´3) (mod 20) = 1, например 7.

5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А®1, В®2, С®3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}.

ШТ1 = (3⁷) (mod 33) = 2187 (mod 33) = 9,

ШТ2 = (1⁷) (mod 33) = 1 (mod 33) = 1,

ШТ3 = (2⁷) (mod 33) = 128 (mod 33) = 29.

6. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:

ИТ1 = (9³) (mod 33) = 729 (mod 33) = 3,

ИТ2= (1³) (mod 33) = 1 (mod 33) = 1,

ИТ3 = (29³) (mod 33) = 24389 (mod 33) = 2.

Здесь ШТ – шифротекст, ИТ – исходный текст.

Итак, в реальных системах алгоритм RSA реализуется следующим образом: каждый пользователь выбирает два больших простых числа, и в соответствии с описанным выше алгоритмом выбирает два простых числа e и d. Как результат умножения первых двух чисел (p и q) устанавливается n.

{e,n} образует открытый ключ, а {d,n} - закрытый (хотя можно взять и наоборот).

От­кры­тый ключ пуб­ли­ку­ет­ся и дос­ту­пен ка­ж­до­му, кто же­ла­ет по­слать вла­дель­цу клю­ча со­об­ще­ние, ко­то­рое за­шиф­ро­вы­ва­ет­ся ука­зан­ным ал­го­рит­мом. По­сле шифрования, со­об­ще­ние не­воз­мож­но рас­крыть с по­мо­щью от­кры­то­го клю­ча. Вла­де­лец же за­кры­то­го клю­ча без тру­да мо­жет рас­шиф­ро­вать при­ня­тое со­об­ще­ние.

Скорость шифрования, обеспечиваемая двухключевыми (асимметричными) шифрами, на несколько порядков ниже скорости, которой обладают одноключевые (симметричные) криптосистемы. Поэтому наиболее эффективны гибридные криптосистемы, в которых информация шифруется с помощью одноключевых шифров, а распределение сеансовых ключей осуществляется по открытому каналу с помощью двухключевых шифров. Например, используя криптосистему RSA, можно легко обменяться сеансовым ключом с любым абонентом, зашифровав сеансовый ключ с помощью его открытого ключа. Зашифрованный сеансовый ключ можно безопасно передать по открытому каналу связи, поскольку необходимым для дешифрования секретным ключом обладает только абонент, открытый ключ которого был использован для зашифрования.

Для непосредственного засекречивания информации двухключевые шифры находят ограниченное применение.