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

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

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

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

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

где N - модуль: N = Р*Q. (4.2)

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

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

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

1 < К_В <= f(N), НОД (К_В, f(N)) = 1, (4.3)

f(N) = (P-1)(Q-1) (4.4)

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

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

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

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

k_B * K_B =1 (mod f(N)) (4.5)

или

k_B = K_B^-1 (mod (P-1)(Q-1)).

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

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

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

С = Е_КB(М) = Е_B(М) = М^КB(mod N). (4.6)

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

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

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

М = Dk_B (С) = D_B (С) = С^kB (mod N). (4.7)

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

D_B(Ев (М)) = М. (4.8)

Подставляя в (4.8) значения (4.6) и (4.7), получаем:

(М^Кв )^kв = М (mod N)

или

М^КвkB = М(mod N). (4.9)

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

X^f(N) = 1 (mod N),

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

X^{nf(N) + 1} = X (mod N) (4.10)

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

К_B * k_B = n * f (N) +1

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

К_B * k_B =1 (mod f (N)}.

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

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

С = М^Кв(mod N)

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

(М^KB)^kB = м^КBkB = М^nf(N)+1 = М (modN).

Таким образом, получатель В, который создает криптоси­стему, защищает два параметра: 1) секретный ключ k_B и 2) пару чисел (Р, Q), произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и от­крытый ключ К_B.

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

f(N) = (Р-1)(Q-1)

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

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

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

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

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

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

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

f(N) = (Р-1)(Q-1)

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

1<К_B <= f(N), НОД(К_B, f(N)) = 1.

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

k_B = K_B^-1 (mod f(N)).

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

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

1. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в ви­де числа М_i = 0, 1, 2, ..., N-1.

2. Пользователь А шифрует текст, представленный в виде последовательности чисел М_i по формуле С_i = М_i^Кв (mod N) и отправляет криптограмму С₁, С₂, С₃, ..., С_i, ... пользователю В.

3. Пользователь В расшифровывает . принятую крип­тограмму С₁, С₂, С₃, ..., С_i, ... используя секретный ключ k_B, по формуле М_i = С_i^kв(mod N).

В результате будет получена последовательность чисел Мi, которые представляют собой исходное сообщение М. Чтобы алгоритм RSА имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие про­стые числа, уметь оперативно вычислять значения ключей К_B и k_B.

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

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

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

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

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

f(N) = f(33) = (Р -1 )(Q -1) = 2*10 = 20.

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

1 < К_B <= 20, НОД (K_B, 20) = 1.

Пусть К_B= 7.

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

k_B = 7^-1 (mod 20).

Решение дает k_B= 3.

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

Рассмотрим подробнее, как получено решение k_B=3.

Расчет k_B осуществляется с использованием частного режима работы расширенного алгоритма Евклида, использующего равенство НОД(К_В, f(N))=1.

1. Введем трехмерные векторы u, v, t

u = {0, 1, f(N)}, v = (1, 0, K_B)

2. Если u₃=1, то переход к пункту 4; в противном случае, переход к пункту 3.

3. S=[u₃ / v₃]целая часть; t=u-v*s; u=v; v=t; переход к пункту 2.

Конец, k_B = u₁.

Процесс поиска решения можно задать таблицей.

S	U1	U2	U3	V1	V2	V3
	0	1	20	1	0	7
2	1	0	7	-2	1	6
1	-2	1	6	3	-1	1
1	3	-1	1

В результате решения получаем, что k_B=3.

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

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

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

Сi = M_i^KB (mod N) = M_i⁷(mod 33).