Криптосистема шифрования данных RSA

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

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

В криптосистеме RSA открытый ключ К_в, секретный ключ k_в, сообщение М и криптограмма С принадлежат множеству целых чисел

Z_N = {0, 1, 2, ..., N –1}, (1)

где N – модуль:

N = P*Q. (2)

Здесь PиQ – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают PиQ равной длины и хранят в секрете.

Множество Z_Nс операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ К_в выбирают случайным образом так, чтобы выполнялись условия:

1< К_в £ j (N), НОД (К_в, j (N)) =1, (3)

j (N)=(P –1) (Q –1), (4)

где j (N) – функция Эйлера.

Функция Эйлера j (N) указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно проcтысN.

Второе из указанных выше условий означает, что открытый ключ К_в и функция Эйлера j (N) должны быть взаимно простыми.

Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ k_в, такой, что

k_в * К_в º 1 (mod j (N)) (5)

или

k_в = К_в^–1 (mod (P –1)(Q –1)).

Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко найти j (N). Заметим, что k_виN должны быть взаимно простыми.

Открытый ключ К_в используют для шифрования данных, а секретный ключ k_в– для расшифрования.

Преобразование шифрования определяет криптограмму С через пару (открытый ключ К_в, сообщение М) в соответствии со следующей формулой:

C = (M) = E_В (M) = (mod N). (6)

В качестве алгоритма быстрого вычисления значения C используют ряд последовательных возведений в квадрат целого M и умножений на M с приведением по модулю N.

Обращение функции C = (mod N), т.е. определение значения M по известным значениям C, К_виN, практически не осуществимо при N » 2 ⁵¹².

Однако обратную задачу, т.е. задачу расшифрования криптограммы С, можно решить, используя пару (секретный ключ k_в, криптограмма С) по следующей формуле:

М = (С) = D_В (C) = (mod N). (7)

Процесс расшифрования можно записать так:

D_В(E_В (М)) = М. (8)

Подставляя в (8) значения (6) и (7), получаем:

= М (mod N)

или

= M (mod N). (9)

Величина j (N) играет важную роль в теореме Эйлера, которая утверждает, что если НОД (x, N) =1, то

x^j(N) º 1 (mod N),

или в несколько более общей форме

x^n×j(N)+1 º x (mod N). (10)

Сопоставляя выражения (8) и (9), получаем

К_в * k_в = n * j (N) +1

или, что то же самое,

К_в * k_в º1 (mod j (N)).

Именно поэтому для вычисления секретного ключа k_в используют соотношение (5).

Таким образом, если криптограмму

C = (mod N)

возвести в степень k_в, то в результате восстанавливается исходный открытый текст М, так как

= = M^n×j(N)+1 º M (mod N).

Таким образом, получатель В, который создает криптосистему, защищает два параметра:

1) секретный ключ k_в

2) пару чисел (P,Q), произведение которых дает значение модуля N.

С другой стороны, получатель В открывает значение модуля N и открытый ключ К_в.

Противнику известны лишь значения К_виN. Если бы он смог разложить число N на множители Pи Q, то он узнал бы "потайной ход" – тройку чисел {P,Q,К_в}, вычислил значение функции Эйлера

j (N) = (P –1) (Q –1)

и определил значение секретного ключа k_в.

Однако, как уже отмечалось, разложение очень большого N на множители вычислительно не осуществимо (при условии, что длины выбранных PиQ составляют не менее 100 десятичных знаков).

5. Процедуры шифрования и расшифрования в криптосистеме RSA

Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В – в роли получателя. Как отмечалось выше, криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В. Рассмотрим последовательность действий пользователя Ви пользователя А.

1. Пользователь В выбирает два произвольных больших простых числа PиQ.

2. Пользователь В вычисляет значение модуля N = P * Q.

3. Пользователь В вычисляет функцию Эйлера

j (N) = (P –1) (Q –1)

и выбирает случайным образом значение открытого ключа К_в с учетом выполнения условий:

1< К_в £ j (N), НОД (К_в, j (N)) =1.

4. Пользователь В вычисляет значение секретного ключа k_в, используя расширенный алгоритм Евклида при решении сравнения

k_в º К_в^–1 (mod j (N)).

5. Пользователь В пересылает пользователю А пару чисел (N, К_в) по незащищенному каналу.

Если пользователь А хочет передать пользователю В сообщение М, он выполняет следующие шаги.

6. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в виде числа

М_i = 0, 1, 2, ..., N –1.

7. Пользователь А шифрует текст, представленный в виде последовательности чисел М_iпо формуле

C_i = (mod N)

и отправляет криптограмму

С₁, С₂, С₃, ..., C_i, ...

пользователю В.

8. Пользователь В расшифровывает принятую криптограмму

С₁, С₂, С₃, ..., C_i, ...,

используя секретный ключ k_в, по формуле

М_i = (mod N).

В результате будет получена последовательность чисел М_i, которые представляют собой исходное сообщение М.

Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей К_в иk_в.

Пример.Шифрование сообщения САВ. Для простоты вычислений будут использоваться небольшие числа. На практике применяются очень большие числа (см. следующий раздел).

Действия пользователя В.

1. Выбирает P = 3иQ = 11.

2. Вычисляет модуль N = P*Q = 3*11 = 33.

3. Вычисляет значение функции ЭйлерадляN = 33:

j (N) = j (33) = (P –1)(Q –1) = 2*10 = 20.

Выбирает в качестве открытого ключа К_в произвольное число с учетом выполнения условий:

