Криптосистема RSA

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

Итак, имеем два отображения:

где S -- множество всевозможных незашифрованных сообщений, T -- множество зашифрованных сообщений. Буква "E" -- первая буква слова "Encoding", буква "D" -- первая буква слова "Decoding". Отображение

переводит исходное сообщение s в зашифрованное сообщение t, отображение

переводит зашифрованное сообщение t обратно в s. Тот факт, что D является декодирующей процедурой, на математическом языке означает, что композиция отображений DE является тождественным отображением: для всякого s справедливо

Все это справедливо для любой схемы асимметричного кодирования. Перейдем непосредственно к схеме RSA, названной так по первым буквам фамилий ее авторов -- Rumley, Shamir, Adleman. Отметим сразу, что схема RSA обладает двумя дополнительными
очень полезными свойствами.

1. Множество исходных сообщений S совпадает с множеством закодированных сообщений T; в качестве этого множества используется кольцо вычетов по модулю m, где m -- произведение двух больших простых чисел (десятичная запись m имеет длину не меньше 200).
   

2. Не только DE = 1, но и ED = 1! Таким образом, D и E -- два взаимно обратных отображения. Это позволяет владельцу секретной процедуры декодирования D применять ее для кодирования. При этом все могут раскодировать это сообщение, используя открытую процедуру E, но только владелец секретной процедуры D может послать его. Такая "обратная" схема применения открытого ключа позволяет удостоверить отправителя сообщения. В практических применениях (для аутентификации отправителя) обратная схема даже более важна, чем прямая.
   

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

произведение двух больших простых чисел (длина десятичной записи каждого из чисел p и q не меньше 100). Всякое сообщение представляется в виде элемента Z_m. (Любое собщение -- это последовательность битов, которую можно рассмотреть как большое целое число. Если длина сообщения больше, чем длина двоичной записи m, то оно разбивается на блоки, и каждый блок шифруется отдельно.)

Число m открытое, однако разложение m на множители -- секретное. Разложение позволяет вычислить функцию Эйлера (следствие 3):

Нетрудно показать, что знание функции Эйлера дает возможность разложить число на множители, так что сложность задачи взламывания открытого ключа равна сложности задачи разложения на множители. Математики верят, что это действительно сложная задача, хотя никаких удовлетворительных оценок снизу в настоящее время не получено. (И вряд ли это NP-полная задача.)

Построение кодирующей процедуры E

Сгенерируем случайный элемент e в кольце вычетов по модулю phi(m), такой, что он обратим в этом кольце (т.е. взаимно прост с phi(m)). Пара (m, e) является открытым ключом. Отображение E состоит в возведении в степень e в кольце вычетов по модулю m.

Для практического вычисления применяется алгоритм быстрого возведения в степень.

Построение декодирующей процедуры D

Для элемента e вычисляется обратный элемент d в кольце вычетов по модулю phi(m).

Покажем, что отображение D является левым обратным к E, т.е. для всякого ссобщения s выполняется равенство D(E(s)) = s. Имеем

Так как e*d == 1 (mod phi(m)), имеем

По следствию 4,

Итак, DE = 1. Аналогично доказывается, что ED = 1.

Рассматривается множество сообщений Z_m, где m -- произведение двух больших простых чисел: m = p*q.
Число m является открытым, но его разложение на множители -- секретным. Знание разложения позволяет вычислить функцию Эйлера phi(m) = (p-1)*(q-1). Случайным образом выбирается обратимый элемент e в кольце вычетов по модулю phi(m). Для него вычисляется (с помощью расширенного алгоритма Евклида) обратный элемент d в кольце вычетов по модулю phi(m). Отображение E задается парой (m, e) и состоит в возведении в степень e по модулю m:

Отображение D задается парой (m, d) и состоит в возведении в степень d по модулю m:

Эти два отображения взаимно обратны. Пара (m, e) является открытым ключом (public key), пара (m, d) является
секретным ключом (private key).

Пример. Рассмотрим пример с небольшими числами, чтобы только проиллюстрировать схему RSA. В реальных приложениях используют большие целые числа, порядка 200-400 десятичных цифр.

Пусть m = 11*13 = 143. Вычислим функцию Эйлера phi(m) = 10*12 = 120. Выберем e = 113, тогда d = 17 -- обратный к e элемент в кольце Z₁₂₀.

Действительно,

Пара (143, 113) составляет открытый ключ, пара (143, 17) -- секретный ключ. Отображение E состоит в возведении в степень 113 по модулю 143, отображение D -- в степень 17 по модулю 143. Рассмотрим произвольное сообщение s = 123. Тогда

Таким образом, 41 -- это закодированное сообщение. Применим к нему декодирующую процедуру:

Мы получили исходное сообщение.

Алгоритмические задачи, связанные со схемой RSA.

В связи со схемой RSA возникает ряд алгоритмических задач.

1. Для генерации ключей нам надо уметь генерировать большие простые числа. Близкой задачей является проверка простоты целого числа.
   

2. Для взламывания ключа в RSA нужно уметь раскладывать целое число на множители (или, что практически то же самое, уметь вычислять функцию Эйлера). Взлом ключа может интересовать только преступников, но, с другой стороны, те, кто пытаются защитить информацию, должны быть уверены, что задача разложения на множители достаточно сложна.