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

В этюде 3.2 описано, как Диффи и Хеллмэн с помощью односторонней функции с секретом построили криптосистему с открытым ключом. Правда, они не предложили функций, удобных для реализации.

Однако уже в начале 1977 г. американские специалисты по компьютерным наукам Р. Ривест, А. Шамир и Л. Адлеман придумали одну такую функцию. Система на основе этой функции оказалась очень практичной и получила широкое распространение под названием «система RSA» по первым английским буквам фамилий авторов.

Опишем систему RSA. При этом мы будем использовать без подробных пояснений обозначения и результаты этюдов 3.2 и 3.3. Пусть n = p q, где p и q – большие простые числа, а e – некоторое число, взаимно простое с φ (n). Найдем число d из уравнения: d ∙ e =1(mod φ (n)).

Числа p, q и d будем считать секретными и обозначим секрет K ={ p, q, d }. Числа n и e будем считать общедоступными. Множества открытых сообщений X и шифрованных сообщений Y будем считать равными: X = Y = {1, 2,..., n −1}.

Функцию F _K: X → Y определим равенством: F _K (x) = x ^e (mod n).

Свойство а) односторонней функции с секретом выполнено для F _K очевидным образом. Проверим свойство в). Для этого просто укажем, как при известном K инвертировать функцию F _K: решением уравнения F _K (x) = y будет x = y ^d (mod n). Подробное доказательство этого факта оставляем читателю, приведем лишь необходимые выкладки без комментариев:

d ∙ e = φ (n)∙ m + 1

(x ^e ) ^d (mod n) = x ^{φ (n)∙ m +1}(mod n) = (x ^{φ (n)}) ^m ∙ x (mod n) = (1) ^m ∙ x (mod n) = x.

Свойство б) для функции F _K строго не доказано. Пока общепризнано, что для инвертирования F _K необходимо разложить n на множители, а, как указывалось в этюде 3.4, задача факторизации целых чисел относится к трудным математическим задачам.

Таким образом, описанную функцию F _K можно считать кандидатом на звание односторонней функции с секретом. Система RSA строится с помощью этой функции так, как рассказано в этюде 3.2.

В газете «Известия» за 29 апреля 1994 г. под заголовком «Сверхсекретный шифр разгадан за 17 лет» появилось следующее сообщение: «Когда в 1977 году математики Рональд Ривест, Ади Шамир и Леонард Адлеман зашифровали фразу из нескольких слов, используя комбинацию из 129 цифр, они утверждали, что на разгадку понадобятся триллионы лет. Однако ключ к самому сложному в мире шифру «РСА‑129» (RSA) был найден за 17 лет... Разгадка шифра за такой относительно короткий срок имеет огромное значение для государственных организаций и предпринимателей, которые пользуются аналогичными длинными цифровыми кодами для защиты секретных сведений в своих компьютерных базах данных...» Пока это сообщение не подтверждено научными публикациями, ясно лишь, что речь идет о том, что удалось разложить на множители то 129‑значное число, которое было использовано в 1977 году. Но уже давно в реальных системах RSA используются более длинные числа.

Подумайте сами:

1. Разберите примеры работы системы RSA, приведённые на стр. 241–243 книги М. Гарднера «От мозаик Пенроуза к надёжным шрифтам».