Криптосистема шифрования данных 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 десятичных знаков).