1< К_в £ 20, НОД (К_в, 20) = 1.

Пусть К_в= 7.

4. Вычисляет значение секретного ключа k_в, используя расширенный алгоритм Евклида при решении сравнения

k_в 7^–1 (mod 20).

Решение дает k_в= 3.

5. Пересылает пользователю А пару чисел (N = 33, К_в= 7).

Действия пользователя A.

6. Представляет шифруемое сообщение как последовательность целых чисел в диапазоне 0 ... 32. Пусть буква А представляется как число 1, буква В – как число 2, буква С – как число 3. Тогда сообщение САВ можно представить как последовательность чисел 312,т.е.М₁ = 3, М₂ = 1, М₃ = 2.

7. Шифрует текст, представленный в виде последовательности чисел М₁, М₂иМ₃, используя ключ К_в= 7 и N = 33, по формуле

Получает

С₁ = 3⁷ (mod 33) = 2187 (mod 33) = 9,

С₂ =1 ⁷ (mod 33) =1 (mod 33) =1,

С₃ = 2⁷ (mod 33) =128 (mod 33) = 29.

Отправляет пользователю В криптограмму

С₁, С₂, С₃ = 9, 1, 29.

Действия пользователя В.

8. Расшифровывает принятую криптограмму С₁, С₂, С₃, используя секретный ключ k_в= 3, по формуле

Получает

М₁ = 9³ (mod 33) = 729 (mod 33) = 3,

М₂ =1³ (mod 33) =1 (mod 33) =1,

М₃ = 29³ (mod 33) = 24389 (mod 33) = 2.

Таким образом, восстановлено исходное сообщение: С А В

3 1 2

6. Безопасность и быстродействие криптосистемы RSA

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

Действительно, криптостойкость алгоритма RSA определяется тем, что:

1) после формирования секретного ключа k_в и открытого ключа К_в "стираются" значения простых чисел РиQ, и тогда исключительно трудно определить секретный ключ k_в по открытому ключу К_в, поскольку для этого необходимо решить задачу нахождения делителей Р и Q модуля N.

2) разложение величины N на простые множители РиQ позволяет вычислить функцию j (N) = (P –1)(Q –1) и затем определить секретное значение k_в, используя уравнение

К_в * k_в º1 (mod j (N)).

Другим возможным способом криптоанализа алгоритма RSA является непосредственное вычисление или подбор значения функции

j (N) = (P –1)(Q –1).

Если установлено значение j (N), то сомножители РиQ вычисляются достаточно просто.

В самом деле, пусть:

x = P + Q = N +1 – j (N),

y = (P – Q)² = (Р + Q)² – 4*N.

Зная j (N), можно определить x и затем y; зная xиy, можно определить числа РиQ из следующих соотношений:

P = 1/2 (x + ), Q = 1/2 (x – ).

Однако эта атака не проще задачи факторизации модуля N

Задача факторизации является трудно разрешимой задачей для больших значений модуля N.

Сначала авторы алгоритма RSA предлагали для вычисления модуля N выбирать простые числа PиQ случайным образом, по 50 десятичных разрядов каждое. Считалось, что такие большие числа N очень трудно разложить на простые множители. Один из авторов алгоритма RSA, Р.Райвест, полагал, что разложение на простые множители числа из почти 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Однако этот прогноз не оправдался из-за сравнительно быстрого прогресса компьютеров и их вычислительной мощности, а также улучшения алгоритмов факторизации.

Один из наиболее быстрых алгоритмов, известных в настоящее время, алгоритм NFS (Number Field Sieve) может выполнить факторизацию большого числа N (с числом десятичных разрядов больше 120) за число шагов, оцениваемых величиной

.

В 1994 г. было факторизовано число со 129 десятичными цифрами. Это удалось осуществить математикам А.Ленстра и М.Манасси посредством организации распределенных вычислений на 1600 компьютерах, объединенных сетью, в течение восьми месяцев. По мнению А.Ленстра и М.Манасси, их работа компрометирует криптосистемы RSA и создает большую угрозу их дальнейшим применениям. Теперь разработчикам криптоалгоритмов с открытым ключом на базе RSA приходится избегать применения чисел длиной менее 200 десятичных разрядов. Самые последние публикации предлагают применять для этого числа длиной не менее 250 – 300 десятичных разрядов.

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

Эти оценки (табл.1.) даны для трех групп пользователей в соответствии с различием требований к их информационной безопасности, в том числе:.

· индивидуальных пользователей,

· корпораций

· государственных организаций.

Конечно, данные оценки следует рассматривать как сугубо приблизительные, как возможную тенденцию изменений безопасных длин ключей асимметричных криптосистем со временем.

Таблица 1

Оценки длин ключей для асимметричных криптосистем, бит

Криптосистемы RSA реализуются как аппаратным, так и программным путем.

Для аппаратной реализации операций зашифрования и расшифрования RSA разработаны специальные процессоры.

Эти процессоры, реализованные на сверхбольших интегральных схемах (СБИС), позволяют выполнять операции RSA, связанные с возведением больших чисел в колоссально большую степень по модулю N, за относительно короткое время.

И все же аппаратная реализация RSA примерно в 1000 раз медленнее аппаратной реализации симметричного криптоалгоритма DES.

Одна из самых быстрых аппаратных реализаций RSA с модулем 512 бит на сверхбольшой интегральной схеме имеет быстродействие 64 Кбит/с. Лучшими из серийно выпускаемых СБИС являются процессоры фирмы CYLINK, выполняющие 1024-битовое шифрование RSA.